www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - O(1) dictionaries

reply mandel <oh no.es> writes:
Hi,

I have made a dictionary that way:
enum Word { Hello, Bye };
char[][Word] dict;

static this()
{
   dict = [
     Word.Hello : "Hello",
     Word.Bye : "Bye"
   ];
}

Now there are two problems I have with this:

- the dict is an AA, but an array would be much faster,
  but it is not possible to assign it via an array literal
  with a mixed order and supplied keys.
char[][Word.max] dict = [Word.Hello : "Hello", ...]

- in place initialisation with a literal is not possible.
  Instead, the use of "static this" makes the code look long winded.

Does anyone have some nice workaround for these limitations?

The current solution is long winded (ok, I can make the name shorter),
but a literal would be nicer much.
static this()
{
    english_dictionary[ Word.Hello] = "Hello";
    //[...]
}
Nov 13 2007
next sibling parent reply Tim Keating <holyspamster gmail.com> writes:
mandel wrote:
 Hi,
 
 I have made a dictionary that way:
 enum Word { Hello, Bye };
 char[][Word] dict;
 
 static this()
 {
    dict = [
      Word.Hello : "Hello",
      Word.Bye : "Bye"
    ];
 }
 
 Now there are two problems I have with this:
 
 - the dict is an AA, but an array would be much faster,
   but it is not possible to assign it via an array literal
   with a mixed order and supplied keys.
 char[][Word.max] dict = [Word.Hello : "Hello", ...]

Why does the array literal have to be in mixed order? You can just do the enum and the array in the same order: enum Word { Hello, Bye }; char[] dict = [ "Hello", "Bye" ]; The only complication there is that for a dictionary of any meaningful length, it won't line up quite as nicely. Ensuring each enum value matches its correct word will be a real pain. In this situation, I might use code generation.
 - in place initialisation with a literal is not possible.
   Instead, the use of "static this" makes the code look long winded.

It seems from what you say above that you already know its, but that's not true anymore. Array literals were recently added to the language (see the "expressions" section of the language spec). However, if you think _that's_ long-winded, consider how you would do that initialization in C++ . . . TK
Nov 14 2007
parent reply mandel <oh no.es> writes:
Tim Keating Wrote:

 mandel wrote:
 Hi,
 
 I have made a dictionary that way:
 enum Word { Hello, Bye };
 char[][Word] dict;
 
 static this()
 {
    dict = [
      Word.Hello : "Hello",
      Word.Bye : "Bye"
    ];
 }
 
 Now there are two problems I have with this:
 
 - the dict is an AA, but an array would be much faster,
   but it is not possible to assign it via an array literal
   with a mixed order and supplied keys.
 char[][Word.max] dict = [Word.Hello : "Hello", ...]

Why does the array literal have to be in mixed order? You can just do the enum and the array in the same order: enum Word { Hello, Bye }; char[] dict = [ "Hello", "Bye" ]; The only complication there is that for a dictionary of any meaningful length, it won't line up quite as nicely. Ensuring each enum value matches its correct word will be a real pain. In this situation, I might use code generation.

The dict may also change order when words are added and quite possibly regrouped. The entire alignment will be hard to maintain.
 
 - in place initialisation with a literal is not possible.
   Instead, the use of "static this" makes the code look long winded.

It seems from what you say above that you already know its, but that's not true anymore. Array literals were recently added to the language (see the "expressions" section of the language spec).

is not possible with AAs. The use of "static this" for this causes the binary to abort execution immediately because of "cyclic dependencies" (In cases of multiple static this in different modules). And a custom init function also doesn't look that nice.
 
 However, if you think _that's_ long-winded, consider how you would do 
 that initialization in C++ . . .

But imho it could be done even better in D. :P
Nov 14 2007
parent reply Jari-Matti =?ISO-8859-1?Q?M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:
mandel wrote:

 Tim Keating Wrote:
 
 mandel wrote:
 Hi,
 
 I have made a dictionary that way:
 enum Word { Hello, Bye };
 char[][Word] dict;
 
 static this()
 {
    dict = [
      Word.Hello : "Hello",
      Word.Bye : "Bye"
    ];
 }
 
 Now there are two problems I have with this:
 
 - the dict is an AA, but an array would be much faster,
   but it is not possible to assign it via an array literal
   with a mixed order and supplied keys.
 char[][Word.max] dict = [Word.Hello : "Hello", ...]

Why does the array literal have to be in mixed order? You can just do the enum and the array in the same order: enum Word { Hello, Bye }; char[] dict = [ "Hello", "Bye" ]; The only complication there is that for a dictionary of any meaningful length, it won't line up quite as nicely. Ensuring each enum value matches its correct word will be a real pain. In this situation, I might use code generation.

The dict may also change order when words are added and quite possibly regrouped. The entire alignment will be hard to maintain.

That's no good excuse to not use templates :P : template _E(T...) { static if (T.length>1) const _E = T[0] ~ "," ~ _E!(T[1..$]); else const _E = T[0] ~ "};"; } template _A(T...) { static if (T.length>1) const _A = `"` ~ T[0] ~ `"[],` ~ _A!(T[1..$]); else const _A = `"` ~ T[0] ~ `"[]];`; } template RealEnum(char[] aName, char[] eName, T...) { const RealEnum = "enum " ~ eName ~ "{" ~ _E!(T) ~ "char[][] " ~ aName ~ "=[" ~ _A!(T); } mixin(RealEnum!("Word", "dict", "Hello", "Bye")); CTFE would produce smaller binaries though.
Nov 14 2007
next sibling parent Robert Fraser <fraserofthenight gmail.com> writes:
Jari-Matti Mäkelä Wrote:

 mandel wrote:
 
 Tim Keating Wrote:
 
 mandel wrote:
 Hi,
 
 I have made a dictionary that way:
 enum Word { Hello, Bye };
 char[][Word] dict;
 
 static this()
 {
    dict = [
      Word.Hello : "Hello",
      Word.Bye : "Bye"
    ];
 }
 
 Now there are two problems I have with this:
 
 - the dict is an AA, but an array would be much faster,
   but it is not possible to assign it via an array literal
   with a mixed order and supplied keys.
 char[][Word.max] dict = [Word.Hello : "Hello", ...]

