Быстрая реализация алгоритма для сортировки очень маленького списка

Question

Это проблема, с которой я столкнулся давным-давно. Я думал, что могу спросить у вас ваши идеи. Предположим, у меня очень маленький список чисел (целых чисел), 4 или 8 элементов, которые нужно быстро отсортировать. какой будет лучший подход / алгоритм?

Мой подход состоял в том, чтобы использовать функции max/min (10 функций для сортировки 4 чисел, без ветвей, iirc).

// s(i,j) == max(i,j), min(i,j)
i,j = s(i,j)
k,l = s(k,l)
i,k = s(i,k) // i on top
j,l = s(j,l) // l on bottom
j,k = s(j,k)

Я предполагаю, что мой вопрос больше относится к реализации, а не к типу алгоритма.

На данный момент это становится несколько аппаратно-зависимым, поэтому давайте предположим, что 64-битный процессор Intel с SSE3

Спасибо

Answer 1

Для небольших массивов, подобных этому, вам, вероятно, следует обратиться к сетям сортировки. Как вы можете видеть на этой странице, сортировка вставок может быть выражена как сеть сортировки. Однако, если вы заранее знаете размер массива, вы можете разработать оптимальную сеть. Взгляните на этот сайт, который может помочь вам найти оптимальные сети сортировки для заданного размера массива (хотя оптимальное гарантировано только до размера 16, я полагаю). Компараторы даже группируются в операциях, которые могут выполняться параллельно. Компараторы по сути те же, что и ваша функция s(x,y), хотя, если вы действительно хотите, чтобы это было быстро, вам не следует использовать min и max, потому что тогда вы делаете вдвое больше необходимых сравнений.

Если вам нужен этот алгоритм сортировки для работы с широким диапазоном размеров, то вам, вероятно, следует просто выполнить сортировку вставкой, как предлагали другие.

Answer 2

Для сортировки небольших количеств чисел необходим простой алгоритм, поскольку сложность добавляет больше накладных расходов.

Например, наиболее эффективный способ сортировки четырех элементов состоит в том, чтобы распутать алгоритм сортировки для линейных сравнений, тем самым устраняя все накладные расходы:

function sort(i,j,k,l) {
  if (i < j) {
    if (j < k) {
      if (k < l) return [i,j,k,l];
      if (j < l) return [i,j,l,k];
      if (i < l) return [i,l,j,k];
      return [l,i,j,k];
    } else if (i < k) {
      if (j < l) return [i,k,j,l];
      if (k < l) return [i,k,l,j];
      if (i < l) return [i,l,k,j];
      return [l,i,k,j];
    } else {
      if (j < l) return [k,i,j,l];
      if (i < l) return [k,i,l,j];
      if (k < l) return [k,l,i,j];
      return [l,k,i,j];
    }
  } else {
    if (i < k) {
      if (k < l) return [j,i,k,l];
      if (i < l) return [j,i,l,k];
      if (j < l) return [j,l,i,k];
      return [l,j,i,k];
    } else if (j < k) {
      if (i < l) return [j,k,i,l];
      if (k < l) return [j,k,l,i];
      if (j < l) return [j,l,k,i];
      return [l,j,k,i];
    } else {
      if (i < l) return [k,j,i,l];
      if (j < l) return [k,j,l,i];
      if (k < l) return [k,l,j,i];
      return [l,k,j,i];
    }
  }
}

Тем не менее, код растет с каждым добавляемым дополнительным элементом. Добавление пятого элемента делает код примерно в четыре раза больше. На восьми позициях это будет примерно 30000 строк, поэтому, хотя это все еще наиболее эффективно, это много кода, и вам придется написать программу, которая пишет код, чтобы получить его правильно.

Answer 3

Я вижу, у вас уже есть решение, которое использует 5 сравнений (при условии, что s(i,j) сравнивает два числа один раз и либо меняет их местами, либо нет). Если вы придерживаетесь сортировки на основе сравнения, то вы не можете сделать это с помощью менее чем 5 сравнений.

Это можно доказать, потому что их 4! = 24 возможных способа заказа 4 номера. Каждое сравнение может сократить возможности только пополам, поэтому с 4 сравнениями вы можете различать только 2^4 = 16 возможных упорядочений.

Answer 4

Сортировка вставок считается лучшей для небольших массивов. См. Быстрая стабильная сортировка для небольших массивов (до 32 или 64 элементов).

Answer 5

Сортировка сетей может быть легко реализована в SIMD, хотя она начинает становиться безобразной примерно при N = 16. Для N = 4 или N = 8, хотя это будет хорошим выбором. В идеале вам нужно много небольших наборов данных для одновременной сортировки, то есть если вы сортируете 8-битные значения, вам нужно отсортировать как минимум 16 наборов данных - гораздо сложнее делать подобные вещи по векторам SIMD.

Смотрите также: Самый быстрый вид массива с фиксированной длиной 6 int

Answer 6

Для такого небольшого набора данных вам нужен как можно более простой алгоритм. Скорее всего, базовая сортировка вставок будет работать так, как вам хочется.

Нужно было бы узнать больше о системе, в которой она работает, сколько раз вам нужно делать такую ​​сортировку в секунду и т. Д.... но общее правило для небольших сортировок - сохранять простоту. Быстрая сортировка и тому подобное не выгодны.