www.digitalmars.com         C & C++   DMDScript  

D - Associative arrays...

reply lesnin rpi.edu writes:
I'm curious, how is the associative array type implemented? is it merely a
dynamic array with two sets of data per element, or is it implemented as a
linked list, or bst or something?

I looked through the D documentation and couldn't find an answer, so I figured
I'd ask here.

Thanks,
--Nick
Feb 23 2003
parent reply Nick Lesniewsk-Laas <lesnin rpi.edu> writes:
OK, I asked prematurely.  I realized soon after posting this question that the
source was right in front of my nose.  Granted it looks rather confusing to my
tired eyes, but it looks like a bst, no?  Is it balanced or anything funky like
that?  Yeah I'll probably figure that out on my own in a minute, so sorry to
bother you guys with these posts!

--Nick


In article <b3a2vd$2u5b$1 digitaldaemon.com>, lesnin rpi.edu says...
I'm curious, how is the associative array type implemented? is it merely a
dynamic array with two sets of data per element, or is it implemented as a
linked list, or bst or something?

I looked through the D documentation and couldn't find an answer, so I figured
I'd ask here.

Thanks,
--Nick

Feb 23 2003
parent reply "Walter" <walter digitalmars.com> writes:
"Nick Lesniewsk-Laas" <lesnin rpi.edu> wrote in message
news:b3a5ne$30au$1 digitaldaemon.com...
 OK, I asked prematurely.  I realized soon after posting this question that

 source was right in front of my nose.  Granted it looks rather confusing

 tired eyes, but it looks like a bst, no?  Is it balanced or anything funky

 that?  Yeah I'll probably figure that out on my own in a minute, so sorry

 bother you guys with these posts!

It's a hashed array of binary trees. Such is a simple data structure, but I've found with years of experience that it is as efficient as about anything else. The reason this isn't mentioned in the D spec is because the underlying algorithm is left up to the implementor, leaving them plenty of room to come up with a better scheme.
Feb 23 2003
next sibling parent reply "Mike Wynn" <mike.wynn l8night.co.uk> writes:
how do I change the underlying impl of assoc arrays ?
for instance to allow
typedef int delegate ( int, Object ) mydp;
mydp[char[]] foo;

which I can't do at present;

or within my win32 lib I use a assoc array for message handler lookup, I
wnat to try some cacheing algorythms in the assoc array (keep the last
message, and keep track of the order x is usually followed by y etc)



"Walter" <walter digitalmars.com> wrote in message
news:b3bacm$tng$2 digitaldaemon.com...
 "Nick Lesniewsk-Laas" <lesnin rpi.edu> wrote in message
 news:b3a5ne$30au$1 digitaldaemon.com...
 OK, I asked prematurely.  I realized soon after posting this question


 the
 source was right in front of my nose.  Granted it looks rather confusing

 tired eyes, but it looks like a bst, no?  Is it balanced or anything


 like
 that?  Yeah I'll probably figure that out on my own in a minute, so


 to
 bother you guys with these posts!

It's a hashed array of binary trees. Such is a simple data structure, but I've found with years of experience that it is as efficient as about anything else. The reason this isn't mentioned in the D spec is because

 underlying algorithm is left up to the implementor, leaving them plenty of
 room to come up with a better scheme.

Feb 24 2003
parent reply "Walter" <walter digitalmars.com> writes:
"Mike Wynn" <mike.wynn l8night.co.uk> wrote in message
news:b3dh66$2r71$1 digitaldaemon.com...
 how do I change the underlying impl of assoc arrays ?
 for instance to allow
 typedef int delegate ( int, Object ) mydp;
 mydp[char[]] foo;

 which I can't do at present;

 or within my win32 lib I use a assoc array for message handler lookup, I
 wnat to try some cacheing algorythms in the assoc array (keep the last
 message, and keep track of the order x is usually followed by y etc)

