Dictionary type

Starkis · 2011-02-06 16:22:37

Delphi 7 doesn't have dictionary type collection - maybe there are custom units for that? generics also are not available for the D7

found:
- delphi collections (http://www.warmachine.u-net.com/delphi_collections/)
- decal (http://sourceforge.net/projects/decal/)
and several variations, but users complain about poor performance :-/

Last edited by Starkis (2011-02-06 19:14:42)

ab · 2011-02-07 08:02:45

You can use our SynBigTable unit, and never store content on disk.
For that, use a temporary file name, then never call UpdateToFile method.
All content will stay in memory.

You'll have fast performance, and Delphi 6-XE compatibility.

Using TSynBigTableRecord, your collection will be able to have fields within each record, and internal indexes for fast retrieval.

Note that by using a temporary file, your collection could use much more space than the current RAM available: this unit flushes the in-memory data to disk when 256 MB of data is stored in RAM (manual flush was confusing for some users) - see the new BIGTABLE_AUTOFLUSH_SIZE constant.

dataman · 2011-03-19 20:46:29

Starkis wrote:

Delphi 7 doesn't have dictionary type collection - maybe there are custom units for that? generics also are not available for the D7
found:
- delphi collections (http://www.warmachine.u-net.com/delphi_collections/)
- decal (http://sourceforge.net/projects/decal/)
and several variations, but users complain about poor performance :-/

I like RBS AntiDOT library

Starkis · 2011-11-20 12:56:48

I only could dream about AntiDOT implementation in synopse style

Of course every dictionary can be handled by DB, but personally separate notions of lightweight memory storage dictionary and all purpose heavier sibling DB table. Maybe that's the effect with beeing familiar with other language

ab · 2011-11-20 14:10:31

Those RBS Libraries are well written, but not optmized for speed.
And they lack of a true MPL license and source code repository IMHO.
They are not free for commericial applications, AFAIK.

Did you try our TDynArray and TDynArrayHashed wrappers?
They could perctfly fit the need of such dictionaries.

Philnext · 2011-11-21 19:26:13

I confirm that TDynArrayHashed is OK for TDictionnary replacement, except that the syntax is quite different and TDynArrayHashed is more efficient and compatible with more Delphi versions.
If there was a TDynArrayHashed descendant (ie TDynDictionnary) with a syntax more close to TDictionnary's one I would (and surely other people do) use it in more projects !!

Starkis · 2011-11-21 20:00:04

I have seen TDynArray, but haven't used it - as I look TDynArrayHashed is much better candidate for the TDynDictionary. And interface wishes to resemble traditional ones more - maybe .NET?

And don't follow the Count issue? what's the problem to define dedicated class attribute Count for the TDynDictionary with entries and buckets ...

+1 vote for the dedicated TDynDictionary

ab · 2011-11-22 06:25:10

About the Count variable, it did make sense to make it stand-alone when using a wrapper.

In fact, all data is external to TDynArray/TDynArrayHashed.
And the data is either:
- A dynamic array and its internal count (slower but standard);
- A dynamic array and an external count variable (faster).

A TSynDictionnary (i.e. including Count variable) could make sense in some cases... but what about the dynamic array itself?

Philnext · 2011-11-22 08:31:13

Arnaud,
I don't have sufficient level of knowledge in Delphi but isn't it possible to internally, in the wraper, create the dynamic array ?

ab · 2011-11-22 10:34:01

I can code something to create the dynamic array internally - but in this case, how will you access to the items?

The compiler needs to have a basic element type for accessing the dynamic array content.

A generic-based syntax could be envisaged, but it will not work before Delphi 2009 - and in this case, there are already some existing units and classes.

Starkis · 2011-11-23 15:02:25

dynamic array (TDynArray) could be used as a dictionary, but it is much better use hashed dynamic array (TDynArrayHashed). Current state of those two out of the box doesn't encourage their usage for the dictionaries - Count is an example of additional wrapping type for the dedicated dictionary type (Count + TDynArrayHashed). If there would be question: "Is it posible and doible to use TDynArray* out of the box to simulate dictionary" answer by all means would be "Yes". Current state seems more like a sceleton for developer friendly/habitual usage, what Philnext and have noticed.

What I like in synopse, is theirs attitude - attitude towards efficiency. Maybe AntiDOT idea of instantiation, synopse efficiency and attitude with the simulated Delphi 2009 dictionary interface could be the way for the developer friendly and object-oriented complete functional dictionary implementation? that way without generics and subset of Delphi 2009 dictionary interface (count, keys, values & etc) efficient dictionary could be available before the Delphi 2009

Last edited by Starkis (2011-11-24 16:39:38)

ab · 2011-11-24 06:24:58

So I follow your mind, we'll need a generic-based implementation of a dictionary, using TDynArrayHashed behind the scene for its handling.

Starkis · 2011-11-24 16:50:18

sort of - hope I have managed intelligibly to convey an essence. Good ideas come out of nowhere, so others may have more or even better ones for the TSynDictionary

Last edited by Starkis (2011-11-24 16:51:38)

Starkis · 2011-12-14 16:24:37

ab, is there any hope of movement in synopse version of dictionary direction?

As I read, there was (maybe still is?) memory leak problem with the TDictionary in Delphi 2009

ab · 2011-12-14 16:30:27

At this time, I want my code to run with Delphi 7 (at least), so I do not want to depend on generics.

Therefore, I've no plan to implement a TSynDictionary in the close future.

Starkis · 2012-01-18 18:46:41

dictionary implementation is actually quite simple, the only thing that stop me is lack of the idea/knowledge how to create appropriate backing (entries) array (in a form of TSynDictionary.Create(integer, string) for the key value pair (record) with integer keys and string values). Is any way to simulate such "generics" in Delphi prior 2009?

ab · 2012-01-18 18:58:12

AFAIK there is no way of simulating such "generics" notation prior Delphi 2009.

You will have to rely on a separated declaration of a record, then use TypeInfo(aRecordType), just like our TDynArray wrapper.

It is a bit more verbose, but, in fact, not a big issue.

Starkis · 2012-01-19 19:51:33

I follow the reason of moving hash to the buckets (index and hash in fHashs) in TDynArrayHashed, but how to you protect for the same hash problem? can't think up an elegant solution for the next index without generics in entries. Do you sort or fully iterate the fHashs?

ab · 2012-01-19 20:20:08

The main interest of using a hash instead of an index is to use a lookup list in order to reach close to O(1) resolution time:
- Hash is calculated on the searched value;
- Position is found in the hash look up table;
- In case of no hash collision, it is found instantly - in case of hash collision, it will be a bit slower, because it will search until a match is found, or a hash item is not set (void position);*
- Since all hashes are in a separate lookup list, iteration is very fast, since it will be already in the CPU L1 cache.

Whereas using the hash only for comparison and fully iterate the list will be O(n), i.e. much slower in case of high number of items.
It will be faster than plain comparison of items content (and, due to CPU cache, not necessary much faster), but it still won't scale.

Believe me, the current implementation is fast.
I did not invent it, just re-implemented a very proven solution.

See http://en.wikipedia.org/wiki/Hash_table

RaelB · 2014-09-14 13:47:32

ab wrote:

You can use our SynBigTable unit, and never store content on disk.
For that, use a temporary file name, then never call UpdateToFile method.
All content will stay in memory.
You'll have fast performance, and Delphi 6-XE compatibility.

Hi,

I was in the process of trying to use TSynBigTable as a dictionary, but then read comment that says "keys" (i.e. ID's), have to always be added sequentially. This would seem to make it impossible to use the unit as a dictionary...

ab · 2014-09-14 14:15:26

If you use TSynBigTable, the IDs are indeed sequential IDs.
So it is not a dictionary, more like an array.

But if you use TSynBigTableString, IDs are case-sensitive strings.
Sounds pretty much like a dictionary, this time.

RaelB · 2014-09-18 14:01:54

Thanks, that does work.

mORMot Open Source

#1 2011-02-06 16:22:37

Dictionary type

#2 2011-02-07 08:02:45

Re: Dictionary type

#3 2011-03-19 20:46:29

Re: Dictionary type

#4 2011-11-20 12:56:48

Re: Dictionary type

#5 2011-11-20 14:10:31

Re: Dictionary type

#6 2011-11-21 19:26:13

Re: Dictionary type

#7 2011-11-21 20:00:04

Re: Dictionary type

#8 2011-11-22 06:25:10

Re: Dictionary type

#9 2011-11-22 08:31:13

Re: Dictionary type

#10 2011-11-22 10:34:01

Re: Dictionary type

#11 2011-11-23 15:02:25

Re: Dictionary type

#12 2011-11-24 06:24:58

Re: Dictionary type

#13 2011-11-24 16:50:18

Re: Dictionary type

#14 2011-12-14 16:24:37

Re: Dictionary type

#15 2011-12-14 16:30:27

Re: Dictionary type

#16 2012-01-18 18:46:41

Re: Dictionary type

#17 2012-01-18 18:58:12

Re: Dictionary type

#18 2012-01-19 19:51:33

Re: Dictionary type

#19 2012-01-19 20:20:08

Re: Dictionary type

#20 2014-09-14 13:47:32

Re: Dictionary type

#21 2014-09-14 14:15:26

Re: Dictionary type

#22 2014-09-18 14:01:54

Re: Dictionary type

Board footer