Вычислить время выполнения поиска членства генератора в python - PullRequest
Новая
       37

Вычислить время выполнения поиска членства генератора в python

0 голосов
/ 16 февраля 2020

В настоящее время я работаю с генераторами и факториалами в python. В качестве примера: itertools.permutations(range(100)) Значение, я получаю объект генератора , содержащий 100! значений.

На самом деле этот код выглядит немного сложнее; Я использую список подсписков вместо диапазона (100), чтобы найти комбинацию подсписков, отвечающих моим условиям.

Это код: 

mylist = [[0, 0, 1], ..., [5, 7, 3]] # random numbers
x = True in (combination for combination in itertools.permutations(mylist) 
             if compare(combination))
# Compare() does return True for one or a few combination in that generator

I понял, что это очень много времени. Есть ли более эффективный способ сделать это, и, кроме того, способ вычислить, сколько времени это займет?

Я сделал несколько% времени, используя i python: 

%timeit (combination for combination in itertools.permutations(mylist) if compare(combination))
 --> 697 ns

%timeit (combination for combination in itertools.permutations(range(100)) if compare(combination))
 --> 572 ns

Примечание: Я понимаю, что генератор только создается, когда он «потребляется», то есть понимание генератора должно быть выполняется сначала, чтобы вообще запустить самого себя.

Я видел много уроков, объясняющих, как работают генераторы, но я ничего не нашел о времени выполнения. Более того, мне не нужно точное значение, такое как время выполнения, используя модуль времени в моей программе, поэтому мне нужно приблизительное значение перед выполнением.

Редактировать: Я также проверил это для меньшего количества значений , для списка, содержащего 24 подсписка, 10 подсписков и 5 подсписков. При этом я получаю мгновенный вывод . Это означает, что программа работает, это всего лишь вопрос времени.

Моя проблема (сказано более прояснено): Сколько времени это собирается возьмите и: есть ли менее трудоемкий способ сделать это?

1 Ответ

0 голосов
/ 16 февраля 2020

Сравнение генераторов, выражений генератора, списков и списочных представлений: 

In [182]: range(5)                                                                             
Out[182]: range(0, 5)
In [183]: list(range(5))                                                                       
Out[183]: [0, 1, 2, 3, 4]
In [184]: (x for x in range(5))                                                                
Out[184]: <generator object <genexpr> at 0x7fc18cd88a98>
In [186]: [x for x in range(5)]                                                                
Out[186]: [0, 1, 2, 3, 4]

Некоторые моменты времени: 

In [187]: timeit range(1000)                                                                   
248 ns ± 2.79 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [188]: timeit (x for x in range(1000))                                                      
802 ns ± 6.97 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [189]: timeit [x for x in range(1000)]                                                      
43.4 µs ± 27.2 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [190]: timeit list(range(1000))                                                             
23.6 µs ± 1.03 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

время для настройки генератора (практически) не зависит от параметр. Заполнение списка масштабируется примерно до размера. 

In [193]: timeit range(100000)                                                                 
252 ns ± 1.57 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [194]: timeit list(range(100000))                                                           
4.41 ms ± 103 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

edit

Время показывает, что тест in на генераторе несколько быстрее, чем list, но все равно масштабируется с len: 

In [264]: timeit True in  (True for x in itertools.permutations(range(15),2) if x==(14,4))     
17.1 µs ± 17.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [265]: timeit list (True for x in itertools.permutations(range(15),2) if x==(14,4))         
18.5 µs ± 158 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [266]: timeit (14,4) in itertools.permutations(range(15),2)                                 
8.85 µs ± 8.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [267]: timeit list(itertools.permutations(range(15),2))                                     
11.3 µs ± 21.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
...