Supposons que j'ai deux listes:

a = ['30', '10', '90', '1111', '17']
b = ['60', '1201', '30', '17', '900']

Comment classeriez-vous cela le plus efficacement possible, de telle sorte que:

La liste b est triée par rapport à a. Les éléments uniques de b doivent être placés à la fin de la liste triée. Les éléments uniques de a peuvent être ignorés.

Exemple de sortie:

c = ['30', '17', '60', '1201', '900']

Désolé, c'est une question simple. Ma tentative est bloquée au point de prendre l'intersection.

intersection = sorted(set(a) & set(b), key = a.index)
5
William 13 févr. 2020 à 18:27

5 réponses

Meilleure réponse

Il n'est pas nécessaire de trier ici. Vous voulez que les éléments dans a qui sont dans b, dans le même ordre qu'ils étaient dans a; suivi des éléments de b qui ne sont pas de a, dans le même ordre qu'ils l'étaient de b.

Nous pouvons simplement le faire avec deux filtres, en utilisant les ensembles pour des tests d'appartenance rapides:

>>> a = ['30', '10', '90', '1111', '17']
>>> b = ['60', '1201', '30', '17', '900']
>>> a_set = set(a)
>>> b_set = set(b)
>>> [*filter(lambda x: x in b_set, a), *filter(lambda x: x not in a_set, b)]
['30', '17', '60', '1201', '900']

Ou si vous préférez les compréhensions:

>>> [*(x for x in a if x in b_set), *(x for x in b if x not in a_set)]
['30', '17', '60', '1201', '900']

Les deux prennent du temps linéaire, ce qui est mieux que le tri.

6
kaya3 14 févr. 2020 à 15:04

Comme vous avez indiqué l'utilisation de set, il me semble que les deux listes contiennent des éléments non dupliqués. Ensuite, vous pouvez simplement faire la compréhension de la liste:

c = [x for x in a if x in b] + [x for x in b if x not in a]

Il s'agit cependant de O (n ^ 2). Si votre liste est volumineuse et que vous souhaitez la rendre plus rapide, essayez de créer un ensemble de a et b respectivement et utilisez-les pour vérifier l'adhésion.

2
adrtam 13 févr. 2020 à 15:33

Votre titre est en fait plus clair que votre description et peut être traduit assez directement en code:

Trier une liste par présence d'éléments dans une autre liste

Code:

>>> sorted(b, key=set(a).__contains__, reverse=True)
['30', '17', '60', '1201', '900']

Ou

>>> sorted(b, key=lambda x, s=set(a): x not in s)
['30', '17', '60', '1201', '900']

Le tri des booléens est pratiquement impossible à distinguer du temps linéaire, et ces solutions sont plus rapides que la solution acceptée à la fois sur vos données d'exemple ainsi que sur les données d'exemple que j'ai essayées avec des millions de nombres aléatoires (où environ la moitié des éléments de b étaient dans a).


Repères

   n    b in a   kaya1    kaya2    heap1    heap2    heap3
----------------------------------------------------------
   1024 53.12%  0.00046  0.00033  0.00020  0.00067  0.00018
   2048 51.03%  0.00142  0.00069  0.00048  0.00071  0.00060
   4096 50.34%  0.00226  0.00232  0.00127  0.00183  0.00125
   8192 50.42%  0.00938  0.00843  0.00328  0.00471  0.00351
  16384 50.38%  0.02010  0.01647  0.00776  0.00992  0.00839
  32768 49.96%  0.03987  0.03165  0.01661  0.02326  0.01951
  65536 50.20%  0.08002  0.06548  0.03326  0.04828  0.03896
 131072 50.04%  0.16118  0.12863  0.06671  0.09642  0.07840
 262144 50.06%  0.32698  0.26757  0.13477  0.19342  0.15828
 524288 50.08%  0.66735  0.54627  0.27378  0.38365  0.32496
1048576 50.00%  1.34095  1.08972  0.54703  0.78028  0.65623
2097152 50.03%  2.68957  2.20556  1.13797  1.60649  1.33975
4194304 50.01%  5.36141  4.33496  2.25494  3.18520  2.70506
8388608 49.99% 10.72588  8.74114  4.56061  6.35421  5.36515

Remarque:

  • n est la taille de b.
  • a est préparé en tant que set avant de comparer les fonctions, afin de se concentrer sur leurs différences. La taille de a est toujours 8388608 afin de garder les in a vérifications à temps constant (même les set ralentissent lorsqu'ils deviennent plus gros).
  • b in a est le pourcentage d'éléments de b dans a. Je les ai faites pour que ce soit environ 50%.
  • kaya1 et kaya2 sont issus de la réponse acceptée par @ kaya3, modifiés de manière à faire ce que je pense être la tâche (trier b par présence d'éléments dans a, pas "a & b" suivi de "b \ a").
  • heap1 et heap2 sont mes deux solutions ci-dessus utilisant sorted.
  • heap3 est la solution la plus rapide sans sorted que j'ai pu écrire.
  • Les résultats sont des temps en secondes.

Code de référence:

from timeit import repeat
import random

def kaya1(a_set, b):
    return [*filter(lambda x: x in a_set, b), *filter(lambda x: x not in a_set, b)]

def kaya2(a_set, b):
    return [*(x for x in b if x in a_set), *(x for x in b if x not in a_set)]

def heap1(a_set, b):
    return sorted(b, key=a_set.__contains__, reverse=True)

def heap2(a_set, b):
    return sorted(b, key=lambda x: x not in a_set)

def heap3(a_set, b):
    not_in_a = []
    append = not_in_a.append
    in_a = [x for x in b if x in a_set or append(x)]
    in_a.extend(not_in_a)
    return in_a

print('   n    b in a   kaya1    kaya2    heap1    heap2    heap3')
print('----------------------------------------------------------')

A = random.sample(range(2**24), 2**23)
B = random.sample(range(2**24), 2**23)
a_set = set(A)

for e in range(10, 24):
    n = 2**e
    b = B[:n]
    print('%7d %5.2f%%' % (n, 100 * len(set(b) & a_set) / len(b)), end='')
    expect = None
    for sort in kaya1, kaya2, heap1, heap2, heap3:
        t = min(repeat(lambda: sort(a_set, b), number=1))
        print('%9.5f' % t, end='')
        output = sort(a_set, b)
        if expect is None:
            expect = output
        else:
            assert output == expect
    print()
2
Heap Overflow 24 févr. 2020 à 23:04

Peut-être que cela devrait fonctionner.

intersection = sorted(set(a) & set(b), key=a.index)
intersection.extend([ele for ele in b if ele not in intersection])
0
Mo7art 13 févr. 2020 à 15:36

Vous pouvez créer un dictionnaire personnalisé, les clés étant les entrées de a et les valeurs leur position. Triez ensuite b selon les valeurs du dictionnaire. Vous pouvez utiliser dict.get pour la recherche et inf si la valeur n'est pas présente:

a = ['30', '10', '90', '1111', '17']
b = ['60', '1201', '30', '17', '900']

d = {i:ix for ix, i in enumerate(a)}
#{'30': 0, '10': 1, '90': 2, '1111': 3, '17': 4}
sorted(b, key=lambda x: d.get(x, float('inf')))
#['30', '17', '60', '1201', '900']
6
yatu 13 févr. 2020 à 15:30