Python сортирует параллельные массивы на месте?

Question

Существует ли простой (то есть, без использования собственной функции сортировки) способ сортировки параллельных списков без ненужного копирования в Python? Например:

foo = range(5)
bar = range(5, 0, -1)
parallelSort(bar, foo)
print foo # [4,3,2,1,0]
print bar # [1,2,3,4,5]

Я видел примеры, использующие zip, но кажется глупым копировать все ваши данные из параллельных списков в список кортежей и обратно, если этого можно легко избежать.

Answer 1

Вот простой способ:

perm = sorted(xrange(len(foo)), key=lambda x:foo[x])

Это генерирует список перестановок - значение в perm [i] является индексом i-го наименьшего значения в foo. Затем вы можете получить доступ к обоим спискам в следующем порядке:

for p in perm:
  print "%s: %s" % (foo[p], bar[p])

Вам нужно будет сравнить его, чтобы выяснить, является ли он более эффективным, хотя - я сомневаюсь, что это имеет большое значение.

Answer 2

Есть ли простой способ? Да. Используйте почтовый индекс.

Есть ли "простой способ, который не использует почтовый вариант"? Нет.

Если вы хотите уточнить, почему вы возражаете против использования zip, это было бы полезно. Либо вы копируете объекты, в этом случае Python будет копировать по ссылке, либо вы копируете что-то более легкое в легкий кортеж, чтобы не быть достойным оптимизации.

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

Answer 3

Любое решение, которое я могу себе представить, кроме введения с нуля, использует индексы, или дикт, или что-то еще, что действительно не способно спасти вашу память.В любом случае, использование zip только увеличит использование памяти на постоянный коэффициент, поэтому стоит убедиться, что это действительно проблема перед решением.

Если возникает проблема, возможно, существуют более эффективные решения.Поскольку элементы foo и bar так тесно связаны, вы уверены, что их правильное представление не является списком кортежей?Вы уверены, что они не должны быть в более компактной структуре данных, если у вас не хватает памяти, такой как пустой массив или база данных (последняя из которых действительно хороша для такого рода манипуляций)?

(Также, кстати, itertools.izip может сэкономить вам немного памяти по сравнению с zip, хотя в результате сортировки вы все равно получите полный сжатый список в виде списка.)

Answer 4

Чтобы достичь этого, вам нужно реализовать свой собственный вид.

Однако: действительно ли ненужное копирование вредит вашему приложению? Часто части Python кажутся мне неэффективными, но они достаточно эффективны для того, что мне нужно.