-1

Cで保持する必要のあるソート済みリストを抽象化しました。一方の方法は読み取りに最適で、もう一方の方法は書き込みに最適です。

WRITE: search KeyNumeric then KeyAlpha and write *Data

Key1 : [ KeyA, *Data1A, KeyB, *Data1B, KeyC, *Data1C ]
Key2 : [ KeyA, *Data2A, KeyB, *Data2B, KeyC, *Data2C ]
Key3 : [ KeyA, *Data3A, KeyB, *Data3B, KeyC, *Data3C ]


READ: search KeyAlpha then KeyNumeric and read *Data

KeyA : [ Key1, *Data1A, Key2, *Data2A, Key3, *Data3A ]
KeyB : [ Key1, *Data1B, Key2, *Data2B, Key3, *Data3B ]
KeyC : [ Key1, *Data1C, Key2, *Data2C, Key3, *Data3C ]

このデータ構造をメモリで表現するための最も効率的な方法を誰かが認識していますか？

4

2 に答える 2

3

私が正しく理解している場合：

  • データには、数字とある種のアルファベットで構成される複合キーがあります（文字か文字列かはわかりません）。
  • アルファキーを持っていて、数値を検索する必要がある場合もあれば、その逆の場合もあります（たまたま読み取りと（上書き）書き込みが行われますが、それはおそらく重要ではありません）。
  • 挿入と削除はまれですが、サポートする必要があります。

また、データキーがスパースであると想定するため、単純な「[N][A]」配列は機能しません。

データに二重のインデックスを付けたいので、リストまたはツリーのいずれかのリンクされた構造が必要であることをお勧めします。

リンクリストでこれを行うには、C構造体は次のようになります。

struct stuff {
  int num_key;
  char alpha_key;

  /* The number-first lists.  */
  struct {
    struct stuff *next_num;
    struct stuff *next_alpha;
  } num_list;

  /* The alpha-first links.  */
  struct {
    struct stuff *next_alpha;
    struct stuff *next_num;
  } alpha_list;

  struct data Data;
};

したがって、データアイテムがある場合、1A, 1B, 1C, 2A, 2B, 2C, 3A, 3B, 3Cこれらのリンクは次のように機能します。

  • 1A num_list.next_numを指し2Aます。
  • 1A num_list.next_alphaを指し1Bます。
  • 1A num_alpha.next_alphaを指し1Bます。
  • 1A num_alpha.next_numを指し2Aます。
  • 2B num_list.next_numですNULL。
  • 2B num_list.next_alphaを指し2Cます。
  • 2B num_alpha.next_alphaですNULL。
  • 2B num_alpha.next_numを指し3Bます。

つまり、言葉で言えば、num_list.next_num常に次の番号の何かを指しますが、最初の文字が利用可能です。同様に、alpha_list.next_alpha常に次の文字で何かを指しますが、最初の数字が利用可能です。セカンダリリストの先頭を見ていない場合、プライマリリストへのポインタはNULL、データをそのようにトラバースしたくないためです。実際のポインタをそこに維持すると、バグが発生するか、挿入または削除時に余分なメンテナンスが発生します。 。

これは、リストの2つのリストと考えることができます。

  • num_list.next_numリストの先頭のnum_list.next_alphaリストです。
  • aplha_list.next_alphaリストの先頭のalpha_list.next_numリストです。

アイテムを見つけるには、最初にプライマリリストの1つ、num_list.next_numまたはを移動しaplha_list.next_alpha、次にセカンダリリストの1つ、またはを下にnum_list.next_alpha移動しますnum_alpha.next_num。

したがって、これには明らかにいくつかの効率の問題があります。

  • これらすべての小さなデータブロックのmallocは非効率的です。
  • リストはアクセスするO（n）です。

大量のデータを処理している場合、私は2つのことを行います。

  1. フラットリストの代わりに、ある種のバランスの取れたツリーを使用します。「リストの頭」は「木の根」になります。

  2. の固定サイズの配列を割り当て、struct stuffポインタの代わりに配列インデックスをリンクとして使用します。次に、未使用のスロットの「空きリスト」を維持するだけです。データが配列より大きくなる場合はrealloc、2番目のメモリブロックを使用または割り当て、どのインデックスがどのブロックにあるかを覚えておいてください。

