Сравнение перечня списков и явных циклов (3 генератора массива быстрее, чем 1 для цикла)

Я сделал домашнее задание, и я случайно обнаружил странную несогласованность в скорости алгоритма. Вот 2 версии кода той же функции bur с 1 разницей: в первой версии я использую 3-х кратный генератор массивов для фильтрации некоторого массива, а во второй версии я использую 1 для цикла с операторами 3 if для выполнения такой же работы фильтра.

Итак, вот код 1-й версии:

def kth_order_statistic(array, k): pivot = (array[0] + array[len(array) - 1]) // 2 l = [x for x in array if x < pivot] m = [x for x in array if x == pivot] r = [x for x in array if x > pivot] if k <= len(l): return kth_order_statistic(l, k) elif k > len(l) + len(m): return kth_order_statistic(r, k - len(l) - len(m)) else: return m[0] 

И вот код второй версии:

 def kth_order_statistic2(array, k): pivot = (array[0] + array[len(array) - 1]) // 2 l = [] m = [] r = [] for x in array: if x < pivot: l.append(x) elif x > pivot: r.append(x) else: m.append(x) if k <= len(l): return kth_order_statistic2(l, k) elif k > len(l) + len(m): return kth_order_statistic2(r, k - len(l) - len(m)) else: return m[0] 

Выход IPython для 1-й версии:

 In [4]: %%timeit ...: A = range(100000) ...: shuffle(A) ...: k = randint(1, len(A)-1) ...: order_statisctic(A, k) ...: 10 loops, best of 3: 120 ms per loop 

И для 2-й версии:

 In [5]: %%timeit ...: A = range(100000) ...: shuffle(A) ...: k = randint(1, len(A)-1) ...: kth_order_statistic2(A, k) ...: 10 loops, best of 3: 169 ms per loop 

Итак, почему первая версия быстрее второй? Я также сделал третью версию, использующую функцию filter () вместо генератора массивов, и она была медленнее второй версии (она получила 218 мс за цикл)

4 Solutions collect form web for “Сравнение перечня списков и явных циклов (3 генератора массива быстрее, чем 1 для цикла)”

Давайте определим функции, которые нам понадобятся, чтобы ответить на вопрос и время:

 In [18]: def iter(): l = [x for x in range(100) if x > 10] ....: In [19]: %timeit iter() 100000 loops, best of 3: 7.92 µs per loop In [20]: def loop(): l = [] for x in range(100): if x > 10: l.append(x) ....: In [21]: %timeit loop() 10000 loops, best of 3: 20 µs per loop In [22]: def loop_fast(): l = [] for x in range(100): if x > 10: pass ....: In [23]: %timeit loop_fast() 100000 loops, best of 3: 4.69 µs per loop 

мы видим, что циклы for без команды append так же быстро, как понимание списка. На самом деле, если мы посмотрим на байт-код, мы увидим, что в случае понимания списка python может использовать встроенную команду байт-кода LIST_APPEND вместо:

  • Загрузите список: 40 LOAD_FAST
  • Загрузите атрибут: 43 LOAD_ATTRIBUTE
  • Вызовите загруженную функцию: 49 CALL_FUNCTION
  • Выгрузить список (?): 52 POP_TOP

Как видно из вывода ниже, предыдущий байт-код отсутствует со списком и функцией «loop_fast». Сравнение времени трех функций ясно, что они отвечают за разные сроки трех методов.

 In [27]: dis.dis(iter) 2 0 BUILD_LIST 0 3 LOAD_GLOBAL 0 (range) 6 LOAD_CONST 1 (1) 9 LOAD_CONST 2 (100) 12 CALL_FUNCTION 2 15 GET_ITER >> 16 FOR_ITER 24 (to 43) 19 STORE_FAST 0 (x) 22 LOAD_FAST 0 (x) 25 LOAD_CONST 2 (100) 28 COMPARE_OP 4 (>) 31 POP_JUMP_IF_FALSE 16 34 LOAD_FAST 0 (x) 37 LIST_APPEND 2 40 JUMP_ABSOLUTE 16 >> 43 STORE_FAST 1 (l) 46 LOAD_CONST 0 (None) 49 RETURN_VALUE In [28]: dis.dis(loop) 2 0 BUILD_LIST 0 3 STORE_FAST 0 (1) 3 6 SETUP_LOOP 51 (to 60) 9 LOAD_GLOBAL 0 (range) 12 LOAD_CONST 1 (1) 15 LOAD_CONST 2 (100) 18 CALL_FUNCTION 2 21 GET_ITER >> 22 FOR_ITER 34 (to 59) 25 STORE_FAST 1 (x) 4 28 LOAD_FAST 1 (x) 31 LOAD_CONST 3 (10) 34 COMPARE_OP 4 (>) 37 POP_JUMP_IF_FALSE 22 5 40 LOAD_FAST 0 (l) 43 LOAD_ATTR 1 (append) 46 LOAD_FAST 1 (x) 49 CALL_FUNCTION 1 52 POP_TOP 53 JUMP_ABSOLUTE 22 56 JUMP_ABSOLUTE 22 >> 59 POP_BLOCK >> 60 LOAD_CONST 0 (None) 63 RETURN_VALUE In [29]: dis.dis(loop_fast) 2 0 BUILD_LIST 0 3 STORE_FAST 0 (1) 3 6 SETUP_LOOP 38 (to 47) 9 LOAD_GLOBAL 0 (range) 12 LOAD_CONST 1 (1) 15 LOAD_CONST 2 (100) 18 CALL_FUNCTION 2 21 GET_ITER >> 22 FOR_ITER 21 (to 46) 25 STORE_FAST 1 (x) 4 28 LOAD_FAST 1 (x) 31 LOAD_CONST 3 (10) 34 COMPARE_OP 4 (>) 37 POP_JUMP_IF_FALSE 22 5 40 JUMP_ABSOLUTE 22 43 JUMP_ABSOLUTE 22 >> 46 POP_BLOCK >> 47 LOAD_CONST 0 (None) 50 RETURN_VALUE 

