So sortieren Sie zwei Listen (die aufeinander verweisen) genau auf die gleiche Weise

139

Angenommen, ich habe zwei Listen:

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

Wenn ich laufe list1.sort(), wird es sortiert, [1,1,2,3,4]aber gibt es auch eine Möglichkeit, list2synchron zu werden (also kann ich sagen, dass das Element dazu 4gehört 'three')? Die erwartete Ausgabe wäre also:

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

Mein Problem ist, dass ich ein ziemlich komplexes Programm habe, das gut mit Listen funktioniert, aber ich muss anfangen, auf einige Daten zu verweisen. Ich weiß, dass dies eine perfekte Situation für Wörterbücher ist, aber ich versuche, Wörterbücher in meiner Verarbeitung zu vermeiden, da ich die Schlüsselwerte sortieren muss (wenn ich Wörterbücher verwenden muss, weiß ich, wie man sie verwendet).

Grundsätzlich liegt die Natur dieses Programms darin, dass die Daten in zufälliger Reihenfolge (wie oben) vorliegen. Ich muss sie sortieren, verarbeiten und dann die Ergebnisse senden (die Reihenfolge spielt keine Rolle, aber die Benutzer müssen wissen, welches Ergebnis zu welchem ​​gehört Schlüssel). Ich habe darüber nachgedacht, es zuerst in ein Wörterbuch aufzunehmen und dann die Liste eins zu sortieren, aber ich hätte keine Möglichkeit, Elemente mit demselben Wert zu unterscheiden, wenn die Reihenfolge nicht eingehalten wird (dies kann sich auf die Übermittlung der Ergebnisse an die Benutzer auswirken). Wenn ich die Listen habe, würde ich im Idealfall lieber einen Weg finden, beide Listen zusammen zu sortieren. Ist das möglich?

Fehler 404
quelle
Ich sollte darauf hinweisen, dass Ihre Variablen in Liste2 nicht auf die Ints in Liste1 verweisen. Wenn Sie beispielsweise einen Wert wie list1 [0] = 9 ändern und sich list2 ansehen, ist list2 [0] immer noch 3. Bei Ganzzahlen in Python wird der Verweis / Zeiger nicht verwendet, sondern der Wert kopiert. Du wärst besser dran gewesen list2 = list1 [:]
robert king

Antworten:

242

Ein klassischer Ansatz für dieses Problem ist die Verwendung der Redewendung "Dekorieren, Sortieren, Nichtdekorieren", die mit der in Python integrierten zipFunktion besonders einfach ist :

>>> 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')

Dies sind natürlich keine Listen mehr, aber das kann leicht behoben werden, wenn es darauf ankommt:

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

Es ist erwähnenswert, dass das oben Genannte Geschwindigkeit für Knappheit opfern kann; Die In-Place-Version, die 3 Zeilen belegt, ist auf meinem Computer für kleine Listen etwas schneller:

>>> %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

Andererseits könnte bei größeren Listen die einzeilige Version schneller sein:

>>> %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

Wie Quantum7 hervorhebt, ist der Vorschlag von JSF noch etwas schneller, wird aber wahrscheinlich immer nur ein bisschen schneller sein, da Python intern für alle schlüsselbasierten Sortierungen dieselbe DSU -Sprache verwendet. Es passiert nur ein bisschen näher am Bare Metal. (Dies zeigt, wie gut die zipRoutinen optimiert sind!)

Ich denke, der zipbasierte Ansatz ist flexibler und etwas lesbarer, deshalb bevorzuge ich ihn.

senderle
quelle
6
Was bedeutet das Sternchen in der dritten Zeile?
Jeffrey
8
Um auf das oben *
Gesagte einzugehen
1
Das von JF Sebastian vorgeschlagene sortierte Index- / Kartenparadigma ist für mich etwa 10% schneller als jede Zip-Lösung (unter Verwendung von Listen mit 10000 zufälligen Ints):% timeit index = range (len (l1)); index.sort (key = l1 .__ getitem__); map (l1 .__ getitem__, index); map (l2 .__ getitem__, index) 100 Schleifen, Best of 3: 8,04 ms pro Schleife (vs 9,17 ms, 9,07 ms für Senderles Timits)
Quantum7
1
Die erste und zweite Zip in Liste1, Liste2 = Zip (* sortiert (Zip (Liste1, Liste2))) machen so unterschiedliche Dinge. Das * macht den Unterschied.
Ashu
1
@ashu, in gewissem Sinne ja! Aber in einem anderen Sinne sind sie kaum anders. zip(*x)hat die interessante Eigenschaft, dass es seine eigene Umkehrung ist: gibt l = [(1, 2), (3, 4)]; list(zip(*zip(*l))) == lzurück True. Es ist effektiv ein Umsetzungsoperator. zip()Dies ist für sich genommen der gleiche Operator, setzt jedoch voraus, dass Sie die Eingabesequenz manuell entpackt haben.
senderle
30

Sie können Indizes mit Werten als Schlüssel sortieren:

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

So erhalten Sie sortierte Listen mit sortierten Indizes:

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

In Ihrem Fall sollten Sie nicht haben list1, list2sondern eine einzelne Liste von Paaren:

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

Es ist einfach zu erstellen; In Python ist es einfach zu sortieren:

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

Nur nach dem ersten Wert sortieren:

