1

私は C を使用してハードウェア仮想アナログ シンセサイザーに取り組んでおり、着信 MIDI メッセージに応答してシンセサイザー ボイスの動的な割り当てを管理するための効率的なデータ構造を考え出そうとしています。

単一のシンセサイザー音声 (ピッチ、低周波オシレーター、ADSR 設定など) のデータを保持する構造型があり、MIDI "ノートオン" メッセージがデコードされたときに実行される "NoteOn" コールバック関数があります。この関数は、「アイドル」プールから「アイドル」ボイスを取得し、構造内のいくつかの設定を変更し、それをメイン シンセ エンジンがオーディオ サンプルを生成するために使用する「再生中」プールに割り当てる必要があります。次に、「ノート オフ」メッセージが受信されると、「ノート オフ」メッセージの値に対応する音価を持つボイスが「再生中」のプールから選択され、そのデータ構造が再度変更され、最終的に返される必要があります。 「アイドル」プールへ (エンベロープ/ADSR 設定による)。

両方のプールにリンク リストを使用して実装を試みましたが、私の実装はかなり面倒で遅いように見えました。再生の応答性を維持するために、このプロセスをできるだけ迅速に行いたいと考えています。助言がありますか？

4

1 に答える 1

3

リンクされたリストが遅すぎる場合、通常の答えはハッシュ テーブルを実装することです。データ構造とアルゴリズムには、非常に多くの可能なバリエーションがあります。オープンな "single"-hashingについてだけ説明します。これは、私が最もよく知っているバリエーションです。

したがって、オープン ハッシュ テーブルでは、テーブルは単なる配列です (「クローズド」ハッシュにも配列がありますが、各要素はリンクされたリストです)。パフォーマンス上の理由から、アレイはせいぜい約半分まで使用する必要があります。また、最大容量では、満たされたテーブルには実際にはまだ 1 つの空のスロットがあります。これは、アルゴリズムが単純化されるためです。

キー値の型を受け入れ、整数を返すハッシュ関数も必要です。クラスター化されたキーと全体的なパフォーマンスに関して、ハッシュ関数がどのように動作するかを予測することは非常に困難です。したがって、後で簡単に変更できる独立した機能であることを確認してください。すべてのバイトをシフトアラウンドしてそれらを加算するのと同じくらい簡単です。

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;
}

いくつかの癖を処理するために、この関数の前にもう 1 つの関数が必要です。キーが見つからないだけでなく、テーブル自体がいっぱいであることを示す NULL ポインターを返す場合があります。オーバーフル テーブル。これは実際には「完全に満杯」を意味しますが、「満杯」のテーブルには実際には 1 つの空の要素が必要であると以前に判断しました。これは、両方のforループが最後まで実行されないことを意味します。空のテーブル位置が見つかった場合、それは失敗です。テーブルがいっぱいになると、キーが存在しないことを発見する前にテーブル全体をスキャンする必要があるため、ハッシュを使用することによるパフォーマンスの利点の多くがまったく失われます。

ルックアップ関数は、空のスロットへの有効なポインターを返すこともできます。これも値が見つからないことですが、エラーではありません。初めてキーと値のペアを追加する場合、これはそれを格納するスロットになります。

または、目的のテーブル要素へのポインターを返すこともできます。これは、配列であろうと連結リストであろうと、線形検索よりも高速です。

テーブルからキーを削除するには、シーケンス内の空いた位置を埋める必要があります。いくつかのオプションがあります。

テーブルのスペースが不足する心配がない場合 (テーブルは非常に大きく設定されており、有効期間と使用量を制御できます)、空のキーとは異なり、削除された特別なキーでエントリを上書きできます。

または、スペースも再利用したい場合は、キーを検索してから、残りの「チェーン」(次の空のスロットまでのキーのシーケンス (ラップアラウンドを含む)) をスキャンして移動する必要があります。削除するキーの位置に一致するハッシュを持つ最後のキー。次に、この移動したキー/値の位置を空のキーで上書きします。.... おっとっと！チェーンの最後のキーを実際にクリアするまで、この最後の一致するキーに対してこのプロセスを繰り返す必要があります。(今すぐ実装でこれを修正する必要があります!....)

于 2013-11-11T05:50:18.223 に答える