优化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 已经排序。我已经尝试在 sum 上排序 product(a,b,c)，但这真的很慢，因为它使用了所有产品。我对 a, b and c 进行排序的最初计划是这样我就可以在一个失败时立即跳出循环。有什么想法吗？

谢谢。

Answer 1

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

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

如果您只想要计数，建议的方法可以在 O(n^2*logn) 中轻松找到。

优化python算法

Optimize python algorithm

python

algorithm

sorting

itertools