That should work.
Feb 24 2003
parent reply "Mike Wynn" <mike.wynn l8night.co.uk> writes:
it does as does

alias char[] str;
str[whatever] foo;

and I'm 100% sure that never worked b4.

back to the orginal question ... how do I change the underlying impl ?

"Walter" <walter digitalmars.com> wrote in message
news:b3ets5$cah$1 digitaldaemon.com...
 "Mike Wynn" <mike.wynn l8night.co.uk> wrote in message
 news:b3dh66$2r71$1 digitaldaemon.com...
 how do I change the underlying impl of assoc arrays ?
 for instance to allow
 typedef int delegate ( int, Object ) mydp;
 mydp[char[]] foo;

 which I can't do at present;

 or within my win32 lib I use a assoc array for message handler lookup, I
 wnat to try some cacheing algorythms in the assoc array (keep the last
 message, and keep track of the order x is usually followed by y etc)

That should work.

Feb 24 2003
parent "Walter" <walter digitalmars.com> writes:
"Mike Wynn" <mike.wynn l8night.co.uk> wrote in message
news:b3eu93$cgd$1 digitaldaemon.com...
 back to the orginal question ... how do I change the underlying impl ?

Modify the library code in \dmd\src\phobos
Mar 05 2003
prev sibling parent reply "Robert M. Münch" <robert.muench robertmuench.de> writes:
"Walter" <walter digitalmars.com> schrieb im Newsbeitrag
news:b3bacm$tng$2 digitaldaemon.com...

 It's a hashed array of binary trees. Such is a simple data structure, but
 I've found with years of experience that it is as efficient as about
 anything else.

Hi, any chance that we can see a feature in D to serialize these to disk and be able to read them in again? IMO this would give a simple (KISS) embedded database functionality to D that will be OK for some 50%+ of data-storing problems. Robert
Feb 25 2003
parent reply "Walter" <walter digitalmars.com> writes:
"Robert M. Münch" <robert.muench robertmuench.de> wrote in message
news:b3hqs1$22n0$1 digitaldaemon.com...
 "Walter" <walter digitalmars.com> schrieb im Newsbeitrag
 news:b3bacm$tng$2 digitaldaemon.com...
 It's a hashed array of binary trees. Such is a simple data structure,


 I've found with years of experience that it is as efficient as about
 anything else.


 be able to read them in again? IMO this would give a simple (KISS)

 database functionality to D that will be OK for some 50%+ of data-storing
 problems. Robert

That was in my original plan for D, but I've made no progress towards it.
Mar 05 2003
parent reply "Robert M. Münch" <robert.muench robertmuench.de> writes:
"Walter" <walter digitalmars.com> schrieb im Newsbeitrag
news:b45jmi$25b8$2 digitaldaemon.com...

 Hi, any chance that we can see a feature in D to serialize these to disk
 and be able to read them in again?

 That was in my original plan for D, but I've made no progress towards it.

Hi, I don't know how hard it would be. But IMO only being able to serialize associative arrays don't help a lot, we would need a serialization method for objects as well... Robert
Mar 07 2003
next sibling parent reply "Mike Wynn" <mike.wynn l8night.co.uk> writes:
would  you want a delphi style 'published' (you chose what an Object out/in
Stream can write), Java style 'transient'(you can chose which members are
not serialied) or all members accessable at runtime so the whole object (and
all connected objects) can be written to a stream.

personally I think 'transient' is a better approach. err's on the side of
caution, although to be able to write an Object stream in D without it being
hidden in the language the runtime would require something like
ClassInfo * getClassInfoForName( char[] );
Object newInstance( ClasssInfo * info, char[] constructorSignature, ... );
// another reason for generic varags/params
bit writeMember( ClasssInfo * info, char[] membername, char[]
memberSignature, ... );
bit readMember( ClasssInfo * info, char[] membername, char[]
memberSignature, ... );



