Блог

Главная - Вопросы по программированию - Оптимизация поиска в словаре Python в Cython

Оптимизация поиска в словаре Python в Cython

#python #c #c #dictionary #cython

#python #c #c #словарь #cython

Вопрос:

Я пытаюсь улучшить скорость этой функции в Cython, потому что это основная функция алгоритма.

 cpdef float _cost(list path, int lenth, dict time, dict cost):
    cdef: 
        float final_cost = 0
        float time_sum = 0
        int count = 0, i=0, 
    
    for i in range(lenth):
        p1 = path[i]
        p2 = path[i 1]
        if time_sum < 8:
            time_sum  = time[p1][p2]
            final_cost  = cost[p1][p2]
        else:
            time_sum = time[p1][path[0]]   time[path[0]][p2]
            final_cost  = cost[p1][path[0]]   cost[path[0]][p2]
            count  =1
            
    final_cost  =  cost[path[0]][path[lenth]]
    return final_cost   count * 9.25 * 2

Оба словаря формируются с помощью int в качестве ключа и другого словаря в качестве значения с помощью и int в качестве ключа и float в качестве значения. В c типизация следующая unordered_map<int, unordered_map<int, float>> cost;

  • Одной из первых оптимизаций, которые я сделал, было написание функции на c с использованием, unordered_map но хеш-словари Python невероятно быстры. Таким образом, код был немного медленнее.
  • Вторая оптимизация, которую я сделал, немного улучшила скорость. Как вы можете видеть в коде, p1 и p2 переменные не типизированы, это потому, что если я набираю, Cython должен выполнить множество преобразований, чтобы адаптировать cython int к типу dict int (это не то же самое, что тип int cython).

Потратив много времени на изучение того, как его улучшить, я не могу решить эти два вопроса:

  1. Есть ли какой-либо способ ввести p1 и p2 правильно? Я думаю, это улучшит скорость !.
  2. Есть ли какой-либо способ улучшить эту функцию? возможно, есть что-то, чего мне не хватает…

Комментарии:

1. Вы не можете значительно ускорить Python’s dict. В прошлый раз, когда я проводил сравнение с c -maps, неупорядоченная карта c была немного быстрее для поиска (так что, возможно, вы сделали что-то не так). Существует также dense_hash_map от Google, который работает даже быстрее, чем реализация c .

2. Написанный код не компилируется (что не может помочь). Ввод p1 и p2 вряд ли что-либо улучшит для Python dicts, поскольку единственное, для чего вы их используете, — это dict поиск, для которого требуется общий объект Python. Вы определенно пробовали очевидные подходы — может быть, это так же быстро, как работает ваш алгоритм?

3. С unordered_map — главное было бы убедиться, что данные остаются в виде unordered_map . Вы не хотите копировать его в Python и из него dict .

4. Будет ли работать 2d-массив вместо вложенных dict массивов? Это зависело бы от того, насколько разрежены данные, но, вероятно, было бы значительно быстрее, если бы это было возможно?

5. Вам вообще не нужно выполнять итерации. Поместите значения времени и затрат для path[i] в time[path[i]] и time[cost[i]] так же, как вы сейчас делаете с dicts. Компромисс здесь заключается в том, что вам нужно выделить два массива максимальной длины (path[]), и это может быть очень большим. (Рассмотрите возможность использования для этого ndarrays или memoryviews.)