Сортировка 1000-2000 элементов с большим количеством ошибок кэша

Question

У меня есть массив из 1000-2000 элементов, которые являются указателями на объекты. Я хочу сохранить мой массив отсортированным и, очевидно, хочу сделать это как можно быстрее. Они сортируются по элементу и не выделяются непрерывно, поэтому допускается пропуск кэша при каждом доступе к элементу сортировки.

В настоящее время я сортирую по требованию, а не по добавлению, но из-за отсутствия кэша и [предположительно] отсутствия встраивания доступа к элементу внутренний цикл моей быстрой сортировки идет медленно.

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

Редактировать: Может быть, я неправильно сформулировал это :), мне на самом деле не нужно, чтобы мой массив сортировался все время (я не перебираю их последовательно ни для чего) Мне просто нужно отсортировать его, когда я делаю бинарную отбивку найти подходящий объект, и выполнение этой быстрой сортировки в это время (когда я хочу выполнить поиск) в настоящее время является моим узким местом из-за пропусков и скачков кэша (я использую оператор <на своем объекте, но я надеюсь, что inlines в релизе) </p>

Answer 1

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

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

Answer 2

Вместо массива указателей вы можете рассмотреть массив структур, которые состоят как из указателя на ваш объект, так и из критериев сортировки. То есть:

Вместо

struct MyType {
    // ...
    int m_SomeField; // this is the sort criteria
};

std::vector<MyType*> arr;

Вы можете сделать это:

strcut ArrayElement {
    MyType* m_pObj; // the actual object
    int m_SortCriteria; // should be always equal to the m_pObj->m_SomeField

};

std::vector<ArrayElement> arr;

Вы также можете удалить поле m_SomeField из вашей структуры, если вы только обращаетесь к своему объекту через этот массив.

Таким образом, чтобы отсортировать массив, вам не нужно разыменовывать m_pObj каждую итерацию. Следовательно, вы будете использовать кеш.

Конечно, вы должны постоянно синхронизировать m_SortCriteria с m_SomeField объекта (если вы его редактируете).

Answer 3

Как вы упомянули, вам придется выполнить некоторое профилирование, чтобы определить, является ли это узким местом и обеспечивают ли другие подходы какое-либо облегчение.

Альтернативами использованию массива являются std :: set или std :: multiset , которые обычно реализуются в виде двоичных деревьев R-B и поэтому имеют хорошую производительность для большинства приложений. Вам придется взвесить их, используя частоту шаблона сортировки при поиске, который вы реализовали.

В любом случае, я бы не советовал использовать собственную сортировку или поиск, если вы не заинтересованы в получении дополнительной информации о том, как это делается.

Answer 4

Простой подход: сортировка вставок на каждой вставке. Так как ваши элементы не выровнены в памяти, я угадываю связанный список. Если это так, то вы можете преобразовать его в связанный список с переходом на 10-й элемент, 100-й и так далее. Это похоже на следующее предложение.

Или вы реорганизуете свою структуру контейнера в бинарное дерево (или любое дерево, которое вам нравится, B, B *, красно-черный, ...) и вставляете элементы, как если бы вы вставляли их в дерево поиска.

Answer 5

Я думаю, что лучшим подходом в вашем случае было бы изменение вашей структуры данных на что-то логарифмическое и переосмысление вашей архитектуры. Поскольку узким местом вашего приложения является не сортировка , а вопрос , почему вы должны сортировать все на каждой вставке и пытаться компенсировать это, добавляя сортировку по требованию? .

Еще одна вещь, которую вы можете попробовать (которая основана на вашей текущей реализации) реализует внешнюю таблицу / функцию отображения pointer - something и сортирует эти вторые ключи, но я на самом деле сомневаюсь, что в этом случае будет полезно .

Answer 6

Я думаю, что сортировка при вставке будет лучше. Мы говорим о сравнениях O (log N), скажем, ceil( O(log N) ) + 1 поиск данных для сортировки.

Для 2000 это составляет: 8

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

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