Am 11.02.2011 21:38, schrieb Steven Schveighoffer:
> On Fri, 11 Feb 2011 14:46:26 -0500, Tom <no.email@gmail.com> wrote:
>
>> what with this?:
>> auto arr = ["foo", "bar", "aaa", "zzz"];
>> sort(arr);
>> assert(canFind("foo"));
>> assert(canFind("aaa"));
>> assert(!canFind("aa"));
>> I had a "Error 1 Error: module algorithem is in file 'std\algorithem.d'
>
> it's spelled "algorithm", no e in there.
>
> -Steve

I allways try to import 'algorythm' because of the german word 'Algorythmus'. When this happend for the first time, I spent about five minutes to find out what's wrong.

Mafi

On 02/11/2011 10:33 PM, Mafi wrote:
> Am 11.02.2011 21:38, schrieb Steven Schveighoffer:
>> On Fri, 11 Feb 2011 14:46:26 -0500, Tom <no.email@gmail.com> wrote:
>>
>>> what with this?:
>>> auto arr = ["foo", "bar", "aaa", "zzz"];
>>> sort(arr);
>>> assert(canFind("foo"));
>>> assert(canFind("aaa"));
>>> assert(!canFind("aa"));
>>> I had a "Error 1 Error: module algorithem is in file 'std\algorithem.d'
>>
>> it's spelled "algorithm", no e in there.
>>
>> -Steve
>
> I allways try to import 'algorythm' because of the german word 'Algorythmus'.
> When this happend for the first time, I spent about five minutes to find out
> what's wrong.

It is spelled Algorithmus in German, no ypsilon ;-) http://de.wiktionary.org/wiki/Algorithmus
The word is not from greek, but from arabic/persian etymology (like many words starting in al-). From wiktionary: http://en.wiktionary.org/wiki/algorithm:

From French algorithme; from the Old French algorisme ("the Arabic numeral system"), a modification likely due to a mistaken connection with Greek ἀριθμός (number); from Medieval Latin algorismus, a transliteration of the name of the Persian mathematician al-Khwārizmī (Arabic: الخوارزمي, "native of Khwarezm.")

denis
-- 
_________________
vita es estrany
spir.wikidot.com

On 02/11/2011 10:35 AM, spir wrote:

> D's builtin AAs seem /very/ fast
> on key access. You'd probably have a hard time even approaching their
> performance using whatever kind of tree (or rather, of trie).

That is expected. D AAs are hash tables, meaning that they provide O(1) complexity for element access; compared to the O(log N) complexity of binary trees.

For completeness: adding elements is still O(1) for a hash table; compared to O(N log N) of a tree.

Ali

On 02/12/2011 12:56 AM, Ali Çehreli wrote:
> On 02/11/2011 10:35 AM, spir wrote:
>
>>  D's builtin AAs seem /very/ fast
>>  on key access. You'd probably have a hard time even approaching their
>>  performance using whatever kind of tree (or rather, of trie).
>
> That is expected. D AAs are hash tables, meaning that they provide O(1)
> complexity for element access; compared to the O(log N) complexity of binary
> trees.
>
> For completeness: adding elements is still O(1) for a hash table; compared to
> O(N log N) of a tree.

You are right, but O(1) & O(log N) do not tell the whole story, --they're just proportional to a given factor that may be whatever.
Also, trees are not always O(logN): tries ()  are O(1) for access, relative to number of elements, in fact their search is not related to that factor, just like hash table instead to the length of keys (O(log(length)).
Hash tables actually have an access time firstly depending on hash computation time, which can be costly: they are like O(k), where can like for tries often depends on key size. Then statistically a linear time O(n) inside "buckets" enters the game; hard to manage & evaluate because it depends on average load, meaning numbered of elements relative to number of buckets. Then, it's a question of pondering time vs space cost.

FWIW, I have implemented tries as fast as library hash tables for a single key type in freepascal (without even optimising). And both of those "sophisticated" data structures only were worth it above a threshold of about 100 items; I mean compared to plain arrays of (key,value) pairs!
In D, not only there is no way (for me) to even approach builtin AA perf with tries (even with some search for optimisation), but those deadly flash-fast AAs are worth it as early as with a few items! (again, compared to arrays of (key,value) pairs). If you want numbers, search the archives of the PiLuD mailing list, I published much data in a thread there (last year): http://groups.google.com/group/pilud/
 People, like me, concluded for instance that to implement namespaces it's really not worth it to use complicated data structures. We were wrong (I had not yet met D's AAs then).