"Robert M. Münch" <robert.muench robertmuench.de> wrote in message
news:b49qve$1lnt$1 digitaldaemon.com...
 "Walter" <walter digitalmars.com> schrieb im Newsbeitrag
 news:b45jmi$25b8$2 digitaldaemon.com...

 Hi, any chance that we can see a feature in D to serialize these to disk
 and be able to read them in again?

 That was in my original plan for D, but I've made no progress towards


 Hi, I don't know how hard it would be. But IMO only being able to

 associative arrays don't help a lot, we would need a serialization method
 for objects as well... Robert

Mar 07 2003
parent reply Bill Cox <bill viasic.com> writes:
Mike Wynn wrote:
 would  you want a delphi style 'published' (you chose what an Object out/in
 Stream can write), Java style 'transient'(you can chose which members are
 not serialied) or all members accessable at runtime so the whole object (and
 all connected objects) can be written to a stream.
 
 personally I think 'transient' is a better approach. err's on the side of
 caution, although to be able to write an Object stream in D without it being
 hidden in the language the runtime would require something like
 ClassInfo * getClassInfoForName( char[] );
 Object newInstance( ClasssInfo * info, char[] constructorSignature, ... );
 // another reason for generic varags/params
 bit writeMember( ClasssInfo * info, char[] membername, char[]
 memberSignature, ... );
 bit readMember( ClasssInfo * info, char[] membername, char[]
 memberSignature, ... );

Hi, Mike. "Transient" is cool, so is serialization support in C++, Java and other languages. I have a strong opinion on the subject, but respect the point of view of the majority on this. Basically, I'd like to bash object based binary load/save a bit more... Simple binary stream in/stream out, even with 'transient' data labeled everywhere, is a weak aproach in general. If it were a really good idea, the Swing developers would have made good stuff with it. Here's an artical about serialization in Swing. http://wwwswt.fzi.de/~jjh/tools/swing/products/jfc/swingdoc-current/serialize.html If they had adopted a text format, and written a writer and parse, they could be backward compatible (or at least close to it) with the very first version. Also, it'd take up less disk space, and probably be useful for debugging. They probably would have put less work into it than they've put into explaining why their binary load/save couldn't be done right until JFC stopped changing. BTW, they are fooling themselves if they think it ever will. The real problem I have with standard object-based serialization is that the right number of lines of code to write to get this is 0, and it shouldn't take any enhancements to the language either. The language should have a powerful way to implement this sort of stuff in standard libraries. I'll try to elaborate on this in my next post, which I think will be called "Compile-time meta-programming". Bill
Mar 07 2003
parent reply "Robert M. Münch" <robert.muench robertmuench.de> writes:
"Bill Cox" <bill viasic.com> schrieb im Newsbeitrag
news:3E688AD4.7090201 viasic.com...

 If they had adopted a text format, and written a writer and parse, they
 could be backward compatible (or at least close to it) with the very
 first version.  Also, it'd take up less disk space, and probably be
 useful for debugging.

Hi, as a Rebol user I most like the fact that I can load & save data in text form. Even nested structures are no problem. Of course references to other objects are not handeled but can be decoupled if you use some IDs. Anyway, what I think is needed in D is a way to handle references. If I have an associative array that has a key and an other associative array, list, etc. as data part this needs to be recreated on load. We will need some persistent layer that knows how to handle those situations... Robert
Mar 08 2003
parent Bill Cox <Bill_member pathlink.com> writes:
In article <b4cmdo$82f$1 digitaldaemon.com>, Robert M. Münch says...
"Bill Cox" <bill viasic.com> schrieb im Newsbeitrag
news:3E688AD4.7090201 viasic.com...

 If they had adopted a text format, and written a writer and parse, they
 could be backward compatible (or at least close to it) with the very
 first version.  Also, it'd take up less disk space, and probably be
 useful for debugging.

