python - 选择python数据结构加速算法实现

Question

所以我得到了大量(大约 20 万个)列表。每个包含数字 0 到 27 的子集。我想返回两个列表，其中它们的长度乘积大于任何其他列表对的长度乘积。还有一个条件，即列表没有共同的数字。

我为此找到了一个算法(不记得来源，对 Prop 的非特异性表示歉意)它利用了这样一个事实，即数字 0 到 27 的总子集比字典中的单词少。

我做的第一件事是遍历所有列表，找到组成它的唯一整数子集并将其索引为 0 到 1<<28 之间的数字。如下:

def index_lists(lists):
    index_hash = {}
    for raw_list in lists:
        length = len(raw_list)

        if length > index_hash.get(index,{}).get("length"):
           index = find_index(raw_list)
           index_hash[index] = {"list": raw_list, "length": length}

    return index_hash

这为我提供了最长列表以及实际包含在给定列表集合中的每个子集的列表长度。自然地，不一定包括从 0 到 (1<<28)-1 的所有子集，因为不能保证提供的集合具有包含每个唯一子集的列表。

然后，对于从 0 到 1<<28 的每个子集(这次都是所有子集)，我想要的是最多包含该子集的最长列表。这是杀死我的部分。在高层次上，对于每个子集，它应该首先检查该子集是否包含在 index_hash 中。然后它应该将散列中该条目的长度(如果它存在)与先前存储在当前子集的当前散列中的长度减去一个数字(这是一个内部循环 27 strong)进行比较。其中最大的存储在外循环当前子集的这个新散列中。现在的代码如下所示:

def at_most_hash(index_hash):
    most_hash = {}
    for i in xrange(1<<28):  # pretty sure this is a bad idea
        max_entry = index_hash.get(i)
        if max_entry:
           max_length = max_entry["length"]
           max_word = max_entry["list"]
        else:
           max_length = 0
           max_word = []
        for j in xrange(28):  #  again, probably not great
           subset_index = i & ~(1<<j) # gets us a pre-computed subset
           at_most_entry = most_hash.get(subset_index, {})
           at_most_length = at_most_entry.get("length",0)
           if at_most_length > max_length:
              max_length = at_most_length
              max_list = at_most_entry["list"]
        most_hash[i] = {"length": max_length, "list": max_list}
    return most_hash

这个循环显然需要几个永远才能完成。我觉得我对 python 还很陌生，我对如何迭代和使用什么数据结构的选择可能完全是灾难性的。更不用说试图填写字典可能带来的内存问题。是否有更好的结构或包可用作数据结构？还是设置迭代的更好方法？或者我可以更稀疏地执行此操作？

算法的下一部分只是循环遍历我们得到的所有列表，并通过在 at_most_hash 中查找它们来获取子集的 max_length 和互补子集的最大长度的乘积，并取其中的最大值。

这里有什么建议吗？我很感激耐心地解决我冗长的问题，并尝试将其编码。

从理论上讲，这仍然是比单独使用列表集合更好的方法，因为该方法大致为 o(200k^2) 而这个大致为 o(28*2^28 + 200k)，但我的实现阻碍了我。

Answer 1

鉴于您的索引只是整数，您可以通过使用列表而不是字典来节省一些时间和空间。我会走得更远并引入 NumPy阵列。它们提供紧凑的存储表示和高效的操作，让您可以隐式地在 C 中执行重复性工作，从而绕过大量的解释器开销。

我们首先构建一个 NumPy 数组，而不是 index_hash，其中 index_array[i] 是最长列表的长度，其元素集由 表示i，或者 0 如果没有这样的列表:

import numpy

index_array = numpy.zeros(1<<28, dtype=int)  # We could probably get away with dtype=int8.
for raw_list in lists:
    i = find_index(raw_list)
    index_array[i] = max(index_array[i], len(raw_list))

然后我们使用 NumPy 操作来冒泡 C 中的长度，而不是解释 Python。事情可能会从这里变得困惑:

for bit_index in xrange(28):
    index_array = index_array.reshape([1<<(28-bit_index), 1<<bit_index])
    numpy.maximum(index_array[::2], index_array[1::2], out=index_array[1::2])

index_array = index_array.reshape([1<<28])

每个 reshape 调用都采用数组的新 View ，其中偶数行中的数据对应于 bit_index 处的位清除的集合，而奇数行中的数据行对应于设置了 bit_index 位的集合。 numpy.maximum 调用然后对该位执行冒泡操作。最后，index_array 的每个单元格 index_array[i] 表示元素是集合 i 的子集的最长列表的长度。

然后我们计算互补索引的长度乘积:

products = index_array * index_array[::-1]  # We'd probably have to adjust this part
                                            # if we picked dtype=int8 earlier.

找到最好的产品在哪里:

best_product_index = products.argmax()

而最长的列表，其元素是 best_product_index 表示的集合的子集及其补集是我们想要的列表。