グラフ構造 (挿入が非常に遅い) を変更するにはどうすればよいですか?

Question

私がやっているこのプログラムはソーシャル ネットワークに関するもので、ユーザーとそのプロフィールが存在します。プロファイルの構造は次のとおりです UserProfile.

現在、さまざまな可能な Graph 実装があり、私が最適なものを使用しているとは思えません。私は持っています Graph 構造体と内部には、タイプのリンクされたリストへのポインタがあります。 Vertex. 。それぞれ Vertex 要素には値、次の要素へのポインタがあります。 Vertex およびタイプのリンクされたリストへのポインタ Edge. 。それぞれ Edge 要素には値 (重みや必要なものを定義できる)、次の要素へのポインタがあります。 Edge そして、へのポインタ Vertex 所有者。

(CSV スタイルで) 処理してグラフに挿入するデータを含む 2 つのサンプル ファイルがあります。最初のデータはユーザー データ (1 行に 1 人のユーザー) です。2 つ目はユーザー関係 (グラフ用) です。最初のファイルはすぐにグラフに挿入されます。これは、私は常に先頭に挿入しており、ユーザー数が約 18000 人であるためです。2 番目のファイルには時間がかかりますが、それでも先頭にエッジを挿入します。このファイルには約 520,000 行のユーザー リレーションがあり、グラフに挿入するのに 13 ～ 15 分かかります。簡単なテストを行ったところ、データの読み取りは非常に速く、本当に瞬時に行われました。問題は挿入部分にあります。

この問題は、頂点のリンク リストを使用して実装されたグラフがあるために発生します。リレーションを挿入する必要があるたびに、2 つの頂点を検索して、それらをリンクできるようにする必要があります。これが問題です...約 520,000 のリレーションに対してこれを行うと、時間がかかります。

これはどうやって解決すればいいのでしょうか？

解決策 1) グラフ (頂点部分) をリンク リストではなく配列として実装することを勧めた人もいます。この方法では、すべての頂点に直接アクセスできるため、挿入はおそらく大幅に低下します。しかし、[18000] 個の要素を含む配列を割り当てるという考えは好きではありません。これはどの程度現実的なのでしょうか?私のサンプル データには ~18000 がありますが、必要なデータがそれより少ない場合、またはもっと多い場合はどうすればよいでしょうか?リンク リストのアプローチには柔軟性があり、メモリがある限り、必要なサイズを自由に設定できます。しかし、配列はそうではありません。そのような状況にどう対処すればよいでしょうか?あなたの提案は何ですか?

リンク リストの使用は、空間の複雑さには適していますが、時間の複雑さには悪影響を及ぼします。また、配列の使用は、時間の複雑さには良いですが、空間の複雑さには悪影響を及ぼします。

この解決策について何か考えはありますか?

解決策 2) このプロジェクトでは、名前インデックスと ID インデックスに基づいた素早い検索を可能にする、ある種のデータ構造も必要です。このために、ハッシュ テーブルを使用することにしました。私のテーブルは衝突解決として個別のチェーンを使用して実装されており、負荷係数 0.70 に達すると、通常はテーブルを再作成します。次のテーブルのサイズはこれに基づいています http://planetmath.org/encyclopedia/GoodHashTablePrimes.html.

現在、両方のハッシュ テーブルは、 UserProfile ユーザープロファイル自体を複製するのではなく、それは愚かなことです。データを変更するには 3 回の変更が必要であり、そのように行うのは本当に愚かです。したがって、ポインタを UserProfile. 。同じユーザー プロファイル ポインタも各グラフの値として保存されます。 Vertex.

つまり、3 つのデータ構造、1 つのグラフと 2 つのハッシュ テーブルがあり、それらのすべてがまったく同じものを指しています。 UserProfile. 。グラフ構造は最短パスなどを見つける目的で使用され、ハッシュ テーブルは名前と ID による迅速なインデックスとして機能します。

グラフの問題を解決するために私が考えているのは、ハッシュ テーブルの値が UserProfile, 、対応するものを指します Vertex. 。これはまだポインターであり、使用されるスペースはそれ以上も少なくもありません。指すものを変更するだけです。

このように、必要な各頂点を簡単かつ迅速に検索し、それらをリンクすることができます。これにより、~520000 のリレーションが非常に迅速に挿入されます。

私がこの解決策を思いついたのは、すでにハッシュ テーブルを持っていて、それが必要だったからです。それなら、ユーザー プロファイルの代わりにグラフ頂点のインデックス付けにそれを利用してみてはどうでしょうか?基本的には同じなので、引き続きアクセスできます UserProfile すぐに、に行ってください。 Vertex そして、へ UserProfile.

しかし、最初の解決策に対して、この 2 番目の解決策には欠点があると思いますか?それとも、最初の解決策の長所と短所を圧倒する長所だけでしょうか?

他の解決策) 他に解決策があれば、何でもお待ちしています。ただし、前の 2 つの解決策と比べて、その解決策の長所と短所を説明してください。今、これに無駄にしている時間はあまりありません。このプロジェクトを進めなければなりません。そのため、そのような変更を行う場合は、何を変更する必要があるのか​​、そしてそれが本当に変更なのかを正確に理解する必要があります。進むべき道。

これを読んで居眠りしてブラウザを閉じてしまう人がいないことを祈りますが、重大な遺言で申し訳ありません。しかし、私はこれに対して何をすべきかを本当に決める必要があり、本当に変化を起こす必要があります。

追伸： 私が提案した解決策に答えるときは、私と同じように列挙してください。そうすれば、あなたが何を言っているのか正確にわかり、これ以上混乱しないようになります。

Answer 1

最初のアプローチは、ここでの主な問題は速度ですので、私は配列のアプローチを好むです。

あなたは、もちろん、名前、インデックスの検索にハッシュテーブルを維持する必要があります。

私が正しく理解している場合、

、あなただけのデータを一度に処理。だから、何の動的データ挿入はありません。

スペースの割り当ての問題に対処するために、私はお勧めします。

1 - 。読むのファイルに一度、頂点の数を取得するには、

2 - そのスペースを割り当てる

あなたのデータが動的である場合は、

、あなたは50％の段階で、配列のサイズをインクリメントするためにいくつかの簡単な方法を実装することができます。

3 - エッジでは、あなたの代わりには、配列のためのリンクリスト。このアレイは、動的に、50％のステップでインクリメントされるべきである。

あなたが50％の段階でサイズをインクリメントする場合であっても割り当てられた「余分な」スペースで、配列が使用する合計サイズが唯一のリンクリストのサイズよりもわずかに大きくする必要があります。

私は私が助けることを願っています。