c# - 大規模な無向グラフの効率的な格納、検索、および操作

Question

約5000ノードの無向グラフGがあります。ノードの任意のペアをエッジで接続できます。エッジの長さ、方向、またはその他の特徴は無関係であり、2 つの点の間に存在できるエッジは多くても 1 つであるため、ノード間の関係はバイナリです。したがって、合計 12497500 の潜在的なエッジがあります。

各ノードは、番号ではなく文字列名で識別されます。

このようなグラフ (入力データとしてプログラムに読み込まれる) を保存したいのですが、どのようなデータ構造が最適かわかりません。

特定のノードのペアが接続されているかどうかを何度も検索する必要があるため、検索のパフォーマンスがおそらく主な関心事です。
要素の追加と削除のパフォーマンスコストは問題になりません。
また、バグが発生する可能性を減らし、デバッグを容易にするために、構文を可能な限りシンプルかつエレガントに保ちたいと考えています。

2 つの可能性:

bool[numNodes, numNodes]a は、Dictionary<string, int>各ノード名をインデックスに一致させます。長所: シンプルで高速なルックアップ。短所：ノードを簡単に削除または追加できない（行/列を追加/削除する必要がある）、冗長（g[n1, n2]vsに注意する必要があるg[n2, n1]）、毎回 HashMap を通過する必要があるため構文がぎこちない。
HashSet<HashSet<string>>. 長所: 直観的で、ノードは文字列で直接識別され、エッジのみが保存され、ノード自体は暗黙的であるため、「ノードの追加/削除」が簡単です。短所: ガベージ入力を入力する可能性があります (セットには 3 つのメンバーがあるため、3 つのノードを「接続」するエッジ)。

2番目のオプションに関しては、いくつかの点についても不明です。

の配列よりもはるかに多くのメモリが必要boolですか?
2 つの .NET セットは、メンバーシップの目的で (要素の容量や順序などによって区別されるのではなく) まったく同じメンバーを持っている場合にのみ等しいという意味で、数学的なセットと同等HashSetですか? (つまり、クエリはouterSets.Contains(new HashSet<string>{"node1", "node2"})実際に機能しますか?)
検索はの配列よりもはるかに時間がかかりboolますか?

score 1 · Accepted Answer

O(1) ルックアップのパフォーマンスに近づけるために、ハッシュテーブルのエッジを表すキーを生成するときに、文字列連結とタプルを使用することに興味がありました。ここで、無向辺の要件を処理するための 2 つの可能性があります。

エッジの記述でどのノードを最初に指定しても同じになるようにキーを正規化します。私のテストでは、序数の比較値が最も低いノードをキーの最初のコンポーネントとして選択するだけです。
エッジの各方向に 1 つずつ、ハッシュテーブルに 2 つのエントリを作成します。

ここでの重要な前提は、文字列ノード識別子がそれほど長くないため、検索に比べてキーの正規化が低コストであるということです。

キーの正規化を使用した文字列連結とタプルバージョンは、ほぼ同じように機能するようです。リリースモードの VirtualBox VM で、約 3 秒で約 200 万回のランダムルックアップが完了していました。

キーの正規化がルックアップ操作の効果を圧倒していたかどうかを確認するために、3 番目の実装ではキーの正規化を行わず、エッジの可能な両方の方向に関して対称エントリを維持します。これはルックアップで約 30 ～ 40% 遅くなるようですが、これは (私にとっては) 少し予想外でした。おそらく、基礎となるハッシュテーブルバケットは、要素数が 2 倍あるために平均占有率が高く、各ハッシュバケット内で (平均して) より長い線形検索が必要になるのでしょうか?

interface IEdgeCollection
{
    bool AddEdge(string node1, string node2);
    bool ContainsEdge(string node1, string node2);
    bool RemoveEdge(string node1, string node2);
}

class EdgeSet1 : IEdgeCollection
{
    private HashSet<string> _edges = new HashSet<string>();

    private static string MakeEdgeKey(string node1, string node2)
    {
        return StringComparer.Ordinal.Compare(node1, node2) < 0 ? node1 + node2 : node2 + node1;
    }

    public bool AddEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Add(key);
    }

    public bool ContainsEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Contains(key);
    }

    public bool RemoveEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Remove(key);
    }
}

class EdgeSet2 : IEdgeCollection
{
    private HashSet<Tuple<string, string>> _edges = new HashSet<Tuple<string, string>>();

