How can I present a line of musical notes in such a way that any index can be quickly inserted?

Question

For fun and learning functional programming, I am developing a program in Clojure that performs an algorithmic composition using ideas from this music theory called Westergaard's Theory. It generates musical lines (where the line is just one character, consisting of a sequence of notes, each with a step and duration). It basically works as follows:

• Start with a line consisting of three notes (the selection is not important).
• Randomly perform one of several "operations" on this line. The operation is randomly selected from all pairs of adjacent notes that meet certain criteria (for each pair, the criterion depends only on the pair and does not depend on other notes in the string). It inserts 1 or more notes (depending on the operation) between the selected pair. Each operation has its own unique criteria.
• Continue to randomly perform these operations on the line until the line is needed.

The problem I am facing is that my implementation is rather slow and I suspect that it could be done faster. I am new to Clojure and functional programming in general (although I have experience with OO), so I hope that someone with more experience can indicate whether I think in the functional paradigm or not miss some FPs.

My current implementation is that each line is a vector containing maps. Each card has: a note and a: dur .: the note value is a keyword representing a musical note of type A4 or C # 3 .: dur value is a fraction representing the duration of a note (1 - a whole note, 1/4 - a quarter note etc.). So, for example, a line representing a scale of C starting with C3 would look like this:

[ {: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} ] 

This is a problematic representation, because there really is no quick way to insert a vector into an arbitrary index. But insertion is the most frequently performed operation on these lines. My current awful function for inserting notes into a string basically splits the vector using subvec at the insertion point, uses conj to append the first part + notes + last part, then uses flatten and vec to make them all in a one-dimensional vector. For example, if I want to insert C3 and D3 into the main scale C with index 3 (where F3 is), it will do this (I will use the name of the note instead of the cards: note and: dur):

• (conj [C3 D3 E3] [C3 D3] [F3 G3 A4 B4]), which creates [C3 D3 E3 [C3 D3] [F3 G3 A4 B4]]
• (vec (flatten previous-vector)), which gives [C3 D3 E3 C3 D3 F3 G3 A4 B4]

Runtime - O (n), AFAIK.

I am looking for a way to make this insert faster. I was looking for information on Clojure data structures that have a quick insert but didn't find anything that could work. I found finger trees, but they only allow quick insertion at the beginning or end of the list.

Edit: I divided this into two questions. The other part is here.

Answer 1

One thing you missed is that, in any case, finger trees give a quick insert at any index. They only directly allow you to insert from both ends, but they also provide quick separation and quick concatenation, so you can create a quick insert function anywhere like "split into two sequences, add to one of them, and then combine them again."

I say “theoretically” because finger trees rely on constant access to memory, but they generate far more cache misses than a simple vector, and often do not perform as well as you expected. Fingers are very fun to play with, but they are usually not used in clojure, and I would not recommend using them really.

One possibility is simply to continue slow operations. If your vectors are never very long, and performance is not critical, then the O (n) input operation will simply not matter much.

If this is not good, there is a solution that has the O (log (n)) attachment that you need, although it is not very fun. The answer is ... to simulate volatile pointers! This is an approach that often works: if the pointers were volatile, you can only have a linked list where each cell knows its two neighbors and updates them as needed when inserted. But you cannot here, because circular links are not suitable for functional data. But you can add a level of indirection: give each cell a unique “label” and store only the labels of its neighbors. Then you do not have round links, and you can do local updates cheaply. Here is an example of the layout I am describing, your C-major scale:

 {: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} 

The numbers are consistent here, but you can see how you could add a node between 5 and 6 by creating a new node with {:left 5 :right 6} and changing :right to node 5, and :left of node 6.

This organization is a complex problem, but it meets your needs.

Answer 2

How about using the ratio keys on the map? Thus, the insertion is performed with the key on average by the keys for the selected pair.

You can even use a sorted map if you need to go through it at the end of construction.

EDIT: with your example:

• scale 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}}) 

• position to insert C3 (between E3 and F3)

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

• Paste 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)] ...) 

• then insert D3 (between the newly inserted C3 and 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)] ...) 

If pos1 and pos2 are different relations (either ints or bigints), you are sure that pos-C3 is different from both ( / will produce relations that are exact, not floating point numbers). This way you always insert a new note (without replacing the existing note). To create a list of notes in order, you just need to sort it:

 (map second (sort-by first line)) 

Or:

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

And you get your notes in order.