アルゴリズム - naobe @ ウィキ

ソフトウェア共通に戻る

トポロジカルソート

http://www.geocities.jp/oraclesqlpuzzle/csharp/csharp-8-18.html　参照

閉路のない有向グラフ(Directed Acyclic Graph)(DAG)をソートする。結合ノードごとに経路をソートする。ジョブの実行順序を求めるために使う。

ハッシュ

SDBM

http://www.cse.yorku.ca/~oz/hash.html 参照

sdbm（ndbmのpublic domain reimplimentation）データベースライブラリ用に作成された。ビットスクランブルが良い。
実質の機能は、hash(i) = hash(i - 1) * 65599 + str[i]。バークレーDBでは以下のアルゴリズムを使っている、

   static unsigned long
   sdbm(str)
   unsigned char *str;
   {
       unsigned long hash = 0;
       int c;
  
       while (c = *str++)
           hash = c + (hash << 6) + (hash << 16) - hash;
  
       return hash;
   }