Given parallel lists, how can I sort one while permuting (rearranging) the other in the same way?

Предположим, у меня есть:

list1 = [3, 2, 4, 1, 1]
list2 = ['three', 'two', 'four', 'one', 'one2']

Вызов list1.sort() отсортирует его, что приведет к [1, 1, 2, 3, 4]. Однако могу ли я заставить list2 быть перегруппированным синхронно с этим, чтобы получить подобный результат?

list1 = [1, 1, 2, 3, 4]
list2 = ['one', 'one2', 'two', 'three', 'four']

_{Иногда люди формулируют проблему по-разному: имея два списка, они хотели бы использовать один для определения порядка сортировки для другого, т. Е. Сортировать list2 в порядке, описанном соответствующими значениями в list1. Хитрость в том, что это эквивалентно сортировке значений "ключа" (list1), а затем перегруппировке list2 таким же образом. Другими словами, именно то, что описано здесь. Однако некоторые ответы на другой вопрос впоследствии отбрасывают "отсортированные ключи".}

_{Смотрите также: Как я могу отсортировать список в соответствии с тем, где его элементы появляются в другом списке? - это еще один распространенный способ, которым люди хотят отсортировать один список "на основе" другого. Прежде чем пытаться закрыть повторяющиеся вопросы, проявите особую осторожность, чтобы точно проверить, чего хочет OP. Ключевой ключ: списки должны быть одинаковой длины?}

Одним из классических подходов к этой проблеме является использование идиомы "decorate, сортировать, undecorate", которая особенно проста с использованием встроенной в python функции zip:

>>> list1 = [3,2,4,1, 1]
>>> list2 = ['three', 'two', 'four', 'one', 'one2']
>>> list1, list2 = zip(*sorted(zip(list1, list2)))
>>> list1
(1, 1, 2, 3, 4)
>>> list2 
('one', 'one2', 'two', 'three', 'four')

Это, конечно, больше не списки, но это легко исправить, если это имеет значение:

>>> list1, list2 = (list(t) for t in zip(*sorted(zip(list1, list2))))
>>> list1
[1, 1, 2, 3, 4]
>>> list2
['one', 'one2', 'two', 'three', 'four']

Стоит отметить, что вышеуказанное может принести в жертву скорость из-за краткости; версия на месте, которая занимает 3 строки, немного быстрее на моей машине для небольших списков:

>>> %timeit zip(*sorted(zip(list1, list2)))
100000 loops, best of 3: 3.3 us per loop
>>> %timeit tups = zip(list1, list2); tups.sort(); zip(*tups)
100000 loops, best of 3: 2.84 us per loop

С другой стороны, для списков большего размера однострочная версия может быть быстрее:

>>> %timeit zip(*sorted(zip(list1, list2)))
100 loops, best of 3: 8.09 ms per loop
>>> %timeit tups = zip(list1, list2); tups.sort(); zip(*tups)
100 loops, best of 3: 8.51 ms per loop

Как указывает Quantum7, предложение JSF еще немного быстрее, но, вероятно, оно будет только немного быстрее, потому что Python использует ту же самую идиому DSU внутри для всех сортировок на основе ключей. Это просто происходит немного ближе к голому металлу. (Это показывает, насколько хорошо оптимизированы zip процедуры!)

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

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

В этом случае вы можете отсортировать индексы, как предложено в ответе jfs, или вы можете предоставить sort ключевую функцию, которая позволяет избежать сравнения элементов list2:

result1, result2 = zip(*sorted(zip(list1, list2), key=lambda x: x[0]))

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

Вы можете сортировать индексы, используя значения в качестве ключей:

indexes = range(len(list1))
indexes.sort(key=list1.__getitem__)

# Or on Python 3, where range does not return a list
indexes = sorted(range(len(list1)), key=list1.__getitem__)

Для получения отсортированных списков с учетом отсортированных индексов:

sorted_list1 = map(list1.__getitem__, indexes)
sorted_list2 = map(list2.__getitem__, indexes)

# Python 3 version, converting map iterator to true list
sorted_list1 = list(map(list1.__getitem__, indexes))
sorted_list2 = list(map(list2.__getitem__, indexes))

В вашем случае у вас не должно быть list1, list2 а скорее один список пар:

data = [(3, 'three'), (2, 'two'), (4, 'four'), (1, 'one'), (1, 'one2')]

Его легко создать; его легко отсортировать на Python:

data.sort() # sort using a pair as a key

Сортировка только по первому значению:

data.sort(key=lambda pair: pair[0])

Я долгое время использовал ответ, данный senderle, пока не обнаружил np.argsort. Вот как это работает.

# idx works on np.array and not lists.
list1 = np.array([3,2,4,1])
list2 = np.array(["three","two","four","one"])
idx   = np.argsort(list1)

list1 = np.array(list1)[idx]
list2 = np.array(list2)[idx]

Я нахожу это решение более интуитивно понятным, и оно работает действительно хорошо. Производительность:

def sorting(l1, l2):
    # l1 and l2 has to be numpy arrays
    idx = np.argsort(l1)
    return l1[idx], l2[idx]

# list1 and list2 are np.arrays here...
%timeit sorting(list1, list2)
100000 loops, best of 3: 3.53 us per loop

# This works best when the lists are NOT np.array
%timeit zip(*sorted(zip(list1, list2)))
100000 loops, best of 3: 2.41 us per loop

# 0.01us better for np.array (I think this is negligible)
%timeit tups = zip(list1, list2); tups.sort(); zip(*tups)
100000 loops, best for 3 loops: 1.96 us per loop

Несмотря на то, что np.argsort это не самый быстрый список, я нахожу его более простым в использовании.

Это можно сделать с помощью того, что программисты Perl называют преобразованием Шварца , также известным как идиома decorate-sort-undecorate . Встроенная сортировка на Python стабильна, поэтому два 1s не вызывают проблем.

>>> l1 = [3, 2, 4, 1, 1]
>>> l2 = ['three', 'two', 'four', 'one', 'second one']
>>> zip(*sorted(zip(l1, l2)))
[(1, 1, 2, 3, 4), ('one', 'second one', 'two', 'three', 'four')]