Пользователь пока ничего не рассказал о себе

Достижения

Все достижения (1)

Наибольший вклад в теги

Все теги (26)

Лучшие ответы пользователя

Все ответы (19)
  • Методы парсинга BBCode?

    @zibada
    > Регулярки, как известно, не предназначены для парсинга вложенных конструкций.

    Действительно, теория нам подсказывает, что одной могучей регуляркой грамматику ббкодов не одолеть.
    Но это не значит, что регулярки в данной задаче вообще применять нельзя.
    (загляните в парсеры популярных форумов, например)

    Вкратце — одним проходом матчим самую глубоко вложенную пару тегов и заменяем на нечто, их не содержащее, повторяем в цикле, пока находится совпадение.
    Ответ написан
  • ORDER BY `вероятность`?

    @zibada
    тупое решение, если записей немного и не пугает делать full scan на каждый селект:

    в каждой записи хранить:
    — собственный приоритет (любое положительное число)
    — сумму приоритетов всех предыдущих элементов (в порядке добавления, например, по id)
    и где-то хранить сумму всех приоритетов (на самом деле, можно получать из записи с максимальным id)
    можно их нормализовать, но тогда не получится сделать быстрый insert.

    select сводится к генерации нескольких рандомных чисел из диапазона [0, сумма_всех_приоритетов), и выборке элементов, где диапазон [сумма, сумма+свой_приоритет) включает хотя бы одно из выбранных чисел.
    insert — простое дописывание в конец, обновление суммы приоритетов
    delete — простое удаление
    update (изменение приоритета) — удаление+вставка если приоритет увеличился, простой апдейт, если уменьшился.

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

    итого — все операции за амортизированную O(1), кроме селекта, с которым все печально.

    для его оптимизации можно использовать spatial index (не в курсе насчет поддержки в современных БД), т.к. у нас запрос на принадлежность точки отрезку.

    честное и быстрое, но сложное решение:

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

    select одного элемента (для простоты далее рассматривается бинарное дерево):
    генерируем число от 0 до суммы приоритетов (хранится в корне), идем от корня:
    — если число меньше суммы приоритетов в левом поддереве, то налево
    — иначе — направо, и вычитаем из числа сумму приоритетов в левом поддереве
    — когда дойдем до листа — вернуть его id

    update/insert/delete — обычные операции с деревом с обновлением суммы приоритетов во всех промежуточных вершинах.

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

    производительность всех операций — O(logN), выборки — O(KlogN), где K — размер выборки.
    тоже есть проблема, что один элемент может выбраться несколько раз, чтобы это побороть, можно выбранные элементы удалять сразу после выбора (ну или просто обнулять приоритет), а в самом конце вставлять обратно.

    как все это хранить?
    ну если все влезает в память — то отлично, вешаем отдельного демона, который при старте строит дерево по исходной табличке и поехали.
    если нет — либо в базе (но эффективность работы с деревьями на реляционных базах это большой вопрос), либо в файлах, т.е., по сути, писать свой движок базы…
    но это уже явный overkill =) наверняка существуют готовые решения, которые все это уже делают.
    Ответ написан

Лучшие вопросы пользователя

Все вопросы (1)