J'ai une liste où chaque élément est une combinaison de deux identifiants d'événement: (Ceci est juste un extrait de la liste beaucoup plus grande de paires)
['10000381 10007121', '10000381 10008989', '10005169 10008989', «10008989 10023817», «10005169 10043265», «10008989 10043265», «10023817 10043265», «10047097 10047137», «10047097 10047265», «10047137 10047265», «10000381 10056453», «10047265 10056453», «10000381 10060557», «10007121 10060557», «10056453 10060557», «10000381 10066013», «10007121 10066013», «10008989 10066013», «10026233 10066013», «10056453 10066013», «10056453 10070153», «10060557 10070153», «10066013 10070153», «10000381 10083798», «10047265 10083798», «10056453 10083798», «10066013 10083798», «10000381 10099969», «10056453 10099969», «10066013 10099969», «10070153 10099969», «10083798 10099969», «10056453 10167029», «10066013 10167029», «10083798 10167029», «10099969 10167029», «10182073 10182085», «10182073 10182177», «10182085 10182177», «10000381 10187233», «10056453 10187233», «10060557 10187233», «10066013 10187233», «10083798 10187233», «10099969 10187233», «10167029 10187233», «10007121 10200685», «10099969 10200685», "10066013 10218005", "10223905 10224013"]
Je dois trouver chaque instance de chaque paire d'identifiants et l'indexer dans une nouvelle liste. En ce moment, j'ai quelques lignes de code qui font cela pour moi. Cependant, ma liste compte plus de 2 000 000 lignes et s'agrandira à mesure que je traiterai plus de données.
Pour le moment, le délai d'exécution estimé est d'environ 2 jours.
J'ai vraiment besoin d'une méthode beaucoup plus rapide pour cela.
Je travaille dans Jupyter Notebooks (sur un ordinateur portable Mac)
def compiler(idlist):
groups = []
for k,i in enumerate(idlist):
position = []
for c,j in enumerate(idlist):
if i == j:
position.append(c)
groups.append(position)
return(groups)
J'ai aussi essayé:
def compiler(idlist):
groups = []
for i in idlist:
groups.append([index for index, x in enumerate(idlist) if x == i])
return(groups)
3 Réponses :
Au lieu d'une liste, utilisez un dict, ce qui permet de rechercher l'existence O(1):
def compiler(idlist):
groups = {}
for idx, val in enumerate(idlist):
if val in groups:
groups[val].append(idx)
else:
groups[val] = [idx]
Remplacez groupes par un defaultdict (liste) et voyez comment cela simplifie votre code (le corps de la boucle for se réduira à une seule instruction). Mais vous devez toujours créer la liste des listes demandées par l'OP.
Vous pouvez utiliser un collections.OrderedDict code > afin de réduire la complexité temporelle à O (n). Puisqu'il se souvient de l'ordre d'insertion, les valeurs ressemblent aux différents identifiants dans l'ordre de leur occurrence:
from collections import OrderedDict
groups = OrderedDict()
for i, v in enumerate(idlist):
try:
groups[v].append(i)
except KeyError:
groups[v] = [i]
Ensuite, list (groups.values ()) contient votre résultat final .
Plutôt que d'attraper KeyError , vous pouvez simplement utiliser setdefault : groups.setdefault (v, []). Append (i) .
@DanielPryden try / except est plus rapide (par exemple pour idlist = np.random.randint (10_000, size = 2_000_000) il atteint 717 ms ± 14,2 ms contre 997 ms ± 29,3 ms pour setdefault ).
Si vous avez beaucoup de données, je vous suggère d'utiliser Voici une implémentation d'un benchmark basé sur le temps utilisant Pypy3: Pypy3 avec 2000000 itérations: Pypy3 au lieu de l'interpréteur CPython et vous obtiendrez x5-x7 code > exécution de code plus rapide. CPython et Pypy3 avec 1000 itérations : func: op_implementation [200000 iterations] took: 4.6364 sec
func: ordreddict_implementation [200000 iterations] took: 0.3201 sec
func: defaultdict_implementation [200000 iterations] took: 2.2032 sec
func: defaultdict_implementation_2 [200000 iterations] took: 2.4052 sec
func: dict_implementation [200000 iterations] took: 2.2429 sec
func: op_implementation [10000 iterations] took: 0.2370 sec
func: ordreddict_implementation [10000 iterations] took: 0.0243 sec
func: defaultdict_implementation [10000 iterations] took: 0.1216 sec
func: defaultdict_implementation_2 [10000 iterations] took: 0.1299 sec
func: dict_implementation [10000 iterations] took: 0.1175 sec
func: op_implementation [10000 iterations] took: 1.3096 sec
func: ordreddict_implementation [10000 iterations] took: 0.1866 sec
func: defaultdict_implementation [10000 iterations] took: 0.3311 sec
func: defaultdict_implementation_2 [10000 iterations] took: 0.3817 sec
func: dict_implementation [10000 iterations] took: 0.3231 sec
from time import time
from collections import OrderedDict, defaultdict
def timeit(func, iteration=10000):
def wraps(*args, **kwargs):
start = time()
for _ in range(iteration):
result = func(*args, **kwargs)
end = time()
print("func: {name} [{iteration} iterations] took: {elapsed:2.4f} sec".format(
name=func.__name__,
iteration=iteration,
args=args,
kwargs=kwargs,
elapsed=(end - start)
))
return result
return wraps
@timeit
def op_implementation(data):
groups = []
for k in data:
groups.append([index for index, x in enumerate(data) if x == k])
return groups
@timeit
def ordreddict_implementation(data):
groups = OrderedDict()
for k, v in enumerate(data):
groups.setdefault(v, []).append(k)
return groups
@timeit
def defaultdict_implementation(data):
groups = defaultdict(list)
for k, v in enumerate([x for elm in data for x in elm.split()]):
groups[v].append(k)
return groups
@timeit
def defaultdict_implementation_2(data):
groups = defaultdict(list)
for k, v in enumerate(map(lambda x: tuple(x.split()), data)):
groups[v].append(k)
return groups
@timeit
def dict_implementation(data):
groups = {}
for k, v in enumerate([x for elm in data for x in elm.split()]):
if v in groups:
groups[v].append(k)
else:
groups[v] = [k]
return groups
if __name__ == '__main__':
data = [
'10000381 10007121', '10000381 10008989', '10005169 10008989', '10008989 10023817',
'10005169 10043265', '10008989 10043265', '10023817 10043265', '10047097 10047137',
'10047097 10047265', '10047137 10047265', '10000381 10056453', '10047265 10056453',
'10000381 10060557', '10007121 10060557', '10056453 10060557', '10000381 10066013',
'10007121 10066013', '10008989 10066013', '10026233 10066013', '10056453 10066013',
'10056453 10070153', '10060557 10070153', '10066013 10070153', '10000381 10083798',
'10047265 10083798', '10056453 10083798', '10066013 10083798', '10000381 10099969',
'10056453 10099969', '10066013 10099969', '10070153 10099969', '10083798 10099969',
'10056453 10167029', '10066013 10167029', '10083798 10167029', '10099969 10167029',
'10182073 10182085', '10182073 10182177', '10182085 10182177', '10000381 10187233',
'10056453 10187233', '10060557 10187233', '10066013 10187233', '10083798 10187233',
'10099969 10187233', '10167029 10187233', '10007121 10200685', '10099969 10200685',
'10066013 10218005', '10223905 10224013'
]
op_implementation(data)
ordreddict_implementation(data)
defaultdict_implementation(data)
defaultdict_implementation_2(data)
dict_implementation(data)
Vous pouvez d'abord les diviser, puis les convertir en tableau NumPy, puis utiliser
uniquecomme indiqué icivous avez besoin d'une structure de données différente pour cela, il y a environ quelques millions de lignes. Consultez les dictionnaires si vous êtes autorisé à apporter des modifications.
En ce moment, vous parcourez la liste pour chaque élément, c'est-à-dire que vous avez des performances
O (n ^ 2)Vous pouvez utilisergroups = collections.defaultdict (list)et ensuite fairepour index, élément dans enumerate (idlist): groupes [élément] .append (index)qui estO (n).Copie possible de Comment trouver index des éléments correspondants dans deux listes
Pourriez-vous mettre à jour votre question pour afficher des exemples de données et une sortie "ce que je veux" qui correspondent? Recherchez-vous également des identifiants en double («10000381» et «10007121») ou des paires d'identifiants en double («10000381 10007121»)?
@PaulMcG D'après l'exemple de code, il est assez évident que les éléments individuels ne doivent pas être divisés mais plutôt être comparés tels quels.