Assegnare ID univoco alla lista delle liste in Python in cui i duplicati ottenere lo stesso id

Question

Ho una lista di liste (che può contenere fino a 90k elementi)

[[1,2,3], [1,2,4], [1,2,3], [1,2,4], [1,2,5]] 

vorrei assegnare un ID a ciascun elementi , dove l'ID è unico, tranne quando l'elemento è duplicato. Così, per la lista di cui sopra, avrei bisogno di questo ritorno:

[0,1,0,1,2] 

Qual è il modo più efficace per fare questo?

Answer 1

Mantieni una mappa di elementi già visti con l'ID associato.

from itertools import count 
from collections import defaultdict 


mapping = defaultdict(count().__next__) 
result = [] 
for element in my_list: 
    result.append(mapping[tuple(element)]) 

si potrebbe anche usare un elenco-di comprensione:

result = [mapping[tuple(element)] for element in my_list] 

Purtroppo list s non sono hashable modo da avere per convertirli in un tuple quando la loro memorizzazione come chiavi della mappatura.

---

nota il trucco di usare defaultdict, e count().__next__ per fornire gli ID unici crescenti. Su python2 devi sostituire .__next__ con .next.

Il defaultdict assegnerà un valore predefinito quando non riesce a trovare una chiave. Il valore predefinito si ottiene chiamando la funzione fornita nel costruttore. In questo caso il metodo __next__ del generatore count() produce numeri crescenti.

Come alternativa portatile più si potrebbe fare:

from functools import partial 

mapping = defaultdict(partial(next, count())) 

---

Una soluzione alternativa, come proposto nei commenti, è usare solo l'indice come ID univoco:

result = [my_list.index(el) for el in my_list] 

Ciò tuttavia è necessario:

• It tak es O (N^2) volta invece di O (N)
• Gli ID sono unici, aumentando ma non consecutivi (che può o non può essere un problema)

Per confronto delle due soluzioni si veda:

In [1]: from itertools import count 
    ...: from collections import defaultdict 

In [2]: def hashing(seq): 
    ...:   mapping = defaultdict(count().__next__) 
    ...:   return [mapping[tuple(el)] for el in seq] 
    ...: 

In [3]: def indexing(seq): 
    ...: return [seq.index(i) for i in seq] 
    ...: 

In [4]: from random import randint 

In [5]: seq = [[randint(1, 20), randint(1, 20), randint(1, 20)] for _ in range(90000)] 

In [6]: %timeit hashing(seq) 
10 loops, best of 3: 37.7 ms per loop 

In [7]: %timeit indexing(seq) 
1 loop, best of 3: 26 s per loop 

nota come una lista degli elementi 90K la soluzione di mappatura richiede meno di 40 millisecondi mentre la soluzione di indicizzazione richiede 26 secondi .

Answer 2

questo è come mi avvicinai:

from itertools import product 
from random import randint 
import time 

t0 = time.time() 
def id_list(lst): 
    unique_set = set(tuple(x) for x in lst) 
    unique = [list(x) for x in unique_set] 
    unique.sort(key = lambda x: lst.index(x)) 

    result = [unique.index(i[1]) for i in product(lst, unique) if i[0] == i[1]] 

    return result 

seq = [[randint(1, 5), randint(1, 5), randint(1, 5)] for i in range(90000)] 

print(id_list(seq)) 

t1 = time.time() 

print("Time: %.4f seconds" % (t1-t0)) 

che stampa la sequenza di ID, insieme a un tempo approssimativo impiegato per calcolare una sequenza di numeri interi casuali in una lista tra e , volte.

Time: 2.3397 seconds # Will slightly differ from computation to computation 

Il tempo effettivo sarà sempre un po 'più alto, dal momento che deve essere contabilizzata nel conto di stampa alla fine, ma non dovrebbe essere troppo di una differenza.

Ho anche utilizzato la libreria time per etichettare gli intervalli di tempo tra l'inizio e la fine del blocco di codice.

import time 

t0 = time.time() 

# code block here 

t1 = time.time() 

# Difference in time: t1 - t0 

La biblioteca itertools con product utilizzato nel segmento di codice si accelera il calcolo troppo.

Answer 3

ho leggera modifica della soluzione di Bakuriu che funziona solo con gli array NumPy, funziona meglio in termini di occupazione di memoria e di calcolo (in quanto ha bisogno di gettare le matrici di tuple):

from itertools import count 
from collections import defaultdict 
from functools import partial 

def hashing_v1(seq): 
    mapping = defaultdict(partial(next, count())) 
    return [mapping[tuple(el)] for el in seq] 

def hashing_v2(seq): 
    mapping = defaultdict(partial(next, count())) 
    result = [] 
    for le in seq: 
     le.flags.writeable = False 
     result.append(mapping[le.data]) 
    return result 

In [4]: seq = np.random.rand(50000, 2000) 

In [5]: %timeit hashing_v1(seq) 
1 loop, best of 3: 14.1 s per loop 

In [6]: %timeit hashing_v2(seq) 
1 loop, best of 3: 1.2 s per loop