Идиоматичный способ обработки списков и диктовок
Недавно я обнаружил "способ Python" для обработки списков, диктов, множеств и т. Д. В этой степени я изменил свою функцию, чтобы вычислить первое N простые числа, назовем его версией "Pure Dict":
def findprimeuptoG(x):
n_primes = {}
for i in range(2, x):
if i not in n_primes.values():
n_primes[i]=i
for k, v in n_primes.items():
if i > v:
n_primes[k] += k
return sorted(n_primes)
Эта функция работает следующим образом:
вести список простых чисел и список целых чисел тех же простых чисел в диктанте
эти кратные должны быть больше или равны целому числу
iесли число отсутствует в списке целых кратных существующих простых чисел, то оно должно быть простым и добавляется в список простых
увеличение
iначиная с2(наименьшее простое число), доxвернуть список простых чисел
Я переписывал эту функцию несколько раз, используя списки, наборы, но эта версия кажется самой идиоматичной. Он короткий и легко читается.
Если кто-то будет достаточно любезен, дайте мне знать, если это может быть написано более четко, пожалуйста, прокомментируйте, как я хотел бы прочитать это.
А теперь вопрос: первая версия этой функции не так чиста и намного более C-подобна:
def findprimeupto(x):
primes = []
n_primes = []
for i in range(2, x):
if i not in n_primes:
primes.append(i)
n_primes.append(i)
for j in range(len(primes)):
if i > n_primes[j]:
n_primes[j] += primes[j]
return primes
Но эта первая версия абсолютно быстрая, когда я запускаю ее с pypy компилятор:
python3:
Primes up to: 100000
Algo: Clean version , primes: 9592, time: 102.74523687362671
Algo: Dict, Set , primes: 9592, time: 58.230621337890625
Algo: **FirstVersion** , primes: 9592, time: 59.945680379867554
Algo: List of List[1] , primes: 9592, time: 71.41077852249146
Algo: List of MutableNum , primes: 9592, time: 292.3777365684509
Algo: **Pure Dict** , primes: 9592, time: 56.381882667541504
pypy (версия 2.3.1):
Primes up to: 100000
Algo: Clean version , primes: 9592, time: 29.3849189281
Algo: Dict, Set , primes: 9592, time: 85.8557658195
Algo: **FirstVersion** , primes: 9592, time: 1.11557507515
Algo: List of List , primes: 9592, time: 42.2394959927
Algo: List of MutableNum , primes: 9592, time: 38.764893055
Algo: **Pure Dict** , primes: 9592, time: 110.416568995
Я понимаю, что полученная версия 'Pure Dict' была вызвана тем, что я не использовала итераторы в своих циклах, но ускорение FirstVersion было феноменальным.
Поскольку большая часть нашего кода, вероятно, в конечном итоге будет скомпилирована в производственном процессе, должны ли мы писать код более похожим на C образом, а не на идиоматический Python?
РЕДАКТИРОВАТЬ:
чтобы устранить путаницу, нужно ли мне использовать списки вместо dict, я отправляю другую версию этой функции, которую я называю "Чистая версия". Эта версия не использует прямой доступ к N-му элементу списка, вместо этого она перебирает списки, как я считаю, наиболее питонским способом (кстати, эта версия больше всего похожа на версию lisp того же кода:)
def findprimeuptoB(x):
primes = []
n_primes = []
for i in range(2, x):
if not (i in n_primes):
primes.append(i)
n_primes.append(i)
new_n_primes = []
for prime, n_prime in zip(primes, n_primes):
if i > n_prime:
new_n_primes.append(prime + n_prime)
else:
new_n_primes.append(n_prime)
n_primes = new_n_primes
return primes
1 ответ
Да, если вы заботитесь о производительности, "Первая версия" - это путь. Вы можете увидеть, что происходит с помощью cProfile.
Для справки, на pypy 2.5.0, работает python -m cProfile -s cumulative x.py с "Первая версия" дает мне:
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.727 0.727 x.py:1(<module>)
1 0.724 0.724 0.727 0.727 x.py:29(findprimeupto)
99999 0.002 0.000 0.002 0.000 {len}
99999 0.001 0.000 0.001 0.000 {range}
19184 0.001 0.000 0.001 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
OTOH, с "Pure Dict" я получаю:
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 16.864 16.864 x.py:1(<module>)
1 1.441 1.441 16.864 16.864 x.py:1(findprimeuptoG)
99998 12.376 0.000 12.376 0.000 {method 'items' of 'dict' objects}
99998 3.047 0.000 3.047 0.000 {method 'values' of 'dict' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {range}
который показывает, что большую часть времени тратится на создание временных списков n_primes.items() а также n_primes.values(),
Теперь это легко исправить: заменить .items() а также .values() с их соответствующими версиями итератора, .iteritems() а также .itervalues(), Тем не менее, результат по-прежнему намного медленнее, чем версия списка, потому что диктовки имеют более сложную структуру, чем списки, и поэтому низкоуровневые операции диктовки намного медленнее, чем эквивалентные операции списка:
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 3.155 3.155 x.py:1(<module>)
1 3.147 3.147 3.155 3.155 x.py:15(findprimeuptoH)
99998 0.006 0.000 0.006 0.000 {method 'itervalues' of 'dict' objects}
99998 0.002 0.000 0.002 0.000 {method 'iteritems' of 'dict' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {range}
Наконец, "Чистая версия" явно плохая, поскольку она создает новую n_primes список на каждой итерации. Действительно, я рассчитываю на 21,795 секунды.
Вывод: создание новых контейнеров (списков, диктов, ...) очень медленное, избегайте его всякий раз, когда можете. Кроме того, диктанты медленнее списков. В этой задаче вам не нужны диктовки, поэтому вы должны использовать списки.