Vale la pena provare a scrivere strutture di dati infallibili?

Question

Vale la pena provare a scrivere strutture di dati infallibili?

#1 da (3 voti)
#2 da (2 voti)
#3 da (1 voti)

3

Il problema

Abbiamo bisogno di memorizzare i dati in un modo simile alla tabella, ma abbiamo limiti di spazio molto stretti (~ 1Mb per tabella di 10k + righe). Archiviamo dati come questo:

ID | reviews | factor | score | interval | etc.
---+---------+--------+-------+----------+-----
 1 |     244 |    2.4 |    10 |     4268 | ...

in un semplice formato binario (una matrice unidimensionale di byte, in cui l'indice di ogni riga può essere calcolato semplicemente conoscendo la lunghezza di ogni riga, che è fissa).

C'è solo una funzione che legge sempre questi dati (ottiene una riga dal suo indice) e solo una funzione che aggiunge una nuova riga (alla fine). La rimozione di elementi dalla tabella non sarà mai richiesta (la tabella è solo per l'aggiunta). Entrambe le funzioni sono coperte da una discreta quantità di test unitari.

Il problema è il seguente: dobbiamo essere in grado di scorrere rapidamente le righe ordinate da diverse colonne . In altre parole, abbiamo bisogno che i dati siano ordinati per almeno due colonne.

Una soluzione semplice

Per risolvere questo problema, implementeremmo degli indici che, ancora una volta, sarebbero costituiti da blocchi di dati binari. Ora lo farebbe intuitivamente creando strutture dati ordinate che elencano solo l'indice della riga nella tabella originale:

factor_index        score_index
------------        -----------
          6                  2
          2                  1
          3                  6
          1                  4
          .                  .

La funzione che aggiunge una nuova riga alla tabella dovrebbe essere aggiornata per far sì che anche gli indici vengano aggiornati.

