logo标签列表

高效存储、查找和操作大型无向图

c#performancedata-structuresgraphhashset
3
我有一个无向图G，大约有5000个节点。任何一对节点都可以通过边相连。边的长度、方向或其他特征都不重要，并且两点之间最多只能有一条边，因此节点之间的关系是二元的。因此，总共有12497500个潜在的边。
每个节点由一个字符串名称而非数字标识。
我想存储这样的图（作为输入数据加载到我的程序中），但我不确定哪种数据结构最好。
  • 我需要多次查找给定节点对是否连接，因此查找性能可能是主要问题。
  • 添加和删除元素的性能成本不是问题。
  • 如果可能的话，我还希望保持语法简单优雅，以减少引入错误并使调试更容易。
两个可能的选择：

  • bool[numNodes, numNodes]和Dictionary<string, int>匹配每个节点名称到一个索引。优点：简单，查找快速。缺点：不能轻松地添加或删除节点（必须添加/删除行/列），冗余（必须小心处理g[n1, n2]与g[n2, n1]），语法笨拙，因为我必须每次都通过HashMap。

  • HashSet<HashSet<string>>。优点：直观，节点直接由字符串标识，易于“添加/删除节点”，因为只存储边缘，而节点本身是隐含的。缺点：可能输入垃圾数据（边连接三个节点，因为集合有三个成员）。

关于第二个选项，我还不清楚以下几点：
  1. 它是否需要比一个bool数组更多的内存？
  2. 两个.NET集合是否相当于数学集合，即只有在具有完全相同成员的情况下才相等（而不是通过容量或元素顺序等区分）用于HashSet成员身份验证？（即使用outerSets.Contains(new HashSet<string>{"node1", "node2"})查询实际上会起作用吗？）
  3. 查找是否要比bool数组慢？
1
当然。n个人之间的握手数。对于这种类型的问题，哈希表非常快，但比数组慢得多。将操作抽象成一个接口，而不是在客户端代码中直接处理边缘查找/操作，这样，如果你的第一次实现似乎有些老旧，你可以将其替换为完全不同的后端，而不必重写使用它的代码。如果速度很关键，并且内存充足，则数组似乎是最佳选择，但十倍的节点意味着100倍的内存。测试、测试，再测试。 - spender
2
你预计节点字符串标识符的平均长度是多少？如果它们不太长，并且由于边是无向的，那么将(node1, node2)坐标规范化为单个键值可能不会太昂贵，可以在单个哈希表中用作后续查找。例如，基于字符串比较：string key = (node1 < node2) ? node1+node2 : node2+node1; - Monroe Thomas
＠MonroeThomas 在我的情况下，我并没有看到超过10个字符的名称，当然也不会有20个。绝大多数（或许全部）都是由7个字母和数字（大写字母和数字）组成的。 - Superbest
2
outerSets.Contains(new HashSet<string>{"node1", "node2"}) 不起作用。如果这样做，事情会变得混乱，因为这意味着更改集合中的项可能会破坏项唯一性的约定。HashSet仅按引用比较，而不是其中包含的值。在HashSet中使用.SetEquals进行比较将是更好的方法。 - spender
即使没有规范化和字符串连接，我们也可以创建一个具有正确相等性和哈希方法的数据结构，作为单个哈希表中的查找。但是，参与相等性和哈希的成员必须是不可变的。 - spender
显示剩余2条评论
2个回答
1

我对使用字符串拼接与元组在生成哈希表中表示边的键时，以 O(1) 的查找性能为目标的方法感到好奇。在处理无向边的要求时有两种可能：

  1. 规范化键，使其在边的描述中指定哪个节点是第一个组件时保持一致。在我的测试中，我只选择将具有最低序数比较值的节点作为键的第一个组件。

  2. 在哈希表中创建两个条目，一个用于每个方向的边。

这里的一个关键假设是字符串节点标识符不是很长，因此与查找相比，键规范化的成本较低。

字符串拼接和带键规范化元组版本似乎效果差不多：在 release 模式下，在 VirtualBox VM 中完成了约 200 万次随机查找，耗时约 3 秒。

为了确定键规范化是否掩盖了查找操作的影响，第三个实现不进行键规范化，但是对于边的两个可能方向保持对称条目。这似乎比查找慢30-40％左右，这让我稍微感到意外。也许基础哈希表桶由于有两倍的元素数量而具有更高的平均占用率，在每个哈希桶内需要更长的线性搜索（平均而言）？
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();
    }
}
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接