Наивное решение
Простой алгоритм будет
- Выполнять поэлементное копирование исходных вложенных итераций.
- Делать
n копий поэлементной копии. - Получите координаты, относящиеся к каждой независимой копии.
, которая может быть реализована как
from itertools import tee
from operator import itemgetter
from typing import (Any,
Iterable,
Tuple,
TypeVar)
Domain = TypeVar('Domain')
def copy_nested_iterable(nested_iterable: Iterable[Iterable[Domain]],
*,
count: int = 2
) -> Tuple[Iterable[Iterable[Domain]], ...]:
def shallow_copy(iterable: Iterable[Domain]) -> Tuple[Iterable[Domain], ...]:
return tee(iterable, count)
copies = shallow_copy(map(shallow_copy, nested_iterable))
return tuple(map(itemgetter(index), iterables)
for index, iterables in enumerate(copies))
Плюсы:
- довольно легко читается иобъяснить.
Минусы:
- , если мы хотим расширить наш подход для итерируемых элементов с большим уровнем вложенности (например, итерируемых для вложенных итераций и т. д.), этот подход невыглядит полезным.
Мы можем сделать лучше.
Улучшенное решение
Если мы посмотрим на itertools.tee документацию по функциям , она содержит Pythonрецепт, который с помощью functools.singledispatch оформитель может быть переписан как
from collections import (abc,
deque)
from functools import singledispatch
from itertools import repeat
from typing import (Iterable,
Tuple,
TypeVar)
Domain = TypeVar('Domain')
@functools.singledispatch
def copy(object_: Domain,
*,
count: int) -> Iterable[Domain]:
raise TypeError('Unsupported object type: {type}.'
.format(type=type(object_)))
# handle general case
@copy.register(object)
# immutable strings represent a special kind of iterables
# that can be copied by simply repeating
@copy.register(bytes)
@copy.register(str)
# mappings cannot be copied as other iterables
# since they are iterable only by key
@copy.register(abc.Mapping)
def copy_object(object_: Domain,
*,
count: int) -> Iterable[Domain]:
return itertools.repeat(object_, count)
@copy.register(abc.Iterable)
def copy_iterable(object_: Iterable[Domain],
*,
count: int = 2) -> Tuple[Iterable[Domain], ...]:
iterator = iter(object_)
# we are using `itertools.repeat` instead of `range` here
# due to efficiency of the former
# more info at
# /6616473/kakova-tsel-v-python-itertools-repeat#6616580
queues = [deque() for _ in repeat(None, count)]
def replica(queue: deque) -> Iterable[Domain]:
while True:
if not queue:
try:
element = next(iterator)
except StopIteration:
return
element_copies = copy(element,
count=count)
for sub_queue, element_copy in zip(queues, element_copies):
sub_queue.append(element_copy)
yield queue.popleft()
return tuple(replica(queue) for queue in queues)
Плюсы:
- обрабатывает вложенность на более глубоких уровнях или даже смешанные элементы, такие каки итерируемые и не итерируемые на одном уровне,
- может бытьзакончено для пользовательских структур (например, для создания их независимых глубоких копий).
Минусы:
- менее читаемые (но, как мы знаем * ) практичность превосходитpurity "),
- предоставляет некоторые накладные расходы, связанные с диспетчеризацией (но это нормально, поскольку он основан на поиске в словаре, который имеет
O(1) сложность).
Тест
Подготовка
Давайте определим нашу вложенную итерацию следующим образом
nested_iterable = [range(10 ** index) for index in range(1, 7)]
Поскольку создание итераторов ничего не говорит о производительности базовых копий, давайте определим функцию для исчерпания итераторов (описано * 1069)* здесь )
exhaust_iterable = deque(maxlen=0).extend
Время
Использование timeit пакета
import timeit
def naive(): exhaust_iterable(copy_nested_iterable(nested_iterable))
def improved(): exhaust_iterable(copy_iterable(nested_iterable))
print('naive approach:', min(timeit.repeat(naive)))
print('improved approach:', min(timeit.repeat(improved)))
У меня на ноутбуке с Windows 10 x64 в Python 3.5.4
naive approach: 5.1863865
improved approach: 3.5602296000000013
Память
Использование memory_profiler пакета
Line # Mem usage Increment Line Contents
================================================
78 17.2 MiB 17.2 MiB @profile
79 def profile_memory(nested_iterable: Iterable[Iterable[Any]]) -> None:
80 68.6 MiB 51.4 MiB result = list(flatten(flatten(copy_nested_iterable(nested_iterable))))
для "наивного" подхода и
Line # Mem usage Increment Line Contents
================================================
78 17.2 MiB 17.2 MiB @profile
79 def profile_memory(nested_iterable: Iterable[Iterable[Any]]) -> None:
80 68.7 MiB 51.4 MiB result = list(flatten(flatten(copy_iterable(nested_iterable))))
для «улучшенного».
Примечание : я сделал разные запуски скрипта, потому что делал их сразуне является репрезентативным, поскольку второе выражение будет повторно использовать ранее созданные скрытые объекты int.
Заключение
Как мы видим, обе функции имеют одинаковую производительность, нопоследний поддерживает более глубокие уровни вложенности и выглядит довольно расширяемым.
Реклама
Я добавил «улучшенное» решение для lz пакета из 0.4.0 версии, котораяможет использоваться как
>>> from lz.replication import replicate
>>> iterable = iter(range(5))
>>> list(map(list, replicate(iterable,
count=3)))
[[0, 1, 2, 3, 4], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4]]
Это тестирование на основе свойств с использованием hypothesis framework , поэтому мы можем быть уверены, что оно работает как положено.