2

我正在寻找一种非常有效的方法来计算 n 个列表中的所有可能组合，然后保持组合具有最小的最小二乘差。

我已经有一个代码可以做到这一点，但是当它达到数百万个组合时，事情就会变慢。

Candidates_len包含长度为 [[500, 490, 510, 600][300, 490, 520][305, 497, 515]] 的列表的列表Candidate_name包含名称为 [['a', ' 的列表的列表b', 'c', 'd']['mi', 'mu', 'ma']['pi', 'pu', 'pa']]

两个列表都有n 个列表。

#    Creating the possible combinations and store the lists of lengths in vector r
r=[[]]
for x in candidates_len:
    r = [ i + [y] for y in x for i in r ]
#Storing the names of the combinations and store the lists of identifiers in vector z
z=[[]]
for x in candidates_name:
    z = [ i + [y] for y in x for i in z ]          
#Calculating distances and storing the minimum one
min_index = 0
min_dist = 0
list_best = []
for index, item in enumerate(r):
    n = 0
    dist = 0
    while n < len(candidates_len):
        for i in range(n,len(candidates_len)):
            dist = dist + (item[n]-item[i])**2
        n=n+1
    if index==0:
            min_dist = dist
            min_index = index
            list_best.append(item)
    elif dist < min_dist:
        min_dist = dist
        min_index = index
        list_best = []
        list_best.append(z[index])
least_combination = min_index

一个硬案例： http: //pastebin.com/BkVQTQWK

以下是一些测试时间。不到一分钟左右会很好。我不知道这是否可能。

combinations time(s)
77760   1.255663
41184   1.580333
69120   6.214786
8960   1.131834
537600  14.855361
89100   1.264126
16384   3.247404
4199040 666.853284
226800   3.935878
9289728 679.064149
4

2 回答 2

5

我在这里的第一个想法是您花费大量时间来建立您不需要的列表。至少，废弃它们会使事情变得更简单，但不能保证它实际上会让事情变得更快：

r = itertools.product(*candidates_len)
z = itertools.product(*candidates_name)

min_dist = None
for item, names in itertools.izip(r, z):
  dist = 0
  for n in range(len(item)):
    for i in range(n, len(item)):
      dist += (item[n]-item[i])**2
  if min_dist is None or dist < min_dist:
    min_dist = dist
    best = item, names

print(best)

对于您的测试数据，显式列表占用了千兆字节的内存。我不确定有多少——我可怜的 4GB 笔记本电脑甚至在它完成生成z列表之前就进入了交换颠簸地狱，一切都慢了下来。与没有它的设置部分相比，整个操作所花费的时间更少itertools……在一台拥有 16GB RAM 的机器上可能不是这样，但是，如果你不需要它，为什么还要使用它呢？

我的下一个想法是，您所做的只是在一堆数组上计算 LSD。你有大量的小阵列吗？如果是这样，您可以对它们进行去锯齿（例如，用 None 填充它们）和numpy整个事情吗？另一方面，如果它是一个大数组的数组，您可能需要一个数组列表（或者，如上所述，一个迭代器）numpy，所以至少您可以向量化一个维度。

无论哪种方式，向量化都是优化任何涉及对大数组进行简单操作的关键，并且numpy通常比专业的 C++-and-Fortran-and-platform-specific-assembly 编码器可能手动执行的任何事情都做得更好。

在没有仔细考虑代码或试图深入理解算法的情况下，我的第一次尝试是生成r一个序列（如我上面的代码）但numpy行向量（类似于matrix(x, dtype=int) for x in itertools.product(*candidates_len)）。item然后你可以通过 just计算每个的差异item - item.T，然后总结下三角形的平方（我必须查一下才能弄清楚如何做）。然后，您可能可以通过首先找出仅计算下三角形的方法来进一步提高性能。典型的技巧是弄清楚如何将下三角形和作为矢量化操作的一部分放入对角线，然后您只需提取对角线，但这并不总是合适的。请参阅广播文档有关如何在不创建显式矩阵的情况下矢量化内部循环的一些想法。最后，看看是否有一种方法可以从整个事物中创建一个 3D 数组（这可能意味着将各个项目填充到固定宽度），然后对整个操作进行矢量化。（内存使用不会那么糟糕，因为numpy只需要为每个值而不是一个整体分配 4 个字节PyObject......但它可能仍然很糟糕，你失去的比你得到的多。）对不起，如果这只是一点点含糊不清，但希望它足以让你开始实验。

另一个想法是你可能可以并行化这个。任何有足够内存来处理大量列表的机器，我敢打赌它至少有 4 个内核。而且你有一长串完全独立的操作，这是世界上最容易并行化的事情。作为第一步，创建一个multiprocessing.Pool, 并使外部循环将作业提交到池中，而不是直接完成工作。您可能会发现作业太小，因此您淹没在开销中，但是您始终可以将每 N 个项目批量处理（明确地，或查看文档grouper中的配方itertools），并使作业成为“循环在这 N 个项目上，并返回具有最小 LSD 的项目”。（可能需要一些调整才能找到最佳 N。）您甚至可以与顶层一起执行此操作numpy，通过沿 x 轴将巨型阵列分成块并将它们作为工作进行耕种。

再想一想：您的算法从 N*M 的乘积开始，其中每个元素的长度为 N。然后，对于每个元素，您循环两次。因此，最好的性能将是 O(N^3*M)。这真的是正确的算法吗？如果是这样，您实际上是否从您的算法中获得了 N^3*M 的性能？如果这两个问题的答案是否定的，则您不应该尝试对其进行微优化。只有当你实际上得到了最有效的算法并且编码正确时，才值得做一些事情，比如矢量化、避免多余的工作、将紧密循环移动到 C++ 和 Fortran 中等等。否则，你只会回来说“但是当我达到上次测试运行的 4 倍时，它仍然会爆炸。”

于 2012-12-05T20:16:22.477 回答
2

我要做的第一件事就是尽可能多地把它放在 Numpy 数组中。Numpy 中基于数组的操作以或多或少的 C 速度执行。看起来大部分事情都可以在 Numpy 中完成......

如果这不能让你的血液流动，那么我会分析代码，并在 Cython 中为瓶颈创建一个函数。假设你可以在列表/数组上放置一个静态类型，如果你想留在 Pythonic 世界，Cython 可能是你最好的选择。我亲眼目睹了使用 Cython 的一些瓶颈的 100 倍加速。

这是 他们文档中使用 Cython 进行图像卷积的示例。

于 2012-12-05T20:20:13.570 回答