python - 如何使用字典将随机采样函数的性能从O(n)提高到O(logn)？

Question

我必须创建一个存储事件及其发生概率的类。我正在使用一个字典，将事件作为键，并将事件发生的次数作为值。由此，我可以轻松找到事件的可能性。

from random import randint

class Distribution:

    def __init__(self):
        self._d = {}
        self._events = 0

    def add(self,e,multiplicity = 1):
        self._d[e] = self._d.get(e,0) + multiplicity
        self._events += multiplicity

    def count(self,e):
        return self._d[e]

    def prob(self,e):
        return self._d.get(e,0)/self._events

    def sample(self):
        r = randint(0,self._events)
        for key in self._d:
            r -= self._d[key]
            if r <= 0:
                return key

    def __len__(self):
        return len(self._d)

d = Distribution()
d.add('a')
d.add('a')
d.add('a')
d.add('b')
d.add('b')
d.add('c')

d.prob('a') #returns 1/2
d.prob('b') #returns 1/3

d.sample() #returns a random even based on the probability associated with that event

现在，我必须优化示例函数，使其在O（logn）时间运行。将事件添加到分发后，它可以在第一次运行时以O（nlogn）运行。我想不出任何办法将其降至O（logn）。通常，我将登录与二进制搜索相关联，但在这里看不到如何应用。

Answer 1

分析实际方法

让我们考虑一下最坏的情况：

“像从一篮子N个数字中提取特定数字的情况一样，以相同的概率p = 1 / N分配N个事件”。

因此，我们在self._d中填充了N个键，并且每个键的值均分配为1，而self.events也是N。

考虑到这一点并调用我们字典的大小，让我们看看您的sample()方法。
它的成本是“生成指示事件发生的随机整数”加上“循环搜索每个键以查找具有特定值的键”。
假设循环的成本要比生成随机数大得多，现在让我们忽略第二个。
在最坏的情况下，您的循环需要在返回每个键之前先查看每个键，这是因为r被分配了N个值，因此它花费了O(n*O(self._d[key]))，而在此简单字典中检索值的成本基于此< aa>，在最坏的情况下为O(n)。

最后，您的函数将为O(n*O(n)) = O（n ^ 2），而当检索顺利进行时，最终成本将为O(n*O(1)) = O（n）。在收取O(logn)费用的dict实施中，就像您说的最终费用将是O（nlogn）。

可能的解决方案

考虑到先前的推理，如果我们发现在python中使用常量成本O（1）来实现字典检索的关键实现，则将方法成本降低到O（n），这比O（n ^ 2）更有效）。
这些是我可以加快函数速度的方法，但是由于r在最坏的情况下，我们在返回每个键之前都会循环每个键，因此它永远不会是O（logn）。

例如，假设我们在插入一些字典后
d1 = {"a":1, "b":1, "c":1}
和randint()分配r=3。现在将要发生的是，我们取一个键，也许是b并减去它的值，导致r = 2不会通过if条件，因此不会通过下一个，但是最后一个是。因此，使用像d1这样的大词典，您将在n个元素上循环。

但是，如果您希望该示例返回一个事件，该事件具有价值，那么您所生成的第一个因果r比我拥有的解决方案包括使用二进制搜索。
对于这些，让我们使用一些支持结构来显示两个Python列表：一个用于维护插入的键（我现在将其称为标签），另一个用于维护将调用数据的值。
要订购数据列表，也要使用现代标签，因此字典（键，值）对组件将位于两个列表的相同位置，然后使用“二进制搜索”在O（logn）中查找r，并使用创建位置返回标签列表中的相应键。
以下是我的代码，该代码需要导入要工作的模块，提示如何通过值source排序字典的输出。

 def fastSample(self):
        #supporting data structures
        labels = [] #to contain the keys
        data = [] #to contain the values

        #retrieving the pairs in the dictionary
        #ordered by values
        ordered_pairs = sorted(self._d.items(), key=operator.itemgetter(1))

        #Having our ordered list o pairs by value
        #I split it in two lists
        for pair in ordered_pairs:
          labels.append(pair[0])
          data.append(pair[1])

        r = choice(data) #take a random number between the possible values
        index = binarySearch(data,r)
        print(index)

        return labels[index]

该解决方案能够使用我们生成的随便 r查找密钥，但是相对于之前，现在需要确保返回的数字是我们字典的值。为此，必须使用 random.choice()，它将从数据列表中随意选择一个数字作为字典中的值。
最后一件事是 sorted()函数有一个我不知道的开销，但是我确信充其量是 O(n)或 O(nlogn)看到排序算法 here的开销，因为它比搜索我们使用的fastSample（）的成本将是排序的成本。

但是，从此处进行改进很容易，我们只需要移出两个列表即可，使它们像类的 __init__中的实例变量一样。现在，添加事件时，我们必须修改列表，因此它们始终是有序的。
对于最后一种解决方案，需要使用更多的内存，但是通过这种方式，我们无需在调用二进制搜索之前对它们进行排序，并且我们的 fastSample()将像您想要的那样花费O（logn）。根据情况，唯一的问题可能是，对于每个键二进制搜索都具有相同的值将返回列表中心的元素。

一些输出

以下是使用fastSample（）展示其结果时的一些输出。

labels: ['e', 'f', 'h', 'c', 'a', 'b']
data: [1, 1, 1, 2, 6, 7]
r = 7
Lucky one is: b

labels: ['e', 'f', 'h', 'c', 'a', 'b']
data: [1, 1, 1, 2, 6, 7]
r = 1
Lucky one is: h

labels: ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o', 'p', 'q']
data: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
r = 1
Lucky one is: h