在链表中查找元素

Question

有一个数据结构为迭代器提供以下接口:

struct iterator {
    T value();
    void next();
    bool isValid();
}

如何设计一个算法，在循环结束时，每个元素都以相同的概率从列表中返回一些值?列表可以很长，因此列表的长度不能用int或long表示。

列表不能修改。

任何想法?谢谢。

Answer 1

你不知道列表的长度，所以你必须一直迭代到最后。您需要保留当前选择的项目值的副本(或项目，但在您的问题中似乎没有办法做到这一点)。然后，对于迭代到的每一个新项，您需要确定所选的项是应该保留还是更改，以递减的概率。

既然你说列表的长度可能不适合原生/原始数据类型(我假设你的意思是当你谈论int和long时，它们是编程语言甚至方言特定的数据类型，你没有指定编程语言)，我认为你的意思是列表可能是任意长。所以你需要一个bignum库，它可以给你任意随机数。

伪代码:

T current = empty value
bignum index = 0
iterator = first item of list
while iterator.isValid()
    index = index + 1
    if bignum_random_below(index) == 0
        # 0 is interpreted as, take value from current index,
        # everything else is interpreted as keep the previous value
        current  = iterator.value()
    end if
    iterator.next()
end while
# index value 0 indicates empty list, even if T doesn't have empty value

摘自M Oehm的评论:这叫做储层取样。