но я бы хотел напрямую воздействовать на spam_list, например list.sort (), а не копировать его, как sorted ()
ВСЕГО ONE SOLUTION,это именно то, что вы просите. Каждое другое решение неявно делает копию одного или обоих списков (или превращает его в диктовку и т. Д.). То, что вы запрашиваете, - это метод, который сортирует два списка на месте, используя O(1) дополнительный пробел , используя один список в качестве ключей другого.Лично я бы смирился с дополнительным пространством, но если бы вы действительно этого хотели, вы могли бы сделать это:
(правка: возможно, это тот случай, когда оригинальный постер на самом деле не заботится о .sort, потому чтоон эффективен, но скорее потому, что он изменяет состояние, в общем, опасно хотеть, и языки не низкого уровня пытаются этого избежать и даже запретить, но решения, использующие назначение срезов, достигнут семантики «на месте»)
- Создать пользовательский подкласс словаря (фактически класс
Zip), который поддерживается обоими сортируемыми списками. - Индексация
myZip[i] -> приводит к кортежу (list1[i],list2[i]) - Назначение
myZip[i]=(x1,x2) -> отправляет в list1[i]=x1, list2[i]=x2. - Используйте , что , чтобы сделать
myZip(spam_list,spam_order).sort(), и теперь оба spam_list и spam_orderсортируются по месту
Пример:
#!/usr/bin/python3
class LiveZip(list):
def __init__(self, list1, list2):
self.list1 = list1
self.list2 = list2
def __len__(self):
return len(self.list1)
def __getitem__(self, i):
return (self.list1[i], self.list2[i])
def __setitem__(self, i, tuple):
x1,x2 = tuple
self.list1[i] = x1
self.list2[i] = x2
spam_list = ["We", "are", "the", "knights", "who", "say", "Ni"]
spam_order = [0,1,2,4,5,6,3]
#spam_list.magical_sort(spam_order)
proxy = LiveZip(spam_order, spam_list)
Теперь посмотрим, работает ли он ...
#proxy.sort()
#fail --> oops, the internal implementation is not meant to be subclassed! lame
# It turns out that the python [].sort method does NOT work without passing in
# a list to the constructor (i.e. the internal implementation does not use the
# public interface), so you HAVE to implement your own sort if you want to not
# use any extra space. This kind of dumb. But the approach above means you can
# just use any standard textbook in-place sorting algorithm:
def myInPlaceSort(x):
# [replace with in-place textbook sorting algorithm]
СЕЙЧАС это работает:
myInPlaceSort(proxy)
print(spam_list)
К сожалению нет способа просто отсортировать один список в O(1) spтуз без сортировки другой ;если вы не хотите сортировать оба списка, вы можете также использовать свой оригинальный подход, который создает фиктивный список.
Однако вы можете сделать следующее:
spam_list.sort(key=lambda x:x)
, но если функция key или cmp делает какие-либо ссылки на какую-либо коллекцию (например, если вы передаете dict.__getitem__ изречения, который вы должны были создать), это не лучше, чем ваш первоначальный O(N) -пространственный подход, если только выуже случалось иметь такой словарь.
Оказывается, это дублирующий вопрос Имеются ли параллельные массивы сортировки Python? , но на этот вопрос также не было правильных ответов, кроме этот , который эквивалентен моему, но без примера кода.Если вы не оптимизированный или специализированный код, я бы просто использовал ваше оригинальное решение, которое по пространственной сложности эквивалентно другим решениям.
edit2: как указал отправитель, OP не хочет сортировкивообще, но скорее желает, я думаю, применить перестановку .Чтобы достичь этого, вы можете и ДОЛЖНЫ использовать простое индексирование, которое другие ответы предлагают [spam_list[i] for i in spam_order], но необходимо сделать явную или неявную копию, поскольку вам все еще нужны промежуточные данные.(Не относится и к записи, применение обратной перестановки - это, я думаю, обратная параллельная сортировка с тождеством, и вы можете использовать одну для получения другой, хотя сортировка менее эффективна по времени. _,spam_order_inverse = parallelSort(spam_order, range(N)), затем сортировка по spam_order_inverse. Я оставляю рассмотренное выше обсуждение сортировки по записи.)
edit3:
Однако можно достичь перестановки на месте в O(#cycles) места, но с ужасной эффективностью времени.Каждая перестановка может быть разложена на непересекающиеся перестановки, применяемые параллельно на подмножествах.Эти подмножества называются циклами или орбитами.Период равен их размеру.Таким образом, вы делаете прыжок веры и делаете следующее:
Create a temp variable.
For index i=0...N:
Put x_i into temp, assign NULL to x_i
Swap temp with x_p(i)
Swap temp with x_p(p(i))
...
Swap temp with x_p(..p(i)..), which is x_i
Put a "do not repeat" marker on the smallest element you visited larger than i
Whenever you encounter a "do not repeat" marker, perform the loop again but
without swapping, moving the marker to the smallest element larger than i
To avoid having to perform the loop again, use a bloom filter
Это будет выполняться за O (N ^ 2) время и O (#cycles) без фильтра Блума или ~ O (N)время и пространство O (#cycle + bloomfilter_space), если вы их используете