于 2013-02-02T18:30:41.857 に答える
1

あなたが求めている複数のインデックスを処理する良い一般的な方法は、ペアのハッシュテーブルと、アルファキーと数値キーの順序が重要ではない可換ハッシュ関数を使用することです。

typedef struct hash_node_s {
  struct hash_node_s *next;
  char *keyAlpha;
  unsigned keyNumeric;
  void *data
} HASH_NODE, *HASH_NODE_PTR;

#define HASH_TABLE_SIZE 997
typedef HASH_NODE_PTR HASH_TABLE[HASH_TABLE_SIZE];

// Hash a string and integer in one value.
unsigned hash(char *keyAlpha, unsigned keyNumeric) {
  unsigned h = 0;
  for (int i = 0; keyAlpha[i]; i++) {
    h = h * 31 ^ keyAlpha[i] ^ keyNumeric;
    keyNumeric *= 31;
  }
  return h;
}

static HASH_NODE *find_or_insert(HASH_TABLE tbl, char *keyAlpha, unsigned keyNumeric) {
  unsigned h = hash(keyAlpha, keyNumeric) % HASH_TABLE_SIZE;
  for (HASH_NODE *p = tbl[h]; p; p = p->next)
    if (strcmp(keyAlpha, p->keyAlpha) == 0 && keyNumeric == p->keyNumeric)
      return p;
  HASH_NODE *n = safe_malloc(sizeof *n);
  n->next = tbl[h];
  n->keyAlpha = safe_strdup(keyAlpha);
  n->keyNumeric = keyNumeric;
  n->data = NULL;
  tbl[h] = n;
  return n;
}

void insert(HASH_TABLE tbl, char *keyAlpha, unsigned keyNumeric, void *data) {
  find_or_insert(keyAlpha, keyNumeric)->data = data;
}

void write(HASH_TABLE tbl, unsigned keyNumeric, char *keyAlpha, void *data) {
  find_or_insert(keyAlpha, keyNumeric)->data = data;
}

void *read(HASH_TABLE tbl, char *keyAlpha, unsigned keyNumeric) {
  return find_or_insert(keyAlpha, keyNumeric)->data;
}

void delete(HASH_TABLE tbl, char *keyAlpha, unsigned keyNumeric)
{
  unsigned h = hash(keyAlpha, keyNumeric) % HASH_TABLE_SIZE;
  for (HASH_NODE *q = NULL, *p = tbl[h]; 
       p; 
       q = p, p = p->next)
    if (strcmp(keyAlpha, p->keyAlpha) == 0 && keyNumeric == p->keyNumeric) {
      if (q) 
        q->next = p->next;
      else 
        tbl[h] = p->next;
      safe_free(p->keyAlpha);
      safe_free(p);
      return;
    }
}

このコードはテストされていませんが、マイナーなタイプミスを除いて信頼できるはずです。

すべての操作のコストはほぼ同じです。ハッシュ関数の計算は、キーの長さに依存します。これを除いて、すべての操作は確率的にO（1）です。つまり、ハッシュ関数が疑似ランダム結果を生成しないという悪いケースに遭遇したり、テーブルの読み込みが高くなりすぎたりしない限り、これは確かに非常に高速です。

このコードの弱点は、要素ごとに2つのキーを格納し、文字列キーが任意に大きくなる可能性があることです。ただし、これは別の文字列テーブル（文字列のハッシュテーブル）を使用して修正できるため、重複する文字列は同じポインタで表されます。文字列テーブルの挿入と削除（参照カウントがゼロに達したとき）は、safe_strdupとのfree呼び出しを置き換えます。他のすべての場合、コードは同じままです。これにより、ストレージのオーバーヘッドは整数とデータ項目ごとのポインタになります。

于 2013-02-04T18:23:49.193 に答える