通过并行执行将列表与自身进行比较

Question

我有以下代码，我用到现在为止通过哈希码将文件条目列表与 itsef 进行比较

    for (int i = 0; i < fileLists.SourceFileListBefore.Count; i++) // Compare SourceFileList-Files to themselves
            {
                for (int n = i + 1; n < fileLists.SourceFileListBefore.Count; n++) // Don´t need to do the same comparison twice!
                {
                    if (fileLists.SourceFileListBefore[i].targetNode.IsFile && fileLists.SourceFileListBefore[n].targetNode.IsFile)
                        if (fileLists.SourceFileListBefore[i].hash == fileLists.SourceFileListBefore[n].hash)
                        {
                            // do Something
                        }
                }
            }

其中 SourceFileListBefore 是一个列表

我想更改此代码以能够在多个内核上并行执行。我想过用 PLINQ 来做这件事，但我对 LINQ 完全陌生。

我试过了

      var duplicate = from entry in fileLists.SourceFileListBefore.AsParallel()
                            where fileLists.SourceFileListBefore.Any(x => (x.hash == entry.hash) && (x.targetNode.IsFile) && (entry.targetNode.IsFile))
                            select entry;

但它不会像这样工作，因为我必须为每对两个哈希码匹配条目执行代码。因此，我至少必须从 LINQ 获得带有 x+entry 的一组结果，而不仅仅是一个条目。 PLINQ 可以吗？

Answer 1

你为什么不先看看优化你的代码？

查看此声明：

if (fileLists.SourceFileListBefore[i].targetNode.IsFile && fileLists.SourceFileListBefore[n].targetNode.IsFile)

意味着您可以直接构建 1 个文件列表，其中 IsFile == true（已经使循环变小了）

其次，

if (fileLists.SourceFileListBefore[i].hash == fileLists.SourceFileListBefore[n].hash)

你为什么不先构建哈希的哈希查找。

然后遍历您的过滤列表，在您创建的查找中查找，如果它包含> 1，则表示存在匹配（当前节点哈希+一些其他节点哈希）。所以你只对不是你的节点的匹配哈希做一些工作。

我写了一篇关于它的博客post，你可以在@CodePERF[dot]NET -.NET Nested Loops vs Hash Lookups

阅读

PLINQ 只会略微改善您问题的糟糕解决方案。

添加了一些比较：

Total File Count: 16900
TargetNode.IsFile == true: 11900
Files with Duplicate Hashes = 10000 (5000 unique hashes)
Files with triplicate Hashes = 900 (300 unique hashes)
Files with Unique hashes = 1000

以及实际设置方法：

    [SetUp]
    public void TestStup()
    {
        _sw = new Stopwatch();
        _files = new List<File>();
        int duplicateHashes = 10000;
        int triplicateHashesCount = 900;
        int randomCount = 1000;
        int nonFileCount = 5000;

        for (int i = 0; i < duplicateHashes; i++)
        {
            var hash = i % (duplicateHashes / 2);
            _files.Add(new File {Id = i, Hash = hash.ToString(), TargetNode = new Node {IsFile = true}});
        }
        for (int i = 0; i < triplicateHashesCount; i++)
        {
            var hash = int.MaxValue - 100000 - i % (triplicateHashesCount / 3);
            _files.Add(new File {Id = i, Hash = hash.ToString(), TargetNode = new Node {IsFile = true}});
        }

        for (int i = 0; i < randomCount; i++)
        {
            var hash = int.MaxValue - i;
            _files.Add(new File { Id = i, Hash = hash.ToString(), TargetNode = new Node { IsFile = true } });
        }

        for (int i = 0; i < nonFileCount; i++)
        {
            var hash = i % (nonFileCount / 2);
            _files.Add(new File {Id = i, Hash = hash.ToString(), TargetNode = new Node {IsFile = false}});
        }
        _matched = 0;
    }

比你目前的方法：

    [Test]
    public void FindDuplicates()
    {
        _sw.Start();

        for (int i = 0; i < _files.Count; i++) // Compare SourceFileList-Files to themselves
        {
            for (int n = i + 1; n < _files.Count; n++) // Don´t need to do the same comparison twice!
            {
                if (_files[i].TargetNode.IsFile && _files[n].TargetNode.IsFile)
                    if (_files[i].Hash == _files[n].Hash)
                    {
                        // Do Work
                        _matched++;
                    }
            }
        }

        _sw.Stop();
    }

在我的机器上大约需要 7.1 秒。

使用查找查找多次出现的哈希需要 21 毫秒。

    [Test]
    public void FindDuplicatesHash()
    {
        _sw.Start();

        var lookup = _files.Where(f => f.TargetNode.IsFile).ToLookup(f => f.Hash);

        foreach (var duplicateFiles in lookup.Where(files => files.Count() > 1))
        {
            // Do Work for each unique hash, which appears multiple times in _files.

            // If you need to do work on each pair, you will need to create pairs from duplicateFiles
            // this can be an excercise for you ;-)
            _matched++;
        }

        _sw.Stop();
    }

在我的测试中，使用 PLINQ 来计算查找次数，实际上速度较慢（因为在线程之间划分列表和聚合结果的成本很高）

    [Test]
    public void FindDuplicatesHashParallel()
    {
        _sw.Start();

        var lookup = _files.Where(f => f.TargetNode.IsFile).ToLookup(f => f.Hash);

        _matched = lookup.AsParallel().Where(g => g.Count() > 1).Sum(g => 1);

        _sw.Stop();
    }

这花费了 120 毫秒，几乎是我当前源列表的 6 倍。

通过并行执行将列表与自身进行比较

Compare list to itself with parallel execution

c#

plinq