Python выравнивает массив, почему funtools работает медленнее? - PullRequest
Новая
       14

Python выравнивает массив, почему funtools работает медленнее?

0 голосов
/ 08 июля 2019

на основе этого вопроса Python сгладить массив массива

Я хочу более быстрый способ, чем решение с двойной петлей. поэтому я пишу функцию, основанную на functools, но она кажется намного медленнее. 

orders2.shape
(9966, 1)

import time

t0 = time.time()
[x for i in orders2.values.tolist() for x in i[0].tolist()]
t1 = time.time()

t1-t0
0.009984493255615234
import time

t0 = time.time()
functools.reduce(lambda a,b: a+b[0].tolist() , orders2.values.tolist(), [])
t1 = time.time()

t1-t0
1.4101920127868652

У меня вопрос 1. Как это могло случиться? 2. будет ли алгоритм functools быстрее двойного цикла при использовании больших данных? 3. Есть ли другие алгоритмы, которые быстрее, чем двойной цикл?

Ответы [ 3 ]

2 голосов
/ 08 июля 2019

Это тесно связано с ответами на понимание списка по сравнению с картой , так как вы используете lambda с оператором reduce, вы отправляете код Python, который будет выполняться для каждой итерации, таким образом замедление снижения. Понимание списка должно было быть намного более эффективным и читаемым, поэтому они являются предпочтительным методом выбора.

Тем не менее, почему бы не использовать itertools.chain.from_iterable, а также map ping operator.itemgetter. Это приводит к тому же результату при использовании некоторых замечательных встроенных методов. Не проверял на скорость 

>>> from itertools import chain
>>> from operator import itemgetter
>>> arr = array([[array([33120, 28985,  9327, 45918, 30035, 17794, 40141,  1819, 43668],
      dtype='int64')],
       [array([33754, 24838, 17704, 21903, 17668, 46667, 17461, 32665],
      dtype='int64')],
       [array([46842, 26434, 39758, 27761, 10054, 21351, 22598, 34862, 40285,
       17616, 25146, 32645, 41276], dtype='int64')],
       [array([24534,  8230, 14267,  9352,  3543, 29397,   900, 32398, 34262,
       37646, 11930, 37173], dtype='int64')],
       [array([25157], dtype='int64')],
       [array([ 8859, 20850, 19322,  8075], dtype='int64')]], dtype=object)
>>> array(list(chain.from_iterable(map(itemgetter(0),arr.tolist()))))
[33120 28985  9327 45918 30035 17794 40141  1819 43668 33754 24838 17704
 21903 17668 46667 17461 32665 46842 26434 39758 27761 10054 21351 22598
 34862 40285 17616 25146 32645 41276 24534  8230 14267  9352  3543 29397
 900 32398 34262 37646 11930 37173 25157  8859 20850 19322  8075]
2 голосов
/ 08 июля 2019

Короче говоря, при вызове функций и перераспределении списков накладных расходов ваш алгоритм с вложенными циклами равен O (N), а алгоритм с использованием Reduce - O (N²).

Даже если бы алгоритмы не отличались, идея, что вызов функции имеет «0», исходит из математики, если функции являются хорошими теоретическими конструкциями.

При выполнении в компьютерной программе,вызов функции требует инициализации контекста - в случае Python создание объекта Frame с локальными переменными.Поскольку у вас есть передаваемые аргументы, это подразумевает в кортеже аргументы, которые создаются перед вызовом функции и де-конструируются в теле функции (хотя эти шаги могут быть оптимизированы реализацией).

При использовании подхода с 2-мя вложенными циклами все, что вам нужно сделать, - это итерировать итератор в собственном коде - хотя теоретически, согласно спецификациям Python, это также подразумевало бы вызов функции (метод __iter__ объекта)), это обычно намного быстрее в реальных реализациях итераторов собственного кода.

Это, однако, не учитывает разницу, которую вы видите там.Основная проблема заключается в том, что для каждой итерации при выполнении a + b[0].tolist() в памяти создается новый список «c», в него копируются значения «a», затем к нему добавляются значения из b [0].И этот новый список + копия уже сглаженных элементов будет происходить на каждом этапе.В случае осмысления списков избыточное копирование не происходит - новый элемент помещается по мере их появления после развертывания родительской 2D-структуры, а Python хорошо оптимизирован для предварительного выделения пространства для списков, которые растут, когда былипостроен в таком виде.

0 голосов
/ 08 июля 2019

Я думаю, что есть как минимум две проблемы:

  1. с первым вы создаете список и добавляете в него элементы. Но со вторым вы продолжаете объединять два списка на a+b[0].tolist(), что приводит к новому списку.

  2. functools.reduce вернуть генератор, это основная цель. Короче говоря, это не для скорости.

...