wake-up-neo.com

Wie sortiere ich eine Liste nach einer anderen Liste?

Es gibt eine Liste:

a = [("ax", 1), ("ec",3), ("bk", 5)]

eine andere Liste: 

b = ["ec", "ax", "bk"]

Ich möchte nach b sortieren:

sort_it(a, b)

a = [("ec",3), ("ax", 1), ("bk", 5)]

Wie macht man das?

35
alwbtc
a.sort(key=lambda x: b.index(x[0]))

Dies sortiert a vor Ort anhand des Indexes in b des ersten Elements jedes Tuples von a als den Werten, nach denen es sortiert wird.

Eine andere, möglicherweise sauberere Schreibweise wäre:

a.sort(key=lambda (x,y): b.index(x))

Wenn Sie eine große Anzahl von Elementen hatten, ist es möglicherweise effizienter, die Dinge ein bisschen anders zu machen, da .index() für eine lange Liste eine teure Operation sein kann und Sie keine vollständige Sortierung durchführen müssen, da Sie die Reihenfolge bereits kennen :

mapping = dict(a)
a[:] = [(x,mapping[x]) for x in b]

Beachten Sie, dass dies nur für eine Liste von 2-Tupeln funktioniert. Wenn Sie möchten, dass Tupel mit beliebiger Länge funktionieren, müssen Sie sie leicht ändern:

mapping = dict((x[0], x[1:]) for x in a)
a[:] = [(x,) + mapping[x] for x in b]
59
Amber

Eine andere Möglichkeit ist, a zu sortieren, die Indizes von b nach b zu sortieren und dann die a nach Indizes zu sortieren

a.sort(key=lambda x: x[0])
ind = [i[0] for i in sorted(enumerate(b),key=lambda x: x[1])]
a = [i[0] for i in sorted(Zip(a,ind),key=lambda x: x[1])]

da für jede Sortierung n * log (n) erforderlich ist, ist dies für größere Listen noch skalierbar

1
fritz-johann

Es gibt tatsächlich eine Möglichkeit, dies in linearer O(n) Zeit zu tun, da dies nicht wirklich eine Sortieroperation ist. Die Existenz der Liste b bedeutet, dass die Sortierung erfolgt Alles, was wir wirklich tun müssen, ist, die Elemente von a in der gleichen Reihenfolge anzuordnen, was dank Wörterbüchern effizient möglich ist.

from collections import defaultdict

def sorted_by(seq_to_sort, desired_order, key=None):
    if key is None:
        key = lambda x: x

    # group the elements by their key
    grouped_items = defaultdict(list)
    for item in seq_to_sort:
        k = key(item)
        grouped_items[k].append(item)

    # flatten the dict of groups to a list
    return [item for key in desired_order for item in grouped_items[key]]

Verwendungszweck:

a = [("ax", 1), ("ec", 3), ("bk", 5)]
b = ["ec", "ax", "bk"]
result = sorted_by(a, b, lambda tup: tup[0])
print(result)  # output: [("ec", 3), ("ax", 1), ("bk", 5)]

Anmerkungen:

  • Dies ist eine stabile Sorte; Wenn zwei Listenelemente denselben Schlüssel haben, bleibt ihre Reihenfolge erhalten. Beispiel:

    >>> sorted_by([1, 2, 3], [5], key=lambda x: 5)
    [1, 2, 3]
    
  • Wenn Listenelemente Schlüsseln zugeordnet werden, die in desired_order Nicht vorhanden sind, werden diese Elemente stillschweigend verworfen. Zum Beispiel:

    >>> sorted_by([1, 2, 3], [1, 2, 3], key=lambda x: 5)
    []
    

Siehe auch:

1
Aran-Fey

Eine herkömmliche Sortierung ist möglicherweise nicht erforderlich.

[tup for lbl in b for tup in a if tup[0] == lbl]
# [('ec', 3), ('ax', 1), ('bk', 5)]
0
pylang