Hi

Is there an implementation of a hash map where the keys are integers. It is needed when the integers are too big for a lookup array. I only need check the existence of keys so the data type is not important. About like this:

var
  Len: integer;
  SeenLen: TIntMap; // or whatever the type is called
  ...
  if not SeenLen.Has(Len) then begin
    ... work with Len ...
    SeenLen[Len] := nil;  // If the data type is pointer
  end;

A related question:
What is the state of the generic containers now?
I want to use FPC 2.4.x features for this program and I will not experiment with new development code now, but some time later I will. Do the generic containers work equally well with primitive types like integer, pointer and string, and then with TObject derivatives? I would guess the primitive types are a challenge.

Regards,
Juha

important.

About like this:

uses fgl;
type
  TIntMap = specialize TFPGMap<Integer, Integer>; //Maps Int --> Int

FPC 2.4.x should be fine with generics, although 2.5 is still more advanced in that sector.

Best regards,
Andreas.

Andreas Schneider wrote

uses fgl; type TIntMap = specialize TFPGMap<Integer, Integer>; //Maps Int --> Int

Thanks. I tried that. However the class name, TFPGMap, turned out to be misleading. It inherits from TFPSMap which inherits from TFPSList, which is a list, not a map, as the name says.
Lists should be named as "List", not as "Map".

I already have a self-made TIntList. It has Quicksort and Find functions and it is as fast as can be. I made it years ago because I didn't find any proper alternative. (Java people don't need to do such things...)

Is it really so there is no generics HashMap container in fgl, or in other FPC libraries? Someone should make it!
And, the name "Map" should really be reserved for hash maps and not used for lists (= kind of poor man's map).

My prog has a big amount of integers, thats why an integer list is not enough. A binary search from a sorted list is pretty fast but the problem is that I am adding items to the list and it must be sorted after every addition.

My experience from string hashmaps says that the speed difference can be huge, compared to any list implementation.

Juha

I don't think the name map is misleading. It does exactly what a map does. It maps a type Key to another type Value. A list maps an integer(index) to a type Value The search is of course based on a list. Hash tables, as far as I know, are usually only profitable when you have a large number of insertions on keys that take a long time to compare

I don't think there's a generic hash table for FPC. So I'm sure many could benefit from it if you implemented it :)

There's a string based hash table in contnrs.pp

My prog has a big amount of integers, thats why an integer list is not enough. A binary search from a sorted list is pretty fast but the problem is

that

I am adding items to the list and it must be sorted after every

addition.

My experience from string hashmaps says that the speed difference can be huge, compared to any list implementation.

Afaik, inserting items into a sorted List is done via InsertSort, which is the fastest way (O(n))to go (IMHO), so you do /not/ have to resort the list. I am not really sure, how else you would implement a hash map ... internally you always have to have some list like structure, be it an array or a linked list. A tree wouldn't be really fast for lots of inserts, since rebalancing a tree isn't that cheap either.
Ok, sure, you could have a huge array of buckets that are either assigned or not, but IMHO that would waste too much memory or would have too much overlapping items/hashes.

Also I think "map" is the right term for what the TFPGMap does, even if it inherits from a list. A mapping is simply a relation from some key to some data, and thats exactly what TFPGMap does.

... take a long time to compare and to insert. Yes, I have that. Your comment about map definition is valid. "Map" doesn't define the implementation, "hashmap" would define it.

I don't think there's a generic hash table for FPC. So I'm sure many could benefit from it if you implemented it :) There's a string based hash table in contnrs.pp

Let's see :-)

Juha

Andreas Schneider wrote

Afaik, inserting items into a sorted List is done via InsertSort, which is the fastest way (O(n))to go (IMHO), so you do /not/ have to resort the list.

True. I could optimize the current implementation a little. Now I insert and then sort. However, inserting means moving lots of data which is slow, and on the other hand quicksort is very fast when data is "almost sorted" already. I would not expect any big speed-up there.

"waste too much memory" ... No, hash arrays are always implemented as an array of buckets. The only drawback is that you must know about the size of your data in advance. Otherwise the array is too big and wastes memory or it is too small and thus slow because of overlapping items/hashes.

I can tell about my experience of a string hashmap with Delphi. I had a reporting feature in my application. The huge amount of data was read from an in-memory tree-DB which is very fast and didn't slow things down. (I plan to publish the related component soon...)
Due to a complex data structure there were duplicate lines in the report. It was not enough to check for duplicates in 1 record, I had to check the whole generated report line. I used TStringList for that. The report took > 20 minutes to generate... I optimized, pre-calculated things... the time dropped to 8 minutes. Not bad.
I realized most time was spent checking for duplicate report lines. I figured by using a hash map I could cut that time maybe to half, to 4 minutes (!).

I used the class StringHashMap which I later extracted and ported to FPC and published:
http://wiki.freepascal.org/StringHashMap
It seems to be a very fast implementation of a string hash map.

After that the report was generated in 6 seconds (not minutes, seconds!). I was looking at the memory consumption. According to Windows resource diagram 850 MB mem was used with the old version. With the new version it was maybe 860 MB. Who cares really... Total mem was 1 GB.

Also I think "map" is the right term for what the TFPGMap does, even if it inherits from a list. A mapping is simply a relation from some key to some data, and thats exactly what TFPGMap does.

True, the name "map" does not define the implementation. But still, most often a "map" is implemented as a hashmap. I was surprised that it is not so in this case. I felt almost like cheated in fact ... sorry :-)

Juha

Andreas Schneider wrote

uses fgl; type TIntMap = specialize TFPGMap<Integer, Integer>; //Maps Int --> Int

I compared the performance of this generics map to a simple integer list. The map was much slower and it also ate huge amouts of memory, > 1.5 GB. Strange. My data is only some kilobytes, not gigabytes. The code runs in parallel threads. Could that be a problem? Anyway, I will look for some other lookup methods now...

Juha