На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Выбор оптимальных структур данных (список, хеш-таблица, деревья, etc) , речь не про алгоритм, а про структуры данных
    Всем хай! Сходу перехожу к делу!

    Вот такое условие. На вход программе подаются однотипные объекты (будем называть их 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 @
      Вопрос: структуры данных, которые я хочу пока что применить (двусвязный список + дин.массив со ссылкой на элемент списка, по факту индекс, как в БД) они нормально подходят для такой задачи или здесь вообще все совсем по-другому, вот в корне все по-другому??

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

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

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

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

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

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

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

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

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

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

        p.s. но здесь 100% не нужны графы...вроде...
          Декартово дерево (treap, дерамида) https://e-maxx.ru/algo/treap



          Или очередь по приоритетам на основе бинарной кучи (binary heap) по ключу value, совмещённая с хэш-таблицей для поиска index
          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
          0 пользователей:


          Рейтинг@Mail.ru
          [ Script execution time: 0,0339 ]   [ 15 queries used ]   [ Generated: 28.03.24, 09:51 GMT ]