Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=423019&view=findpost&p=3852045 Thu, 16 Sep 2021 08:41:27 +0000 Выбор оптимальных структур данных (список, хеш-таблица, деревья, etc) https://forum.sources.ru/index.php?showtopic=423019&view=findpost&p=3852045 https://e-maxx.ru/algo/treap



Или очередь по приоритетам на основе бинарной кучи (binary heap) по ключу value, совмещённая с хэш-таблицей для поиска index]]> MBo Алгоритмы https://forum.sources.ru/index.php?showtopic=423019&view=findpost&p=3852028 Wed, 15 Sep 2021 20:03:22 +0000 Выбор оптимальных структур данных (список, хеш-таблица, деревья, etc) https://forum.sources.ru/index.php?showtopic=423019&view=findpost&p=3852028 Цитата Akina @

Хотя я бы для очистки совести покурил R-Tree.

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

Цитата Akina @
Проблемка. На value ведь никакого условия уникальности нет, верно? прикинь, надо удалить 2 минимальных, а у тебя с минимальным значением 4 элемента - ну и какие 2 из них удалять?

абсолютно точно подмечено!
на value нет никакого условия уникальности. Еще плохо то, что диапазон допустимых значений неизвестен, кроме того, что value > 0, т к это цена.
Как я понял из условия, программа должна обрабатывать наиболее ранние поступившие на обработку объекты (FIFO), поэтому при вставке объекта в отсортированный список дополнительно буду смотреть на index. Др.словами, будут удаляться снача те объекты, у которых index минимальный.

Итого. Очень вероятно, что здесь действительно, надо делать через R-tree, но это пока неподъемно).
Оставлю список + массив. Это приводит к тому, что удаление по индексу выполняется за О(1), удаление первых N элементов, ну тоже за О(1) (или это О(N) считается, не знаю точно) и все время будет тратиться в основном на вставку объекта в нужную позицию с сохранением упорядоченности.

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

p.s. но здесь 100% не нужны графы...вроде...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=423019&view=findpost&p=3852025 Wed, 15 Sep 2021 18:47:32 +0000 Выбор оптимальных структур данных (список, хеш-таблица, деревья, etc) https://forum.sources.ru/index.php?showtopic=423019&view=findpost&p=3852025 Цитата FasterHarder @
Вопрос: структуры данных, которые я хочу пока что применить (двусвязный список + дин.массив со ссылкой на элемент списка, по факту индекс, как в БД) они нормально подходят для такой задачи или здесь вообще все совсем по-другому, вот в корне все по-другому??

Ну реально прям задачка для SQL-сервера, один в один. Кластерный индекс по value и обычный по index.

Хотя я бы для очистки совести покурил R-Tree.

Цитата FasterHarder @
1. удалить N первых минимальных по value объектов.

Проблемка. На value ведь никакого условия уникальности нет, верно? прикинь, надо удалить 2 минимальных, а у тебя с минимальным значением 4 элемента - ну и какие 2 из них удалять?]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=423019&view=findpost&p=3852013 Wed, 15 Sep 2021 16:46:32 +0000 Выбор оптимальных структур данных (список, хеш-таблица, деревья, etc) https://forum.sources.ru/index.php?showtopic=423019&view=findpost&p=3852013
Вот такое условие. На вход программе подаются однотипные объекты (будем называть их T), обладающих только 2мя свойствами:
  • index (натуральное уникальное число, стартующее с 1 и увеличивающееся на +1)
  • value (дробное положительное значение, диапазон неизвестен)
то есть на вход программе подаются объекты 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).]]> FasterHarder Алгоритмы