Любой пакет Python для ускорения вычисления цикла?

Question

У меня есть два списка L и C, оба отсортированы от наименьшего к наибольшему.L содержит натуральные числа, C содержит как натуральные, так и дробные числа (e.g. 0.01,0.05,..,100).Длина C фиксирована на 6000+, длина L является переменной (between 2 and 3000).

Цель: задана некоторая постоянная M, найти l из L и c из C st l*c<=M и максимально близко к M.

В настоящее время я использую для цикла более C и двоичного поиска по списку L, чтобы найти наибольшееl*c что составляет <=M.Однако это очень медленно.

candidate_list = []
for c in C:
    binary search on list L using while loop to find out the best l*c<=M
    candidate_list.append(best l*c)
print(max(candidate_list))

При заданной длине L, равной N, использование двоичного поиска займет logN.Однако, поскольку длина C равна 6000+, цикл более c будет медленным.И если у меня несколько списков L разной длины, использование цикла for будет очень медленным.Могу ли я узнать, есть ли какой-нибудь простой или скучный пакет для ускорения вычислений?

Примечание. Поскольку у меня много списков L, я не могу просто выполнить умножение матриц-матриц между L и C_transpose и используйте argmax, чтобы узнать максимальное значение l*c, равное <=M.

Answer 1

Пакет numba .Он специально разработан для ускорения Python для циклов.

С их веб-сайта: Numba переводит функции Python в оптимизированный машинный код во время выполнения, используя стандартную библиотеку компилятора LLVM. Численные алгоритмы, скомпилированные в Numba, в Python могут приближаться к скоростям C или FORTRAN.

Answer 2

Пользователь @Mbo поставил хорошую точку в свой ответ :

Пройдите один список в прямом направлении и найдите лучшую пару для item[A] из второго списка, но начинайтепоиск с обратной стороны второго списка.Для следующего item[A+1] его элемент пары обязательно должен быть меньше или равен индексу, как предыдущий (K), поэтому вам нужно только один прогон по второму списку.

Вот пример реализациипсевдокод, который он предоставляет ( линейное время сложность, привязанная к длине вашего самого большого списка, который будет списком C из вашего вопроса):

def find(list_c, list_l, threshold):
    # all pairs of elements whose product is smaller than 'threshold'
    possible_pairs = []

    j = len(list_l) - 1
    for i in range(len(list_c)):
        while list_c[i] * list_l[j] > threshold:
            # product is too big, pick a smaller element from 'list_l'
            j -= 1

            if j < 0:
                # exit while loop
                break

        if j < 0:
            # exit for loop
            break

        # we store some extra info here
        possible_pairs.append({
            'c_index': i,
            'c_elem': list_c[i],
            'l_index': j,
            'l_elem': list_l[j],
            'product': list_c[i] * list_l[j],
        })

    print(possible_pairs)

    # return the pair with the biggest product (closest to threshold)
    return max(
        possible_pairs,
        key=lambda x: x['product'])

Я также проверил это решение:

import random

list_c = list(sorted(random.random()*100 for i in range(100)))
list_l = list(sorted(random.random()*100 for i in range(20)))
print('list_c', list_c)
print('list_l', list_l)

elem = find(list_c, list_l, threshold=50)

print('the best pair is')
print(elem)

В последнем выводе выводится что-то вроде:

{
    'c_index': 47,
    'c_elem': 46.42324820342966,
    'l_index': 0,
    'l_elem': 1.0709460533705695,
    'product': 49.716794448105375,
}

Как вы можете видеть, подобное решение можно использовать для последовательного вычисления поиска по множеству L списков, которые вы упомянули.в вашем вопросе.

Answer 3

Поскольку оба списка отсортированы, достаточно использовать алгоритм linear :

Обойти один список в прямом направлении, найти лучшую пару для item[A] из второго списка (скажем, вindex K)

Для следующего item[A+1] парный элемент определенно имеет меньший или равный индекс, как предыдущий (K), поэтому вам нужно только один , проходящий через второй список.

Псевдокод:

 iL = len(L)-1
 for iC in range(len(C)):
     while L[iL] * C[iC] > M:
          iL -= 1
     use pair  L[iL], C[iC]