LINUX.ORG.RU

Быстрый поиск по шаблону


0

0

Имеется такой массив:

[code] static record_t handlers[] =

{

{0x0f800010, 0x06000010, handler1},

{0x1ff00030, 0x06800010, handler2},

// ... примерно 100 еще таких записей ... {0x1fb000f0, 0x06a00030, handlerN},

};

[/code]

По нему из потока выбираются числа, на них накладывается маска (1 число) и сравнивается со значением (2 число). Если совпало, то вызывается соответствующий handler. Причем записи расположены так, чтобы наиболее "конкретная" из похожих находилась выше более "широкой".

Сейчас поиск осуществляется довольно медленно и хочется его ускорить.

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

★★★★

Re: Быстрый поиск по шаблону

В общем случае дерево мне кажется должно ускорить процесс.

OxiD ★★★★ ()

Re: Быстрый поиск по шаблону

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

ЗЫ ты случаем не эмулятор пишешь? просто примерно такое же встретилось в softgun (ARM эмулятор). но там задачу решили еще проще (и мб топорнее) - после фильтрации оказалось, что значимых бит там меньше 16 и создали массив указателей на 2^кол-во_бит элементов. в результате выборка работает значительно быстрее чем дерево (правда памяти ест больше).

generatorglukoff ★★ ()

Re: Быстрый поиск по шаблону

(X&B==C) => (X&B&C + !X&B&C) => (X == B&C)

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

wfrr ★★☆ ()
Ответ на: Re: Быстрый поиск по шаблону от generatorglukoff

Re: Быстрый поиск по шаблону

> реализовать суффиксное дерево

ИМХО предыдущий оратор имел в виду двоичное дерево....

Я рекомендую классический хэш. Очевидно, в данном случае всё остальное "сольёт", даже префиксное дерево (не говоря уж о двоичном). Хэш 32-битных целых вычисляется одной операцией, быстрее на современных процах только FP...

Die-Hard ★★★★★ ()
Ответ на: Re: Быстрый поиск по шаблону от Die-Hard

Re: Быстрый поиск по шаблону

Не совсем понятно, наверное, высказался..

Входное число по модулю простого, в соответствующем элементе массива -- начало цепочки всех пар ("маска", "результат").

Die-Hard ★★★★★ ()
Ответ на: Re: Быстрый поиск по шаблону от wfrr

Re: Быстрый поиск по шаблону

Мысль хороша, но булеву алгебру-таки забыл. (X == Y) <=> (X&Y + !X&!Y)

(X&B == C) <=> (X&B&C + !(X&B)&!C) <=> (X&B&C + (!X + !B)&!C)

balodja ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.