ESEMPIO: per ottenere il primo elemento ordinato per punteggio, basta cercare il primo valore nella tabella indice per il punteggio (2) e ottenere la riga corrispondente dalla tabella originale (la terza riga se siamo d'accordo che la tabella è a zero indici).

Tuttavia, mi è stato suggerito di adottare un approccio diverso.

Una versione più complessa ma presumibilmente più sicura

Invece di archiviare solo gli indici, duplichiamo i campi ID in ogni tabella indice:

factor_index | ID        score_index | ID
-------------+---        ------------+---
          6  | 46                  2 |  8
          2  |  8                  1 | 14
          3  | 91                  6 | 46
          1  | 14                  4 | 60
          .  |  .                  . |  .

Quindi mantieni la tabella originale ordinata per ID e usa gli indici solo come posizione di partenza per una ricerca binaria nella tabella originale.

La funzione che aggiunge un nuovo record ora dovrà eseguire una ricerca binaria per ID per trovare dove inserire la nuova riga, e perché gli indici vengano aggiornati.

ESEMPIO: per ottenere il primo elemento ordinato per punteggio, cerchiamo la prima riga nella tabella indice per il punteggio (2, 8) e utilizziamo l'indice (2) come posizione di partenza per una ricerca binaria nella tabella. Se i dati sono validi, non abbiamo nemmeno bisogno di fare una ricerca binaria, perché nella posizione 2 troveremo la riga con l'ID 8. Se, tuttavia, troviamo che il record nella posizione 2 ha un indice diverso, continuiamo con una ricerca binaria per trovare quella giusta e registrare l'errore.

L'argomento per questo approccio è che funzionerà anche se l'indice punta alla riga sbagliata nella tabella.

Trovo difficile credere che questo approccio sia davvero migliore, per i seguenti motivi:

Richiede una ricerca binaria, che può essere una nuova fonte di bug.
Richiede che la tabella sia mantenuta in ordine, il che implica un inserimento più complesso (al contrario di una semplice append).
Non fa in modo che il tavolo principale non funzioni: se ciò accade, l'indice potrebbe anche non riuscire a trovare il record tramite la ricerca binaria.
Richiede la scrittura (e il test) di codice che non è mai nemmeno pensato per essere eseguito.
Utilizza più dati di quelli necessari.

La domanda

È molto prioritario per la nostra applicazione che il dato di cui sopra sia sempre valido. Ma questo giustifica la scrittura di strutture di dati più complesse e meccanismi di ricerca per evitare casi limite che potrebbero o meno accadere? Non dovremmo invece impiegare tempo e sforzi per scrivere casi di test più robusti per una versione più semplice?

defensive-programming data-structures

posta Attila O. 03.03.2013 - 04:10

fonte

3 risposte

2

Se la validità dei dati è fondamentale, qualsiasi trasformazione dei dati deve portare i dati trasformati da uno stato valido a uno stato valido. I meccanismi di trasformazione dovrebbero garantire la validità dell'output dato un input valido. Una trasformazione non riuscita dovrebbe fallire in sicurezza, lasciando i dati in uno stato valido.

Il test dell'unità può solo garantire che la trasformazione sia valida in ogni condizione a cui hai pensato durante la scrittura dei test . La coerenza con tutti i metodi di trasformazione dei dati garantisce che i dati rimangano validi in tutte le possibili condizioni .

Quindi, se la validità dei dati è una priorità elevata, ti suggerisco di creare metodi di modifica dei dati sempre validi e di testarli accuratamente. Non fidarti della coerenza in coincidenza.

risposta data 03.03.2013 - 05:03

fonte

1

Per prima cosa, una cosa che puoi tenere contro i tuoi argomenti:

se uno vuole usare gli ID come hai scritto, sicuramente implementerà per prima cosa un indice ID-to-row (quindi le ricerche ID non richiedono la tabella originale in un ordine speciale, e non devi implementare una ricerca binaria su quella tabella)

Ma se ci pensi per un momento, ora vedi che hai spostato il tuo problema originale su un altro livello: devi assicurarti che l'indice ID-to-row non sia fuori sincrono. Ovviamente, il vantaggio ora è che puoi ricostruire questo indice indipendentemente quando l'ordine delle righe della tabella originale cambia. Ciò ha senso quando devi aspettarti tali cambiamenti, sai quando accadono e che si verificano raramente / in momenti specifici nel tempo.

Tuttavia, vale davvero la pena? Quando sei sicuro al 100% che il numero di riga nella tabella originale sia una chiave primaria valida e immutabile, crea la soluzione più semplice possibile, in base ai numeri di riga, tutto il resto è più soggetto a errori e "prematuri". Altrimenti usa gli ID.

Ecco alcuni scenari in cui non puoi essere sicuro il tuo numero di riga è una chiave primaria valida:

le righe in un database relazionale in genere non dovrebbero avere un ordine speciale
in uno scenario basato su file: la quantità di dati aumenta e, a causa dei limiti di spazio, è necessario suddividerli su più tabelle fisiche. Quindi l'ID potrebbe essere ancora una chiave primaria valida, ma il numero della tua riga no.

Assicurati di non trovarti in una situazione simile quando utilizzi un approccio basato su numero di riga.

risposta data 03.03.2013 - 09:00

fonte

Leggi altre domande sui tag defensive-programming data-structures

python casuale con uno skew È corretto escludere i nomi degli argomenti dai prototipi di funzioni?

score 3 · Accepted Answer

Se sto capendo correttamente i tuoi indici non sono il modo più efficace per memorizzarli.

Non puoi ordinare il tuo tavolo su due chiavi contemporaneamente, quindi non penso che dovresti provare a ordinarlo del tutto. Piuttosto, ordina i tuoi indici.

10k righe: un valore a due byte può fare riferimento a qualsiasi voce nella tabella. Quindi costruisci due array che sono inizialmente seminati con 1..10k (o comunque molte voci sono nella tua tabella). Mentre questi non sono puntatori nel senso della parola della CPU, li usano comunque come puntatori. Ordinate entrambi gli array in base ai valori nella tabella.

L'inserimento è gestito semplicemente aggiungendo il record e quindi ricostruendo gli array. Sì, un'operazione abbastanza costosa, ma poiché hai specificato che gli array non sono così grandi e non possono crescere troppo, questo non dovrebbe essere fatto troppo spesso. Qualunque cosa tu faccia è inerentemente almeno O (n), un resort completo è solo O (n log n), io prenderei la seconda strada. (E potresti anche scoprire che è più veloce perché richiede molto meno scrivere sulla memoria principale piuttosto che spostare i record.)

Tieni presente che questi array sono semplicemente valori a due byte, NON coppie di valori-chiave come sembra che tu stia indicando.

Vengono in mente anche un paio di altre cose: ti sembra insolitamente preoccupato per la dimensione dei dati. Questo mi dice che o stai trasmettendo questi blocchi (a quel punto gli indici possono essere omessi perché possono essere ricreati dall'altra parte) o se ne hai un sacco in memoria in una sola volta. In quest'ultimo caso, se si utilizza un linguaggio che supporta riferimenti deboli, è possibile utilizzarli: lasciare che gli indici per i blocchi non vengano utilizzati attivamente per ottenere i dati raccolti e quindi ricreati quando necessario.