• programming key-value Есть key value база данных. В ней среди прочего хранятся квадраты как (TopLeft_x, TopLeft_y, Width, Height)+всякие даные; в данный момент ключем является форма квадрата, т.е. сериализация этих самых (x,y,w,h); вопрос, есть ли идеи как это складывать таким образом, чтобы можно было эффективно выгружать интересные квадраты, т.е. те которые пересекаются с заданным?

    Кстати хорошую структурку, в которую эти квадраты можно сложить в памяти (в haskell) тоже бы не помешало.
    ♡ recommended by @ndtimofeev

Replies (23)

  • @qnikst, Если у тебя координаты целые ограниченного размера, то упакуй все углы в одно число и делай выборку по диапазонам чисел.
  • @qnikst, quadtree не?
  • @blaze, Хотя нет, так не получится, наверное. Это надо по маскам выбирать, твой средний KV storage так не умеет.

    Тогда сделай внешний индекс, порежь пространство на фиксированные квадраты и храни в них ключи второй базы, с настоящими квадратами из твоей задачи. Будешь по первому индексу выбирать подмножество и потом его фильтровать.
  • @vovanium, были бы точки так или оно или R-tree, а так не понятно
  • @blaze, ограничены, но Int64
  • @qnikst, Квадрат помещается в поддерево, если полностью влезает в него, иначе в текущий узел. Как-то так обычно делают. Если анноят мелкие квадраты на стыках, можно попробовать ветки с перекрытием сделать.
  • @qnikst, сделай сотню полос по одной из координат, в запросе выгребай подмножество по этим полосам, в котором считай пересечения честно, например. в принципе можно и по двум координатам.
  • @lurker, но это вряд ли сильно отличается от индексов по x/у с т зр бд
  • @vovanium, ну наверное, в общем-то это наверное самый очевидный из вариантов.
    Да, данных не факт, что много так что возможно вариант выгрузить все и построить умную структуру в памяти — рассматривается
  • @qnikst, Граф, вершины — квадраты, грани — между пересекающимися.
  • @killy, чо? да, то что лежит в базе — гарантировано не пересекающееся
  • @qnikst, Т.е. это чтобы при добавлении быстро чекать новые квадраты на пересечение?
  • @blaze, Если умеет по непрерывным диапазонам чисел, можно координаты с перемежёнными битами (блоками битов) хранить: x0y0w0h0x1y1w1h1... Но придётся повозиться с упаковкой-распаковкой и вычислением диапазонов.
  • @killy, да, и на то надо ли что-нить из базы грузить или нет.
  • @qnikst, Ну тут вряд ли можно что-то принципиально отличное от предложения @vovanium сделать.
  • @killy, ну quadtree то что в голову сразу лезет; RTree в том же направлении, но сбалансировано; сетка и в каждом узле которой список индексов областей, которые его задевают (в общем-то близко к quadtree, но вроде на key-value проще ляжет).
  • @qnikst, сетка?

    Кажется, разница только в том, как строить каждое из этих деревьев. Проверка будет одинаковая.

    RTree выйдет дольше построить, но быстрее проверять.
  • @qnikst, Почему квадратов есть ширина и высота, когда достаточно одного? Что есть квадраты?
  • @mabu, квадраты разной формы :))
  • @alar, Возьму линейку, проведу прямую — и мигом круг квадратом обернётся.
  • @mabu, раз они задаются четырьмя углами, то квадратов круглой формы тут наверное нет
  • @alar, Там криволинейная система координат.
  • @mabu, Решение в гиперболических координатах принимается