Fast searching algorithms in C

[felix]

Hi Guys,

I'm searching for fast searching algorithms, I found about hash tables and btree algorithms. I got some files from web how it work and I'm starting to read now. But I couldn't find a good example in C.

Can someone give-me a example of hash table and/or btree ?

ps: What do you prefer hash table or btree ? why ?

Thks a lot.

Regards,

[felix]

Ahh, I'm not sure if It help, but I will use it fast searching algorithm in a file, like if it was a table with some coluns in a database. ;)

But I'm searching to this algorithms just because I don't want to use a database... hehehe

Regards,

[i3839]

With thing like this (hashes, trees, sorting algorithms) it's much better to know how they work instead of seeing some code that implements them. Once you understand the idea it shouldn't be too hard to make an implementation yourself, which perhaps isn't the fastest or best, but that's not the goal anyway (it's about learning and fun).

You can find a lot of trees and hashes in the kernel source code, if you want searching stuff then the source code of e.g. slocate can be interesting.

I prefer trees above hashes because although hashes are closer to O(1), they aren't really and are a bit ugly (use a lot of memory, added complexity thanks to collisions and in the end they're just an array of pointers to linked lists ;-).

It more important how you handle the data than what searching algorithm you use. I mean, if you're sure that the list of items isn't much bigger than, say, 1000 items than even using a flat, simple linked list isn't really noticeable. If that file won't fit into memory then that will have a much bigger impact.

[felix]

Hi i3839,

Thks for your reply. I finished to read about the hash and btree (and some variations like b*tree and b+tree) and it's newer for me, so I'm a little confused yet, but in general I think I know how to insert and delete values from tree. hehehe ;)

I will take a look at source of updatedb and locate and see if I understand it, to try implement something... like exercise I'm thinking in write a code that generate a tree from all my .c source codes and a description and then I can search, insert and delete from it, etc

I will try, if I have problems I post here..

Thks for your reply.

Regards,

[Nope]

I also prefer binary trees when I have to deal with dynamic data. The
structure is simple, yet powerful and I like that. But I have to admit that
my last btree construction in C++ is one ugly piece of code which is part
of the management of the dynamic file cache of my web-server. I'd like
to have it balanced, but the speed loss for analysing such a thing doesn't
allow it, so I have implemented (and still expanding this) code to at least
keep it in an optimised state after adding or removing nodes. This also
forbids recursive functions, so I use a translucent (weighted) tree type.
The btree portion of the file cache is now beyond 700 lines of code.

[ellzey]

Do you understand linked lists? If you don't yet, I would look at them before going into hashing.

Btree's and hashing, are in some ways, very different from eachother. Not many hash imp's revolve around sorting, (like all btree varients, transucent to splays). Hashing is for fast access to memory with minimal searching. The art of the hash comes into your hashing routine (how you make your data into an integer that can fit into that array). The less collisions the better (this is only in some cases though, I have recently worked on a project where I wanted more collisions, since I actually splay'd out instead of doing LL's for my collisions).

Hashing in concept is very easy.

Take a peice of data, turn it into a number. Make that number fit into the number of elements you defined in an array. Of course this is simplifying it quite a bit.

You can get some good examples from here, but algorithms in C has a very good example and explaination in there. You can find the examples free on the internet.

[felix]

Hi,

Thks all for help and attention! I will check your tips.. ;)

Regards,