0

ローエンドでは 2^12 のスペースから、ハイエンドでは 2^32 までサンプリングされた最大 15000 個の符号なし整数をハッシュする必要があります。逆引き用のインデックスも保存する必要があります。C++ STL を使用した単純な例は次のようになります。

std::map<unsigned int, std::set<unsigned int /* unique indices */> > m;

密なケースでは、これを次のように考えることができます。

std::vector<std::set<unsigned int /* unique indices */> > v;

さて、問題です。ここでは速度が最も重要な要素ですが、メモリに関してはまだ制限があります。これらのマップを 1000 個メモリに格納し、低レイテンシ アプリケーションで高速にアクセスする必要があります。クエリを実行する必要があります。ナノ秒の。

現在、密な方法を使用してデータを保存しています。ただし、ハッシュする必要があるキーの範囲を 2^32 に増やしたいと思います。これにより、密な方法が問題になります。覚えておいてください、マップには最大 15000 個のキーを保存するだけで済みます。

プラス面としては、マップが構築されると、二度とマップに何も挿入しません。後で照会するだけです。挿入は依然としてかなり高速である必要がありますが、クエリほど重要ではありません。

私が実験したいくつかのコードは次のとおりです。

Google SparseHash
Google DenseHash
STL unordered_map
STL マップ

独自のハッシュ テーブルを作成してもかまいません。自分で取り組む前に、専門家のアドバイスを得たかったのです。

4

1 に答える 1

0

平均 GET 操作は、1024 エントリ (メモリ内 349KB) の 189ns から 27,648 エントリ (メモリ内 6MB) の 888ns の範囲で 1 ミリ秒未満である必要があります。27k エントリのエントリの最大レイテンシは 44,000ns です。ただし、平均時間が重要であり、レイテンシがそれほど高くない場合は、基本的にこれが必要な場合があります. さらに最適化できると思いますが、得られる利益はわかりません。

typedef unsigned int uintptr;
typedef unsigned int uint32;
typedef unsigned short uint16;
typedef unsigned char uint8;


namespace anything { namespace linklist {
typedef struct _HDR {
    void              *next;
    void              *prev;
} HDR;

void *next(void *ptr) {
    if (ptr == 0) {
        return 0;
    }
    return ((void**)ptr)[0];
}

void add(void **chain, void *toadd) {
    ((void**)toadd)[0] = *chain;
    ((void**)toadd)[1] = 0;         /* set previous */

    /* set previous link if valid pointer */
    if (*chain)
        ((void**)*chain)[1] = toadd;

    *chain = toadd;
}
}}

namespace anything{ namespace hash {
   typedef struct _B {
      MASS_LL_HDR    llhdr;
      uint32         id;
      union {
         struct _B    *chain;
         uintptr      value;
      };
   } B;

   typedef struct _HT {
      B        *buckets;
      uint16   depth;
      uint8    bbl;
   } HT;

   void init(HT *ht, uint8 bbl) {
      ht->buckets = 0;
      ht->bbl = bbl;
   }

   void _free(B **chain, uint16 dcnt, uint16 dcntmax, uint32 *_m) {
      B        *ba, *_ba;

      for (ba = *chain, _ba = 0; ba; ba = _ba) {
         _ba = (B*)mass_ll_next(ba);

         if (dcnt < dcntmax - 1) {
            _free(&ba->chain, dcnt + 1, dcntmax, _m);
            *_m = *_m + 1;
            dfree(ba);
         }
      }

      /* zero the chain out */
      *chain = 0;
   }

   void free(HT *ht) {
      uint32      m;
      uint16      dm;

      dm = (sizeof(uintptr) * 8) / ht->bbl;
      m = 0;

      _free(&ht->buckets, 0, dm, &m);
   }

   int get(HT *ht, uintptr k, uintptr *v) {
      uintptr        a;
      B             *ba, **cur;

      uint16         bi, lcnt;
      uint32         mask;

      lcnt = (sizeof(uintptr) * 8) / ht->bbl;

      cur = &ht->buckets;

      mask = ~(~0 << ht->bbl);

      for (bi = 0; bi < lcnt; ++bi) {

         a = (k >> (bi * ht->bbl)) & mask;

         for (ba = *cur; ba; ba = (B*)mass_ll_next(ba)) {
            if (ba->id == a) {
               break;
            }
         }

         if (!ba) {
            return 0;
         }

         cur = &ba->chain;
      }

      *v = ba->value;
      return 1;
   }

   void put(HT *ht, uintptr k, uintptr v) {
      uintptr       a;
      B             *ba, **cur;

      uint16         bi, lcnt;
      uint32         mask;

      lcnt = (sizeof(uintptr) * 8) / ht->bbl;

      cur = &ht->buckets;

      mask = ~(~0 << ht->bbl);

      for (bi = 0; bi < lcnt; ++bi) {

         a = (k >> (bi * ht->bbl)) & mask;

         for (ba = *cur; ba; ba = (B*)mass_ll_next(ba)) {
            if (ba->id == a) {
               break;
            }
         }

         if (!ba) {
            ba = (B*)dmalloc(sizeof(B));
            ba->id = a;
            ba->chain = 0;
            mass_ll_add((void**)cur, ba);
         }

         cur = &ba->chain;
      }

      ba->value = v;
   }
}}

anything::hash::HT      ht;
anything::hash::init(&ht, 1);
anything::hash::put(&ht, key, value);
if (!anything::hash::get(&ht, key, &value) {
   printf("not found!\n");
}

Anything::hash::init(&ht, 4) を使用すると、メモリ使用量を 15000 エントリあたり約 900kb に減らすことができますが、これによりレイテンシが増加します。

于 2013-11-24T19:00:12.267 に答える