Test di Liste Veloci


di leonardo maffi, data 16 Febbraio 2003.

Test del mio primo package per la gestione delle liste veloci.
Tratto da http://www.verbeia.com/mathematica/tips/HTMLLinks/Tricks_215.html
Scarica il package: listeVeloci.m
(Nota: il package va collocato dove il Mathematica può trovarlo, oppure gli va dato un percorso giusto quando lo si carica).

Parti essenziali del package:

Clear[h999000]

creaLV = h999000[];

prependLV[l_, x_] := h999000[x, l];

appendLV[l_, x_] := h999000[l, x];

convertiLV[l_] := Flatten[l] /.

h999000 -> List;

__________________________________

Scarica questo notebook: TestListeVeloci.nb

    <<listeVeloci.m

Aggiunta in coda della sottolista: {i, i} utilizzando la Append che ha complessità O(n) o la appendLV che ha complessità costante, seguita dal confronto tra i due tempi.

     Timing[lk1 = {}; Do[lk1 = Append[lk1, {i, i}], {i, 7000}];]
    {13.139 Second, Null}
    Timing[lk2 = creaLV; Do[lk2 = appendLV[lk2, {i, i}], {i, 7000}]; lk2 = convertiLV[lk2];]
    {0.180 Second, Null}
    lk2 == lk1
    True

Aggiunta in testa della sottolista: {i, i} utilizzando la Prepend che ha complessità O(n) o la prependLV che ha complessità costante, seguita dal confronto tra i due tempi.

    Timing[lk1 = {}; Do[lk1 = Prepend[lk1, {i, i}], {i, 7000}];]
    {13.099 Second, Null}
    Timing[lk2 = creaLV; Do[lk2 = prependLV[lk2, {i, i}], {i, 7000}] ; lk2 = convertiLV[lk2];]
    {0.190 Second, Null}
    lk2 == lk1
    True

Confronto tra i tempi usando le liste veloci e usando normali liste "nidificate". Questo metodo mostra che le liste veloci sono due volte più lente, ma la Flatten non può essere usata se ci sono sotto-liste all'interno.

    Timing[lk3 = creaLV; Do[lk3 = appendLV[lk3, i], {i, 400000}]; lk3 = convertiLV[lk3];]
    {8.903 Second, Null}
    Timing[lk4 = {}; Do[lk4 = {lk4, i}, {i, 400000}] ; lk4 = Flatten[lk4];]
    {4.046 Second, Null}
    lk3 == lk4
    True

Incredibilmente la ListeVeloci funziona più velocemente di una inizializzazione di un array pieno di zeri, seguita da inserimento di un elemento alla volta usado lk5[[i]] =...
Poi faccio il confronto con i tempi dell'uso di una Range, che è il modo più veloce in Mathematica di generare l'array semplice. Si noti che nel caso di array semplici di numeri il Mathematica usa i packed array.

    Timing[n = 400000; lk5 = Array[0, n]; Do[lk5[[i]] = i, {i, n}]; ]
    {5.408 Second, Null}
    Timing[lk6 = Range[400000]; ]
    {0.02 Second, Null}
    lk6 == lk5
    True

Misura dei tempi disaggregati, per vedere quanto incide la doppia scrittura di lk5. Mathematica pare proprio non ottimizzato per questo tipo di programmazione procedurale, se una scrittura in un vettore (paked) impiega lo stesso tempo della creazione di una lista ipernidificata e successivo "appiattimento" con la Flatten.

    {Timing[n = 400000; lk5 = Array[0, n];], Timing[Do[lk5[[i]] = i, {i, n}]; ]}
    {{1.412 Second, Null}, {4.176 Second, Null}}

[Torna all'indice]