Ычан: [d | au / b / bro / hr / l / m / mu / o / s / tran / tu / tv / vg / x | a / aa / c / fi / jp / rm / tan / to / vn]
[Назад]
Ответ в нить
Имя
Animapcha image [@] [?]
Тема   ( ответ в 25954)
Сообщение flower
Файл 
Пароль  (для удаления файлов и сообщений)
Параметры   
  • Прежде чем постить, ознакомьтесь с правилами.
  • Поддерживаются файлы типов 7Z, BZ, BZ2, GIF, GZ, JPG, MO, MP3, MP4, OGG, OGV, PDF, PNG, PSD, RAR, SVG, SWF, TXT, WEBM, WEBP, XCF, ZIP размером до 5000 кБ.
  • Ныне 3632 unique user posts. Посмотреть каталог
  • Предельное количество бампов нити: 500
No. 25954  
Делаю свою буру и не понимаю, как сделать теги. Хочу за O(1) отвечать на вопрос вида "какие ID у картинок с тегами t1,...,tn, но без тегов e1,...,en, на странице с оффсетом 12000?" Ну или формально доказать, что я обнаглел и это невозможно. Как вы это делаете?
No. 25955  
> какие ID у картинок с тегами t1,...,tn, но без тегов e1,...,en
Создаешь инвертированный индекс, где к каждому тегу привязана кишка с айдишниками соответствующих документов. Итерируешься по одной из кишок (ты можешь выбрать самую короткую), получаешь сложность O(длина кишки). Так делается в больших нагруженных поисковых системах.
> на странице с оффсетом 12000
Добавляешь еще один тег (поисковый литерал), означающий номер страницы.

Возможно, на маленькой буре можно сделать что-то более быстрое по времени, но за счет большего потребления памяти. Я не уверен, что это на самом деле нужно.
No. 25957  
О, а мысль протегировать страницы мне не приходила в голову.
No. 25958  
>>25954
Разве такое не должно быть уже решено в СУБД?
Но гляньте https://roaringbitmap.org/
Если в кратце, для каждого тэга храним сжатый битовый массив, для выполнения запроса and-аем чанки этих массивов между собой, делая popcnt по результату, пока не достигнем нужный offset.
No. 26010  
1418651108864.png - (28.27KB, 225×239)
26010
Моя бура состоит из двух TSV текстовых файлов вида тэг|хэш и хэш|путь-к-файлу, которые я грепаю скритом.

What is O(1), is it tasty
Удалить сообщение []
Пароль  
[Mod]