非常に大きなソーシャルネットワーキングのデータ構造を設計することを考えます。
二人のユーザ間のつながりを示すアルゴリズムをどのように設計すればいいでしょうか?
解答例
個々のユーザを一つのノードとして、お互いのユーザが友達であれば2つのノード間に辺を作る、という方法でグラフを作ります。
二人のユーザ間につながりがあるかどうか調べたい時は、一人のユーザーから始めて単純に幅優先探索を行います。
大規模なサービスの場合、一つのマシンに全てのデータを保持することはまず不可能です。
友達同士が同じマシン上にいないかもしれないからです。
そこで、代わりに友人のリストをIDのリストに置き換えて、次のように巡回する。
1 それぞれのIDに対して、int machine_index = getMachineIDForUser(personID);
2 machine_indexのマシンに移る
3 そのマシン上でPerson friend = getPersonWithID(person_id);
これが概略になります。
以下のコードはこの概略を実現しているだけなので、載せる必要はないかもしれないですが、一応載せておきます。
Java
1import java.util.HashMap; 2 3public class Server { 4 HashMap<Integer, Machine> machines = new HashMap<Integer, Machine>(); 5 HashMap<Integer, Integer> personToMachineMap = new HashMap<Integer, Integer>(); 6 7 public Machine getMachineWithId(int machineID) { 8 return machines.get(machineID); 9 } 10 11 public int getMachineIDForUser(int personID) { 12 Integer machineID = personToMachineMap.get(personID); 13 return machineID == null ? -1 : machineID; 14 } 15 16 public Person getPersonWithID(int personID) { 17 Integer machineID = personToMachineMap.get(personID); 18 if (machineID == null) { 19 return null; 20 } 21 Machine machine = getMachineWithId(machineID); 22 if (machine == null) { 23 return null; 24 } 25 return machine.getPersonWithID(personID); 26 } 27}
Java
1import java.util.ArrayList; 2 3public class Person { 4 private ArrayList<Integer> friends; 5 private int personID; 6 private String info; 7 8 public String getInfo() { return info; } 9 public void setInfo(String info) { 10 this.info = info; 11 } 12 13 public int[] getFriends() { 14 int[] temp = new int[friends.size()]; 15 for (int i = 0; i < temp.length; i++) { 16 temp[i] = friends.get(i); 17 } 18 return temp; 19 } 20 public int getID() { return personID; } 21 public void addFriend(int id) { friends.add(id); } 22 23 public Person(int id) { 24 this.personID = id; 25 } 26}
Java
1import java.util.HashMap; 2 3public class Machine { 4 public HashMap<Integer, Person> persons = new HashMap<Integer, Person>(); 5 public int machineID; 6 7 public Person getPersonWithID(int personID) { 8 return persons.get(personID); 9 } 10}
普通の幅優先探索ではノードクラスに調べたかどうかを記録するフラグを用意しますが、今回はそのようにはしたくありません。
同時に複数の探索が行われる可能性がありますので、データ自体を捜査する方法はよくないからです。
フラグを用意する代わりに、ハッシュテーブルを使ってノードの探索と探索済みかどうかのチェックを行うようにします。
ここで質問です。
「フラグを用意する代わりに、ハッシュテーブルを使ってノードの探索と探索済みかどうかのチェックを行うようにします。」
についてなんですが、どこかのクラスにハッシュテーブルを用意して、探索したPersonはそのハッシュテーブルに格納して、次に探索するPersonを決めるときにそのハッシュテーブルに格納されているかどうかで探索するかどうかを決めるということでしょうか?
そして、Personに対応させる値は探索済みかどうかを示す数字などが入ってくるのでしょうか?
もしこの方法でやるとするなら、この方法って早いのでしょうか?
フラグがあれば、基本的には0か1か(ここでは0と1にしましたが、いろいろなフラグがあると思います。)で0だったら探索、1だったら、次のPersonに進む、というようなことができると思うのですが、ハッシュテーブルに含まれているかどうかというのは高速に処理できるのでしょうか?
さらに、ハッシュテーブルに入れる意義もよくわかりません。
というのは、配列でも同様のことはできるように思えるからです。値として、フラグのようなものを設置するのは無駄なように思えます。
解答お願いします。
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2016/09/15 13:45
2016/09/16 08:01
退会済みユーザー
2016/09/17 02:16
2016/09/17 05:13
退会済みユーザー
2016/09/17 10:41
2016/09/17 15:31
退会済みユーザー
2016/09/18 09:12