Ich habe zwei Listen (eigentlich zwei Datenrahmenspalten). Sie haben die gleichen Elemente, aber eine Liste ist ungeordnet. Ich möchte die Indizes der ungeordneten Liste erhalten, die der geordneten Liste entsprechen. Gibt es eine einfache Möglichkeit, dies zu tun?

I.E. list1 [Indizes] == list2

Ich muss die Indexvariable erhalten.

-2
dduque 18 Apr. 2018 im 19:31

3 Antworten

Beste Antwort

Die Antwort von C8H10N42 hat eine zeitliche Komplexität von O (n ^ 2), auf großen Listen wird es lange dauern. Jeder Aufruf von index () ist O (n) und wird n-mal aufgerufen.

Wenn Sie eine bessere Leistung benötigen, können Sie stattdessen diese O (n) -Lösung verwenden:

l1 = ['a','b','c','d']
l2 = ['c','d','b','a']
indices = {val: i for i, val in enumerate(l1)}

[indices[x] for x in l2]

Das Erstellen des Wörterbuchs ist O (n). Anschließend können Sie den Aufruf von O (n) index () durch O (1) dict access ersetzen. Die Komplexität ist also O (n) + O (n) anstelle von O (n ^ 2).

Wenn Sie beide mit unterschiedlichen Listengrößen ausprobieren, sehen Sie, dass je größer die Liste ist, desto schlechter ist die Leistung von index () im Vergleich:

from timeit import timeit
from random import shuffle

for n in range(0, 50, 5):
    l1 = list(range(n))
    l2 = l1[:]
    shuffle(l2)

    t1 = timeit('indices = {val: i for i, val in enumerate(l1)}; [indices[x] for x in l2]', 'from __main__ import l1, l2')
    t2 = timeit('[l1.index(x) for x in l2]', 'from __main__ import l1, l2')
    print("n = %s, t1 = %s, t2 = %s, t2/t1 = %s" % (n, t1, t2, t2/t1))

Ergebnis:

n = 0, t1 = 0.410041093826, t2 = 0.0470049381256, t2/t1 = 0.114634700847
n = 5, t1 = 1.01210093498, t2 = 0.980098009109, t2/t1 = 0.96837970921
n = 10, t1 = 1.70017004013, t2 = 2.06220698357, t2/t1 = 1.21294160872
n = 15, t1 = 2.12121200562, t2 = 3.28132796288, t2/t1 = 1.54691183823
n = 20, t1 = 2.64426398277, t2 = 4.81948184967, t2/t1 = 1.82261751515
n = 25, t1 = 3.42534303665, t2 = 6.57365703583, t2/t1 = 1.9191237098
n = 30, t1 = 3.95739603043, t2 = 8.52685213089, t2/t1 = 2.15466232475
n = 35, t1 = 4.24842405319, t2 = 10.8080809116, t2/t1 = 2.54402121265
n = 40, t1 = 4.75647592545, t2 = 13.3403339386, t2/t1 = 2.80466760427
n = 45, t1 = 5.33353281021, t2 = 15.6205620766, t2/t1 = 2.92874584865
0
jbch 18 Apr. 2018 im 17:43

Verwenden Sie list.index() innerhalb eines Listenverständnisses:

l1 = ['a','b','c','d']
l2 = ['c','d','b','a']

[l1.index(x) for x in l2] #[2, 3, 1, 0]

Wenn Sie dies in einem DataFrame versuchen, können Sie wie in: np.array nach list und zurück konvertieren.

import numpy as np
import pandas as pd

df = pd.DataFrame({'v1':np.array(l1), 'v2':np.array(l2)})

df['index_of_v2_in_v1'] = np.array([list(df['v1']).index(x) for x in list(df['v2'])])

df
# Result:
#   v1 v2  index_of_v2_in_v1
# 0  a  c                  2
# 1  b  d                  3
# 2  c  b                  1
# 3  d  a                  0

Wenn Sie 100% sicher sind , dass Liste 1 bereits sortiert ist (wie aus Ihrer Frage hervorgeht), können Sie einfach np.argsort(l2) für die Liste oder das Array verwenden, wie in:

np.argsort(df['v2'])
# Returns:
#0    3
#1    2
#2    0
#3    1
#Name: v2, dtype: int64
1
C8H10N4O2 18 Apr. 2018 im 16:52

Die Verwendung von map ist in diesem Beispiel etwa 3,6-mal schneller als das Listenverständnis:

from timeit import timeit

l1 = ['a','b','c','d']
l2 = ['c','d','b','a']

t1 = timeit('map(lambda e: l1.index(e), l2)', globals=globals())
t2 = timeit('[l1.index(x) for x in l2]', globals=globals())
print("t1 = %s, t2 = %s, t2/t1 = %s" % (t1, t2, t2/t1))

Ergebnis:

t1 = 0.32407195774213654, t2 = 1.162188749526786, t2/t1 = 3.586205846454439

EDIT: Zusätzlicher Vergleich einschließlich der von @jbch vorgeschlagenen Lösung:

from timeit import timeit
from random import shuffle

for n in range(10, 70, 10):
    l1 = list(range(n))
    l2 = l1[:]
    shuffle(l2)

    t1 = timeit('indices = {val: i for i, val in enumerate(l1)}; [indices[x] for x in l2]', globals=globals())
    t2 = timeit('[l1.index(x) for x in l2]', globals=globals())
    t3 = timeit('map(lambda e: l1.index(e), l2)', globals=globals())
    print("n = %d, t1 = %g, t2 = %g, t3 = %g" % (n, t1, t2, t3))

Ergebnis:

n = 10, t1 = 3.25064, t2 = 3.70473, t3 = 0.339757
n = 20, t1 = 5.01145, t2 = 9.22295, t3 = 0.341116
n = 30, t1 = 7.18546, t2 = 16.6379, t3 = 0.344537
n = 40, t1 = 8.96271, t2 = 26.0522, t3 = 0.336952
n = 50, t1 = 11.0635, t2 = 37.7291, t3 = 0.341935
n = 60, t1 = 12.6453, t2 = 51.1519, t3 = 0.350777
1
sciroccorics 18 Apr. 2018 im 19:58