私が行っているこのプログラムは、ソーシャル ネットワークに関するもので、ユーザーとそのプロファイルが存在することを意味します。プロファイル構造はUserProfile.
現在、考えられるさまざまなグラフの実装があり、最適なものを使用しているとは思いません。私はGraph構造を持っており、内部には type のリンクされたリストへのポインタがありますVertex。各Vertex要素には、値、次Vertexへのポインター、および type のリンクされたリストへのポインターがありますEdge。各Edge要素には、値 (重みと必要なものを定義できるようにするため)、次Edgeへのポインター、およびVertex所有者へのポインターがあります。
(CSV スタイルで) 処理してグラフに挿入するデータを含む 2 つのサンプル ファイルがあります。1 つ目はユーザー データ (1 行に 1 人のユーザー) です。2 つ目はユーザー関係 (グラフ用) です。最初のファイルはすぐにグラフに挿入されます。これは、私が常に先頭に挿入するためです。約 18000 人のユーザーがいます。2 番目のファイルは時間がかかりますが、それでも先頭にエッジを挿入します。このファイルには約 520000 行のユーザー関係が含まれており、グラフに挿入するのに 13 ～ 15 分かかります。簡単なテストを行ったところ、データの読み取りは非常に速く、瞬時に行われました。問題は挿入にあります。
この問題は、頂点のリンク リストを使用して実装されたグラフがあるために発生します。リレーションを挿入する必要があるたびに、それらをリンクできるように 2 つの頂点を検索する必要があります。これが問題です...〜520000のリレーションに対してこれを行うには、しばらく時間がかかります。
これをどのように解決すればよいですか？
解決策 1)グラフ (頂点部分) をリンク リストではなく配列として実装することを勧める人がいます。このようにして、すべての頂点に直接アクセスできるようになり、挿入が大幅に減少する可能性があります。しかし、配列に [18000] 個の要素を割り当てるという考えは好きではありません。これはどれくらい実用的ですか？私のサンプル データは ~18000 ですが、それよりも少ない場合や多い場合はどうすればよいですか? リンクされたリストのアプローチにはその柔軟性があり、メモリがある限り、好きなサイズにすることができます。しかし、配列はそうではありません。そのような状況をどのように処理しますか? あなたの提案は何ですか？
リンクされたリストの使用は、空間の複雑さには適していますが、時間の複雑さには適していません。また、配列の使用は時間の複雑さには適していますが、空間の複雑さには適していません。
このソリューションについて何か考えはありますか？
解決策 2)このプロジェクトでは、名前インデックスと ID インデックスに基づいてすばやく検索できる、ある種のデータ構造も必要です。このために、ハッシュ テーブルを使用することにしました。私のテーブルは、衝突解決として個別の連鎖を使用して実装されており、負荷係数が 0.70 に達すると、通常はテーブルを再作成します。次のテーブル サイズは、このLinkに基づいています。
現在、両方のハッシュ テーブルはUserProfile、ユーザー プロファイル自体を複製する代わりに、へのポインターを保持しています。それはばかげています。データを変更するには 3 つの変更が必要であり、そのようにするのは本当にばかげています。そのため、ポインターを に保存するだけUserProfileです。同じユーザー プロファイル ポインターも、各 Graph に値として保存されますVertex。
したがって、1 つのグラフと 2 つのハッシュ テーブルの 3 つのデータ構造があり、それらのすべてが同じ正確な を指していUserProfileます。グラフ構造は、最短パスなどを見つける目的に役立ちますが、ハッシュ テーブルは名前と ID によるクイック インデックスとして機能します。
グラフの問題を解決するために考えているのは、ハッシュ テーブルの値を に向けるのではなくUserProfile、対応する に向けることVertexです。それはまだポインターであり、使用されるスペースは多かれ少なかれありません。ポイントするものを変更するだけです。
このように、必要な各頂点を簡単かつ迅速に検索して、それらをリンクすることができます。これにより、~520000 のリレーションがすばやく挿入されます。
このソリューションを考えたのは、既にハッシュ テーブルがあり、それらが必要なためです。それなら、ユーザー プロファイルの代わりにグラフ頂点のインデックス作成にそれらを利用してみませんか? それは基本的に同じことです。私はまだUserProfile非常に迅速にアクセスできます.VertexUserProfile
しかし、最初のソリューションに対するこの 2 番目のソリューションの短所はありますか? それとも、最初のソリューションの長所と短所を圧倒する長所だけですか?
その他の解決策) 他に解決策があれば、私はすべて耳にします。しかし、前の 2 に対するそのソリューションの長所と短所を説明してください。私は今、これで無駄にしている時間があまりありません。このプロジェクトを進める必要があるので、そのようなことをしている場合変更する場合、何を変更する必要があるか、それが本当に正しいかどうかを正確に理解する必要があります。
これを読んで居眠りしてブラウザを閉じた人がいないことを願っています。しかし、私は本当にこれについて何をすべきかを決める必要があり、私は本当に変更を加える必要があります.
PS:私が提案した解決策に答えるときは、私と同じようにそれらを列挙してください。そうすれば、あなたが何を話しているのかが正確にわかり、自分自身をこれまで以上に混乱させないようにすることができます。