1

我正在使用 C 开发硬件虚拟模拟合成器，并且我正在尝试提出一种有效的数据结构来管理合成器声音的动态分配以响应传入的 MIDI 消息。

我有一个结构类型，它保存单个合成器声音（音高、低频振荡器、ADSR 设置等）的数据，并且我有一个“NoteOn”回调函数，它在 MIDI“Note On”消息被解码时执行。此功能需要从“空闲”池中获取“空闲”语音，修改结构中的一些设置，并将其分配给主合成引擎使用的“播放”池以生成音频样本。然后，当收到“Note Off”消息时，需要从“正在播放”池中选择与“Note Off”消息中的音符值对应的音符，再次修改其数据结构，最终返回到“空闲”池（取决于信封/ADSR 设置。）

我尝试了对两个池都使用链表的实现，但我的实现似乎相当麻烦和缓慢。我希望这个过程尽可能快，以保持播放响应能力。有什么建议么？

4

1 回答 1

3

如果链表太慢，通常的答案是实现哈希表。数据结构和算法有很多很多可能的变化。我将只描述开放的“单一”哈希，因为这是我最熟悉的变体。

因此，对于开放哈希表，该表只是一个数组（“封闭”哈希也有一个数组，但每个元素都是一个链表）。出于性能原因，我们希望阵列最多为半满。并且在最大容量时，已填满的表实际上仍然有一个空槽，因为这简化了算法。

我们还需要一个接受键值类型并返回整数的哈希函数。很难预测散列函数在聚集键和整体性能方面的表现。因此，只需确保它是一个独立的功能，以后可以轻松更改。它可以像移动所有字节并将它们加在一起一样简单。

int hash (char *key, int key_length, int table_size)
{
    int ret, i;
    for (i=0, ret=0; i < key_length; i++)
    {
        ret += key[i] << i;
    }
    return abs(ret) % table_size;
}

查表函数使用散列函数来决定从哪里开始查找数组。如果在那里找不到键（通过memcmp()对实际搜索键和存储在表中该位置的键执行 a 来确定），它会查看每个连续的键，从数组的末尾回绕到开头，并且如果发现空表元素，则声明失败。

#define RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY \
    if (memcmp(table + i, &key, sizeof key) == 0 || (key_type)table[i] == 0) \
        return table + i;

key_value_pair *hash_lookup(key_value_pair *table, int table_size, key_type key)
{
    int h, i;

    h = hash(&key, sizeof key, table_size);

    i = h;
    RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY
    for ( ; i < table_size; i++)
        RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY
    for (i=0; i < h; i++)
        RETURN_TABLE_I_IF_EQUAL_KEY_OR_EMPTY

    return NULL;
}

在此之前，我们还需要一个函数来处理一些怪癖。它可以返回一个 NULL 指针，这表明不仅没有找到键，而且表本身已满。一个过满的表，这实际上意味着“完全满”，但我们之前决定一个“满”的表应该真的有一个空元素。这意味着两个for循环都不应该运行完成；当它找到一个空表位置时，这是一个失败。对于过满的表，它必须在发现键不存在之前扫描整个表，从而完全失去使用散列的大部分性能优势。

查找函数还可以返回一个指向空槽的有效指针。这也是找值失败，但不是错误。如果是第一次添加键/值对，这将是存储它的槽。

或者它可以返回一个指向所需表格元素的指针。这将比线性搜索更快，无论是数组还是链表。

从表中删除一个键需要我们填写序列中空出的位置。有几个选项。

如果您不担心表空间不足（它设置得非常大，并且可以控制生命周期和使用情况），您可以使用已删除的特殊键覆盖条目，与空键不同。

或者，如果您也想回收空间，则需要查找密钥，然后扫描“链”的其余部分（直到下一个空槽（包括环绕）的密钥序列）并移动具有匹配哈希的最后一个键到要删除的键的位置。然后用空键覆盖这个移动的键/值的位置。....哎呀！必须对最后一个匹配键重复此过程，直到我们真正清除链中的最后一个键。（我现在需要在我的实施中解决这个问题！....）

于 2013-11-11T05:50:18.223 回答