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


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!


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




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!


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




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


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




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




k

and be able to read them in again?

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




t.

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


lize

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


od

 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