    private static Tuple<string, string> MakeEdgeKey(string node1, string node2)
    {
        return StringComparer.Ordinal.Compare(node1, node2) < 0 
            ? new Tuple<string, string>(node1, node2) 
            : new Tuple<string, string>(node2, node1);
    }

    public bool AddEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Add(key);
    }

    public bool ContainsEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Contains(key);
    }

    public bool RemoveEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Remove(key);
    }
}

class EdgeSet3 : IEdgeCollection
{
    private HashSet<Tuple<string, string>> _edges = new HashSet<Tuple<string, string>>();

    private static Tuple<string, string> MakeEdgeKey(string node1, string node2)
    {
        return new Tuple<string, string>(node1, node2);
    }

    public bool AddEdge(string node1, string node2)
    {
        var key1 = MakeEdgeKey(node1, node2);
        var key2 = MakeEdgeKey(node2, node1);
        return _edges.Add(key1) && _edges.Add(key2);
    }

    public bool ContainsEdge(string node1, string node2)
    {
        var key = MakeEdgeKey(node1, node2);
        return _edges.Contains(key);
    }

    public bool RemoveEdge(string node1, string node2)
    {
        var key1 = MakeEdgeKey(node1, node2);
        var key2 = MakeEdgeKey(node2, node1);
        return _edges.Remove(key1) && _edges.Remove(key2);
    }
}

class Program
{
    static void Test(string[] nodes, IEdgeCollection edges, int edgeCount)
    {
        // use edgeCount as seed to rng to ensure test reproducibility
        var rng = new Random(edgeCount);

        // store known edges in a separate data structure for validation
        var edgeList = new List<Tuple<string, string>>();

        Stopwatch stopwatch = new Stopwatch();

        // randomly generated edges
        stopwatch.Start();
        for (int i = 0; i < edgeCount; i++)
        {
            string node1 = nodes[rng.Next(nodes.Length)];
            string node2 = nodes[rng.Next(nodes.Length)];
            edges.AddEdge(node1, node2);
            edgeList.Add(new Tuple<string, string>(node1, node2));
        }
        var addElapsed = stopwatch.Elapsed;

        // non random lookups
        int nonRandomFound = 0;
        stopwatch.Start();
        foreach (var edge in edgeList)
        {
            if (edges.ContainsEdge(edge.Item1, edge.Item2))
                nonRandomFound++;
        }
        var nonRandomLookupElapsed = stopwatch.Elapsed;
        if (nonRandomFound != edgeList.Count)
        {
            Console.WriteLine("The edge collection {0} is not working right!", edges.GetType().FullName);
            return;
        }

        // random lookups
        int randomFound = 0;
        stopwatch.Start();
        for (int i = 0; i < edgeCount; i++)
        {
            string node1 = nodes[rng.Next(nodes.Length)];
            string node2 = nodes[rng.Next(nodes.Length)];
            if (edges.ContainsEdge(node1, node2))
                randomFound++;
        }
        var randomLookupElapsed = stopwatch.Elapsed;

        // remove all
        stopwatch.Start();
        foreach (var edge in edgeList)
        {
            edges.RemoveEdge(edge.Item1, edge.Item2);
        }
        var removeElapsed = stopwatch.Elapsed;

        Console.WriteLine("Test: {0} with {1} edges: {2}s addition, {3}s non-random lookup, {4}s random lookup, {5}s removal",
            edges.GetType().FullName,
            edgeCount,
            addElapsed.TotalSeconds,
            nonRandomLookupElapsed.TotalSeconds,
            randomLookupElapsed.TotalSeconds,
            removeElapsed.TotalSeconds);
    }


    static void Main(string[] args)
    {
        var rng = new Random();

        var nodes = new string[5000];
        for (int i = 0; i < nodes.Length; i++)
        {
            StringBuilder name = new StringBuilder();
            int length = rng.Next(7, 15);
            for (int j = 0; j < length; j++)
            {
                name.Append((char) rng.Next(32, 127));
            }
            nodes[i] = name.ToString();
        }

        IEdgeCollection edges1 = new EdgeSet1();
        IEdgeCollection edges2 = new EdgeSet2();
        IEdgeCollection edges3 = new EdgeSet3();

        Test(nodes, edges1, 2000000);
        Test(nodes, edges2, 2000000);
        Test(nodes, edges3, 2000000);

        Console.ReadLine();
    }
}

c# - 大規模な無向グラフの効率的な格納、検索、および操作

2 に答える 2

Related

Reference