Recent

Author Topic: [SOLVED] Hash list with integer as key  (Read 14001 times)

MathMan

  • Full Member
  • ***
  • Posts: 205
Re: [SOLVED] Hash list with integer as key
« Reply #15 on: December 17, 2014, 11:50:08 pm »
Well, I just used EpickTimer. This is my whole unit, nothing amazing, just connect events to buttons:
Tested myself, it's amazing to know how TFPGMap can beat all other maps though this might be key type specific. THashmap depends much on the hash function, but even a simple `a mod n` is not enough to beat TFPGMap. The final result is a tight gap on insertion, on searching both are equal.

Hi Leledumbo,

I got intriqued and wanted to take a look. Only found the sources in fgl.pp which are unfortunately "reluctantly commented" and an old post from 2010 when there wasn't one available. Has that changed since?

Regards,
MathMan

Leledumbo

  • Hero Member
  • *****
  • Posts: 8273
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: [SOLVED] Hash list with integer as key
« Reply #16 on: December 18, 2014, 05:41:28 am »
I got intriqued and wanted to take a look. Only found the sources in fgl.pp which are unfortunately "reluctantly commented" and an old post from 2010 when there wasn't one available. Has that changed since?
Nope I guess. The latest changes to fgl unit seems to be the addition of enumerator to some classes but that's all AFAIR. No documentation yet, and the unit status seems still the same: testing unit for fpc generics support

Khumarahn

  • New Member
  • *
  • Posts: 10
Re: [SOLVED] Hash list with integer as key
« Reply #17 on: August 06, 2015, 10:50:18 pm »
Hi. I am a novice.

I need a reasonably fast map<string, integer>. I tried TFPGMap on a very simple example:
Code: [Select]
Program Lesson1_Program1;   

uses fgl, sysutils;

type
  TMap = Specialize TFPGMap<string, integer>;

var
  Map: TMap;
  i: longint;
Begin
 Map := TMap.Create;
 for i:=0 to 100000 do
   Map['item #' + IntToStr(i)] := i;
End.

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?

Leledumbo

  • Hero Member
  • *****
  • Posts: 8273
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: [SOLVED] Hash list with integer as key
« Reply #18 on: August 07, 2015, 03:56:17 am »
Did I make a mistake somewhere?
Nope, it's just not a map in the sense of hash map. TFPGMap is a list with map-like behavior. ghashmap from fcl-stl package should give what you want, but currently only available and working correctly in either 3.0 fixes branch or trunk. 2.6.4 won't do.
« Last Edit: August 07, 2015, 04:01:28 am by Leledumbo »

Khumarahn

  • New Member
  • *
  • Posts: 10
Re: [SOLVED] Hash list with integer as key
« Reply #19 on: August 07, 2015, 10:25:36 am »
ok, thank you much. It is very weird that map is still not implemented - pascal is an old language...

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 8795
  • FPC developer.
Re: [SOLVED] Hash list with integer as key
« Reply #20 on: August 07, 2015, 10:40:41 am »
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

  • Guest
Re: [SOLVED] Hash list with integer as key
« Reply #21 on: August 07, 2015, 10:48:13 am »
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.
« Last Edit: August 07, 2015, 10:53:10 am by derek.john.evans »

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 8795
  • FPC developer.
Re: [SOLVED] Hash list with integer as key
« Reply #22 on: August 07, 2015, 11:21:12 am »

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?

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

(output of my unit test)
Code: [Select]
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

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

derek.john.evans

  • Guest
Re: [SOLVED] Hash list with integer as key
« Reply #23 on: August 07, 2015, 11:34:38 am »
This speeds up the element adding.

Map.Sorted:=True;     

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

Khumarahn

  • New Member
  • *
  • Posts: 10
Re: [SOLVED] Hash list with integer as key
« Reply #24 on: August 14, 2015, 10:39:55 am »
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.

 

TinyPortal © 2005-2018