Hi, as a Rebol user I most like the fact that I can load & save data in text form. Even nested structures are no problem. Of course references to other objects are not handeled but can be decoupled if you use some IDs. Anyway, what I think is needed in D is a way to handle references. If I have an associative array that has a key and an other associative array, list, etc. as data part this needs to be recreated on load. We will need some persistent layer that knows how to handle those situations... Robert

Text dumps have uses. I like thier use in debugging. Bill
Mar 08 2003
prev sibling parent reply Ilya Minkov <midiclub 8ung.at> writes:
Robert M. M=FCnch wrote:
 "Walter" <walter digitalmars.com> schrieb im Newsbeitrag
 news:b45jmi$25b8$2 digitaldaemon.com...
=20
=20
Hi, any chance that we can see a feature in D to serialize these to dis=


and be able to read them in again?

That was in my original plan for D, but I've made no progress towards i=


=20
=20
 Hi, I don't know how hard it would be. But IMO only being able to seria=

 associative arrays don't help a lot, we would need a serialization meth=

 for objects as well... Robert

Untagged unions spoil serialisation, that's the problem. And the tagged=20 are not there (yet). I think Burton has written a Pickle library, which=20 serialises objects. D Objects have ClassInfo, remember? ;)
Mar 07 2003
next sibling parent "Mike Wynn" <mike.wynn l8night.co.uk> writes:
unions are o.k. if just values, if the union contains a pointer then you
have trouble.
changes you make to the object are just as big an issue, i.e. the version of
object
adding a new field is not too bad (it can just get a default value)
but renaming when the old value is needed poses more problems
which is why most persistant objects either are incompatable when you change
things or have to have some level of programmer intervention to deal with
versioning and/or manager classes to deal with it.

"Ilya Minkov" <midiclub 8ung.at> wrote in message
news:b4abb5$1u12$2 digitaldaemon.com...

Untagged unions spoil serialisation, that's the problem. And the tagged
are not there (yet). I think Burton has written a Pickle library, which
serialises objects. D Objects have ClassInfo, remember? ;)
Mar 07 2003
prev sibling parent Burton Radons <loth users.sourceforge.net> writes:
Ilya Minkov wrote:
 Robert M. Münch wrote:
 
 "Walter" <walter digitalmars.com> schrieb im Newsbeitrag
 news:b45jmi$25b8$2 digitaldaemon.com...


 Hi, any chance that we can see a feature in D to serialize these to disk
 and be able to read them in again?

 That was in my original plan for D, but I've made no progress towards 
 it.

Hi, I don't know how hard it would be. But IMO only being able to serialize associative arrays don't help a lot, we would need a serialization method for objects as well... Robert

Untagged unions spoil serialisation, that's the problem. And the tagged are not there (yet). I think Burton has written a Pickle library, which serialises objects. D Objects have ClassInfo, remember? ;)

Yeah, I think that would be a better point to argue from since the other language support I've seen has been, uh, suboptimal. Here's the bullet points: - Integers are stored with a simple compression. It's forward-compatible with 64-bit, is endian and complement neutral, saves at least a byte 66% of the time with random data, and has the psychological effect of making type size equivocation irrelevant (should strings have an eight-bit length index, 16-bit, or 32-bit?). - Objects, pointers, and arrays are stored once and then referenced to from then on by an integer handle. - Types and classes are stored once as well, with a fields description passed for aggregates. This allows fields to change order when loading, for new fields to be present, and for it to detect binary incompatibility through fields with different type, no matching class, or fields which no longer exist. An important aspect to me is that it can tell you exactly why it's binary incompatible, rather than some mysterious type error or just a SIGSEGV a few thousand lines later. - For the purposes of argument - it's not actually implemented - there's a set of interfaces for when you need to control serialisation yourself, for a fallback when binary incompatibility is determined, and for doing things like a post-load method call. Unless if text conveys how data is used in addition to data itself, I don't think you can get any better with it. "Text" is also a meaningless word to me in this context, as Python's pickling uses text by default but is line noise. Do you mean something like XML, Bill?
Mar 08 2003