Kevin Pulo <[email protected]> writes:
> On Thu, Apr 02, 2009 at 05:57:17PM +1100, Daniel Pittman wrote:
>
>> jm <[email protected]> writes:
>> > jm wrote:
>> >
>> >> Does anyone know of any algorithms for speeding up searching of access
>> >> control lists? Is there anything more efficient than a sequential search?
>>
>> In answer to your original question, sure there are more efficient ways.
>> Use a better search algorithm, structure the tests so you can
>> efficiently locate the applicable rules. A trie or tree structure might
>> work, if the memory locality issues don't kill you.
>
> One neat way of slightly speeding up repetitive linear searches, when
> you're truly stuck with them, is to use a rocking search. This is
> just a linear search which alterates between searching forwards and
> backwards, recycling the first/last element as it does. This gets you
> down from O(mn) to O(m(n-1)) for n elements and m searches, which can
> be useful if m is huge (particularly wrt to n).
Wouldn't sorting and using a boolean search, or just using a skiplist be
both faster and more efficient in the general case?
It strikes me that the rocking search is likely to cause some fairly
awful memory access patterns, too; most systems don't really like
reading backwards these days, but prefer to scan forwards, no?
Regards,
Daniel
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
