python - 优化python算法

Question

我有三个排序列表，例如

a, b, c = [10,9,8], [9,8,7], [13,5,1]

我想得到所有的组合 x, y, z其中 x in a, y in b and z in c和 1/x + 1/y + 1/z < 1在最快的时间内。我一直在尝试一些不同的方法，

for x, y, z in product(a, b, c):
    if predicative(x,y,z):
        yield (x, y, z)

显然，考虑到我正在检查所有内容和列表 a, b, c，这需要很长时间已经排序。我试过排序 product(a,b,c)在 sum 上，但这真的很慢，因为它使用了所有产品。我最初的计划是 a, b and c sorted 是这样我就可以在一个失败时立即跳出循环。有什么想法吗？

谢谢。

Answer 1

一个可以加快速度的简单解决方案是存储 1/z对于每个 z在c在列表中，对于每对 x,y在a,b - 使用二进制搜索最高 1/z (在辅助列表中)使得 1/x + 1/y + 1/z < 1 - 这将有效地减少第三列表中的许多搜索并让您加快速度。
这会将时间复杂度降低到O(log(n)*n^2 + Y)。 , 其中Y是输出大小(产生的三元组数)。

但是请注意，由于输出大小本身是 O(n^3) (考虑所有元素 > 3.333 的 3 个列表)- 您无法避免最坏情况下的缓慢时间，因为您可能需要生成 n^3三胞胎。

但是，如果您只想要计数，建议的方法可以很容易地在 O(n^2*logn) 中找到它。 .