Как отсортировать два списка (которые ссылаются друг на друга) одним и тем же способом

139

Скажем, у меня есть два списка:

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

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

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

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

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

Ошибка 404
источник
Я должен отметить, что ваши переменные в list2 не указывают на целые числа в list1. Например, если изменить значение, например list1 [0] = 9, и посмотреть на list2, list2 [0] все равно будет 3. С целыми числами в python он не использует ссылку / указатель, он копирует значение. Тебе лучше было бы пойти list2 = list1 [:]
Роберт Кинг

Ответы:

242

Один из классических подходов к этой проблеме - использовать идиому «декорировать, сортировать, декорировать», что особенно просто при использовании встроенной zipфункции python :

>>> 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основанный на них подход более гибок и немного более читабелен, поэтому я предпочитаю его.

senderle
источник
6
что означает звездочка в третьей строке?
Джеффри
8
Чтобы уточнить это, *оператор выполняет распаковку аргументов ,
senderle
1
Сортированная парадигма индекса / карты, предложенная Дж.Ф. Себастьяном, примерно на 10% быстрее, чем любое из zip-решений для меня (используя списки из 10000 случайных чисел):% timeit index = range (len (l1)); index.sort (ключ = l1 .__ getitem__); карта (l1 .__ getitem__, index); map (l2 .__ getitem__, index) 100 циклов, лучшее из 3: 8,04 мс на цикл (против 9,17 мс, 9,07 мс для тактов отправителя)
Quantum7
1
Первый и второй zip в list1, list2 = zip (* sorted (zip (list1, list2))) делают разные вещи. * Имеет все значение.
ашу
1
@ashu, в некотором смысле, да! Но в другом смысле они почти не отличаются. zip(*x)обладает интересным свойством обратного: l = [(1, 2), (3, 4)]; list(zip(*zip(*l))) == lвозвращает True. Это фактически оператор транспонирования. zip()сам по себе является точно таким же оператором, но предполагает, что вы распаковали входную последовательность вручную.
senderle
30

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

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

Чтобы получить отсортированные списки по заданным отсортированным индексам:

sorted_list1 = map(list1.__getitem__, indexes)
sorted_list2 = 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])
JFS
источник
Крутая вещь в этом заключается в том, что я могу хранить индексы и сортировать другие вещи позже, в случае, если list1 является важной координатой, которая влияет на несколько других массивов.
EL_DON
3
indexes = list (range (len (
list1
@DonQuiKong вы также должны list() вокруг , map()если вы хотите использовать этот код в Python 3.
JFS
Или вместо того, чтобы sorted_list1 = list(map(list1.__getitem__, indexes))один мог сделать sorted_list1 = [list1[i] for i in indexes].
Натан
20

Я использовал ответ, данный 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он не самый быстрый, его легче использовать.

Даниэль Таагаард Андреасен
источник
1
Я получаю сообщение об ошибке при запуске вашего примера: TypeError: only integer arrays with one element can be converted to an index(Python 2.7.6, numpy 1.8.2). Чтобы это исправить, списки list1 и list2 должны быть объявлены как массивы numpy.
BenB
Спасибо. Разве это не то, что я пишу в комментарии в функции? Во всяком случае, я думаю, что глупо np.argsortне пытаться преобразовать np.arrayвнутренне.
Даниэль Таагаард Андреасен
Я имел в виду первый фрагмент кода, так как он не работает так, как написано :)
BenB
Я исправил это, преобразовав списки, когда они назначены на массивы. Спасибо за комментарий :)
Daniel Thaagaard Andreasen
Теперь они дважды преобразуются в массивы Numpy;)
BenB
13

Преобразование Шварца . Встроенная сортировка Python стабильна, поэтому две 1проблемы не вызывают проблем.

>>> 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')]
Карл Кнехтель
источник
2
Однако, если вы обнаружите, что вам нужно это сделать, вам следует настоятельно рассмотреть возможность использования двух «параллельных» списков данных, в отличие от хранения списка из двух кортежей (пар) ... или, возможно, даже фактического создания класса. ,
Карл Кнехтель,
3

Что о:

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

sortedRes = sorted(zip(list1, list2), key=lambda x: x[0]) # use 0 or 1 depending on what you want to sort
>>> [(1, 'one'), (1, 'one2'), (2, 'two'), (3, 'three'), (4, 'four')]
Артём Рудзенка
источник
2

Вы можете использовать zip()и sort()функцию для достижения этой цели :

Python 2.6.5 (r265:79063, Jun 12 2010, 17:07:01)
[GCC 4.3.4 20090804 (release) 1] on cygwin
>>> list1 = [3,2,4,1,1]
>>> list2 = ['three', 'two', 'four', 'one', 'one2']
>>> zipped = zip(list1, list2)
>>> zipped.sort()
>>> slist1 = [i for (i, s) in zipped]
>>> slist1
[1, 1, 2, 3, 4]
>>> slist2 = [s for (i, s) in zipped]
>>> slist2
['one', 'one2', 'two', 'three', 'four']

