Какой метод сортировки использовать: быстрая сортировка, сортировка сегментов, основание, ... для крошечных пар данных? (C ++)

Question

Мне нужно оптимизировать некоторый код, который сортирует vector<pair<int, float >> a, где пары должны быть отсортированы по значению с плавающей запятой. Вектор будет иметь длину от 0 до 5. Я гуглял и читал о методах сортировки в C ++, но не могу найти никаких критериев для сортировки крошечных наборов данных. Для системы важно быть настолько быстрым, насколько это возможно, поскольку она используется для системы отслеживания BLOB-объектов в реальном времени.

С уважением, Pollux

Answer 1

Вставка сортировки и Пузырьковая сортировка отлично подходят для крошечных пар данных.

Другим вариантом является жесткий код логики сравнения с парой if операторов.
Проверьте Какой самый быстрый способ сортировки массива из 7 целых чисел? для некоторых идей.

Answer 2

Нет смысла читать о тестах. Вы можете прочитать и сравнить сложность (Big-O) алгоритмов, потому что это зависит только от самих алгоритмов, но сравнительный анализ - это то, что зависит от слишком многих факторов.

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

Answer 3

Есть какая-то конкретная причина, почему вам нужен этот код оптимизирован? Для n == 5 подойдет практически любой вид. Даже Bogosort должен иметь разумное время выполнения, поскольку их всего 5! == 120 возможных перестановок в ваших данных. Вы профилировали свой алгоритм, чтобы узнать, является ли это узким местом?

Answer 4

Для данных, которые вы упоминали (0-5), используйте методы STL sort . (исторически основанный на qsort)

stable_sort - если вы хотите сохранить порядок дубликатов. (исторически основанный на сортировке слиянием)

Answer 5

Используйте несколько неприятных наборов if s для самого быстрого сортирования из 5 элементов, или, если вы хотите сортировку, которая немного медленнее, но намного меньше головной боли, вы можете использовать сортировку сеть . Используйте этот сайт с количеством входов, равным пяти, чтобы получить оптимизированную сеть сортировки. Это даже показывает, как вы можете выполнять некоторые части параллельно, хотя это кажется немного чрезмерным только для 5 входов. Это потребует 9 сравнений, что довольно хорошо. Вы также реализуете сеть сортировки с набором if с, но разница между несколько неприятным набором if с, который я упомянул в начале, который действительно оптимален и является оптимальной сетью сортировки, состоит в свопы: сеть сортировки не минимизирует количество свопов.

Answer 6

Первая , Преждевременная оптимизация - корень всего зла . То есть, сначала сравните ваш код и убедитесь, что сортировка занимает больше всего времени. Если другая часть вашего кода, критичного к производительности, занимает 80% времени выполнения, вы получите существенное улучшение производительности, оптимизировав это в первую очередь.

Учитывая, что у вас есть 5 элементов, вопрос в значительной степени спорный. Любой используемый вами алгоритм (кроме bogosort: D) ​​должен иметь довольно постоянное время выполнения, если вы не запускаете алгоритм несколько сотен раз в секунду или более.

Второй , если вы все еще хотите оптимизировать поиск, если вы точно знаете, , у вас всегда будет 5 элементов , , оптимальный метод - жесткое кодирование comparations (математически можно доказать, что этот метод является оптимальным, обеспечивая минимальное количество выполняемых операций в худшем случае - это было у нас в качестве лабораторного приложения в университете). То же самое применимо, если у вас менее пяти элементов, но алгоритм становится невозможным для записи и выполнения, если у вас более семи элементов - логика запутана для написания и следования, поэтому ваш код будет трудно поддерживать.

Дайте мне знать, если вам нужна помощь в написании самого оптимального жестко запрограммированного алгоритма (хотя я думаю, что вы должны найти реализацию и теорию в сети).

Если у вас не всегда есть пять чисел (или по какой-то причине хотите избежать использования алгоритма сравнения с жестким кодом), используйте сортировку, предоставляемую библиотекой. На этой странице делается вывод, что сортировка stl является оптимальной по времени (не только по количеству выполненных операций). Я не знаю, какая реализация использовалась для поиска.

Answer 7

Если вы действительно уверены (то есть, вы измерили ), что это узкое место и его нужно оптимизировать, и любой алгоритм сортировки из STL не будет достаточно быстрым (и вы Я тоже это измерял), тогда, может быть, вы знаете что-то еще, что вы можете использовать? Стандартные алгоритмы сортировки являются общими и будут работать (достаточно хорошо) для любого набора данных: разное количество элементов, разные диапазоны значений и т. Д. Если вам действительно нужна производительность, часто нужно использовать дополнительную информацию для создания более специализированного алгоритма.

Здесь вы сказали одно: сортировать по 0-5 элементов, как сказал Ник Д. в своем ответе, возможно, это ускорит использование жестко запрограммированных операторов if вместо типичных циклов или рекурсии общей сортировки. алгоритмы.

Но, может быть, есть еще? Например, есть ли какие-либо ограничения на значения с плавающей запятой, которые могут возникнуть?

Answer 8

