Gestione del processo di elenchi su larga scala [chiuso]

0

Quali sono i modi efficaci per elaborare elenchi enormi (+10 milioni) e cose da considerare mentre si manipolano elenchi enormi.

Prima domanda, quando dovrei usare la ricorsione e quando non dovrei. In entrambi i casi, stiamo allocando memoria per archiviare i dati (la complessità della memoria dovrebbe essere uguale), l'utilizzo dell'approccio ricorsivo con una lista enorme comporterebbe un consumo di memoria (immagazzinare la chiamata nella memoria Heap), così come la memorizzazione dei dati in un lista (stack-memory). Quale approccio con meno costi? (Di solito possiamo scrivere qualsiasi algoritmo ricorsivo per algoritmo iterativo).

Seconda domanda, quando si tratta di memoria-comlessità, dovrei pensare di trasformare questa lista in un'altra struttura dati (come LL, BST, .. per manipolare facilmente i dati), il problema con tali soluzioni è che l'allocazione di memoria in questo caso verrebbe raddoppiato (ogni nodo avrebbe valore di riferimento + nodo invece di un valore in una lista).

O dovrei pensare a copiare su disco questo elenco (testo-dati o csv) e elaborare i dati per porzione. Il problema di questa soluzione è che alcune operazioni richiedono la correlazione tra i valori, non è possibile elaborare ogni porzione in modo indipendente, quindi ridurre e concatenare i dati.

Scenario 1: ordinamento di una lista enorme (Merge Sort (Ricorsive) Vs altri)

Scnario 2: consideriamo questo rapido esempio (non è il pefetto e il più pertinente a ciò che sto cercando di chiedere, ma solo per mostrare un altro esempio).

Stiamo aggiungendo il prodotto di 4 elementi successivi a ogni elemento di questi quattro elementi.

L=range(100)
from operator import mul
def prodElement(L):
    getItems= lambda i: L[i:i+4]
    list_mul=[]
    for i in xrange(0,len(L)-3,4):
        p=reduce(lambda x,y:x*y,getItems(i))
        L[i],L[i+1],L[i+2],L[i+3]= L[i]+p,L[i+1]+p,L[i+2]+p,L[i+3]+p
    return L


def prodElement_rec(r,L,i=0):
    if i>=len(L)-1: #Stop
        return res
    else: 
        if i%4==0 or i==0:
            p= L[i]*L[i+1]*L[i+2]*L[i+3]
            L[i],L[i+1],L[i+2],L[i+3]= L[i]+p,L[i+1]+p,L[i+2]+p,L[i+3]+p
            return prodElement_rec(r,L,i+4)
res=[]
assert prodElement_rec(res,L)==prodElement(L)

Ancora una volta, non sto cercando di risolvere un problema specifico, ma sto cercando di capire i migliori approcci da utilizzare quando si tratta di elenchi enormi (+10 milioni di articoli). Quali sono i metodi che dovrei pensare e le questioni critiche che dovrei evitare per risolvere il problema usando liste enormi.

    
posta user3378649 17.11.2014 - 00:00
fonte

1 risposta

2

Nel modulo attuale è probabile che la tua domanda venga chiusa come "troppo ampia", ma dal momento che hai chiesto in questa forma generica, cerco di darti una risposta generica:

    Ricorsione
  • : non utilizzare la ricorsione quando la profondità di ricorsione prevista sarà nell'ordine di grandezza della dimensione della lista. Soprattutto quando il tuo linguaggio di programmazione non ottimizza automaticamente le ricadute di coda ( Python non ). E supponiamo che la profondità della ricorsione sia ragionevole: usala solo quando rende il codice più semplice e comprensibile. Nel tuo esempio sopra, la profondità della ricorsione sarà circa "list size / 4" (che probabilmente finirà in un overflow dello stack quando la dimensione dell'elenco è grande come hai scritto), e il codice non è sicuramente più semplice del non ricorsivo variante.

  • scrittura di dati su disco: fare ciò solo quando si prevede di superare la memoria principale disponibile del sistema (il che significa che la memoria è disponibile per il proprio programma). Ciò implicherà la necessità di un cosiddetto algoritmo esterno per l'attività give, che è quasi sempre più complicato rispetto all'utilizzo di algoritmi in memoria. Quindi fallo solo se devi. EDIT, a causa del commento di cui sopra: l'utilizzo di un database è una buona alternativa per molti scenari. Ciò introdurrà alcuni overhead di programmazione aggiuntivi da un lato, ma può risparmiare molto dall'altro.

  • quale struttura dati utilizzare: inizia con la struttura dati più semplice adatta per l'attività specificata, quindi misura le tue prestazioni (magari con gli elenchi più piccoli, ma assicurati di conoscere l'ordine approssimativo di crescita del runtime dell'algoritmo quando si inizia l'estrapolazione per elenchi più grandi). Solo quando il tuo codice non funziona abbastanza velocemente, prova a utilizzare strutture e algoritmi di dati più complessi (e non dimenticare di misurare nuovamente).

Per riassumere: dipende da cosa farai con tali elenchi, dalla tua memoria e dai limiti di tempo.

    
risposta data 17.11.2014 - 08:30
fonte

Leggi altre domande sui tag