Paralléliser une consolidation de liste en Python

Question

J'ai une liste triée de "définitions de boîtes" que j'aimerais consolider. La liste ressemble à:

big_list = [\ 
# ... 
# ... 
[3, 4, 5, 4, 5, 6, 65],\ 
[3, 4, 5, 4, 5, 6, 60],\ 
[3, 4, 5, 4, 5, 6, 55],\ 
[3, 4, 5, 4, 5, 6, 52],\ 
[3, 4, 5, 4, 5, 6, 23],\ 
[3, 4, 5, 4, 5, 6, 17],\ 
[3, 4, 5, 4, 5, 6, 0],\ 
[5, 8, 9, 6, 9, 10, 90],\ 
[5, 8, 9, 6, 9, 10, 84],\ 
[5, 8, 9, 6, 9, 10, 32],\ 
[5, 8, 9, 6, 9, 10, 0],\ 
# ... 
# ... 
[750, 800, 900, 751, 801, 901, 97],\ 
[750, 800, 900, 751, 801, 901, 24],\ 
[750, 800, 900, 751, 801, 901, 17],\ 
[750, 800, 900, 751, 801, 901, 16],\ 
[750, 800, 900, 751, 801, 901, 0]\ 
# ... 
# ... 
] 

Lorsque la case "format" est le suivant: [x1, y1, z1, x2, y2, z2, attribut], et on peut supposer dx = 1, dy = 1, dz = 1

en outre, on peut supposer la liste a déjà été triés par quelque chose comme:

big_list=sorted(big_list, key=lambda n:n[6], reverse=True) 
big_list=sorted(big_list, key=lambda n:n[2]) 
big_list=sorted(big_list, key=lambda n:n[1]) 
big_list=sorted(big_list, key=lambda n:n[0]) 

la liste peut être plusieurs millions d'articles longs, et je voudrais réduire la liste de sorte que toute discrète "box" obtient seulement le plus haut "attribut" ... donc quelque chose dans ce cas comme:

reduced_big_list = [\ 
[3, 4, 5, 4, 5, 6, 65],\ 
[5, 8, 9, 6, 9, 10, 90],\ 
[750, 800, 900, 751, 801, 901, 97]\ 
] 

La méthode que je me sers actuellement sur cette liste est quelque chose comme:

i = 0 

while i < len(big_list)-1: 
    if big_list[i][0]==big_list[i+1][0]\ 
    and big_list[i][1]==big_list[i+1][1]\ 
    and big_list[i][2]==big_list[i+1][2] \ 
    and big_list[i][6] >= big_list[i+1][6]: 
      del big_list[i+1] 
    else: 
      i=i+1 

Le problème est que lorsque la liste est « long » (10 millions + « boîtes »), le processus est très, très lent.

Existe-t-il une manière intelligente de paralléliser ce processus de "décimation" de liste ou peut-être d'accélérer ce processus?

Answer 1

La lenteur est l'appel à del, qui déplace les éléments du terminer queue de la liste par une étape. Dans votre cas, n'utilisez simplement pas del. Faites à la place une nouvelle liste, à partir d'une liste vide et append ing les éléments que vous souhaitez conserver.

Answer 2

La raison est lente est que chaque fois que vous del une ligne prend une quantité de temps linéaire, rendant le processus total O (n^2).

Si au lieu de supprimer des lignes de la liste d'origine, vous ajoutez les lignes que vous souhaitez conserver dans une nouvelle liste, cela devrait être beaucoup plus rapide.

Mais il existe d'autres façons, peut-être plus Pythonic, d'effectuer la même chose. Par exemple, en utilisant itertools.groupby (en supposant que la liste est triée que vous avez spécifié):

from itertools import groupby 
new_list = [next(group) for val,group in groupby(big_list, key=lambda x: x[:3])] 

Ce regrouperons les éléments de liste par les 3 premiers éléments, et retourner une liste du premier élément dans chaque groupe.

Answer 3

Le booléen and évalue d'abord l'expression de gauche. Il évalue uniquement l'expression de la main droite si la première est vraie. Depuis que vous avez trié votre liste, les éléments adjacents sont peut-être plus susceptibles d'avoir des 0e éléments identiques que des éléments ultérieurs. Essayez

i = 0 

while i < len(big_list)-1: 
    if big_list[i][2]==big_list[i+1][2]\ 
    and big_list[i][1]==big_list[i+1][1]\ 
    and big_list[i][0]==big_list[i+1][0]\ 
    and big_list[i][6] >= big_list[i+1][6]: 
     del big_list[i+1] 
    else: 
     i=i+1