Post #92

В стандартной поставке Python есть один полезный инструмент в библиотеке collections, это класс deque. он очень похож на простой список но он намного быстрее работает в некоторых случаях. Например для обработки элементов в начале списка у него есть дополнительные методы: extendleft(), appendleft() и popleft(). Запустим пару тестов!!! 🚀 >>> from collections import deque >>> import time >>> >>> st = time.perf_counter() >>> for _ in range(1000): >>> l1 = deque() >>> for i in range(5000): >>> l1.append(i) >>> en = round(time.perf_counter()-st, 3) >>> print(f'Test deque: {en}sec') >>> >>> st = time.perf_counter() >>> for _ in range(1000): >>> l2 = list() >>> for i in range(5000): >>> l2.append(i) >>> en = round(time.perf_counter()-st, 3) >>> print(f'Test list: {en}sec') Test deque: 0.452sec Test list: 0.436sec Добавление в конец списка работает примерно одинаково. Теперь попробуем вставлять элемент в начало массива. >>> st = time.perf_counter() >>> for _ in range(1000): >>> l1 = deque() >>> for i in range(5000): >>> l1.appendleft(i) >>> en = round(time.perf_counter()-st, 3) >>> print(f'Test deque: {en}sec') >>> >>> st = time.perf_counter() >>> for _ in range(1000): >>> l2 = list() >>> for i in range(5000): >>> l2.insert(0, i) >>> en = round(time.perf_counter()-st, 3) >>> print(f'Test list: {en}sec') Test deque: 0.435sec Test list: 6.347sec Прирост производительности почти в 15 раз! 😲 Тестим функцию pop() (опустим код теста для краткости) Test deque: 0.48sec Test list: 0.529sec Теперь pop(0) для list и popleft() для deque Test deque: 0.476sec Test list: 3.101sec Быстрей примерно в 6.5 раз. Почему так быстро? Дело в том что deque это некий аналог такого типа данных как "linked list data structure", в Python это занывается "двусвязные списки" (doubly-linked lists). Это список, но не в привычном представлении, а с особой оптимизированной структурой. При создании такого массива данные никуда не переносятся а только линкуются оттуда где были. Да, это похоже на Python-лист, но линковка происходит иначе. Вместо того чтобы собирать некий стек ссылок и назвать его списком, в doubly-linked list каждый элемент просто ссылается на следующий. Такая структура позволяет значительно ускорить, создание списка, изменение с любой стороны. Где это может пригодиться? Конечно же в двусторонних очередях (double-ended queue). То есть когда мы добавляем элементы в начало а забираем с конца, или наоборот. Минус такого подхода в просадке производительности для произвольного доступа к элементам в середине очереди. Полный код тестов 🌎 ______________ Реальное описание несколько сложней, я постарался передать основную суть. #libs#tricks