时间戳

首页 > 解决方案 > 推荐一种高效的数据结构，用于在列表中存储大量重复值

python - 推荐一种高效的数据结构，用于在列表中存储大量重复值

问题描述

我有 20 个标签（比如 1 到 20 个），它们随机重复多次以创建一个包含数百万个数字的列表。在任何给定时间，给定一个标签，我都需要该列表中包含该标签的随机索引。

重要的是，当重复查询同一个标签时，返回同一个索引的概率是最小的。

我尝试使用带有键作为标签和值作为索引列表的 dict，然后在查询期间，使用 random.choice() 来获取索引之一。但是创建分组（使用dict）的过程太慢了。

请提出一种更好更快的方法来创建此类分组。

标签： pythonpython-3.xalgorithm

解决方案

如果（1）你对标签的分布有一定的保证，（2）你只需要一小部分索引，你可以试试下面的惰性方法：

这可能会或可能不会比天真的（但通常是有效的）方法更快，具体取决于用例和数据。

概念证明：

import random

class IndicesGenerator:
    def __init__(self, labels, huge_list, next_idx):
        self._cache = {x:[] for x in labels}
        self._huge_list = huge_list
        self._next_idx = next_idx

    def find(self, label, N=100):
        indices = self._cache[label]
        k = 0
        while indices and k<N: # while there are stored indices and we need indices
            yield indices.pop() # yield indices
            k += 1
        while k<N: # need for more indices
            i = self._next_idx()
            v = self._huge_list[i]
            if v == label: # hit!
                k += 1
                yield i
            else: # cache the values for next search
                self._cache[v].append(i)

labels = list(range(20))
SIZE = 20000
huge_list = random.choices(labels, k=SIZE)
gen = IndicesGenerator(labels, huge_list, lambda: random.randint(0, SIZE-1))

# helper function: pPrint a chunk of the list around index i
def print_context(i):
    return "[{}, {}, {}]".format(
        "..., "+str(huge_list[i-1]) if i>0 else "...",
        huge_list[i],
        str(huge_list[i+1])+", ..." if i<SIZE-1 else "..."
    )

needle = random.choice(range(20))
print("search for", needle)
print("cache before search", gen._cache)
print(", ".join([f"{i}->{print_context(i)}" for i in gen.find(needle, 10)]))
print("cache after search", gen._cache)

如您所见，缓存已准备好提供其他标签的大部分索引，而无需任何计算。

平均案例时间复杂度：

  • 缓存的初始化或重新填充是O(k*|labels|)为k第一个标签提供的索引数
  • O(k)最好的情况是搜索任何其他标签；真正的平均案例复杂度需要更精细的计算，但应该在这个值附近。

显然，空间复杂度O(k*|labels|)太高（平均情况下缓存的大小）。

在最坏的情况下，您（几乎）像天真的方法一样构建所有完整列表，但会产生随机数生成器的开销。（时间和空间复杂度与朴素方法相同。）

推荐阅读