Why does the array literal have to be in mixed order? You can just do the enum and the array in the same order: enum Word { Hello, Bye }; char[] dict = [ "Hello", "Bye" ]; The only complication there is that for a dictionary of any meaningful length, it won't line up quite as nicely. Ensuring each enum value matches its correct word will be a real pain. In this situation, I might use code generation.

The dict may also change order when words are added and quite possibly regrouped. The entire alignment will be hard to maintain.

That's no good excuse to not use templates :P : template _E(T...) { static if (T.length>1) const _E = T[0] ~ "," ~ _E!(T[1..$]); else const _E = T[0] ~ "};"; } template _A(T...) { static if (T.length>1) const _A = `"` ~ T[0] ~ `"[],` ~ _A!(T[1..$]); else const _A = `"` ~ T[0] ~ `"[]];`; } template RealEnum(char[] aName, char[] eName, T...) { const RealEnum = "enum " ~ eName ~ "{" ~ _E!(T) ~ "char[][] " ~ aName ~ "=[" ~ _A!(T); } mixin(RealEnum!("Word", "dict", "Hello", "Bye")); CTFE would produce smaller binaries though.

IMHO, CTFE produces cleaner code, too, and there are no worries about symbol length.
Nov 14 2007
prev sibling parent reply mandel <oh no.es> writes:
Jari-Matti Mäkelä Wrote:

 mandel wrote:
 The dict may also change order when words are added and quite possibly
 regrouped. The entire alignment will be hard to maintain.

That's no good excuse to not use templates :P :

 
 mixin(RealEnum!("Word", "dict", "Hello", "Bye"));
 
 CTFE would produce smaller binaries though.

Your template looks like it does it's jobs quite nicely - thx. The reason I try to avoid templates is that they often look like an entry for an obfuscation competition. ;> Templates in D (in even much more in C++) are hard to understand, they don't look like just compile time D code but like a new language. (well, I guess the D compilers may need an integrated scripting engine to execute D code at compile time). And as many developers, I try to avoid code templates if there is no real benefit or if they stay simple enough for other devs to understand at first sight. I only use hackish code in speed critical sections (not like NASA, but critical in the sense of overall program speed). well, dictionaries in my applications may fit in this role. :}
Nov 15 2007
parent Jari-Matti =?ISO-8859-1?Q?M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:
mandel wrote:

 Jari-Matti Mäkelä Wrote:
 
 mandel wrote:
 The dict may also change order when words are added and quite possibly
 regrouped. The entire alignment will be hard to maintain.

That's no good excuse to not use templates :P :

 
 mixin(RealEnum!("Word", "dict", "Hello", "Bye"));
 
 CTFE would produce smaller binaries though.

Your template looks like it does it's jobs quite nicely - thx. The reason I try to avoid templates is that they often look like an entry for an obfuscation competition. ;>

Hide them in __dontlookhere.d :)
 
 Templates in D (in even much more in C++) are hard to understand,
 they don't look like just compile time D code but like a new language.
 (well, I guess the D compilers may need an integrated scripting engine to
 execute D code at compile time).

I hope you use CTFE instead in a "production code" since the templates have typename limitations and bloat the executable. I pasted some old since I wasn't sure if CTFE supports varargs now and happened to have the old code around.
 
 And as many developers, I try to avoid code templates if there is no real
 benefit or if they stay simple enough for other devs to understand at
 first sight.
 
 I only use hackish code in speed critical sections (not like NASA, but
 critical in the sense of overall program speed). well, dictionaries in my
 applications may fit in this role. :}

I agree mixins would be cleaner if you could do macro like stuff on a bit higher level than now and if they worked in more places (for example inside switches).
Nov 15 2007
prev sibling parent renoX <renosky free.fr> writes:
mandel a écrit :
 Hi,
 
 I have made a dictionary that way:
 enum Word { Hello, Bye };
 char[][Word] dict;
 
 static this()
 {
    dict = [
      Word.Hello : "Hello",
      Word.Bye : "Bye"
    ];
 }
 
 Now there are two problems I have with this:
 
 - the dict is an AA, but an array would be much faster,
   but it is not possible to assign it via an array literal
   with a mixed order and supplied keys.
 char[][Word.max] dict = [Word.Hello : "Hello", ...]
 
 - in place initialisation with a literal is not possible.
   Instead, the use of "static this" makes the code look long winded.
 
 Does anyone have some nice workaround for these limitations?
 
 The current solution is long winded (ok, I can make the name shorter),
 but a literal would be nicer much.
 static this()
 {
     english_dictionary[ Word.Hello] = "Hello";
     //[...]
 }

Quite some times ago, there was a thread on 'reflective enums' where Kevin Bealer, I and other tried to make better enums, you could use the code as a basis of your work. Note that I don't think much of the results: D isn't flexible enough for this .. at least currently. Regards, renoX
Nov 17 2007