python3 двунаправленных генераторов для эффективного поиска / индексации - PullRequest
Новая
       70

python3 двунаправленных генераторов для эффективного поиска / индексации

2 голосов
/ 09 мая 2020

У меня generator, примерно так: 

import numpy as np
attn = [[1, 2, 3, 4, 5, 6], [11, 2, 23, 4, 5, 6], [1, 12, 3, 4, 5, 6], [1, 21, 3, 4, 51, 6], [1, 12, 13, 4, 5, 6]]
def get_weights():
    for i in range(10000000):
        yield np.array(attn[i%5]) * (i**2)%103//3 # randomly chosen

Мне нужно получить значение для случайного индекса.

i_f = get_weights()

Самым быстрым решением для меня кажется создание генератора в списке и получение указанного c индекса в O(1), но для более длинного списка это невозможно. (Также не будет ли операция list() O(N) для составления списка в первую очередь?)

Из некоторых соответствующих ответов я обнаружил, что itertools islice - лучший подход.

Итак, 

import time
t1 = time.time()
print(list(islice(i_f, 9000000,9000001,1)))
t2 = time.time()

[array([10, 20, 30,  5, 15, 25], dtype=int64)]
43.81341481208801

Потребовалось 43 секунды, что очень много. Итак, я подумал, может быть, если я смогу сделать генератор двунаправленным (или, возможно, обобщить и сделать итератор из любого места и в любом направлении в более широком смысле), все будет быстрее. Если местоположение находится выше среднего индекса (N//2), я могу выполнить обратную итерацию, иначе я буду использовать обычный (в простом смысле).

Мой наивный подход был следующим: 

import numpy as np
attn = [[1, 2, 3, 4, 5, 6], [11, 2, 23, 4, 5, 6], [1, 12, 3, 4, 5, 6], [1, 21, 3, 4, 51, 6], [1, 12, 13, 4, 5, 6]]
def get_weights():
    for i in range(10000000):
        yield np.array(attn[i%5]) * (i**2)%103//3

def get_weights_rev():
    for i in range(10000000,-1,-1): # reversely iterating
        yield np.array(attn[i%5]) * (i**2)%103//3

i_f = get_weights()
i_b = get_weights_rev()

import time
t1 = time.time()
print(list(islice(i_f, 9000000,9000001,1)))
t2 = time.time()
print(t2-t1)
t1 = time.time()
print(list(islice(i_b, 1000000,1000001,1)))
t2 = time.time()
print(t2-t1)

[array([10, 20, 30,  5, 15, 25], dtype=int64)]
42.556764125823975
[array([10, 20, 30,  5, 15, 25], dtype=int64)]
4.669842004776001

Использование обратной итерации сократило для меня время. Я ожидал, что второй будет работать примерно в 9 раз быстрее. Итак, это некоторое улучшение. Скорость можно увеличить вдвое. Есть ли лучший способ улучшить сложность, чем O(N)? Как эффективно индексировать генератор более естественным способом / pythoni c без создания списка?

NB: На самом деле у меня другая проблема с доступом к случайным слоям сети через генератор , но это выглядело как хороший фиктивный пример, чтобы представить проблему.

...