Which class offers the fastest search ???

Dear visitor, welcome to QtForum.org. If this is your first visit here, please read the Help. It explains in detail how this page works. To use all features of this page, you should consider registering. Please use the registration form, to register here or read more information about the registration process. If you are already registered, please login here.

myfairlady

Beginner

Posts: 35

Occupation: Software Engineer

Monday, May 9th 2005, 1:53pm

Which class offers the fastest search ???

I want to implement a cache in my program. Which data structure in Qt can I use for that. There is QMap, QPtrDIct, QIntCache. But i want to use the one which is fast in searching ( lookup ). Which one offers the best lookup speed???

Go to the top of the page

wysota

Sage

Posts: 4,276

Location: Warsaw, POLAND

Monday, May 9th 2005, 2:49pm

RE: Which class offers the fastest search ???

Hmm... the proper answer is "it depends". The real answer is probably "none of them". You didn't even tell us what do you want to cache.

QtCentre.org - the largest Qt community site and forum where questions get answered

Go to the top of the page

myfairlady

Beginner

Posts: 35

Occupation: Software Engineer

Tuesday, May 10th 2005, 1:20pm

RE: Which class offers the fastest search ???

It depends on what ??
My problem is I have to implement a cache which stores some details abt a particular class ( just like key-value pairs in a hash ) . So for this I shuld use either a QMap or a QPtrDict ( i came across these two in the docs). So My declaration will be say,
QMap< int, Class*> .
At a later stage i need to lookup the values given a particular id( the key ).
So i want to know which of these 2 ( QMap/ QPtrdict ) offers better searching speed. I want the lookup to be very fast even if insertion is slow.

In the docs it is given that QMap is a value-based and QPtrDict is pointer-based, so does tht mean that QPtrDict is faster in searching ???
Which has faster lookup and why ???

Go to the top of the page

dimitri

Professional

Posts: 1,311

Occupation: Engineer

Tuesday, May 10th 2005, 2:12pm

RE: Which class offers the fastest search ???

Ah, but this is not a cache, not with the usual meaning at least.

Go to the top of the page

wysota

Sage

Posts: 4,276

Location: Warsaw, POLAND

Tuesday, May 10th 2005, 3:40pm

RE: Which class offers the fastest search ???

I think lookup time will be the same for both of these classes. But I think you should use a binary tree instead

Or even a B-tree. The latter are used for database indexes, so you can say they are pretty fast

QtCentre.org - the largest Qt community site and forum where questions get answered

Go to the top of the page

jacek

Master

Posts: 2,729

Location: Warsaw, Poland

Tuesday, May 10th 2005, 4:23pm

RE: Which class offers the fastest search ???

Quoted

Originally posted by wysota
Or even a B-tree. The latter are used for database indexes, so you can say they are pretty fast

B-trees are fast because they require less IO operations, but they won't outrun a balanced binary tree, if it fits in the memory.

Quoted

Originally posted by myfairlady
In the docs it is given that QMap is a value-based and QPtrDict is pointer-based, so does tht mean that QPtrDict is faster in searching ???
Which has faster lookup and why ???

QMap is value based (i.e. it holds copies of your objects), so every time you insert something it will make a copy. QPtrDict doesn't make copies, so insertions should be faster, but I don't see any reason why QMap should have lower lookup speed.

You could write a little benchmark to check which one is really faster.

You can meet me at Qt Centre - The Ultimate Qt Community site.

Go to the top of the page

chickenblood

Professional

Posts: 657

Location: Mountain View, CA

Occupation: Data Monkey

Tuesday, May 10th 2005, 6:16pm

RE: Which class offers the fastest search ???

..and then of course there's QIntCache.

I have enough sense to know that "common sense" is an oxymoron.

Go to the top of the page