如何加速遍历百万值数组的过程？

Question

我在进行一项在线测试，需要实现一段代码来检查某个值是否在数组中。我编写了以下代码：

    using System;
    using System.IO;
    using System.Linq;

    public class Check
    {
        public static bool ExistsInArray(int[] ints, int val)
        {
            if (ints.Contains(val)) return true;
            else return false;
        }
    }

现在我认为这段代码没有问题，因为它可以正常运行，但是某种程度上我仍然未能通过测试，因为当数组包含一百万个值时，“速度不够快”。

我自己编写的唯一代码是：

    if (ints.Contains(val)) return true;
    else return false;

我需要处理的其它代码。

有没有办法加快这个过程的速度？

提前致谢。

编辑： 我发现有人似乎参加了与我相同的测试，而且似乎可以节省CPU周期。

参考：如何在搜索排序列表中的值时节省CPU周期？

现在他方法内的解决方案是：

    var lower = 0;
    var upper = ints.Length - 1;

    if ( k < ints[lower] || k > ints[upper] ) return false;
    if ( k == ints[lower] ) return true;
    if ( k == ints[upper] ) return true;

    do
    {
        var middle = lower + ( upper - lower ) / 2;

        if ( ints[middle] == k ) return true;
        if ( lower == upper ) return false;

        if ( k < ints[middle] )
            upper = Math.Max( lower, middle - 1 );
        else
            lower = Math.Min( upper, middle + 1 );
    } while ( true );

现在我明白了这段代码的作用，但我不清楚它为什么应该更快。如果有人能详细解释一下就好了。

- DLP

---

使用HashSet<int>代替int[]。此外，建议将该方法本身进行清理，因为可以编写return ints.Contains.val);，如果您这样做了，为什么不直接在调用代码中编写它呢？ - Igor

数组是否已排序？ - Chetan

你应该添加测试的实际要求和条件。 - skolldev

@V0ldek - 谁说在该方法中创建一个 HashSet 然后查询它了？如果要查询数百万个值的集合，一开始就不应该使用数组。 - Igor

@Thameem 是的，所谓的“for循环算法”。（来源） - V0ldek

Answer 1

如果这是已排序的数组，您可以使用二分查找加快过程。

public static bool ExistsInArray(int[] ints, int val)
{
    return Array.BinarySearch(ints, val) >= 0;
}

- Mihir Dave

---

我尝试了这个，但结果让我大吃一惊。当我测试代码时，它完美地按照应该的方式工作，但当我查看评估时，它却说这个方法甚至不能在小方法上工作，而结果明显证明它确实可以工作。 - DLP

这个方法甚至在小方法上都不起作用：你是不是想说“如果你有小数组，它会有太多的性能开销”？ - k3b

也许数组没有排序？ - V0ldek

@DLP 在这里，你可以添加一个检查数组长度的条件，如果它很小，你就可以使用你的代码，但问题是什么数字算是“很小”呢？ - Mihir Dave

@DLP之前尝试了10次都失败了，因为解决方案中有一个拼写错误。如果val是ints中的第一项，原始答案将会失败。@MihirDave所做的更正修复了这个问题，这就是为什么现在它能够工作了：)。 - Joshua Robinson

Answer 2

你可以使用Parallel，类似下面的代码：

namespace ParallelDemo
{
    class Program
    {
        static void Main()
        {
            var options = new ParallelOptions()
            {
                MaxDegreeOfParallelism = 2
            };
            List<int> integerList = Enumerable.Range(0,10).ToList();
            Parallel.ForEach(integerList, options, i =>
            {
                Console.WriteLine(@"value of i = {0}, thread = {1}",
                    i, Thread.CurrentThread.ManagedThreadId);
            });

            Console.WriteLine("Press any key to exist");
            Console.ReadLine();
        }
    }
}

注意：它会加快速度，但会使用更多的内存

- Michael

---

这会如何帮助从集合中查找项目？ - Chetan

我认为这里的想法是使用多个处理器并行解决Map-Reduce中描述的问题。这里呈现的代码演示了并行性，但没有解决最初的问题，即检查数字是否包含在列表中。 - k3b

