Оптимизировать питон алгоритм

Question

У меня есть три упорядоченные списки, examplewise

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 - это то, что я мог вырваться из цикла, как только один не удался. Есть идеи?

Спасибо.

Answer 1

Простое решения, которое может ускорить его немного будет хранить 1/z для каждого z в c в списке, и для каждой пары x,y в a,b - использовать бинарный поиск для самого высокого 1/z (в добавочном списке) так что 1/x + 1/y + 1/z < 1 - это позволит эффективно обрезать многие поиски из 3-х списков и ускорить их.
Это уменьшит сложность времени до O(log(n)*n^2 + Y), где Y - размер выходного файла (количество произведенных триплетов).

Обратите внимание, что поскольку размер выходного файла сам по себе равен O(n^3) (рассмотрите 3 списка со всеми элементами> 3.333) - вы не можете избежать наихудшего временного времени, так как вам может понадобиться генерировать триплеты n^3.

Если вы хотите только графа, предложенный подход может легко найти его в O(n^2*logn).