How to speed up the process of looping a million values array?

Question

So I was taking an online test where i had to implement a piece of code to simply check if the value was in the array. I wrote the following code:

    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;
        }
    }

Now i didn't see any problems here because the code works fine but somehow i still failed the test because this is "not fast enough" once the array contains a million values.

The only code i wrote myself is:

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

The other code i was given to work with.

Is there a way to speed up this process?

Thanks in advance.

EDIT: I came across a page where someone apparently took the same test as i took and it seems to come down to saving CPU cycles.

Reference: How to save CPU cycles when searching for a value in a sorted list?

Now his solution within the method is:

    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 );

Now i see how this code works but it's not clear to me why this is supposed to be faster. Would be nice if someone could elaborate.

Answer 1

If it's sorted array you can use BinarySearch To speed Up the process

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

Answer 2

You can use Parallel, something like the code below:

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();
        }
    }
}

Note: It will speed up but you're going to use more memory

Answer 3

If the input array is already sorted, then using BinarySearch is the best approach.

.NET has inbuilt support of BinarySearch by using Array.BinarySearch method.

Just did a quick experiment on Contains and BinarySearch with a sorted array of 1 Million integer values as following.

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);
}

Following is the output.

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

It is clear that the BinarySearch has the upper hand here.

.NET's Contains method does not use BinarySearch internally. Contains is good for small collections but for bigger arrays BinarySearch is better approach.

Answer 4

The correct answer is: it depends.

• Is the list sorted?
• How big is the list?
• How many cores can you throw at the problem?

The simplest answer is that Linq, for all its wonder is actually quite slow. It uses a lot of reflection and generally performs a lot of work under the covers. It's great when ease of readability is your main goal. But for performance? No.

In a single threaded, unsorted list, the old fashioned for loop will give you the best results. If it is sorted then a binary search or some version of the a quick search will work best.

As for parallel, C# has the the parallel class. But beware, if the list is small enough, the overhead of creating threads can overcome your search time.

Simple, single threaded, unsorted answer:

    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;
    }

it's possible that the site you're looking wants this instead. But this only works if the array is sorted.

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

Supporting posts that demonstrate that Linq is not so fast.

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