Answer 3

如果输入数组已经排序，则使用二分查找是最佳方法。

.NET通过使用Array.BinarySearch方法内置支持二分查找。

我刚刚对包含和二分查找进行了一个快速实验，使用了一个包含100万个整数值的排序数组。

public static void Main()
{
    var collection = Enumerable.Range(0, 1000000).ToArray();

    var st = new Stopwatch();

    var val = 999999;

    st.Start();

    var isExist = collection.Contains(val);

    st.Stop();

    Console.WriteLine("Time taken for Contains : {0}", st.Elapsed.TotalMilliseconds);

    t.Restart();

    var p = BinarySearchArray(collection, 0, collection.Length - 1, val);

    st.Stop();
    if(p == -1)
    {
        Console.WriteLine("Not Found");
    }
    else
    {
        Console.WriteLine("Item found at position : {0}", p);
    }

    Console.WriteLine("Time taken for binary search {0}", st.Elapsed.TotalMilliseconds);
}

private static int BinarySearchArray(int[] inputArray, int lower, int upper, int val)
{
    if(lower > upper)
        return -1;

    var midpoint = (upper + lower) / 2;

    if(inputArray[midpoint] == val)
    {
        return midpoint;
    }
    else if(inputArray[midpoint] > val)
    {
        upper  = midpoint - 1;              
    }
    else if(inputArray[midpoint] < val)
    {
        lower =  midpoint+1;    
    }

    return BinarySearchArray(inputArray, lower, upper, val);
}

以下是输出结果。

Time taken for Contains : 1.0518
Item found at position : 999999
Time taken for binary search 0.1522

很明显，在这里BinarySearch占据了优势。

.NET的Contains方法在内部不使用BinarySearch。对于小集合而言，Contains是一个很好的选择，但对于更大的数组，BinarySearch是更好的方法。

- Chetan

Answer 4

正确答案是：这取决于情况。

• 列表是否已排序？
• 列表有多大？
• 你能使用多少个核来解决问题？

最简单的答案是，尽管 Linq 有着很多优点，但实际上它相当慢。它使用了很多反射，在幕后执行了很多工作。如果易读性是您的主要目标，那么它很棒。但对于性能来说？不是。

在单线程、未排序的列表中，传统的 for 循环将给出最佳结果。如果已排序，则二进制搜索或某个版本的快速搜索效果最佳。

至于并行处理，C# 有 parallel 类。但请注意，如果列表足够小，则创建线程的开销可能会超过搜索时间。

简单、单线程、未排序的答案：

    public static bool ExistsInArray(int[] ints, int val)
    {
        for( int index = 0, count = ints.GetLowerBound(0); index < count; ++index)
        {
            if (ints[index] == val) return true;
        }
        return false;
    }

有可能您所查找的网站需要的是这个。但只有在数组已排序的情况下，才能使用此方法。

    public static bool ExistsInArray(int[] ints, int val)
    {
        return Array.BinarySearch(ints, val) > 0;
    }

支持有关 Linq 不太快的帖子。

• For vs. Linq - Performance vs. Future
• https://www.anujvarma.com/linq-versus-loopingperformance/

- Display name

---

你是否有数据证明LINQ运行较慢？我非常确定在简单的“Contains”调用中绝对没有涉及反射，当然也不会有很多。请参阅Enumerable.Contains的源代码。它不是一个重量级方法。 - V0ldek

我会在网上找找看。不过，我们内部的经验表明，Linq 显然比较慢，我曾经通过将 Linq 替换为更传统的方法来解决多个性能问题。只有当 Linq 语句本身是较大循环的一部分时，才会出现这个问题。 - Display name

是的，请查看这个stackoverflow链接: https://dev59.com/ZWUp5IYBdhLWcg3w-Lez。答案的作者重复了我刚才说的话。 - Display name

这位作者在 https://www.anujvarma.com/linq-versus-loopingperformance/ 上说，Linq需要两倍的时间。 - Display name

再次强调，这取决于具体情况。就像 SQL 调优一样，你必须知道你正在使用工具的对象是什么。 - Display name