Блог

Пусть у нас будет массив размером 8, Пусть N будет 3

С массивом: 1 3 2 17 19 23 0 2

Наш результат должен быть: 23, 19, 17

Объяснение: три самых больших числа из массива, перечисленные в порядке убывания.

Я пробовал это:

 int array[8];
int largest[N] = {0, 0, 0};

for (int i = 1; i < N; i  ) {
    for (int j = 0; j < SIZE_OF_ARRAY; j  ) {
        if (largest[i] > array[j]) {
            largest[i] = array[j];
            array[j] = 0;
        }
    }
}
  

Кроме того, пусть ограничение будет таким:

целые числа в массиве должны быть 0 <= i <= 1 000

N должно быть 1 <= N <= SIZE_OF_ARRAY — 1

РАЗМЕР_О_ПАРАГРАФА должен быть 2 <= РАЗМЕР_О_ПАРАГРАФА <= 1 000 000

Мой способ его реализации очень неэффективен, поскольку он очищает весь массив N раз. С огромными массивами это может занять несколько минут.

Какой был бы самый быстрый и эффективный способ реализовать это на C?

Вы должны посмотреть на алгоритм гистограммы. Поскольку значения должны быть от 0 до 1000, вы просто выделяете массив для каждого из этих значений:

 #define MAX_VALUE 1000
int occurrences[MAX_VALUE 1];
int largest[N];
int i, j;

for (i=0; i<N; i  )
    largest[N] = -1;

for (i=0; i<=MAX_VALUE; i  )
    occurrences[i] = 0;

for (i=0; i<SIZE_OF_ARRAY; i  )
    occurrences[array[i]]  ;

// Step through the occurrences array backward to find the N largest values.
for (i=MAX_VALUE, j=0, i; i>=0 amp;amp; j<N; i--)
    if (occurrences[i] > 0)
        largest[j  ] = i;
  

Обратите внимание, что это приведет только к одному элементу в largest для каждого уникального значения. Измените вставку соответствующим образом, если вы хотите, чтобы все вхождения отображались в largest . Из-за этого вы можете получить значения -1 для некоторых элементов, если не было достаточно уникальных больших чисел для заполнения largest массива. Наконец, результаты в largest будут отсортированы от наибольшего к наименьшему. Это будет легко исправить, если вы хотите: просто заполните largest массив справа налево.

Самый быстрый способ — распознать, что данные не появляются просто так (они либо существуют во время компиляции, либо поступают с помощью ввода-вывода — из файлов, из сети и т.д.); И поэтому вы можете найти 3 самых высоких значения при создании данных (во время компиляции; или когда вы анализируете и проверяете работоспособность, а затем сохраняете данные, полученные с помощью ввода-вывода — из файлов, из сети и т.д.). Вероятно, это самый быстрый из возможных способов (потому что вы либо ничего не делаете во время выполнения, либо избегаете необходимости просматривать все данные во второй раз).

Однако; в этом случае, если данные изменяются после их создания, вам нужно будет обновить «3 самых высоких значения» одновременно с изменением данных; что легко, если меньшее значение заменяется более высоким значением (вы просто проверяете, становится ли новое значение одним из 3 самых высоких значений), но включает поиск, если «ранее самое высокое» значение заменяется более низким значением.

Если вам нужно выполнить поиск; тогда это можно сделать с помощью одного цикла, например:

     firstHighest = INT_MIN;
    secondHighest = INT_MIN;
    thirdHighest = INT_MIN;

    for (int i = 1; i < N; i  ) {
        if(array[i] > thirdHighest) {
            if(array[i] > secondHighest) {
                if(array[i] > firstHighest) {
                    thirdHighest = secondHighest;
                    secondHighest = firstHighest;
                    firstHighest = array[i];
                } else {
                    thirdHighest = secondHighest;
                    secondHighest = array[i];
                }
            } else {
                thirdHighest = array[i];
            }
        }
    }
  

Примечание: Точный код будет зависеть от того, что вы хотите сделать с дубликатами (возможно, вам потребуется заменить if(array[j] > secondHighest) { на if(array[j] >= secondHighest) { и if(array[j] > firstHighest) { на if(array[j] >= firstHighest) { , если вам нужны числа 1, 2, 3, 4, 4, 4, 4 дать ответ 4, 4, 4 вместо 2, 3, 4).

Для больших объемов данных это может быть ускорено с помощью SIMD и / или нескольких потоков. Например; если SIMD может выполнять «связки из 8 целых чисел», и у вас есть 4 процессора (и 4 потока); затем вы можете разделить его на четверти, а затем обработать каждую четверть как столбцы из 8 элементов; найдите 3 самых высоких значения в каждом столбце в каждом квартале; затем определите 3 самых высоких значения из «3 самых высоких значений в каждом столбце в каждом квартале». В этом случае вы, вероятно, захотите добавить дополнение (фиктивные значения, установленные на INT_MIN ) в конец массива, чтобы гарантировать, что общий размер массива кратен ширине SIMD и количеству процессоров.

Для небольших объемов данных дополнительные накладные расходы на настройку SIMD и / или координацию нескольких потоков будут стоить больше, чем это экономит; и версия «простого цикла», вероятно, будет настолько быстрой, насколько это возможно.

Для неизвестных / переменных объемов данных вы могли бы предоставить несколько альтернатив (простой цикл, SIMD с одним потоком и SIMD с переменным количеством потоков) и решить, какой метод использовать (и сколько потоков использовать) во время выполнения, исходя из объема данных.

Один из методов, который я могу придумать, — это просто отсортировать массив и вернуть первые N чисел. Поскольку массив отсортирован, возвращаемое нами N число будет N наибольшими числами массива. Этот метод потребует временной сложности, O(nlogn) где n — количество элементов, которые у нас есть в данном массиве. Я думаю, что это, вероятно, очень хорошая временная сложность, которую вы можете получить при подходе к этой проблеме.

Другим подходом с аналогичной временной сложностью было бы использование max-heap . Сформируйте максимальную кучу из данного массива и N раз используйте pop() (или извлекайте, или как вы это называете), чтобы получить самый верхний элемент, который был бы максимальным элементом, оставшимся в куче после каждого pop .

Временную сложность этого подхода можно считать даже лучшей, чем у первого — O(n Nlogn) где n — количество элементов в массиве, а N — количество самых больших элементов, которые нужно найти. Здесь O(n) потребовалось бы собрать кучу, а для извлечения самого верхнего элемента нам понадобилось бы O(logn) N раз, что в сумме равно — O(n Nlogn) , немного лучше, чем O(nlogn)