Лучшая структура данных для хранения больших объемов данных с динамическими и неуникальными ключами?

Question

По сути, у меня есть большое количество структур C для отслеживания, которые по сути:

struct Data {
    int key;
    ...        // More data
};

Мне нужно периодически получать доступ к множеству (сотням) из них, и они должны быть отсортированы по наименьшемудо самых высоких key значений.Ключи не являются уникальными, и они будут изменены в течение программы.Чтобы сделать дела еще более интересными, большинство структур будут отбираться (на основе критериев, совершенно не связанных с ключевыми значениями) из пула непосредственно перед сортировкой, но мне все еще нужно сохранять ссылки на них.

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

Подводя итог, если это неясно выше, мне нужно:

1. Хранить большое количество структур с неуникальными и динамическими ключами.
2. Отбирать большой процентструктуры (но не освобождают их полностью, потому что каждый раз отбираются разные структуры).
3. Сортировка оставшихся структур по максимальному и минимальному значению ключа.

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

РЕДАКТИРОВАТЬ: Отбор выполняется путем итерации по всем объектам и принятия решения для каждого из них.,Ключи меняются между циклами выбраковки / сортировки.Я должен был сказать, что они не сильно меняются, но они меняются, и они могут меняться несколько раз между прогонами отбора / сортировки.(Если это помогает, ключом для каждой структуры на самом деле является z-порядок для Sprite. Их необходимо отсортировать перед каждым циклом рисования, чтобы спрайты с более низкими z-порядками отображались первыми.)

Answer 1

Просто вставьте их в большой массив.

Когда придет время отбирать и сортировать, начните с сортировки. Сделайте вставку сортировки. Это верно - ничего умного, просто сортировка вставок.

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

Это примерно так же эффективно, как и память. Это также должно потребовать очень небольшого количества вычислений: нет никакой бухгалтерии для обновлений между проходами отбора / сортировки, и сортировка будет дешевой - потому что сортировка вставкой является адаптивной, и для почти отсортированного массива, подобного этому, это будет почти O (n) , Единственное, что он не делает, - это локальность кэша: будет два отдельных прохода по массиву для сортировки и отбраковки / вывода.

Если вам требуется больше сообразительности, то вместо сортировки вставкой вы можете использовать другую адаптивную сортировку на месте, которая работает быстрее. Timsort и smoothsort являются хорошими кандидатами; и то, и другое абсолютно ужасно для реализации.

Большой альтернативой этому является сортировка только необработанных объектов с использованием вторичного, временного, списка таких объектов, которые вы сортируете (или храните в двоичном дереве или как угодно). Но дело в том, что если ключи не сильно меняются, то выигрыш, который вы получите от использования адаптивной сортировки на почти отсортированном массиве, (я считаю!) Перевесит выигрыш, который вы получите от сортировки меньшего набора данных. Это O (n) против O (n log n).

Answer 2

Общим решением проблемы такого типа является использование сбалансированного дерева поиска (например, дерева AVL, красно-черного дерева, дерева B), которое гарантирует время O (log n) (почти постоянное, но не совсем) длявставка, удаление и поиск, где n - количество элементов, хранящихся в данный момент в дереве.Гарантировать, что ни один ключ не хранится в дереве дважды, довольно тривиально, и во многих реализациях это делается автоматически.

Если вы работаете в C ++, вы можете попробовать использовать std::map<int, yourtype>.Если в C найти или реализовать какой-нибудь простой двоичный код дерева поиска, и посмотреть, достаточно ли он быстр.

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