python найти все лучшие подходящие массивы

Question

Я пытаюсь создать соответствующий сервис, как показано ниже. По сути, он находит все наиболее подходящие массивы в foods. Я пытался использовать приведенный ниже код, но он был слишком медленным на> = 50 миллионов строк. Я хочу получить результат за 60 секунд, но я не мог придумать лучшего алгоритма. Ниже мой код, который я использовал для 11 записей.

import numpy as np

result = set()

foods = [
    [1, 2, 3, 4, 5],
    [6, 7, 8, 9, 10],
    [2, 9, 5, 3, 10],
    [1, 2, 5, 10, 2],
    [2, 10, 9, 3, 6],
    [10, 3, 4, 6, 7],
    [6, 2, 4, 3, 5],
    [3, 10, 9, 8, 7],
    [2, 9, 5, 3, 1],
    [8, 6, 3, 2, 5],
    [1, 7, 8, 9, 10],
]

foods = [np.array(sorted([f for f in food])) for food in foods]


best_simularity = -1
for base_idx, base_food in enumerate(foods):
    for target_idx, target_food in enumerate(foods[base_idx+1:]):

        sim = len(np.intersect1d(base_food, target_food))
        if sim < best_simularity:
            continue

        if sim > best_simularity:
            result = set()

        result.add(f'{base_idx+1}-{base_idx+1+target_idx+1}')
        best_simularity = sim

# Expecting 
# 4 1-9, 2-8, 3-9, 7-10, 1-7, 2-11, 3-5, 8-11
print(f"{best_simularity}", ", ".join(list(result)))

Answer 1

Мне удалось значительно ускорить код (x40), используя numba. Я также изменил код, чтобы он возвращал список кортежей вместо строки:

import numpy as np
import numba

# generate (100 x 5) foods, with values between 0 and 15
foods = np.random.randint(0, 15, (200, 5))
# calculate unique values to speed up processing
foods = [np.unique(x) for x in foods]

def sim_foods(foods):
    result = []
    best_simularity = -1
    for base_idx, base_food in enumerate(foods):
        for target_idx, target_food in enumerate(foods[base_idx+1:]):

            sim = len(np.intersect1d(base_food, target_food))
            if sim < best_simularity:
                continue

            if sim > best_simularity:
                best_simularity = sim
                result = []

            result.append((base_idx, base_idx+target_idx+1))
    return result

@numba.njit
def sim_foods_numba(foods):
    rows = len(foods)
    # this is a 'trick' to tell numba the result shall be a list of 2-tuples
    result = [(0,0)] 
    best_simularity = -1

    for base_idx in range(rows):
        for target_idx in range(base_idx+1, rows):
            sim_c = np.bincount(np.hstack((foods[base_idx], foods[target_idx])))
            sim = np.sum(sim_c > 1)
            if sim < best_simularity:
                continue

            if sim > best_simularity:
                best_simularity = sim
                result = [(0,0)]

            result.append((base_idx, target_idx,))

    # drop the (0,0) tuple at the front
    return result[1:]

print(sim_foods(foods) == sim_foods_numba(foods))
# True

Сравнение производительности:

%timeit sim_foods(foods)
1 loop, best of 5: 408 ms per loop

# numba has compilation overhead, so the first run will be much slower
%timeit sim_foods_numba(foods)
The slowest run took 52.71 times longer than the fastest. This could mean that an intermediate result is being cached.
1 loop, best of 5: 10.5 ms per loop

Это все равно будет чрезвычайно медленным для миллионов продуктов, однако, поскольку он по-прежнему равен O (n²), но это позволит вашему списку продуктов быть примерно в 6 раз длиннее (6² = 36), чем разрешено вашим предыдущим алгоритмом.

Может быть увеличена производительность (~ x число ядер) получается путем распараллеливания внутреннего l oop, путем агрегирования всех длин и отбрасывания всех, кроме самого длинного, в конце внутреннего l oop вместо каждой итерации. Это происходит за счет увеличения накладных расходов памяти, поэтому распараллеливание внешнего l oop также, вероятно, вызовет проблемы с памятью. Для 32-х ядерных машин с резьбонарезкой вы можете снова получить ускорение примерно в 20-30 раз, так что еще один рост размера списка в 4-5 раз. Таким образом, в общей сложности я вижу примерно 1000-кратный потенциал ускорения за счет оптимизации, но поскольку алгоритм равен O (n²), это все еще не так много, я думаю, вам нужен еще один коэффициент 1000x?

Может быть, вы можете выжать немного больше производительности с помощью Fortran, C или Julia, но опять же, сам алгоритм не улучшится.