Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.147.48.212] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу перехожу к делу!
Вот такое условие. На вход программе подаются однотипные объекты (будем называть их T), обладающих только 2мя свойствами: то есть на вход программе подаются объекты T(index, value). Количество может быть большим (насколько неизвестно, но большим)). У пользователя есть такие команды: 1. удалить N первых минимальных по value объектов. Другими словами, например, если N = 3, то надо удалить 3 объекта, имеющих наименьшее значение value. 2. удалить ЛЮБОЙ объект по полю index. Вот пример входных данных из 5ти объектов Т: T(1, 23.3), T(2, 17.3), T(3, 129.5), T(4, 55.0), T(5, 24.8) ---------------------------------------------------- И вот что-то прикурил я здесь по применению оптимальных структур данных, т к есть проблемки... Коротко мои мысли. 1. Если входные объекты сразу не вставлять в отсортированное пространство по полю value, то удаление N первых минимальных сведется к циклам, т к местоположение наименьших будет хаотичным. Следовательно, при поступлении очередного объекта Т его надо сразу засовывать в нужную позицию отсортированного пространства. Какую структуру данных использовать? Дерево поиска? Не катит вроде вообще. Вижу список, ну, наверное, двусвязный. При поступлении очередного объекта Т придется найти его позицию вставки, это вроде сложность O(K/2), где К - длина списка. Разве не так? Имея такой список удаление N мин.по value объектов будет равносильно удалению из начала списка N объектов. 2. Но список из п1 не годится для операции №2 (удаление по индексу), т к список отсортирован по value и тогда операция удаления будет сводится к фул-скану. Завести динамический массив, у которого индекс+1 равен index объекта Т. Значением элементов такого массива будет ссылка на объект, хранящийся в отсортированном двусвязном списке. При такой организации удаление будет выполнять за время О(1) (или близкое к нему). Но проблема здесь в том, что с течением времени будет возникать фрагментация (будут образовываться пустоты, разреженность). Также неизвестно кол-во входных объектов Т, поэтому хз каким размером нужно делать этот массив. Здесь, возможно, вообще надо уходить в хеш-таблицы с цепочками, но по условии не говорится о диапазоне поля value (хотя может для хеш это и не важно). Вопрос: структуры данных, которые я хочу пока что применить (двусвязный список + дин.массив со ссылкой на элемент списка, по факту индекс, как в БД) они нормально подходят для такой задачи или здесь вообще все совсем по-другому, вот в корне все по-другому?? спс. за внимание Добавлено Еще допишу такой момент. Пользователь достаточно часто вызывает команду №1 и реже команду №2 (в 2-3 реже, чем команду №1). |
Сообщ.
#2
,
|
|
|
Цитата FasterHarder @ Вопрос: структуры данных, которые я хочу пока что применить (двусвязный список + дин.массив со ссылкой на элемент списка, по факту индекс, как в БД) они нормально подходят для такой задачи или здесь вообще все совсем по-другому, вот в корне все по-другому?? Ну реально прям задачка для SQL-сервера, один в один. Кластерный индекс по value и обычный по index. Хотя я бы для очистки совести покурил R-Tree. Цитата FasterHarder @ 1. удалить N первых минимальных по value объектов. Проблемка. На value ведь никакого условия уникальности нет, верно? прикинь, надо удалить 2 минимальных, а у тебя с минимальным значением 4 элемента - ну и какие 2 из них удалять? |
Сообщ.
#3
,
|
|
|
Цитата Akina @ Хотя я бы для очистки совести покурил R-Tree. загуглил это дерево. Да уж, жесть, конечно там) Двоичное дерево поиска является чуть ли не тривиальной структурой по сравнению с деревьями, которые придуманы... Цитата Akina @ Проблемка. На value ведь никакого условия уникальности нет, верно? прикинь, надо удалить 2 минимальных, а у тебя с минимальным значением 4 элемента - ну и какие 2 из них удалять? абсолютно точно подмечено! на value нет никакого условия уникальности. Еще плохо то, что диапазон допустимых значений неизвестен, кроме того, что value > 0, т к это цена. Как я понял из условия, программа должна обрабатывать наиболее ранние поступившие на обработку объекты (FIFO), поэтому при вставке объекта в отсортированный список дополнительно буду смотреть на index. Др.словами, будут удаляться снача те объекты, у которых index минимальный. Итого. Очень вероятно, что здесь действительно, надо делать через R-tree, но это пока неподъемно). Оставлю список + массив. Это приводит к тому, что удаление по индексу выполняется за О(1), удаление первых N элементов, ну тоже за О(1) (или это О(N) считается, не знаю точно) и все время будет тратиться в основном на вставку объекта в нужную позицию с сохранением упорядоченности. Для одномерного массива будет выделен кусок памяти для 1 млн. элементов. Вроде массив будет легчайший (лишь указатель на элемент списка), но фрагментация может быть дичайшей + потребуется динамическое расширение размера массива со временем. Наверное, это некритично) p.s. но здесь 100% не нужны графы...вроде... |
Сообщ.
#4
,
|
|
|
Декартово дерево (treap, дерамида) https://e-maxx.ru/algo/treap
Или очередь по приоритетам на основе бинарной кучи (binary heap) по ключу value, совмещённая с хэш-таблицей для поиска index |