[Алгоритм] Подскажите как лучше.

диапазон возможных координат большой? Сколько всего отрезков?

Сколько всего проверяемых точек?

> диапазон возможных координат большой?

0..(2^32 - 1)

Сколько всего отрезков?

Несколько сотен.

при такой постановке самое быстрое ИМХО - хранить битовую маску всего диапазона, займет всего 512Мб памяти. Поиск опять же битовыми операциями.

> Сколько всего проверяемых точек?

Тоже порядка нескольких сотен.

> Поиск опять же битовыми операциями.

Я не знаю как это. Расскажи.

> Я не знаю как это. Расскажи.

http://en.wikipedia.org/wiki/Bit_array

имхо, твои варианты наиболее адекватны. и по памяти и по производительности

что именно не понятно? Выделяешь кусок памяти нужного размера, из расчета 1 бит = 1 точка, на весь возможный диапазон координат. Заполняешь все нулями, а биты, соответствующие отрезкам, ставишь 1.
Чтобы проверить точку, просто проверяешь значение соответствующего ей бита, тут тебе потребуется вычислить смещение в байтах (или в чем там у тебя будет память адресоваться), затем битовое смещение и конъюнкция.
Конкретные детали реализации уже зависят от языка.

Я тупил с поиском.

Спасибо, разобрался.

И у этого метода есть недостатки.

при такой постановке самое быстрое ИМХО - хранить битовую маску всего диапазона, займет всего 512Мб памяти. Поиск опять же битовыми операциями.

На современных процах лучше побольше посчитать, но поменьше память трогать. В разумных пределах, разумеется. Шерстить полгига памяти - плохая идея.

+1

512 MB вообще как-то слишком много получается.

> Шерстить полгига памяти …

в данном случае «шерстить» нужно всего один байт. точнее — один бит одного байта.

в данном случае «шерстить» нужно всего один байт. точнее — один бит одного байта.

«Но есть нюанс». Какой байт - неизвестно. 512 мб в L1 не влезет -> TLB будет забиваться. 512 мб вообще ни в какой кэш не влезет, так что при активном лукапе будет и кэш вымываться.

А зачем шерстить? Нельзя ли изначально заполнить так, чтобы адрес ячейки памяти с нужным битом вычислялся сразу из координаты точки? Для этого заполнить память надо по какому-нибудь легко вычислимому правилу.

хз как сейчас, но лет пять назад на перенос «слова» (равного разрядности шины данных) из памяти (минуя L1) необходимо было 5+1+1+1+1 циклов (если попадает в L1, то до пенька первого было 3 такта, начиная с пня — 1 такт). для сравнения: безусловный цикл в те времена занимал 7 тактов, условный — 11. но это так, «нюанс» ;) конечно же сравнивать с сотней диапазонов проще, чем загрузить один байт мимо кэша, вы совершенно правы! :)

А зачем шерстить? Нельзя ли изначально заполнить так, чтобы адрес ячейки памяти с нужным битом вычислялся сразу из координаты точки? Для этого заполнить память надо по какому-нибудь легко вычислимому правилу.

Если бы это был старый добрый Z80, в котором можно к любому адресу в пределах адресного пространства обращаться строго за 4 такта, то никаких проблем. К сожалению, современные процессоры не только общаются с памятью через многоуровневую систему мизерных по размеру кэшей и активно спекулируют порядком выполнения инструкций, но ещё и вздумали заниматься типа многозадачностью, которая состоит из последовательных переключений контекстов, при которых содержимое TLB и кэша 1-го уровня выбрасывается. Поэтому чем реже процессору приходится вылазить за пределы тёплого, уютного, но крохотного L1, тем лучше.

За стоимость одного промаха мимо кэша иной алгоритм пяток-другой раз успеет посчитаться.