Использование простых for них быстрее, чем подсчет list comprehesion . Это почти в 2 раза быстрее. Проверьте результаты ниже:

Использование list comprehension : 58 usec

 moin@moin-pc:~$ python -m timeit "[i for i in range(1000)]" 10000 loops, best of 3: 58 usec per loop 

Использование for цикла: 37.1 usec

 moin@moin-pc:~$ python -m timeit "for i in range(1000): i" 10000 loops, best of 3: 37.1 usec per loop 

Но в вашем случае, for занимает больше времени, чем понимание списка, не потому, что YOUR for loop медленнее. Но из-за .append() вы используете код.

С append() in for loop`: 114 usec

 moin@moin-pc:~$ python -m timeit "my_list = []" "for i in range(1000): my_list.append(i)" 10000 loops, best of 3: 114 usec per loop 

Это наглядно показывает, что это .append() которое занимает в два раза больше времени, затраченного for цикл .

Однако при storing the "list.append" in different variable : 69.3 usec

 moin@moin-pc:~$ python -m timeit "my_list = []; append = my_list.append" "for i in range(1000): append(i)" 10000 loops, best of 3: 69.3 usec per loop 

Существует значительное улучшение производительности по сравнению с последним случаем в вышеперечисленных сравнениях, и результат вполне сравним с результатом list comprehension . Это означает, что вместо вызова my_list.append() каждый раз производительность может быть улучшена путем сохранения ссылки на функцию в другой переменной, то есть append_func = my_list.append и совершении вызова с использованием этой переменной append_func(i) .

Это также доказывает, что быстрее вызвать функцию класса, хранящуюся в переменной, по сравнению с прямым вызовом функции с использованием объекта класса .

Спасибо Стефану за то, что он привлек последний случай.

Давайте рассеем это сомнение: вторая версия немного быстрее: понимание списка происходит быстрее , но два цикла цикла и столько же условностей отбрасываются на одной итерации.

 def kth_order_statistic1(array,k): pivot = (array[0] + array[len(array) - 1]) // 2 l = [x for x in array if x < pivot] m = [x for x in array if x == pivot] r = [x for x in array if x > pivot] if k <= len(l): return kth_order_statistic1(l, k) elif k > len(l) + len(m): return kth_order_statistic1(r, k - len(l) - len(m)) else: return m[0] def kth_order_statistic2(array,k): pivot = (array[0] + array[len(array) - 1]) // 2 l = [] m = [] r = [] for x in array: if x < pivot: l.append(x) elif x > pivot: r.append(x) else: m.append(x) if k <= len(l): return kth_order_statistic2(l, k) elif k > len(l) + len(m): return kth_order_statistic2(r, k - len(l) - len(m)) else: return m[0] def kth_order_statistic3(array,k): pivot = (array[0] + array[len(array) - 1]) // 2 l = [] m = [] r = [] for x in array: if x < pivot: l.append(x) for x in array: if x== pivot: m.append(x) for x in array: if x > pivot: r.append(x) if k <= len(l): return kth_order_statistic3(l, k) elif k > len(l) + len(m): return kth_order_statistic3(r, k - len(l) - len(m)) else: return m[0] import time import random if __name__ == '__main__': A = range(100000) random.shuffle(A) k = random.randint(1, len(A)-1) start_time = time.time() for x in range(1000) : kth_order_statistic1(A,k) print("--- %s seconds ---" % (time.time() - start_time)) start_time = time.time() for x in range(1000) : kth_order_statistic2(A,k) print("--- %s seconds ---" % (time.time() - start_time)) start_time = time.time() for x in range(1000) : kth_order_statistic3(A,k) print("--- %s seconds ---" % (time.time() - start_time)) 

 python : --- 25.8894710541 seconds --- --- 24.073086977 seconds --- --- 32.9823839664 seconds --- ipython --- 25.7450709343 seconds --- --- 22.7140650749 seconds --- --- 35.2958850861 seconds --- 

Время может варьироваться в зависимости от случайного розыгрыша, но различия между ними практически одинаковы.

Алгоритмическая структура отличается и условная структура должна быть инкриминирована. тест, добавленный в r и m, может быть отброшен предыдущим тестом. Более строгое сравнение в отношении цикла for с append и пониманием списка было бы против неоптимального следования

 for x in array: if x < pivot: l.append(x) for x in array: if x== pivot: m.append(x) for x in array: if x > pivot: r.append(x) 
  • как я могу создать диспетчер контекста 2.7 python threadsafe
  • Пирамида: схемы маршрутизации и ограничения
  • Не удается получить библиотеку изображений Python для поиска JPEG-поддержки
  • lxml не может разобрать xml (более простая кодировка - utf-8 или нет)
  • Python psycopg2 курсоры
  • Какова точка вызова супер в пользовательских классах ошибок в python?
  • Последний ключ в словаре Python
  • `id` в Python 2.7,` is`, идентификация объекта и определяемые пользователем методы
  • Python - лучший язык программирования в мире.