Denis
-- 
_________________
vita es estrany
spir.wikidot.com

On 02/11/2011 04:55 PM, spir wrote:

> Also, trees are not always O(logN): tries () are O(1) for access,
> relative to number of elements, in fact their search is not related to
> that factor, just like hash table instead to the length of keys
> (O(log(length)).

Yep. I should know: I had written a patricia trie in the context of a networking ASIC. :)

> In D, not only there is no way (for me) to even approach builtin AA perf
> with tries (even with some search for optimisation), but those deadly
> flash-fast AAs are worth it as early as with a few items!

Thank you. It's very good to know that D's AAs are very fast. I had no idea. :)

Ali

On 02/13/2011 01:18 AM, Ali Çehreli wrote:
> On 02/11/2011 04:55 PM, spir wrote:
>
>>  Also, trees are not always O(logN): tries () are O(1) for access,
>>  relative to number of elements, in fact their search is not related to
>>  that factor, just like hash table instead to the length of keys
>>  (O(log(length)).
>
> Yep. I should know: I had written a patricia trie in the context of a
> networking ASIC. :)
>
>>  In D, not only there is no way (for me) to even approach builtin AA perf
>>  with tries (even with some search for optimisation), but those deadly
>>  flash-fast AAs are worth it as early as with a few items!
>
> Thank you. It's very good to know that D's AAs are very fast. I had no idea. :)

Beware: I'm not saying this as an absolute truth out of extensive measures. Just comparing plain arrays of (key,value) pairs versus tries versus hashed AAs in the same language, done in 2 languages only (D and freepascal).

Denis
-- 
_________________
vita es estrany
spir.wikidot.com

Dominic Jones wrote:

> Hello,
> 
> I have a list of strings and I want to determine whether or not a particular string in the is in that list. Assuming I should store the list of strings in a binary tree to facilitate fast searching, I had a look at the std.container documentation and found RedBlackTree, but the documentation for it has no examples. May someone offer an example of how to use it?
> 
> Thank you,
> Dominic Jones

I tried it out and it's simple to use but I stumbled upon some issues. (See below) As others have commented, regular AA's will work fine for this purpose too. Probably the best reason why you would choose a RedBlackTree over AA is when you also need them sorted, this you get for free. A tree is also likely to  consume less memory, which may or may not matter.

Example:

import std.stdio;
import std.container;

void main()
{
    auto stuff = ["foo", "bar"];

    /* using make instead of the constructor ensures the code will work
       when RedBlackTree will become a class: */

    auto set = make!(RedBlackTree!string)(stuff);

    /* iterates in order: */
    foreach( value; set )
        writeln(value);

    set.stableInsert("baz");

    /* the 'in' operator returns bool, not a pointer to the element like
       builtin aa's do: */
    assert( "baz" in set );
}

Now for the issues, this doesn't work but it should:

auto set = make!(RedBlackTree!string)("foo", "bar");

Error: template std.container.RedBlackTree!(string).RedBlackTree.__ctor(U)
if (isImplicitlyConvertible!(U,Elem)) does not match any function template
declaration
Error: template std.container.RedBlackTree!(string).RedBlackTree.__ctor(U)
if (isImplicitlyConvertible!(U,Elem)) cannot deduce template function from
argument types !()(string,string)
...


I couldn't see any function to remove a single element from the tree and std.algorithm.remove doesn't work. Removing a range also doesn't work for strings:

set.remove(stuff);

Error: function std.container.RedBlackTree!(string).RedBlackTree.remove
(Range r) is not callable using argument types (string[])
Error: cannot implicitly convert expression (stuff) of type string[] to
Range

