python蓄水池算法代码

Python中的“蓄水池”算法通常是指大顶堆（Max Heap）数据结构的应用，也称为优先队列。这里是一个简单的Python代码示例，使用`heapq`模块实现了一个大顶堆：

import heapq

class WaterLevel():
    def __init__(self):
        self.min_heap = []

    # 添加元素并调整堆序
    def add(self, level):
        if not self.min_heap or level > self.min_heap[0]:
            heapq.heappush(self.min_heap, -level)
        else:
            heapq.heappushpop(self.min_heap, -level)

    # 获取当前最低水位
    def get_level(self):
        return -self.min_heap[0] if self.min_heap else float('inf')

# 使用示例
water_level = WaterLevel()
water_level.add(5)   # 添加水位5
water_level.add(3)   # 添加水位3
print(water_level.get_level())  # 输出3，因为3是最低的水位

相关问题

python蓄水池采样算法代码

Python中，蓄水池采样（Reservoir Sampling）算法是一种在线随机抽样方法，用于从大规模数据流中抽取固定大小（n）的样本，而不需要一次性加载所有数据。这个算法非常高效，因为它每次只处理一个元素。

以下是简单的Python代码实现蓄水池采样的步骤：

import random

def reservoir_sampling(stream, n):
    # 初始化一个大小为n的空列表作为蓄水池
    reservoir = [stream[0]] if n > 0 else []
    
    # 遍历数据流中的每个元素，从第i+1个开始
    for i in range(1, len(stream)):
        # 生成一个0到i的随机数
        random_number = random.randint(0, i)
        
        # 如果随机数小于当前蓄水池的大小，将当前元素替换进去
        if random_number < n:
            reservoir[random_number] = stream[i]
            
    return reservoir

# 使用示例
data_stream = list(range(100))  # 假设这是一条很长的数据流
sample_size = 10  # 想要抽取10个样本
random_sample = reservoir_sampling(data_stream, sample_size)
print(random_sample)

蓄水池算法python

蓄水池算法是一种常见的抽样算法，用于从一个包含未知大小的数据流中随机抽取k个样本，保证每个元素被选的概率相等。

在Python中，可以通过以下步骤实现蓄水池算法：

1. 从数据流中读取前k个元素，存储在一个列表中；

2. 遍历流中剩余的元素，对于每个元素，有1/k的概率被选择，即生成一个0到1之间的随机数R，当R小于1/k时，将该元素替换掉所存储的列表中的一个元素；

3. 遍历完成后，存储的列表即为抽取的k个样本。

以下是一个Python示例代码：

import random

def reservoir_sampling(stream, k):
    reservoir = []  # 存储k个样本的列表
    for i, element in enumerate(stream):
        if i < k:
            reservoir.append(element)
        else:
            # 以1/i的概率替换掉列表中的一个元素
            r = random.randint(0, i)
            if r < k:
                reservoir[r] = element
    return reservoir

该示例代码中，stream代表数据流，k代表需要抽取的样本数量。当数据流与k均较大时，蓄水池算法能够在常数时间复杂度下完成抽样，具有高效的特点。