[clug] access control list search algorithms

[Kevin Pulo]

On Thu, Apr 02, 2009 at 05:57:17PM +1100, Daniel Pittman wrote:

> jm <jeffm at ghostgun.com> 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).

Kev.

-- 
.----------------------------------------------------------------------.
| Kevin Pulo                Quidquid latine dictum sit, altum viditur. |
| kev at pulo.com.au               _ll l_ng__g_e_ _r_ hi__ly p__d_ct__le. |
| http://www.kev.pulo.com.au/         God casts the die, not the dice. |
`--------------- Linux: The choice of a GNU generation. ---------------'
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.samba.org/archive/linux/attachments/20090406/19a63b0d/attachment.bin