时间戳

首页 > 解决方案 > 使用 c# 进行大量数量比较

c# - 使用 c# 进行大量数量比较

问题描述

数字集的比较太慢了。有什么更有效的方法来解决这个问题？

我有两组集合，每组大约有500万个集合，每组有6个数字，每个数字在1到100之间。集合和组没有排序和重复。

以下是示例。

No.     Group A                 Group B
1       {1,2,3,4,5,6}           {6,2,4,87,53,12}
2       {2,3,4,5,6,8}           {43,6,78,23,96,24}
3       {45,23,57,79,23,76}     {12,1,90,3,2,23}
4       {3,5,85,24,78,90}       {12,65,78,9,23,13}
        ...                     ...

我的目标是比较两组，并在我的笔记本电脑上按 5 小时内的最大常见元素数对 A 组进行分类。

在示例中，A 组的 1 号和 B 组的 3 号具有 3 个共同元素（1,2,3）。此外，A 组 2 号和 B 组 3 号具有 2 个共同元素 (2,3)。因此，我将A组分类如下。

No.     Group A             Maximum Common Element Count
1       {1,2,3,4,5,6}           3
2       {2,3,4,5,6,8}           3
3       {45,23,57,79,23,76}     1
4       {3,5,85,24,78,90}       2
        ...

我的方法是比较每个集合和数字，所以复杂度是 A 组计数 * B 组计数 * 6 * 6。因此需要很多时间。

Dictionary<int, List<int>> Classified = new Dictionary<int, List<int>>();
foreach (List<int> setA in GroupA)
{
    int maxcount = 0;
    foreach (List<int> setB in GroupB)
    {
        int count = 0; 
        foreach(int elementA in setA)
        {
            foreach(int elementB in setB)
            {
                if (elementA == elementB) count++;
            }
        }
        if (count > maxcount) maxcount = count;
    }
    Classified.Add(maxcount, setA);
}

标签： c#

解决方案

这是我的尝试 - 使用 aHashSet<int>并预先计算每个集合的范围以避免像{1,2,3,4,5,6}and那样的集合到集合的比较（正如马特的回答{7,8,9,10,11,12}所指出的那样）。

对我来说（使用随机集运行），它使原始代码的速度提高了 130 倍。你在评论中提到

现在执行时间超过 3 天，所以正如其他人所说我需要并行化。

在这个问题本身

我的目标是比较两组，并在我的笔记本电脑上按 5 小时内的最大常见元素数对 A 组进行分类。

所以假设评论意味着您的数据的执行时间超过了 3 天（72 小时），但您希望它在 5 小时内完成，您只需要提高 14 倍的速度。

框架

我创建了一些类来运行这些基准测试：

  • Range- 取一些int值，并跟踪最小值和最大值。

    public class Range
{
    private readonly int _min;
    private readonly int _max;

    public Range(IReadOnlyCollection<int> values)
    {
        _min = values.Min();
        _max = values.Max();
    }

    public int Min { get { return _min; } }
    public int Max { get { return _max; } }

    public bool Intersects(Range other)
    {
        if ( _min < other._max )
            return false;

        if ( _max > other._min )
            return false;

        return true;
    }
}

  • SetWithRange- 包装 aHashSet<int>和 aRange的值。

    public class SetWithRange : IEnumerable<int>
{
    private readonly HashSet<int> _values;
    private readonly Range _range;

    public SetWithRange(IReadOnlyCollection<int> values)
    {
        _values = new HashSet<int>(values);
        _range = new Range(values);
    }

    public static SetWithRange Random(Random random, int size, Range range)
    {
        var values = new HashSet<int>();

        // Random.Next(int, int) generates numbers in the range [min, max)
        // so we need to add one here to be able to generate numbers in [min, max].
        // See https://docs.microsoft.com/en-us/dotnet/api/system.random.next
        var min = range.Min;
        var max = range.Max + 1;

        while ( values.Count() < size )
            values.Add(random.Next(min, max));

        return new SetWithRange(values);
    }

    public int CommonValuesWith(SetWithRange other)
    {
        // No need to call Intersect on the sets if the ranges don't intersect
        if ( !_range.Intersects(other._range) )
            return 0;

        return _values.Intersect(other._values).Count();
    }

    public IEnumerator<int> GetEnumerator()
    {
        return _values.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

  • SetWithRange.Random使用如下方式生成结果：

    const int groupCount = 10000;
const int setSize = 6;

var range = new Range(new[] { 1, 100 });
var generator = new Random();

var groupA = Enumerable.Range(0, groupCount)
    .Select(i => SetWithRange.Random(generator, setSize, range))
    .ToList();

var groupB = Enumerable.Range(0, groupCount)
    .Select(i => SetWithRange.Random(generator, setSize, range))
    .ToList();

下面给出的时间是在我的机器上平均运行三个 x64 版本构建。

对于所有情况，我生成了具有 10000 个随机集的组，然后通过使用放大以近似 500 万组的执行时间

timeFor5Million = timeFor10000 / 10000 / 10000 * 5000000 * 5000000
                = timeFor10000 * 250000

结果

  • 四个foreach板块：

    平均时间=48628ms；500 万套的估计时间 = 3377 小时

    var result = new Dictionary<SetWithRange, int>();
foreach ( var setA in groupA )
{
    int maxcount = 0;
    foreach ( var setB in groupB )
    {
        int count = 0;
        foreach ( var elementA in setA )
        {
            foreach ( int elementB in setB )
            {
                if ( elementA == elementB )
                    count++;
            }
        }
        if ( count > maxcount ) maxcount = count;
    }
    result.Add(setA, maxcount);
}

  • Three foreach blocks with parallelisation on the outer foreach:

    Average time = 10305ms; estimated time for 5 million sets = 716 hours (4.7 times faster than original):

    var result = new Dictionary<SetWithRange, int>();
Parallel.ForEach(groupA, setA =>
{
    int maxcount = 0;
    foreach ( var setB in groupB )
    {
        int count = 0;
        foreach ( var elementA in setA )
        {
            foreach ( int elementB in setB )
            {
                if ( elementA == elementB )
                    count++;
            }
        }
        if ( count > maxcount ) maxcount = count;
    }

    lock ( result )
        result.Add(setA, maxcount);
});

  • Using HashSet<int> and adding a Range to only check sets which intersect:

    Average time = 375ms; estimated time for 5 million sets = 24 hours (130 times faster than original):

    var result = new Dictionary<SetWithRange, int>();
Parallel.ForEach(groupA, setA =>
{
    var commonValues = groupB.Max(setB => setA.CommonValuesWith(setB));
    lock ( result )
        result.Add(setA, commonValues);
});

    Link to a working online demo here: https://dotnetfiddle.net/Kxpagh (note that .NET Fiddle limits execution times to 10 seconds, and that for obvious reasons its results are slower than running in a normal environment).

推荐阅读