Ленивое перемещение размеров 0 и 2 в модели итератора
Учитывая итерабельность итерируемой итерируемой it_it_it (т. е. ленивое представление трехмерного массива), вы можете лениво транспонировать размеры 0 и 1 на zip(*it_it_it), а размеры 1 и 2 на map(lambda it_it: zip(*it_it), it_it_it).
Однако последняя комбинация (0 и 2) сложнее. Кажется, вы должны полностью оценить два внешних итератора, прежде чем что-либо выдать, и полученный тип должен быть List[List] не ленивым Iterable[Iterable]; самый внутренний итератор — единственный, который может быть лениво оценен (т. е. Iterable[List[List]] — это лучшее, что вы можете сделать).
Я собираюсь дать ответ, но меня интересует более элегантный ответ.
В стороне:
Меня интересует этот вопрос для понимания проблемы со статически типизированными итераторами, то есть ржавчиной и С++. Обязательно настройте свои данные, чтобы вам никогда не приходилось выполнять эту операцию. Лучше всего просто полностью оценить итераторы в List[List[List]], а затем транспонировать стиль c.
@user2357112 user2357112 обоим из них нужно полностью исчерпать только один итератор, но транспозиция (0, 2) должна полностью исчерпать два итератора. Я только что обнаружил, что это немного неожиданно
Ответы 3
import itertools
def transpose_(it_it_it):
blocks = [[iter(it) for it in it_it] for it_it in it_it_it]
it = iter(itertools.cycle(itertools.chain.from_iterable(zip(*blocks))))
while True:
try:
yield [[next(next(it)) for _ in range(len(blocks))]
for _ in range(len(blocks[0]))]
except StopIteration:
break
Вот код для проверки
cycle уже возвращает итератор, вам не нужно вызывать iter его.
@KellyBundy спасибо за эти советы, и вы отвечаете. Я не ожидал, что 3 транспонирования будут самым быстрым решением (ваш код деривации лишь немного медленнее), весь смысл этого заключался в том, чтобы попытаться превзойти 3 транспонирования. Теперь, чтобы портировать это на С++
Вы не можете избежать материализации, которой пытаетесь избежать.
Рассмотрите возможность повторения транспонированного результата, который вы хотите:
for iter1 in transpose_layers_0_and_2(iterator):
for iter2 in iter1:
for iter3 in iter2:
pass
В конце первой итерации внешнего цикла вы получили доступ к каждому элементу каждого вложенного вложенного итератора первого вложенного итератора transpose_layers_0_and_2(iterator).
В исходном итераторе перед транспонированием эти элементы берутся из первого элемента каждого вложенного вложенного итератора исходного iterator.
Это означает, что к моменту завершения первой итерации внешнего цикла вы должны материализовать все первые два слоя исходного итератора для создания каждого вложенного вложенного итератора. Нет никакого способа обойти это. Кроме того, вы использовали только один элемент каждого вложенного вложенного итератора, поэтому вам все равно придется сохранять все эти вложенные вложенные итераторы в памяти для создания остальных элементов. Вы еще не можете отказаться от них.
Я уже понял это, но, вероятно, не очень хорошо написал вопрос. Я спрашивал, есть ли более элегантное решение для Python, чем мой ответ. Все переплетение, а затем разбиение на куски закончилось небольшим дерганьем. Полагаю, мне также было интересно, была ли это лучшая стратегия
Решение
def transpose_(it_it_it):
return zip(*map(zip, *it_it_it))
Попробуйте это онлайн!
Вывод
Моя первая версия была такой, а потом я ее просто минимизировал. Сначала я меняю местами два внешних измерения, затем два внутренних, затем снова два внешних. Используя ваши способы сделать это. Обратите внимание на имена переменных, они отражают размерности/свопы:
def transpose_(xyz):
yxz = zip(*xyz)
yzx = map(lambda xz: zip(*xz), yxz)
zyx = zip(*yzx)
return zyx
Визуализация итерации / исчерпания
Для визуализации я превратил списки 3D-ввода в итераторы, которые сообщают, когда они исчерпаны, и перебирают транспонированные данные, печатая их структуру и значения. Мы можем видеть, что два внешних измерения исчерпаны заранее, а внутреннее измерение исчерпано только в конце:
X-iterator exhausted
Y-iterator exhausted
Y-iterator exhausted
Y-iterator exhausted
[
(
0
8
16
)
(
4
12
20
)
]
[
(
1
9
17
)
(
5
13
21
)
]
[
(
2
10
18
)
(
6
14
22
)
]
[
(
3
11
19
)
(
7
15
23
)
]
Z-iterator exhausted
Z-iterator exhausted
Z-iterator exhausted
Z-iterator exhausted
Z-iterator exhausted
Z-iterator exhausted
Код:
import numpy
def transpose_(it_it_it):
return zip(*map(zip, *it_it_it))
# Versions of zip and map that exhaust all inputs
_zip = zip
def zip(*its):
yield from _zip(*its)
for it in its[1:]:
next(it, None)
_map = map
def map(f, *its):
yield from _map(f, *its)
for it in its[1:]:
next(it, None)
# Iterators that report when they've been exhausted
def X(it):
yield from map(Y, it)
print('X-iterator exhausted')
def Y(it):
yield from map(Z, it)
print('Y-iterator exhausted')
def Z(it):
yield from it
print('Z-iterator exhausted')
# Test data
a = numpy.arange(3*2*4).reshape((3, 2, 4))
b = X(a.tolist())
# Iterate the transposed data
zyx = transpose_(b)
for yx in zyx:
print('[')
for x in yx:
print(' (')
for value in x:
print(' ', value)
print(' )')
print(']')
Попробуйте это онлайн!
Ориентир
Время и память создания и итерации транспонированных данных при данных размера 100×100×100 (три попытки):
317 ms 845540 bytes transpose_Tom
117 ms 825400 bytes transpose_Kelly
351 ms 840144 bytes transpose_Tom
127 ms 824984 bytes transpose_Kelly
324 ms 844120 bytes transpose_Tom
116 ms 824984 bytes transpose_Kelly
Код:
import numpy
import tracemalloc as tm
from timeit import repeat
import itertools
def transpose_Tom(it_it_it):
blocks = [[iter(it) for it in it_it] for it_it in it_it_it]
it = iter(itertools.cycle(itertools.chain.from_iterable(zip(*blocks))))
while True:
try:
yield [[next(next(it)) for _ in range(len(blocks))]
for _ in range(len(blocks[0]))]
except StopIteration:
break
def transpose_Kelly(it_it_it):
return zip(*map(zip, *it_it_it))
def iterate(iii):
for ii in iii:
for i in ii:
for _ in i:
pass
n = 100
a = numpy.arange(n**3).reshape((n, n, n))
b = a.tolist()
for _ in range(3):
for func in transpose_Tom, transpose_Kelly:
tm.start()
iterate(func(b))
zyx = func(b)
memory = tm.get_traced_memory()[1]
tm.stop()
time = min(repeat(lambda: iterate(func(b)), number=1))
print(f'{round(time*1e3)} ms ', memory, 'bytes ', func.__name__)
print()
Попробуйте это онлайн!
Поменяйте местами второй и третий слой, затем поменяйте местами первый и второй. Чистый. (Конечно, материализация все еще там под капотом в * распаковках - этого не обойти.)
... подождите, нет, вы перетасовываете первый слой до конца, а затем меняете местами первые два слоя. map(zip, *it_it_it) сбивает с толку.
@user2357112 user2357112 Да, три обмена. Имена переменных предназначены для их отражения.
@user2357112 user2357112 Добавлена визуализация, показывающая раннее исчерпание двух внешних слоев.
Я получаю вывод, transpose(0,2) можно реализовать с тремя транспонированиями, то есть тремя zips. Но ваш окончательный ответ правильный, но имеет только два zips. О, я думаю, вариационная карта действует как zip
Я думал, что три перестановки будут не такими быстрыми, как их прямая реализация, но я подозреваю, что ваша реализация будет быстрее, чем моя. Я думаю, я должен проверить их на производительность, чтобы узнать
@TomHuntington Mine кажется примерно в 3 раза быстрее вашего (проверено на размере данных 100 × 100 × 100).
Можете ли вы поделиться этим кодом? Если он у вас еще есть topaz.github.io/paste
@TomHuntington См. добавленный раздел тестов для получения результатов и кода.
@TomHuntington При разрешении 50 × 50 × 50 у меня скорость примерно в 6 раз выше, чем у вас. На данный момент я не могу протестировать размер больше 100×100×100. Не могли бы вы?
n=500 83056 мс 20528440 байт transpose_Tom | 64966 мс 20120600 байт transpose_Kelly. Таким образом, в ~ 1,3 раза быстрее. Я запускаю wsl и меня убьют за n=1000 извините
@TomHuntington Я предполагаю, что большое использование памяти делает доступ в среднем медленнее, что одинаково вредит обоим решениям, поэтому их скорости сходятся. Я попробовал b = [[[0] * n] * n] * n (a не нужен), который занимает очень мало памяти, и там мой был примерно в 7 раз быстрее для n = 200. Я думаю, что мои три транспозиции действительно больше похожи на одну, с точки зрения фактической работы. Если бы я явно переместил n³ элементов три раза, это составило бы 3n³ объема работы. Но я не знаю. Две транспозиции двух внешних измерений просто работают с двумя внешними измерениями, что составляет 2n² работы. Итого n³+2n². По крайней мере, я так об этом думаю.
@TomHuntington Или с точки зрения моих почтовых индексов и карты: я создаю один внешний итератор zip, один итератор карты и n внутренних итераторов zip. n внутренних zip-итераторов — это те, кто фактически обрабатывает третье измерение, каждый из которых создает n n-кортежей. Вместе они не работают. Карта получает n итераций с n элементами в каждой и передает эти n² элементов в n внутренних почтовых индексов. Таким образом, итератор карты работает n². Внешний zip получает n итераторов zip и перебирает их, создавая n n-кортежей (из n-кортежей, но не просматривает их). Таким образом, внешний итератор zip также работает только n². Всего работы: n³+2n².
@TomHuntington Позвольте мне сказать по-другому: я не делаю 3 транспонирования. Я делаю колоссальные n+2 транспонирования. Транспонирование по почтовому индексу или карте на самом деле просто двумерное. С zip(*foo) foo является «итерируемым из итерируемых bar». Неважно, что такое bar. Итерабельность, число, что-то еще... не имеет значения. zip просто обрабатывает его как любой объект, не смотрит на него, просто помещает его в свои кортежи результатов. Таким образом, каждое транспонирование — это всего лишь n² работы. Теперь ... Мы думали о map(lambda xz: zip(*xz), yxz) как о 1 транспонировании двух внутренних измерений. Но это только "логично"..
.... вид. На самом деле, с точки зрения реализации, с точки зрения работы, это n zip. Каждый делает транспонирование. Итак, n транспонирует. Не просто 1. Вместе с моими zip(*xyz) и моими zip(*yzx) это всего n+2 транспонирования, каждое из которых выполняет n² работы. Итак, (n+2)n² = n³+2n² общая работа для n+2 транспонирований. Едва ли больше, чем n³ работы, которую необходимо выполнить для любого решения (поскольку во всей трехмерной структуре нужно перебирать n³ базовых элементов). Мое решение oneliner в равной степени выполняет n + 2 транспонирования для работы (n + 2) n², просто заменяет одно транспонирование zip на одно транспонирование карты.
Хорошо, так что transpose(1,2) на самом деле transpose(0, 1) n раз. Я просто посчитал это за один
@TomHuntington Да, я тоже думал об этом и до сих пор думаю. Я думаю, что это более полезно для понимания общей картины. Не думая об этом таким образом, я, возможно, не придумал бы свое решение. Когда я увидел ваш вопрос, я сначала попытался продумать, как будет проходить транспонированная итерация, и какие итераторы мне придется построить. Но через несколько минут я подумал: «К черту все, давайте просто поменяем местами три измерения». Таким образом, низкоуровневое мышление было трудным, но масштабное мышление облегчало задачу.
Звучит так, будто вы думаете, что zip(*it_it_it) ленивее, чем есть на самом деле. Он должен полностью исчерпать внешний итератор, прежде чем даже вызывать zip. Точно так же вещь map полностью исчерпывает каждый it_it перед вызовом zip.