Hello,I suggest that you change the TFPGMap in fgl.

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Hello,I suggest that you change the TFPGMap in fgl.

김봄
if TFPGMap::Sorted is True, then Add method time complexity is O(n) and Indexof,Find method is O(lg n).

or Sorted is False, then Add method is O(1) and Indexof,Find is O(n)

but, most language's map implementation is red/black tree or hashtable.

i don't know why free pascal's map is based on array.

if map implementation is hashtable or r/b tree, then Add,Indexof,Find method have a
log or constant time complexity.

please, answer my suggestion.

sorry for my english.

sincerely.

==

yonsei univ. in korea, kimbom.


_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Hello,I suggest that you change the TFPGMap in fgl.

leledumbo
Administrator
> i don't know why free pascal's map is based on array.

Because the unit was meant mainly for testing the generics support and if you read the line right before the unit clause:
https://github.com/graemeg/freepascal/blob/master/rtl/objpas/fgl.pp#L20

Still, there's no problem having array backed map, the convenience of map data structure is still achieved, it's just the speed that matters.  Use fcl-stl instead, it has gmap which is rbtree backed and ghashmap which is hashtable backed.
Reply | Threaded
Open this post in threaded view
|

Re: Hello, I suggest that you change the TFPGMap in fgl.

Felipe Monteiro de Carvalho
In reply to this post by 김봄
Hello,

You could always send a patch with a TFPGHashedMap or TFPGRedBlackMap
implementation.

thanks,
--
Felipe Monteiro de Carvalho
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal