Ridurre una sequenza di operazioni di modifica dell'array (inserire, ordinare, sostituire, rimuovere)

Question

Ridurre una sequenza di operazioni di modifica dell'array (inserire, ordinare, sostituire, rimuovere)

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

3

Dato un semplice array di valori, ad es.

["Apple", "Orange", "Banana", "Strawberry"]

e un elenco di operazioni dall'insieme di [ insert , delete , sort e replace ], ad es.

[
  {cmd: "insert", index: 2, entries: ["Cherry", "Kiwi"]},
  {cmd: "delete", indices: [3]},
  {cmd: "sort", newOrder: [3,1,2,0,4]},
  {cmd: "insert", index: 3, entries: ["Peach"]},
  {cmd: "replace", index: 3, newEntry: "Raspberry"}
]

che dovrebbe risultare nell'array

["Banana", "Orange", "Cherry", "Raspberry", "Apple", "Strawberry"]

Come posso, con uno sforzo relativamente ridotto, trasformare la mia sequenza di operazioni in qualcosa di meno ridondante? Per es.

[
  {cmd: "sort", newOrder: [2,1,0,3]},
  {cmd: "insert", index: 2, entries: ["Cherry", "Raspberry"]}
]

Si noti che l'eliminazione di una voce e l'inserimento di una voce identica è considerata equivalente all'aggiunta di una voce completamente nuova, mentre l'inserimento di una nuova voce e la successiva eliminazione di annulli. È necessario tenere traccia delle modifiche / sostituzioni / ridenominazioni delle voci, ma non si combinano con nessuna delle altre operazioni.

Domanda:

Questo sembra qualcosa che si presenterebbe nel contesto dell'ottimizzazione delle query del database, ma non ho idea di cosa sia per google. Alla fine sto cercando un algoritmo (preferibilmente un'implementazione JS) che automatizza questo genere di cose per me, anche se solo in modo ingenuo / avido (non è necessario cercare esaustivamente la riduzione migliore, se non può essere fatto in tempo polinomiale).

Sfondo:

Questo è emerso mentre si lavorava su un'app Web in cui l'utente può modificare un elenco di voci, accettare e inviare tali modifiche e quindi attivare un rimpasto di un insieme di matrici corrispondenti sul server. Ciò significa che devo catturare il modo in cui gli elementi si muovono nell'array, non solo come appare l'array dopo aver apportato tutte le modifiche. (Ho bisogno di tenere traccia delle operazioni per la funzionalità di annullamento / ripristino comunque.) Poiché la quantità di dati coinvolti può essere piuttosto grande, combinando tali operazioni prima di inviarle si tradurrebbe in tempi di caricamento più brevi e meno scritture di database sul lato server. Tutto questo è puramente teorico a questo punto e potrebbe benissimo essere un'ottimizzazione prematura, ma ho trovato un problema interessante e mi piacerebbe un po 'di input.

array optimization efficiency query

posta sebastian_k 10.07.2015 - 23:19

fonte

2 risposte

2

Il modo più diretto sarebbe quello di tracciare alcuni metadati insieme all'array, quindi ti ritroverai con una struttura dati simile a questa:

[{name: "Banana", originalOrder: 2},
 {name: "Orange", originalOrder: 1, deleted: true}, 
 {name: "Cherry", new: true}, 
 {name: "Raspberry", new: true}, 
 {name: "Apple", originalOrder: 0}, 
 {name: "Strawberry", originalOrder: 3}]

Quindi sono tutte le operazioni lineari relativamente semplici per trovare il nuovo ordine, creare un elenco di eliminazioni e creare un elenco di inserimenti.

risposta data 10.07.2015 - 23:48

fonte

Leggi altre domande sui tag array optimization efficiency query

Alternativa non nulla a Void (tipo di unità Java) Design del tavolo per le vacanze

score 3 · Accepted Answer

Vorrei provare qualcosa come il calcolo simbolico dove eseguiamo il calcolo su un'astrazione di tutti gli stati iniziali possibili, l'obiettivo di questa esecuzione simbolica è di produrre un'astrazione dello stato finale, che è quindi riflettente dei calcoli eseguiti da l'insieme delle operazioni da ottimizzare.

(Poiché usiamo un'astrazione di tutti gli stati iniziali possibili, possiamo eseguire la trasformazione (mediante l'esecuzione simbolica) dei passaggi di input al loro effetto (come stato di output astratto) senza coinvolgere il database reale.)

Lo stato astratto su cui è possibile eseguire il calcolo memorizzerà nodi di diversi tipi. Primi nodi costanti o noti, con indice fisso e valore noto, come 2:Cherry , che è simile a quello che può essere memorizzato dall'elenco reale e secondi valori sconosciuti su intervalli noti (ad esempio, scrivo ?0-1 per indicare il valore sconosciuto da posizioni da 0 a 1 nell'input originale) e valori sconosciuti su un intervallo solo parzialmente noto (ad es. scriverò ?0-N dove N è la lunghezza dell'elenco di input).

Quindi, lo stato astratto iniziale è un elenco di lunghezza N di valori sconosciuti, che rappresenterò come [ ?0-N ] , un elenco astratto di un nodo che dice che ha i valori originali (sconosciuto) dalle posizioni di lista 0 attraverso N.

Dopo l'inserimento del primo passo, la nostra lista astratta avrà quattro nodi. Uno per rappresentare l'intervallo 0-1, uno per le posizioni 2 e 3 (inserito) e uno per le posizioni rimanenti. L'elenco astratto ora assomiglia a [ ?0-1, 2:Cherry, 3:Kiwi, ?2-N ] dove ?2-N indica il valore originale di 2 attraverso i valori originali alla lunghezza dell'elenco.

Dopo la cancellazione, rimuoviamo l'elemento alla posizione 3 nella lista astratta (corrente), lasciandoci con [ ?0-1, 2:Cherry, ?2-N ] . E così via ...

L'ordinamento funziona immediatamente sopra e ci lascia con: [ ?2, ?1, 2:Cherry, ?0, ?3, ?4-N ] .

Il prossimo inserimento cambia lo stato astratto in: [ ?2, ?1, 2:Cherry, 3:Peach, ?0, ?3, ?4-N ] . E la sostituzione ha come risultato: [ ?2, ?1, 2:Cherry, 3:Raspberry, ?0, ?3, ?4-N ] .

Il risultato finale di questo calcolo simbolico sullo stato astratto ci dirà il comando risultante da eseguire per ottenere quell'effetto su un elenco di input arbitrario e, se lo desideri, può essere diviso in parti, eliminati e inseriti; Tuttavia potremmo stare meglio se potessimo interpretare lo stato del risultato astratto come un singolo comando direttamente aggiungendo un nuovo comando di cambio bulk che può eseguire diversi tipi di operazioni in un colpo solo (ad es. cmd:change-list substitute:[ ?2, ?1, Cherry, Raspberry, ?0, ?3, ?4-N ] )