Come posso rappresentare una linea di note musicali in un modo che consenta l'inserimento veloce in qualsiasi indice?

Question

Per "divertimento", e per imparare la programmazione funzionale, sto sviluppando un programma in Clojure che fa la composizione algoritmica usando le idee di questa teoria della musica chiamata "Teoria di Westergaardian". Genera linee di musica (dove una linea è solo un singolo rigo costituito da una sequenza di note, ciascuna con altezze e durate). Funziona fondamentalmente in questo modo:

1. Inizia con una riga composta da tre note (le specifiche di come vengono scelti non sono importanti).
2. Esegue in modo casuale una delle diverse "operazioni" su questa linea. L'operazione seleziona casualmente da tutte le coppie di note adiacenti che soddisfano un determinato criterio (per ogni coppia, il criterio dipende solo dalla coppia ed è indipendente dalle altre note nella riga). Inserisce 1 o più note (a seconda dell'operazione) tra la coppia scelta. Ogni operazione ha i suoi criteri univoci.
3. Continuare in modo casuale queste operazioni sulla linea fino a quando la linea è la lunghezza desiderata.

Il problema che ho riscontrato è che la mia implementazione di questo è piuttosto lenta, e ho il sospetto che potrebbe essere reso più veloce. Sono nuovo di Clojure e di programmazione funzionale in generale (anche se ho esperienza con OO), quindi spero che qualcuno con più esperienza possa indicare se non sto pensando in un paradigma funzionale o se mi manca una qualche tecnica FP .

La mia attuale implementazione è che ogni linea è un vettore contenente mappe. Ogni mappa ha un: note e a: dur. : il valore della nota è una parola chiave che rappresenta una nota musicale come: A4 o: C# 3. : il valore di dur è una frazione, che rappresenta la durata della nota (1 è una nota intera, 1/4 è una nota da un quarto, ecc ...). Così, per esempio, una linea che rappresenta la C di partenza scala maggiore sulla C3 sarebbe simile a questa:

[ 
{:note :C3 :dur 1} 
{:note :D3 :dur 1} 
{:note :E3 :dur 1} 
{:note :F3 :dur 1} 
{:note :G3 :dur 1} 
{:note :A4 :dur 1} 
{:note :B4 :dur 1} 
] 

Questa è una rappresentazione problematica perché non c'è in realtà un modo veloce per inserire in un indice arbitrario di un vettore. Ma l'inserimento è l'operazione eseguita più frequentemente su queste linee. La mia attuale terribile funzione per inserire note in una linea divide il vettore usando subvec nel punto di inserimento, usa conj per unire la prima parte + note + ultima parte, quindi usa flatten e vec per farle tutte in una dimensione unidimensionale vettore. Per esempio, se voglio inserire C3 e D3 nella scala C maggiore all'indice 3 (dove F3 è), lo farebbe (userò il nome della nota al posto delle mappe: note e: dur):

1. (conj [C3 D3 E3] [C3 D3] [F3 G3 A4 B4]), che crea [C3 D3 E3 [C3 D3] [F3 G3 A4 B4]]
2. (vec (appiattire precedente -vector)) che dà [C3 D3 E3 C3 D3 F3 G3 A4 B4]

Il tempo di esecuzione è O (n), AFAIK.

Sto cercando un modo per rendere questo inserimento più veloce. Ho cercato informazioni sulle strutture dati Clojure che hanno un inserimento veloce ma non hanno trovato nulla che possa funzionare. Ho trovato "finger trees" ma consentono solo l'inserimento rapido all'inizio o alla fine della lista.

Modifica: ho diviso questo in due domande. The other part is here.

Answer 1

Una cosa che ti è sfuggita è che, in teoria, comunque, le barrette danno un inserimento veloce a qualsiasi indice.Loro solo direttamente ti permettono di inserirli alle due estremità, ma forniscono anche una rapida divisione e una rapida concatenazione, così una funzione di inserimento rapido ovunque può essere incorniciata come "divisa in due sequenze, aggiunta a una di esse, e quindi concatenata ancora insieme".

Dico "teoricamente" perché gli alberi delle dita si basano sull'accesso alla memoria a tempo costante, ma generano molti più errori di cache rispetto a un vettore più semplice e spesso non si comportano bene come ci si aspetterebbe. Gli alberi delle dita sono divertenti da giocare, ma non sono comunemente usati nel clojure e non lo consiglierei davvero di usarli per davvero.

