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

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) сравнивает два числа один раз и либо меняет их местами, либо нет).Если вы придерживаетесь сортировки, основанной на сравнении, то вы не сможете сделать это, сравнив не менее пяти.

Это можно доказать, потому что их 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

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

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