algorithm - 我怎样才能提供一个很好的、易于使用的抽象来跟踪列表的 "dirty"元素？

Question

为了“好玩”，为了学习函数式编程，我正在用 Clojure 开发一个程序，它使用这种称为“Westergaardian 理论”的音乐理论中的思想进行算法作曲。它生成音乐线(其中一条线只是一个谱表，由一系列音符组成，每个音符都有音高和持续时间)。它基本上是这样工作的:

1. 以包含三个音符的一行开始(如何选择这些音符的细节并不重要)。
2. 在这条线上随机执行几个“操作”之一。该操作从满足特定标准的所有成对相邻音符中随机挑选(对于每一对，标准仅取决于该对，而独立于该行中的其他音符)。它在所选对之间插入 1 个或多个音符(取决于操作)。每个操作都有自己独特的标准。
3. 继续在线上随机执行这些操作，直到该线达到所需的长度。

我遇到的问题是我的实现速度很慢，我怀疑它可以做得更快。我是 Clojure 和一般函数式编程的新手(虽然我有 OO 经验)，所以我希望有更多经验的人可以指出我是否没有考虑函数式范式或错过了一些 FP 技术.

我目前的实现是每一行都是一个包含 map 的向量。每张 map 都有一个 :note 和一个 :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}
]

让我们忽略使用向量 (that's covered in a different question) 的问题。我想专注于提高确定哪些音符对通过了给定操作的标准的速度。

问题是，每个操作都必须查看哪些相邻的音符对符合其条件。目前，这是 O(n)，其中 n 是线的大小(它只是遍历整条线并查看每一对)，这意味着即使我解决了使用向量的问题，它仍然会很慢。然而，标准检查的好处是它只需要重新评估邻居发生变化的音符(因为每对的标准独立于行中的其他音符)。我不确定我将如何在 Clojure 中跟踪这一点，以便算法跟踪哪些对是脏的，哪些是干净的，并且只能重新评估脏的音符对。从范例的角度来看，使用 map 包围线路并添加元数据来跟踪它是否可以？例如，我会有这样的结构:

{
:line [<the elements of the line>]
:dirty [<indexes of notes that need to be re-checked>]
:valid {
       operation1 [<indexes of notes that operation 1 can be performed on>]
       operation2 [<indexes of notes that operation 2 can be performed on>]
       ...
       }
}

我怎么能做这样的事情，但让它成为一个很好的抽象？这样一来，每次我想对它做些什么时，我就不必记住它的结构了。是否有一些 Clojure 语言功能可用于对此进行抽象？或者这不是一个好方法吗？我正在考虑在 OO 中抽象出这样的实现细节是多么容易(例如，如果我想说给定的音符现在是脏的，我可以做类似 .setDirty(index) 的事情，而不是直接访问向量).我确信在 Clojure/函数式编程中有办法做到这一点。

这看起来是一种跟踪“脏”笔记的好方法吗？我如何在 Clojure 中对此进行编码以使其易于使用(进行很好的抽象，这样我就不必记住 map 的结构)。

Answer 1

Clojure protocols和 records有点类似于面向对象的接口(interface)和类。在这种情况下，您可以定义一个协议(protocol)来抽象一行中的基本方法:

(defprotocol LineProtocol
  (extend [this])
  (note-seq [this])
  (length [this]))

其中 extend 通过对随机适用的音符对应用随机操作生成新行，length 返回行中的音符数，note- seq 返回行中的音符序列。

然后给定一条初始线，您可以通过以下方式获得所需长度的线:

(->> line 
  (iterate extend)
  (drop-while #(< (length %) desired-length))
  first
  note-seq)

您心目中的抽象实现可能看起来像

(defrecord Line [notes valid dirty]
  LineProtocol
  (extend [this] (->Line ...)) ;calc new line from this line's state
  (length [this] (count notes))
  (note-seq [this] (seq notes)))

如果 notes 是一个向量。 (->Line 是由 defrecord 调用生成的工厂方法。)

我认为您的实现似乎走在了正确的轨道上，但我认为您必须评估每次调用 extend 时的所有脏笔记。