Вот процедура для сортировки 4 элементов в оптимальном количестве сравнений. Я бы написал для 5 элементов, но stackoverflow ограничивает сообщения до 30000 символов.

То, будет ли это на самом деле самым быстрым, зависит от того, какое давление может выдержать ваш кэш инструкций ЦП, поэтому тест в реальной программе!

/// Generated sort function for 4 arguments.
template <class T>
void DirectSort(T& a0, T& a1, T& a2, T& a3) {
    if (a0 < a1) {
        if (a0 < a2) {
            if (a0 < a3) {
                if (a1 < a2) {
                    if (a1 < a3) {
                        if (a3 < a2) {
                            {
                                T tmp(a2);
                                a2 = a3;
                                a3 = tmp;
                            }
                        }
                    }
                    else { // a1 >= a3
                        {
                            T tmp(a1);
                            a1 = a3;
                            a3 = a2;
                            a2 = tmp;
                        }
                        // a2 >= a3
                    }
                }
                else { // a1 >= a2
                    if (a1 < a3) {
                        {
                            T tmp(a1);
                            a1 = a2;
                            a2 = tmp;
                        }
                        // a2 < a3
                    }
                    else { // a1 >= a3
                        if (a2 < a3) {
                            {
                                T tmp(a1);
                                a1 = a2;
                                a2 = a3;
                                a3 = tmp;
                            }
                        }
                        else { // a2 >= a3
                            {
                                T tmp(a1);
                                a1 = a3;
                                a3 = tmp;
                            }
                        }
                    }
                }
            }
            else { // a0 >= a3
                if (a1 < a2) {
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a2;
                        a2 = a1;
                        a1 = tmp;
                    }
                    // a1 >= a3
                    // a2 >= a3
                }
                else { // a1 >= a2
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a1;
                        a1 = tmp;
                    }
                    // a1 >= a3
                    // a2 >= a3
                }
            }
        }
        else { // a0 >= a2
            if (a0 < a3) {
                // a1 >= a2
                if (a1 < a3) {
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = a1;
                        a1 = tmp;
                    }
                    // a2 < a3
                }
                else { // a1 >= a3
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = a3;
                        a3 = a1;
                        a1 = tmp;
                    }
                    // a2 < a3
                }
            }
            else { // a0 >= a3
                // a1 >= a2
                // a1 >= a3
                if (a2 < a3) {
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = tmp;
                    }
                    {
                        T tmp(a1);
                        a1 = a3;
                        a3 = tmp;
                    }
                }
                else { // a2 >= a3
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a1;
                        a1 = a2;
                        a2 = tmp;
                    }
                }
            }
        }
    }
    else { // a0 >= a1
        if (a0 < a2) {
            if (a0 < a3) {
                {
                    T tmp(a0);
                    a0 = a1;
                    a1 = tmp;
                }
                // a1 < a2
                // a1 < a3
                if (a3 < a2) {
                    {
                        T tmp(a2);
                        a2 = a3;
                        a3 = tmp;
                    }
                }
            }
            else { // a0 >= a3
                // a1 < a2
                if (a1 < a3) {
                    {
                        T tmp(a0);
                        a0 = a1;
                        a1 = a3;
                        a3 = a2;
                        a2 = tmp;
                    }
                    // a2 >= a3
                }
                else { // a1 >= a3
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a2;
                        a2 = tmp;
                    }
                    // a2 >= a3
                }
            }
        }
        else { // a0 >= a2
            if (a0 < a3) {
                if (a1 < a2) {
                    {
                        T tmp(a0);
                        a0 = a1;
                        a1 = a2;
                        a2 = tmp;
                    }
                    // a1 < a3
                    // a2 < a3
                }
                else { // a1 >= a2
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = tmp;
                    }
                    // a1 < a3
                    // a2 < a3
                }
            }
            else { // a0 >= a3
                if (a1 < a2) {
                    if (a1 < a3) {
                        if (a2 < a3) {
                            {
                                T tmp(a0);
                                a0 = a1;
                                a1 = a2;
                                a2 = a3;
                                a3 = tmp;
                            }
                        }
                        else { // a2 >= a3
                            {
                                T tmp(a0);
                                a0 = a1;
                                a1 = a3;
                                a3 = tmp;
                            }
                        }
                    }
                    else { // a1 >= a3
                        {
                            T tmp(a0);
                            a0 = a3;
                            a3 = tmp;
                        }
                        // a2 >= a3
                    }
                }
                else { // a1 >= a2
                    if (a1 < a3) {
                        {
                            T tmp(a0);
                            a0 = a2;
                            a2 = a3;
                            a3 = tmp;
                        }
                        // a2 < a3
                    }
                    else { // a1 >= a3
                        if (a2 < a3) {
                            {
                                T tmp(a0);
                                a0 = a2;
                                a2 = a1;
                                a1 = a3;
                                a3 = tmp;
                            }
                        }
                        else { // a2 >= a3
                            {
                                T tmp(a0);
                                a0 = a3;
                                a3 = tmp;
                            }
                            {
                                T tmp(a1);
                                a1 = a2;
                                a2 = tmp;
                            }
                        }
                    }
                }
            }
        }
    }
} // DirectSort - 4 arguments.