Forum > General

[SOLVED] Hash list with integer as key

(1/5) > >>

Dibo:
Hi,

I need a list where I add some integers. Size of list can be very
small but also very big (>10k). I need fast solution to quickly check
if integer already exists. TList is too slow. Im using now TFPHashList
with key as integer converted to string. Is exist something with key
as integer? Because converting integer to string cost CPU, not much if
used periodically but I also need compare two big hashed lists.

Regards

Blaazen:
Maybe TFPGMap from unit FGL?

Dibo:
Yes I thought about this too but I saw fight on news group that it is not hashed, just sequence search like in TList. Didn't check speed in my own tests yet

MathMan:

--- Quote from: Dibo on December 12, 2014, 07:34:23 pm ---Hi,

I need a list where I add some integers. Size of list can be very
small but also very big (>10k). I need fast solution to quickly check
if integer already exists. TList is too slow. Im using now TFPHashList
with key as integer converted to string. Is exist something with key
as integer? Because converting integer to string cost CPU, not much if
used periodically but I also need compare two big hashed lists.

Regards

--- End quote ---

Hi Dibo,

Just to check that I got it right - the items in the list are integers (32 / 64 bit?), you need to check if an integer is in the list and you need to compare two lists. And all this is time critical so you are looking for the fastest solution.

First I have a question regarding the comparison you mention. Shall the comparison only state if two lists are equal or do you need a comparison that shows if elements are in one list but not the other?

Regarding your approach - calculation of a hash value (at least a reasonable one that does not generate too many collisions) is time consuming. The values you maintain in the list can easily be compared directly - so you have a fast comparison of items. In this case I would guess that a balanced binary tree is faster - even for the sizes you mention (>10k entries). The comparison of two balanced binary trees is slower than comparing two hash lists - so the decision which way to go also depends on how often you need to compare full lists.

Kind regards,
MathMan

Windsurfer:
If the list is sorted, a binary search is fastest.

If this is the case, I have a routine to search a sorted array of strings TDateTime values that could be modified.

Navigation

[0] Message Index

[#] Next page

Go to full version