Elabora ogni riga una contro l'altra, quanto costerebbe?

È O (n ² ) per definizione.

La distinzione tra n ² e l'algoritmo n * (n-1) / 2 non ha importanza.

Devi elaborare un algoritmo molto migliore per localizzare i "duplicati". Questo business di "controllo di similarità" è probabilmente il tipo di cosa che richiede un algoritmo molto più intelligente di una query SQL.

Devi leggere su hashing sfocato e metafone e relative tecniche. Devi definire chiaramente "simile" e trovare un modo per rilevare simili. L'esecuzione di miliardi di operazioni di database richiederà giorni di esecuzione.

Una buona regola empirica è che il tuo RDBMS può recuperare circa 5000 righe al secondo.

Sono 180.000 secondi (50 ore) per eseguire una di queste query O (n ² ).

Alcuni attributi (diciamo una dozzina) da 30.000 righe sono 360.000 oggetti. Che si adatta alla memoria in qualsiasi computer più grande di iPhone.

Ecco il tuo algoritmo.

1. Leggi tutte le 30.000 righe in memoria.

2. Calcolare hash o riepiloghi o whatevers per la tua dozzina di campi, creare hashmaps o treemaps o qualsiasi altra cosa abbia senso.

   for x in object_list:
       name_map[soundex(x.name)].append(x)
       other_map[transformatioN(x.other)].append(x)
   

3. Scrivi rapporti di riepilogo statistico per assicurarti che le tue misurazioni di somiglianza facciano una specie di razionale senso.

   print( len(name_map), "similar names out of", len(object_list) )
   

4. Quando hai i risultati che ti piacciono, aggiorna il database con i risultati.

   for n in name_map:
       similar_set = [ s.primary_key for s in name_map[n] ]
       c.execute( "UPDATE SOMETHING SET NAME_KEY=n WHERE ID IN ( %0 )", similar_set )
   

Questo non è adatto per SQL. Ma è adatto per "all-in memory".

Penso che sia ((n*(n-1))/2)

Il tuo loop di codice è corretto, è (n * n-1) perché non devi confrontare ogni riga a se stesso e diviso per 2 perché la riga X rispetto alla riga Y è uguale alla riga Y rispetto alla riga X

Guardando quanto segue dovrebbe essere chiaro (se lo vedi come tabella con n righe e n colonne):

 123
1-xx
2 -x
3  -

3*2/2 = 3

 1234
1-xxx
2 -xx
3  -x
4   -

4*3/2 = 6

Dal modo in cui penso che sia ancora in O(n^2) perché O ((n*(n-1))/2) = O((n*(n-1))) = O((n*n)) = O(n^2) MA potrei sbagliarmi! Qualcuno che mi corregga?

A seconda dei parametri effettivi del problema, questo potrebbe non essere effettivamente O (n ^ 2). Se è possibile scrivere una query in modo che il database possa utilizzare gli indici, potrebbe non essere necessario confrontare effettivamente ogni riga. In questo caso potresti guardare una soluzione O (n * Log (n)).

Simile alla risposta fornita da WuHoUnited , puoi ridurre in modo significativo il numero di confronti necessari creando cluster o codici di corrispondenza. Fondamentalmente si crea un campo cluster che contiene alcune caratteristiche salienti del record e confronta solo i record in cui il campo del cluster corrisponde. Ad esempio, è possibile creare un campo cluster che contenga i primi 5 caratteri del nome dell'azienda. Ora devi solo abbinare i record che rientrano in quel cluster. A seconda dei dati e dell'accuratezza richiesta, è possibile aggiungere altri dati, come il codice postale o il numero di telefono parziale al cluster.