Вставка элементов в список, который часто вставляется в сортировку

Question

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

Answer 1

Лучшее место для вставки будет принадлежать элементу в отсортированном списке. Это было бы похоже на упреждающую сортировку вставки.

Answer 2

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

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

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

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

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

Назад к сортировке. Java использует версию quicksort для сортировки коллекций. Quicksort выберет элемент сводной таблицы для разделения коллекции. Этот выбор имеет решающее значение для выполнения алгоритма. Для лучшей производительности элемент поворота должен быть как можно ближе к элементу в середине результата. Обычно quicksort использует элемент из середины текущего раздела в качестве элемента поворота. Кроме того, quicksort начнет обработку списка с небольшими индексами.

Таким образом, добавление новых элементов в конце может не дать вам хорошей производительности. Это не повлияет на выбор элемента управления, но quicksort будет смотреть на новые элементы после того, как он проверит все отсортированные элементы. Добавление новых элементов в середине будет влиять на выбор поворота, и мы не можем действительно сказать, повлияет ли это на производительность или нет. Моя инстинктивная догадка заключается в том, что элемент поворота будет лучше, если quicksort найдет отсортированные элементы в середине разделов.

Это оставляет новые элементы в начале. Таким образом, quicksort, как правило, найдет идеальный элемент поворота (так как середина списка будет отсортирована), и он сначала подберет новые элементы. Недостатком является то, что вы должны скопировать весь массив для каждой вставки. Есть два способа избежать этого: a) As I said elsewhere, сегодняшние ПК копируют огромное количество оперативной памяти практически без каких-либо проблем, поэтому вы можете просто проигнорировать этот небольшой хит производительности. b) Вы можете использовать второй ArrayList, поместить в него все новые элементы, а затем использовать addAll(). Java будет делать некоторые оптимизации внутри этого случая и просто перемещать существующие элементы один раз.

[EDIT2] Я полностью не понял ваш вопрос. Для алгоритма insertion sort лучшее место, вероятно, где-то посередине. Это должно вдвое уменьшить шансы на перемещение элемента по всему списку. Но поскольку я не уверен на 100%, я предлагаю создать пару небольших тестов, чтобы проверить это.