Fast set membership check ?

[Richard]

I need to determine if a given number or string is in a set of
numbers or strings. The standard hack I'd do is make a search tree,
but in this particular application I'm going to be doing a boatload
of these comparisons over and over and over, and I just checking to
see if there's not some smarter way to go about it.

Discussion, links, etc. appreciated.

 

[Les Cargill]

I need to determine if a given number or string is in a set of
numbers or strings. The standard hack I'd do is make a search tree,
but in this particular application I'm going to be doing a boatload
of these comparisons over and over and over, and I just checking to
see if there's not some smarter way to go about it.

Discussion, links, etc. appreciated.

I'd use the file "hash.c" that comes with the Tcl source code. Email me
if you wannit attached to an email.

 

[Sidney Cadot]

I need to determine if a given number or string is in a set of
numbers or strings. The standard hack I'd do is make a search tree,
but in this particular application I'm going to be doing a boatload
of these comparisons over and over and over, and I just checking to
see if there's not some smarter way to go about it.

Discussion, links, etc. appreciated.

You might want to take a look at libjudy: http://judy.sourceforge.net

Best regards,

Sidney

 

[Richard]

(e-mail address removed) wrote...

You might want to take a look at libjudy: http://judy.sourceforge.net

That's a good link. Thanks!

 

[Les Cargill]

(e-mail address removed) wrote...

That's a good link. Thanks!

And a whole lot less intensive than the Tcl hash functions...

 

[Richard]

(e-mail address removed) wrote...

And a whole lot less intensive than the Tcl hash functions...

I pulled down hash.c, then judy, and thought the same thing. The
reduction in cache line fills is just the kind of performance
improvement I was hoping to find.

(Thanks for hash.c, Les.)