Ordina una lista mentre metti insieme o dopo?

Question

Ordina una lista mentre metti insieme o dopo?

#1 da (5 voti)
#2 da (-1 voti)

5

Devo leggere una quantità enorme di dati di rete da vari file di registro e compilare informazioni rilevanti su tali dati per eseguire analisi statistiche su di esso (i principali comunicatori, gli indirizzi IP principali che inviano in media i pacchetti più grandi, media dimensione del pacchetto, ecc.) Ho deciso di creare una matrice in cui ogni indice nell'array esterno corrisponde a un elenco ordinato di IP in ordine incrementale.

Per avere un'idea del mio set di dati, ho un file di log che viene generato ogni giorno che contiene informazioni su tutte le comunicazioni avvenute all'interno di una rete quel giorno. Ho generato file di registro da metà maggio e ogni file di registro ha circa 5 milioni di righe ciascuno, quindi più efficiente è questo programma, meglio è.

La mia domanda è la seguente:

Quando sto compilando i dati di tutti i file di log in questa matrice, dovrei ordinare il mio array array esterno per IP mentre sto ancora assemblando i dati, o semplicemente aggiungo i nuovi IP alla fine del file come li trovo e poi ordinare l'elenco in seguito? C'è un'opzione migliore qui a cui non ho pensato? quale via sarebbe la più efficiente? Userò python 2.7, se questo fa la differenza. Inoltre, a causa delle restrizioni su ciò che posso fare, non posso installare alcun nuovo modulo sulla macchina su cui verrà eseguito questo codice, quindi a meno che non possa creare un database con python in modo nativo, non è disponibile opzione per me.

python data-structures efficiency sorting

posta Ben Schwabe 13.11.2015 - 22:56

fonte

2 risposte

-1

L'inserimento di tutto non richiede confronti, l'ordinamento successivo è in O (n * log (n)), quindi l'inserimento e l'ordinamento sono in O (n * log (n))

Inserendo un elemento in un elenco ordinato in modo da mantenere un elenco ordinato è logaritmico nella dimensione dell'elenco, quindi l'inserimento di n elementi in tale elenco è in O (n * log (n)) poiché la dimensione dell'elenco cresce man mano che continui a inserire elementi.

Ha quindi una complessità simile in termini di confronti, ma l'inserimento di un elemento in python è molto più costoso che accodare (lineare con la dimensione della lista invece che costante). Il più efficiente è quindi aggiungere tutto e quindi ordinare.

Ecco un codice di esempio per verificare le prestazioni dell'elaborazione di 10000 numeri casuali:

import random
import timeit
import bisect


def append_then_sort(data):
    result = []

    for element in data:
        result.append(element)

    result.sort()
    return result


def insert_sorted(data):
    result = []

    for element in data:
        bisect.insort_left(result, element)

    return result

if __name__ == '__main__':
    numbers = [random.randint(0, 3000000) for _ in xrange(10000)]
    print('Append then sort:')
    print(timeit.timeit('append_then_sort(numbers)', setup='from __main__ import append_then_sort, numbers', number=10))
    print('Insert sorted:')
    print(timeit.timeit('insert_sorted(numbers)', setup='from __main__ import insert_sorted, numbers', number=10))

E i risultati sulla mia macchina:

Append then sort:
0.0509831905365
Insert sorted:
0.27309513092

Potresti anche essere interessato a esaminare il modulo sqlite3 che fa parte della libreria python standard quindi dovrebbe essere disponibile sul tuo sistema. Non sono sicuro di quanto bene sqlite gestisca database di grandi dimensioni comunque ...

risposta data 14.11.2015 - 14:28

fonte

Leggi altre domande sui tag python data-structures efficiency sorting

Come evitare le regole aziendali nel repository? Perché dovresti documentare un tipo di reso usando lo scaladoc?

score 5 · Accepted Answer

L'ordinamento di inserzione funziona meglio quando si inserisce un nuovo valore in qualcosa che è già stato ordinato. Quindi quello che vorrei fare è usare Quicksort per ordinare il set di dati originale che hai, quindi quando arrivano voci di registro aggiuntive, aggiungili uno alla volta nel set già ordinato.

Poiché Quicksort è O (n * logn) e Insertion Sort essendo O (n) se usato con un set già ordinato, il tempo totale per tutto sarà O (a * log (a) + b), dove a è la dimensione del set di dati originale e b sono i registri aggiuntivi che inserisci in seguito.