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

Starkis
Member
From: Up in the space
Registered: 2011-01-16
Posts: 26

Dictionary type

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

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)


--- we no need no water, let the ... burn ---

Offline

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

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 13,503
Website

Re: Dictionary type

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.

Online

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

dataman
Member
From: The Milky Way's outskirts
Registered: 2010-07-18
Posts: 5

Re: Dictionary type

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 sad

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

Offline

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

Starkis
Member
From: Up in the space
Registered: 2011-01-16
Posts: 26

Re: Dictionary type

I only could dream about AntiDOT implementation in synopse style wink

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 smile


--- we no need no water, let the ... burn ---

Offline

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

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 13,503
Website

Re: Dictionary type

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.

Online

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

Philnext
Member
Registered: 2011-11-03
Posts: 17

Re: Dictionary type

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

Offline

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

Starkis
Member
From: Up in the space
Registered: 2011-01-16
Posts: 26

Re: Dictionary type

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? smile

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

+1 vote for the dedicated TDynDictionary wink


--- we no need no water, let the ... burn ---

Offline

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

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 13,503
Website

Re: Dictionary type

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?

Online

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

Philnext
Member
Registered: 2011-11-03
Posts: 17

Re: Dictionary type

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 ?

Offline

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

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 13,503
Website

Re: Dictionary type

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.

Online

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

Starkis
Member
From: Up in the space
Registered: 2011-01-16
Posts: 26

Re: Dictionary type

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


--- we no need no water, let the ... burn ---

Offline

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

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 13,503
Website

Re: Dictionary type

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

Online

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

Starkis
Member
From: Up in the space
Registered: 2011-01-16
Posts: 26

Re: Dictionary type

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 wink

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


--- we no need no water, let the ... burn ---

Offline

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

Starkis
Member
From: Up in the space
Registered: 2011-01-16
Posts: 26

Re: Dictionary type

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

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


--- we no need no water, let the ... burn ---

Offline

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

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 13,503
Website

Re: Dictionary type

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.

Online

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

Starkis
Member
From: Up in the space
Registered: 2011-01-16
Posts: 26

Re: Dictionary type

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?


--- we no need no water, let the ... burn ---

Offline

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

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 13,503
Website

Re: Dictionary type

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.

Online

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

Starkis
Member
From: Up in the space
Registered: 2011-01-16
Posts: 26

Re: Dictionary type

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?


--- we no need no water, let the ... burn ---

Offline

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

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 13,503
Website

Re: Dictionary type

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

Online

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

RaelB
Member
Registered: 2010-08-04
Posts: 29

Re: Dictionary type

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

Offline

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

ab
Administrator
From: France
Registered: 2010-06-21
Posts: 13,503
Website

Re: Dictionary type

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

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

Online

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

RaelB
Member
Registered: 2010-08-04
Posts: 29

Re: Dictionary type

Thanks, that does work.

Offline

Board footer

Powered by FluxBB