配列内の整数を見つける最も速い方法は何ですか？

Question

問題：ユーザーID（整数）を指定すると、ユーザーが属するグループをすばやく見つけることができます。グループには15人以下のユーザーが含まれます。さらに、私は読み込みI/Oイベントに渡されるパラメータを制御できないlibevを使用しているので、userID（ファイル記述子/整数）は実際にはのものだけです。

私の解決策： groupIDとuserIDのペアを含むハッシュテーブルにユーザーIDを一度ハッシュします。 groupIDを2回ハッシュし、groupIDと15個のuserIDのペアの配列を含むハッシュテーブルにハッシュします。

解決策は機能しますが、これは不本意ながら実行されるサーバーコードです。二重ハッシングが非効率的で、より良い解決策があるかどうかは疑問です。

Answer 1

グループの配列でuserIDをソートし、バイナリ検索アルゴリズムを使用します。

groupidで同じことを行い、groupIDとユーザーIDの配列を含むクラスまたは構造体を作成します。

あなたのグループの配列を作成し、それらを追加するときに並べ替えるよりも、バイナリ検索アルゴリズムを再度使用してグループを検索してください。

---

編集：「ハッシュマップは、」常にデータ増加のあなたの量と同じ時間がかかりますしながら、

バイナリ検索は少量のデータのために良いかもしれません。

だからここ2つのソリューションの比較で別の質問へのリンクです：私はあなたが正しかったことを認めなければならないWhich is faster, Hash lookup or Binary search?

！

Answer 2

あなたは、libevには限られた量のデータしか与えられていないと言いますが、ev_ioはそれ自身を処理し、そこにはファイル記述子がすべて有益であると結論づけています。まあ、普通、あなたはおそらく正しいでしょうが、あなたができることはきちんとしたトリックがあります。

libevでは構造体を自分で割り当ててからlibevで初期化するので、を割り当てすぎることはありませんスペースです。 libevは余分なスペースに触れないので、そこにあなた自身のものを置くことができます。成功！

これは実際にどのように機能しますか？あなたが最初のメンバーとしてev_ioを含む新しい構造体を作成し、それの後にあなたのデータのすべての残りの部分を入れて、次のように言う：あなたはuv_ioを割り当てるどこ

今

struct my_mutant_io { 
    ev_io handle; 
    int group_id; 
}; 

が、代わりにmy_mutant_ioを割り当てます。あなたが好きしかし、そこにデータを入れて、あなたがlibuv関数にそれを渡す必要があります一度、だけではなく、handleのアドレス取る：

struct my_mutant_io *mutant = malloc(sizeof(struct my_mutant_io)); 
if(!mutant) { 
    abort(); 
} 
mutant->group_id = /* ... */; 
ev_io_init(&mutant, some_callback, fd, EV_READ); 

あなたはev_io libevは与えてくれたが、それはどれも、ですそれは実際にはより大きな構造体の一部に過ぎません。次に、コールバックに移りましょう。あなたはev_ioを元に戻しますが、待ってください！ev_ioは構造体の最初のメンバーなので、そのアドレスは突然変異体のアドレスと同じです。 ev_io *をstruct my_mutant_io *にキャストして使用することができます。 （ただ、厳格なエイリアシングの神々を教えていない。）

このような構造体は、最も一般的にバトンと呼ばれています。