Надеюсь это поможет

Хантер МакМиллен
источник
2

Вы можете использовать ключевой аргумент в методе sorted (), если у вас нет двух одинаковых значений в list2.

Код приведен ниже:

sorted(list2, key = lambda x: list1[list2.index(x)]) 

Он сортирует list2 в соответствии с соответствующими значениями в list1, но убедитесь, что при его использовании никакие два значения в list2 не считаются равными, поскольку функция list.index () дает первое значение

Саурав Ядав
источник
сортировка идет медленно в некоторых условиях, хотя и работает.
Тян
2

Одним из способов является отслеживание того, куда идет каждый индекс, путем сортировки идентификаторов [0,1,2, .. n]

Это работает для любого количества списков.

Затем переместите каждый элемент на свою позицию. Использование сростков лучше всего.

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

index = list(range(len(list1)))
print(index)
'[0, 1, 2, 3, 4]'

index.sort(key = list1.__getitem__)
print(index)
'[3, 4, 1, 0, 2]'

list1[:] = [list1[i] for i in index]
list2[:] = [list2[i] for i in index]

print(list1)
print(list2)
'[1, 1, 2, 3, 4]'
"['one', 'one2', 'two', 'three', 'four']"

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

list1_iter = (list1[i] for i in index)
Роберт Кинг
источник
1

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

import numpy as np

arr1 = np.array([4,3,1,32,21])
arr2 = arr1 * 10
sorted_idxs = np.argsort(arr1)

print(sorted_idxs)
>>> array([2, 1, 0, 4, 3])

print(arr1[sorted_idxs])
>>> array([ 1,  3,  4, 21, 32])

print(arr2[sorted_idxs])
>>> array([ 10,  30,  40, 210, 320])
Куртис Стрейткер
источник
0

алгоритмическое решение:

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


lis = [(list1[i], list2[i]) for i in range(len(list1))]
list1.sort()
list2 = [x[1] for i in range(len(list1)) for x in lis if x[0] == i]

Выходы: -> Скорость выхода: 0.2s

>>>list1
>>>[1, 1, 2, 3, 4]
>>>list2
>>>['one', 'one2', 'two', 'three', 'four']
Джундулла
источник
0

Другой подход к сохранению порядка списка строк при сортировке по другому списку заключается в следующем:

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

# sort on list1 while retaining order of string list
sorted_list1 = [y for _,y in sorted(zip(list1,list2),key=lambda x: x[0])]
sorted_list2 = sorted(list1)

print(sorted_list1)
print(sorted_list2)

вывод

['one', 'one2', 'two', 'three', 'four']
[1, 1, 2, 3, 4]
барсук
источник
0

Я хотел бы расширить ответ open jfs , который отлично подошел для моей задачи: сортировка двух списков по третьему, оформленному списку :

Мы можем создать наш оформленный список любым способом, но в этом случае мы создадим его из элементов одного из двух исходных списков, которые мы хотим отсортировать:

# say we have the following list and we want to sort both by the algorithms name 
# (if we were to sort by the string_list, it would sort by the numerical 
# value in the strings)
string_list = ["0.123 Algo. XYZ", "0.345 Algo. BCD", "0.987 Algo. ABC"]
dict_list = [{"dict_xyz": "XYZ"}, {"dict_bcd": "BCD"}, {"dict_abc": "ABC"}]

# thus we need to create the decorator list, which we can now use to sort
decorated = [text[6:] for text in string_list]  
# decorated list to sort
>>> decorated
['Algo. XYZ', 'Algo. BCD', 'Algo. ABC']

Теперь мы можем применить решение JFS для сортировки наших двух списков по третьему

# create and sort the list of indices
sorted_indices = list(range(len(string_list)))
sorted_indices.sort(key=decorated.__getitem__)

# map sorted indices to the two, original lists
sorted_stringList = list(map(string_list.__getitem__, sorted_indices))
sorted_dictList = list(map(dict_list.__getitem__, sorted_indices))

# output
>>> sorted_stringList
['0.987 Algo. ABC', '0.345 Algo. BCD', '0.123 Algo. XYZ']
>>> sorted_dictList
[{'dict_abc': 'ABC'}, {'dict_bcd': 'BCD'}, {'dict_xyz': 'XYZ'}]

Изменить: Эй, ребята, я сделал блок пост об этом, проверьте, если вам это нравится :) 🐍🐍🐍

frietz58
источник
-1
newsource=[];newtarget=[]
for valueT in targetFiles:
    for valueS in sourceFiles:
            l1=len(valueS);l2=len(valueT);
            j=0
            while (j< l1):
                    if (str(valueT) == valueS[j:l1]) :
                            newsource.append(valueS)
                            newtarget.append(valueT)
                    j+=1
user10340258
источник
2
пара строк объяснения были бы полезны
saiedmomen
@saiedmomen Я разместил его со ссылкой на stackoverflow.com/questions/53829160/… Здесь целевая строка ищется по исходной строке.
user10340258