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

Спасибо, что посмотрели.

Подсчитайте, сколько чисел меньше 4 в упорядоченном массиве чисел.

Как повысить производительность алгоритма для более длинных массивов чисел? Увеличить скорость вычислений. Помогает ли бинарный поиск? Выходы?

    public static int CountNumbers(int[] sortedArray, int lessThan)
    {
        int count = 0;

        for (int i = 0, len = sortedArray.Length; i < len; i++)
            if (sortedArray[i] < lessThan)
                count++;
            else return count;

        return count;
    }

Assert.AreEqual(SortedSearch.CountNumbers(new int[] { 1, 3, 5, 7 }, 4), 2);

.net c# algorithm sortedlist
person Adam83    schedule 21.08.2017    source источник
comment
Используйте бинарный поиск   -  person Sergey Berezovskiy    schedule 22.08.2017
comment
Что произошло, когда вы попытались использовать бинарный поиск?   -  person Servy    schedule 22.08.2017
comment
@SergeyBerezovskiy: Бинарный поиск какого числа?   -  person Tigran    schedule 22.08.2017
comment
@Тигран lessThan числа   -  person Sergey Berezovskiy    schedule 22.08.2017
comment
@ Adam83: используйте подход «разделяй и властвуй», чтобы максимально приблизить его к O (logn), а не к O (n), как сейчас.   -  person Tigran    schedule 22.08.2017
comment
@Tigran O(n log(n)) больше, чем O(n), не меньше. Бинарный поиск — это O(log(n)).   -  person Servy    schedule 22.08.2017
comment
@Servy: опечатка, исправлено, спасибо: думал о быстрой сортировке, когда писал.   -  person Tigran    schedule 22.08.2017
comment
@SergeyBerezovskiy: дело в том, что мы ищем не lessThan, а скорее набор чисел меньше него, но я думаю, что все поняли, что вы имеете в виду, включая меня.   -  person Tigran    schedule 22.08.2017
comment
Не уверен, что двоичный файл повлияет на результат. Алгоритм должен только подсчитывать, сколько чисел предшествует заданному числу. Список уже отсортирован снизу вверх.   -  person Adam83    schedule 22.08.2017
comment
Как уже говорилось, бинарный поиск — ваш друг. Используйте реализацию, которая возвращает позицию искомого значения в заданном массиве (если мы вставляем это значение).   -  person MBo    schedule 22.08.2017
comment
Поэтому я продолжаю сокращать список, пока не найду номер. Я тогда считаю = индекс + 1? Потребуется ли больше выполнения при сокращении списка, а затем получении чисел из массива для их сравнения? Надеюсь, это имеет смысл.   -  person Adam83    schedule 22.08.2017

Ответы (2)


arrow_upward
0
arrow_downward

Вы должны использовать Array.BinarySearch

static int CountNumbers(int[] sortedArray, int lessThan)
{
    if (sortedArray[0] >= lessThan) return 0;

    int lengthOfArray = sortedArray.Length;
    if (lengthOfArray == 0) return 0;
    if (sortedArray[lengthOfArray - 1] < lessThan) return lengthOfArray;

    int index = Array.BinarySearch(sortedArray, lessThan);
    if (index < 0)
        return ~index;
    // Find first occurrence in case of duplicate
    for (; index > 0 && sortedArray[index - 1] == lessThan; index--) ;
    return index;
}
person Florian Talour    schedule 01.03.2018

arrow_upward
-1
arrow_downward

Хороший подход к решению подобной проблемы — разделить массив на более мелкие части и с помощью ThreadPool (см. https://msdn.microsoft.com/en-us/library/3dasc8as(v=vs.80).aspx) увеличивают скорость вычислений.

person Dimos K    schedule 21.08.2017
comment
Двоичный поиск на самом деле невозможно сделать многопоточным, потому что каждая выполняемая операция зависит от результатов предыдущей операции. Вы можете выполнить n-арный поиск, где n — количество потоков плюс один, но однопоточный двоичный поиск очень быстр, а n -ary search потребовал бы так много взаимодействия между потоками, что я не могу представить, чтобы потоки вообще были здесь полезны. - person Tanner Swett; 22.08.2017