I'll file these issues soon, when I have the time.

Am 12.02.2011 00:02, schrieb spir:
> On 02/11/2011 10:33 PM, Mafi wrote:
>>
>> I allways try to import 'algorythm' because of the german word
>> 'Algorythmus'.
>> When this happend for the first time, I spent about five minutes to
>> find out
>> what's wrong.
>
> It is spelled Algorithmus in German, no ypsilon ;-)
> http://de.wiktionary.org/wiki/Algorithmus
> The word is not from greek, but from arabic/persian etymology (like many
> words starting in al-). From wiktionary:
> http://en.wiktionary.org/wiki/algorithm:
>
>  From French algorithme; from the Old French algorisme ("the Arabic
> numeral system"), a modification likely due to a mistaken connection
> with Greek ἀριθμός (number); from Medieval Latin algorismus, a
> transliteration of the name of the Persian mathematician al-Khwārizmī
> (Arabic: الخوارزمي, "native of Khwarezm.")
>
> denis
Holly shit! I feel ashamed now. :(
I'm going to correct all my personal notes about algorithms.

Mafi

On Sun, 13 Feb 2011 09:29:14 -0500, Lutger Blijdestijn <lutger.blijdestijn@gmail.com> wrote:

> Dominic Jones wrote:
>
>> Hello,
>>
>> I have a list of strings and I want to determine whether or not a
>> particular string in the is in that list. Assuming I should store the list
>> of strings in a binary tree to facilitate fast searching, I had a look at
>> the std.container documentation and found RedBlackTree, but the
>> documentation for it has no examples. May someone offer an example of how
>> to use it?
>>
>> Thank you,
>> Dominic Jones
>
> I tried it out and it's simple to use but I stumbled upon some issues. (See
> below) As others have commented, regular AA's will work fine for this
> purpose too. Probably the best reason why you would choose a RedBlackTree
> over AA is when you also need them sorted, this you get for free. A tree is
> also likely to  consume less memory, which may or may not matter.
>
> Example:
>
> import std.stdio;
> import std.container;
>
> void main()
> {
>     auto stuff = ["foo", "bar"];
>    /* using make instead of the constructor ensures the code will work
>        when RedBlackTree will become a class: */
>
>     auto set = make!(RedBlackTree!string)(stuff);
>
>     /* iterates in order: */
>     foreach( value; set )
>         writeln(value);
>
>     set.stableInsert("baz");
>
>     /* the 'in' operator returns bool, not a pointer to the element like
>        builtin aa's do: */
>     assert( "baz" in set );
> }
>
> Now for the issues, this doesn't work but it should:
>
> auto set = make!(RedBlackTree!string)("foo", "bar");
>
> Error: template std.container.RedBlackTree!(string).RedBlackTree.__ctor(U)
> if (isImplicitlyConvertible!(U,Elem)) does not match any function template
> declaration
> Error: template std.container.RedBlackTree!(string).RedBlackTree.__ctor(U)
> if (isImplicitlyConvertible!(U,Elem)) cannot deduce template function from
> argument types !()(string,string)
> ...
>
>
> I couldn't see any function to remove a single element from the tree and
> std.algorithm.remove doesn't work. Removing a range also doesn't work for
> strings:
>
> set.remove(stuff);
>
> Error: function std.container.RedBlackTree!(string).RedBlackTree.remove
> (Range r) is not callable using argument types (string[])
> Error: cannot implicitly convert expression (stuff) of type string[] to
> Range
>
> I'll file these issues soon, when I have the time.

Yes, thank you.  RedBlackTree is certainly not well-used, so it is bound to have lots of usability issues.

-Steve

On 11/02/2011 12:30, Dominic Jones wrote:
<snip>
> Would that not be constructing an associated array? Whilst an associated array
> would do the job, there is no value for the "key:value" pair, just a list of keys.
> In the C++ STL there are the "set" and "map" containers. I want something like "set".
> Dominic

http://pr.stewartsplace.org.uk/d/sutil/

includes a set class template.

Stewart.