cha*_*der 6 algorithm functional-programming clojure data-structures
为了"有趣",并学习函数式编程,我正在使用Clojure开发一个程序,该程序使用来自这种音乐理论的思想称为"Westergaardian Theory"进行算法组合.它产生一系列音乐(其中一行只是一个由一系列音符组成的音符,每个音符都有音高和持续时间).它基本上是这样的:
我遇到的问题是我的实现速度非常慢,我怀疑它可以更快.我是Clojure和函数式编程的新手(虽然我对OO很有经验),所以我希望有更多经验的人可以指出我是不是在考虑功能范例还是错过了一些FP技术.
我目前的实现是每一行都是一个包含地图的矢量.每张地图都有:note和a:dur.:note的值是表示音符的关键字,如:A4或:C#3.:dur的值是一个分数,表示音符的持续时间(1是整个音符,1/4是四分音符等等).因此,例如,表示从C3开始的C大调比例的线条如下所示:
[
{: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}
]
这是一个有问题的表示,因为实际上没有一种快速的方法可以插入到向量的任意索引中.但插入是这些线路上最常执行的操作.我当前用于将音符插入一行的可怕功能基本上在插入点使用子集分割矢量,使用conj连接第一部分+音符+最后部分,然后使用flatten和vec使它们全部在一维中向量.例如,如果我想将C3和D3插入索引3处的C大调(F3所在的位置),它会这样做(我将使用音符名称代替:note和:dur map):
运行时间是O(n),AFAIK.
我正在寻找一种方法来加快插入速度.我已经搜索了有关Clojure数据结构的信息,这些数据结构有快速插入但没有找到任何可行的方法.我找到了"手指树",但它们只允许在列表的开头或结尾快速插入.
编辑:我把它分成两个问题.另一部分在这里.
你遗漏的一件事是,理论上无论如何,手指树确实可以在任何指数处快速插入.它们只能直接允许你在任何一端插入,但它们也提供快速分割和快速连接,因此快速插入任意函数可以被构造为"分成两个序列,附加到其中一个,然后再将它们连接在一起" ".
我说"理论上"因为手指树依赖于恒定时间内存访问,但它们比简单的向量产生更多的缓存未命中,并且通常表现不如您期望的那样好.手指树很有趣,但在clojure中并不常用,我真的不建议真正使用它们.
一种可能性是继续使用慢速操作.如果你的向量永远不会很长,并且性能并不重要,那么O(n)插入操作就没那么重要了.
如果这不好,有一个你想要的O(log(n))插入的解决方案,虽然它不是很有趣.答案是......模拟可变指针!这种方法通常有效:如果指针是可变的,您可以只有一个链表,每个单元知道它的两个邻居,并在插入时根据需要更新它们.但是你不能在这里,因为循环引用对功能数据不是很好.但是,您可以添加一个间接级别:为每个单元格提供一个唯一的"标签",并让它只存储其邻居的标签.那么你没有循环引用,你可以便宜地进行本地更新.这是我所描述的布局的一个例子,你的C大调:
{: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}
这里的数字是连续的,但您可以看到如何通过创建一个新节点{:left 5 :right 6},并更改:right节点5和:left节点6 来添加5到6之间的节点.
这个组织有点麻烦,但它确实满足了您的需求.