Una possibilità è continuare a utilizzare le operazioni lente. Se i tuoi vettori non sono mai molto lunghi e le prestazioni non sono cruciali, l'operazione di inserimento di O (n) non avrà molta importanza.

Se non va bene, c'è una soluzione che ha l'inserimento O (log (n)) che si desidera, anche se non è molto divertente. La risposta è ... per simulare i puntatori mutabili! Questo è un approccio che spesso funziona: se i puntatori fossero mutabili, si potrebbe semplicemente avere un elenco collegato, in cui ogni cella conosce i suoi due vicini e aggiornarli quando necessario durante l'inserimento. Ma non puoi qui, perché i riferimenti circolari non sono grandi per i dati funzionali. Ma puoi aggiungere un livello di riferimento indiretto: attribuisci a ciascuna cella un'etichetta "unica" e conservale solo le etichette dei suoi vicini. Quindi non hai riferimenti circolari e puoi effettuare aggiornamenti locali a basso costo. Ecco un esempio di layout che sto descrivendo, il vostro C-scala maggiore:

{:cell-data {0 {:left nil :right 1, :note :C3 :dur 1} 
      1 {:left 0 :right 2, :note :D3 :dur 1} 
      2 {:left 1 :right 3, :note :E3 :dur 1} 
      3 {:left 2 :right 4, :note :F3 :dur 1} 
      4 {:left 3 :right 5, :note :G3 :dur 1} 
      5 {:left 4 :right 6, :note :A4 :dur 1} 
      6 {:left 5 :right nil, :note :B4 :dur 1}} 
:first-node 0, :last-node 6} 

Ecco i numeri sono sequenziali, ma si può vedere come si potrebbe aggiungere un nodo tra il 5 e 6, con la creazione di un nuovo nodo con {:left 5 :right 6} e modifica del :right del nodo 5 e dello :left del nodo 6.

Questa organizzazione è un po 'una seccatura, ma soddisfa le vostre esigenze.

Answer 2

E che dire dei tasti di rapporto in una mappa? In questo modo l'inserimento viene eseguito con una chiave la media delle chiavi per la coppia scelta.

Si potrebbe anche utilizzare una mappa ordinata se è necessario attraversarlo in fase di costruzione.

EDIT: con l'esempio:

• scala maggiore C:

(def line {0 {:note :C3 :dur 1} 
      1 {:note :D3 :dur 1} 
      2 {:note :E3 :dur 1} 
      3 {:note :F3 :dur 1} 
      4 {:note :G3 :dur 1} 
      5 {:note :A4 :dur 1} 
      6 {:note :B4 :dur 1}}) 

• la posizione in cui inserire C3 (tra E3 e F3)

(def between-E3-and-F3 [2 3]) 

• inserto C3:

(let [[pos-E3 pos-F3] between-E3-and-F3 
     C3    {:note :C3 :dur 1} 
     pos-C3   (/ (+ pos-E3 pos-F3) 2) ;; 5/2 
     line   (accoc line pos-C3 C3)] 
...) 

• quindi inserire D3 (tra C3 appena inserito e F3):

(let [[pos-E3 pos-F3] between-E3-and-F3 
     C3    {:note :C3 :dur 1} 
     pos-C3   (/ (+ pos-E3 pos-F3) 2) ;; 5/2 
     line   (accoc line pos-C3 C3) 
     D3    {:note :D3 :dur 1} 
     pos-D3   (/ (+ pos-C3 pos-F3) 2) ;; 11/4 
     line   (accoc line pos-D3 D3)] 
...) 

Se pos1 e pos2 sono rapporti distinti (o interi , o bigints), sei sicuro che pos-C3 sia diverso da entrambi (/ produrrà rapporti esatti, non numeri in virgola mobile). In questo modo inserisci sempre una nuova nota (nessuna sostituzione di una nota esistente). Per produrre l'elenco delle note in ordine, basta ordinarlo:

(map second (sort-by first line)) 

Oppure:

(vals (sorted-map line)) ;; you can also initialize line as a sorted map 
         ;; before inserting the notes 

E si ottiene le note in ordine.