Forum > General

[SOLVED] Hash list with integer as key

<< < (5/5)

marcov:
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.

derek.john.evans:
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.

marcov:

--- 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)

derek.john.evans:
This speeds up the element adding.

Map.Sorted:=True;     

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

Khumarahn:
Thank you all for your advice. I found an implementation of red-black trees for pascal here:
http://www.vanwal.nl/rbtree/
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.

Navigation

[0] Message Index

[*] Previous page

Go to full version