Which Search Tree To Use ?

[Atropaki]

Hi friends,

I have a file to process in which I have keys in pairs in a line like
key1 key2 relation1
where key1 and key2 are strings and relation is a double value. I may have up to 1 million lines and may have duplicate key lines like
key1 key3 relation2
key1 key2 relation1_1
and goes on. Can some one tell me which kind of search tree (AVL, splay, ternary etc.) to use for maximum insertion and search speed.
Reply to :
keruru@turk.net

 

[JOLESEN]

I would go for the std. library set<class>.

Create a class holding the 3 fields from the records.
Code operator < for this class.

Now you can simply do somthing like this

set<MyClass> my_set;

for each record : construct an object :

MyClass obj(field1, field2, field3);
my_set.insert(obj);

set will only hold unique values, so if the object already exist (Your operator < will help to decide that), it will be replaced by the new object.

set is extremly efficient, and it is very easy to use.

/JOlesen

 

[Atropaki]

Hi Mr. Olensen,

Thank you for your reply. I also read a reply of yours in a different thread. First of all I am not a C++ programmer but a C indeed. I put the thread to wrong place I guess. Anyway what I am really trying to do is I have to keep every record I have. I am parsing a spice netlist. I have to find
1)the number of unique nodes.
2)The number of other unique nodes connected to every unique node if exist.
3)If I have duplicate nodes I have to find the number of different connections between these two same nodes also.
For Example:

R1 kerem osman 2.3
R2 kerem osman 5.2
R3 kerem osman 4.8
L1 kerem osman 9.2
L2 kerem osman 1.2
K1 L1 L2 0.5

This means that I have 2 unique nodes. Node kerem is connected to node osman with 3 Rs and 2 Ls. I have to record each double value at the end for each of these connections. Also I have to record the sum of all R and L values between kerem and osman.

Same thing is done between osman and kerem also.

K's are a different story to handle.

I can handle it in 2 minutes for a 50 MB file but wondering if I can make it faster.

Thank you for your recommendation(s) from now on.

 

[JOLESEN]

Ok, a bit more complicated than I thought ... I am not sure I understand it yet.
However if you want to use C, I won't dig into it.

Good luck !

/JOlesen