data.sort(key=lambda pair: pair[0])
jfs
quelle
Das Coole daran ist, dass ich Indizes behalten und später andere Dinge sortieren kann, falls list1 eine wichtige Koordinate ist, die mehrere andere Arrays betrifft.
EL_DON
3
indexes = list (range (len (list1))) für python 3
DonQuiKong
@ DonQuiKong müssen Sie auch list() herum, map()wenn Sie diesen Code in Python 3 verwenden
jfs
Oder stattdessen sorted_list1 = list(map(list1.__getitem__, indexes))könnte man es tun sorted_list1 = [list1[i] for i in indexes].
Nathan
20

Ich habe die Antwort von senderle lange verwendet, bis ich sie entdeckte np.argsort. So funktioniert es.

# 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]

Ich finde diese Lösung intuitiver und sie funktioniert sehr gut. Die Leistung:

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

Obwohl np.argsortes nicht das schnellste ist, finde ich es einfacher zu bedienen.

Daniel Thaagaard Andreasen
quelle
1
Beim Ausführen Ihres Beispiels wird eine Fehlermeldung TypeError: only integer arrays with one element can be converted to an indexangezeigt : (Python 2.7.6, numpy 1.8.2). Um dies zu beheben, müssen list1 und list2 als numpy-Arrays deklariert werden.
BenB
Vielen Dank. Schreibe ich das nicht in den Kommentar der Funktion? Wie auch immer, ich finde es albern, np.argsortnicht zu versuchen, np.arrayintern zu konvertieren .
Daniel Thaagaard Andreasen
Ich bezog mich auf das erste Code-Snippet, da es nicht wie geschrieben läuft :)
BenB
Ich habe es korrigiert, indem ich die Listen konvertiert habe, wenn sie numpy Arrays zugewiesen wurden. Danke für den Kommentar :)
Daniel Thaagaard Andreasen
Jetzt werden sie zweimal in Numpy-Arrays konvertiert;)
BenB
13

Schwartzsche Transformation . Die integrierte Python-Sortierung ist stabil, sodass die beiden 1keine Probleme verursachen.

>>> 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')]
Karl Knechtel
quelle
2
Wenn Sie jedoch feststellen, dass Sie dies tun müssen, sollten Sie die beiden "parallelen" Datenlisten unbedingt in Betracht ziehen, anstatt eine Liste mit 2 Tupeln (Paaren) zu führen ... oder vielleicht sogar tatsächlich eine Klasse zu erstellen .
Karl Knechtel
3

Wie wäre es mit:

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')]
Artsiom Rudzenka
quelle
2

Sie können die Funktionen zip()und sort()verwenden, um dies zu erreichen:

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']

Hoffe das hilft

Hunter McMillen
quelle
2

Sie können das Schlüsselargument in der Methode sorted () verwenden, es sei denn, Sie haben zwei gleiche Werte in list2.

Der Code ist unten angegeben:

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

Es sortiert list2 nach den entsprechenden Werten in list1, stellt jedoch sicher, dass dabei keine zwei Werte in list2 als gleich ausgewertet werden, da die Funktion list.index () den ersten Wert angibt

Saurav Yadav
quelle
sortiert ist unter bestimmten Bedingungen etwas langsam, obwohl es funktioniert.
Tyan
2

Eine Möglichkeit besteht darin, zu verfolgen, wohin jeder Index führt, indem die Identität [0,1,2, .. n] sortiert wird.

Dies funktioniert für eine beliebige Anzahl von Listen.

Bewegen Sie dann jeden Gegenstand an seine Position. Am besten verwenden Sie Spleiße.

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']"

Beachten Sie, dass wir die Listen hätten iterieren können, ohne sie zu sortieren:

list1_iter = (list1[i] for i in index)
Robert King
quelle
1

Wenn Sie numpy verwenden, können np.argsortSie die sortierten Indizes abrufen und diese Indizes auf die Liste anwenden. Dies funktioniert für eine beliebige Anzahl von Listen, die Sie sortieren möchten.

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])
Kurtis Streutker
quelle
0

eine algorithmische Lösung:

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]

Ausgänge: -> Ausgabegeschwindigkeit: 0.2s

>>>list1
>>>[1, 1, 2, 3, 4]
>>>list2
>>>['one', 'one2', 'two', 'three', 'four']
Jundullah
quelle
0

Ein anderer Ansatz zum Beibehalten der Reihenfolge einer Zeichenfolgenliste beim Sortieren nach einer anderen Liste lautet wie folgt:

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)

Ausgabe

['one', 'one2', 'two', 'three', 'four']
[1, 1, 2, 3, 4]
Brock
quelle
0

Ich möchte die Antwort von open jfs erweitern , die für mein Problem sehr gut funktioniert hat: Sortieren von zwei Listen nach einer dritten, dekorierten Liste :

Wir können unsere dekorierte Liste auf jede Art und Weise erstellen, aber in diesem Fall erstellen wir sie aus den Elementen einer der beiden ursprünglichen Listen, die wir sortieren möchten:

# 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']

Jetzt können wir die Lösung von jfs anwenden , um unsere beiden Listen nach der dritten zu sortieren

# 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'}]

Edit: Hey Leute, ich habe einen Blockpost darüber gemacht, schau es dir an, wenn du Lust dazu hast :) 🐍🐍🐍

frietz58
quelle
-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
quelle
2
ein paar erklärungszeilen wären hilfreich
saiedmomen
@saiedmomen Ich habe es in Bezug auf stackoverflow.com/questions/53829160/… gepostet. Hier wird die Zielzeichenfolge über die Quellzeichenfolge gesucht.
user10340258