Forum > General

[SOLVED] Hash list with integer as key

<< < (5/5)

Well, it is specially the scripting languages that are big on maps because stringly typed code is the norm there.

But even considering that Free Pascal does have a back log there. As said there are various options, but none made default state yet.

There are a few <string, pointer> maps you can try.

TStringHashList in StringHashList
TFPObjectHashTable in contnrs (must set AOwnsObjects to False to store integers)

lazfglhash has this which looks interesting.
generic TLazFPGHashTable<T> = Class(TFPCustomHashTable) 

A search for 'hash' of the lazarus libraries brings up lots of options. I'd stick with the FP stuff.

This seems super fast, but allocates an object per integer.
TMap = specialize TLazFPGHashTable<Integer>;

Typecasting to a Pointer would be better/faster but then may not be classed as 100% correct coding.


--- Quote from: Khumarahn on August 06, 2015, 10:50:18 pm ---
and running it takes 1 minute and 30 seconds on a relatively new i5 processor. It looks very slow. Did I make a mistake somewhere? Or I should look for some other data structure?

--- End quote ---

That's slower than needed btw, even for non hashes, I do 400000 in .4s

(output of my unit test)

--- Code: ---using blocksize: 256
Generate 400000 integers of unique random data
1 creating lightstrmap with 400000 elements containing x=random  <x as string,x as pointer> mappings      0.4070 seconds

Check: items in map:400000
2 Testing contents of randomly filled string map     0.4840 seconds
3 Removing all even elements, and checking result     0.7660 seconds
Check: items in map:200000
99 destroying lightmap

Test for 400000 items took     1.6880 seconds

--- End code ---

(this code is an optimalization for code that used a tstringlist before, and being ordered was very important)

This speeds up the element adding.


But, TLazFPGHashTable is still faster. TFPDataHashTable works if you typecast to Pointer.

Thank you all for your advice. I found an implementation of red-black trees for pascal here:
This is a translation from c++ stl implementation, as far as I understood.

I used it to write a custom version of map, which works for my purposes. So far everything is very fast on tens of millions of elements.


[0] Message Index

[*] Previous page

Go to full version