Не, щас гораздо хуже. На столько, что обращение к разреженному массиву по известному индексу на нехалеме пришлось поменять на дерево двоичного поиска :( Цикл поиска по дереву зато крутит аццки быстро.

Но может ЛОР знает более мудрый (интересный, крутой, труёвый) способ решения?

Он есть. Называется отсутствие преждевременной оптимизации.

По теме: тут только дерево и просится. Просто есть разные деревья, не только двоичные. Есть ище разные хитрожо... хитроустроенные. Поищите в инете. Они не будут лучше O(log n), ибо врядли возможно, но будут быстрее на практике.

Еще стоящей будет попытка распаралелить поиск на несколько ядер.

Ну конечно кроме отстрела себе ног в виде битового массива, который предлагают некоторые ребята здесь. Это не труЪ, а феерических быдлокод. Если уже его использовать, то можно гибридно попытаться смешать с деревом с целью не хранить парочку миллионов нулей в случае чего.

При такой постановке задачи - бинарный поиск, или бинарное упорядочивание - это именно то, что вам нужно.

Еще вариант. Побить всю область на блоки с битом занятости. А вот на каждый блок вешать по-дереву если в блоке хоть что-то занято. Выбрать хороший баланс размера блока и дерева.

Спасибо всем, многого почерпнул.

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

>Но есть нюанс". Какой байт - неизвестно. 512 мб в L1 не влезет
а в чем проблема вычислить смещение для заданной координаты?

обращение к разреженному массиву по известному индексу на нехалеме пришлось поменять на дерево двоичного поиска

мда, не думал, что х86 настолько деградировала.

>Это не труЪ, а феерических быдлокод. Если уже его использовать, то можно гибридно попытаться смешать с деревом с целью не хранить парочку миллионов нулей в случае чего.

с целью экономии памяти можно применить реализацию с поддержкой сжатия. Вообще, предлагаю автору реализовать оба варианта и сравнить скорость. На современных числодробилках вполне возможно дерево будет быстрее.

Отрезков всего несколько сотен - тут вообще можно не заморачиваться.

Вот если бы отрезков было несколько миллионов, тогда да - интересно сравнить.

а в чем проблема вычислить смещение для заданной координаты?

Разверни мысль, не понятно.

мда, не думал, что х86 настолько деградировала.

Это не деградация, это прогресс. К сожалению, память прогрессирует гораздо медленнее, чем процессоры.

>Разверни мысль, не понятно.
это мне не понятно, что тебе мешает узнать смещение нужного байта :)

Это не деградация, это прогресс

трудно назвать прогрессом обвешивание костылями, многомегабайтными кешами и хитрыми алгоритмами. Революция нужна, новый вид памяти например.

это мне не понятно, что тебе мешает узнать смещение нужного байта :)

Ты имеешь в виду, узнать адрес нужного байта? Да нет проблем! Что дальше с ним будешь делать? :)

трудно назвать прогрессом обвешивание костылями, многомегабайтными кешами и хитрыми алгоритмами. Революция нужна, новый вид памяти например.

Тебе броневик подогнать? ;)

>Что дальше с ним будешь делать? :)

ну как бы тянуть из памяти в регистр и обрабатывать. Да, тут будет промах. Было бы интересно посмотреть в цифрах, насколько все это будет тормозить :)

Примерно так против так. В первом случае лениво (без MMAP_POPULATE) выделено дофига терабайт памяти, из которых используется совсем чуть-чуть, мегабайт 100, но обращение к элементам сверхудобное: практически, по индексу. Вторая картинка - тот же самый набор данных с той же самой обработкой, но всё хранится в разбалансированном дереве. Разница на десятичный порядок.

Первый вариант, вообще говоря, был подсмотрен в движке одной не самой паршивой биржи :)

Да, стоит отметить, что вариант биржевиков работает одинаково медленно при любом объёме данных в этом массиве, а вариант на деревьях деградирует с увеличением кол-ва данных, и может стать тормознее первого варианта. Поэтому нужно пробовать несколько вариантов решения задачи и смотреть, какой лучше подходит. В нашем случае таких объёмов не предвиделось, так что деревья выиграли с десятикратным перевесом.

Если бы автор рассказал подробнее условия:

- как возникают рассматриваемые отрезки? постоянно ли их количество?

- есть ли возможность упорядочить каким-либо образом набор отрезков или нет?

- как возникают тестовые точки? сразу все известны или регулярно появляются?

- какие-то статистические особенности в отрезках или тестовых точках?

то мы бы ему ещё нарисовали методов более конкретных.

Если отрезки не пересекающиеся, то:

• список отрезков меняется часто:
  • проверочные точки распределены равновероятно - красно-черное дерево, С++ - std::set<> от стуктуры отрезка с переопределным сравнением по началу;
  • проверочные точки «кучкуюся» по мере поступление запросов поиска - splay-tree (гуглить);
• список отрезков меняется редко - бинарный поиск по отсортированному массиву/вектору.
  
  
• плоский bitmap будет быстрее только если:
  • диаппазон значений мал (мас сам битмап);
  • исходные данные сложно стуктурировать и их очень много. Например миллиард пересекающихся отрезков в GF(32);

не все так однозначно:)

язык - C++? может просто C?

красно-черное дерево? способов балансировки - масса.

проверочные точки «кучкуюся» по мере поступления - вообще можно не сортировать изначальный массив, просто смещая найденные в начало (см. Кнут)

вообщем - еще много чего можно сказать:)