Как ускорить процесс зацикливания массива миллионов значений?

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;

Другой код, с которым мне дали работать.

Есть ли способ ускорить этот процесс??

Заранее спасибо.

РЕДАКТИРОВАТЬ: Я наткнулся на страницу, где кто-то, очевидно, прошел тот же тест, что и я, и, кажется, сводится к экономии циклов процессора.

Ссылка: Как сохранить циклы ЦП при поиске значения в отсортированном списке?

Теперь его решение в рамках метода:

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

Теперь я вижукак работает этот код, но мне не ясно, почему это должно быть быстрее.Было бы неплохо, если бы кто-то мог уточнить.

Answer 1

Если это отсортированный массив, вы можете использовать BinarySearch Для ускорения процесса

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

Answer 2

Правильный ответ: это зависит.

• Список отсортирован?
• Насколько велик список?
• Сколько ядер вы можете бросить на проблему?

Самый простой ответ заключается в том, что Linq, несмотря на все его удивления, на самом деле довольно медленный. Он использует много размышлений и, как правило, выполняет много работы под одеялом. Здорово, когда удобство чтения - ваша главная цель. Но для производительности? Нет.

В однопоточном несортированном списке устаревший цикл for даст вам лучшие результаты. Если он отсортирован, лучше всего подойдет двоичный поиск или какая-либо версия быстрого поиска.

Что касается параллели, C # имеет класс параллели. Но будьте осторожны, если список достаточно мал, накладные расходы на создание потоков могут преодолеть ваше время поиска.

Простой однопоточный несортированный ответ:

    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 не так быстр.

• За против Linq - Производительность против будущего
• https://www.anujvarma.com/linq-versus-loopingperformance/

Answer 3

Если входной массив уже отсортирован, то лучше всего использовать BinarySearch.

.NET имеет встроенную поддержку BinarySearch с использованием метода Array.BinarySearch.

Только что провел быстрый эксперимент с Contains и BinarySearch с отсортированным массивом из 1 миллиона целочисленных значений, как показано ниже.

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 здесь имеет преимущество.

Метод Contains в .NET не использует BinarySearch для внутреннего использования. Contains хорош для небольших коллекций, но для больших массивов лучше использовать BinarySearch.

Answer 4

Вы можете использовать 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();
        }
    }
}

Примечание: это ускорится, но вы собираетесь использовать больше памяти