• Bedros (21/21) Jun 14 2013 I'm converting some code into D while learning D and need some
• bearophile (16/31) Jun 15 2013 Is the average number of items in the whole data structure

"Bedros" <2bedros gmail.com> writes:

I'm converting some  code into D while learning D and need some 
help to implement this


I have a node of struct { ulong mask; ulong value};

now I need to create a list and insert that node; but first I 
don't need duplicates, so, I first check if node already exists 
in list.

I also need to traverse the list, and remove a node

currently I'm using dynamic array in D, but it's not efficient; 
is there a better way to do the following

insert with no duplicates
remove
traverse
find

I read about containers in D, but the documentation is confusing; 
and not sure if container implementation is mature.

BTW, my code will generate 100s of millions of nodes, and each 
node on average is used once or twice then removed

I'll appreciate it if someone points me to some examples or 
documentation of a feature in D.

Thanks in advance

Bedros

"bearophile" <bearophileHUGS lycos.com> writes:

Bedros:

 I have a node of struct { ulong mask; ulong value};

 now I need to create a list and insert that node; but first I 
 don't need duplicates, so, I first check if node already exists 
 in list.

 I also need to traverse the list, and remove a node

 currently I'm using dynamic array in D, but it's not efficient; 
 is there a better way to do the following

 insert with no duplicates
 remove
 traverse
 find

 I read about containers in D, but the documentation is 
 confusing; and not sure if container implementation is mature.

 BTW, my code will generate 100s of millions of nodes, and each 
 node on average is used once or twice then removed

Is the average number of items in the whole data structure 
constant? How much do you have to transverse the data structure 
(beside finding the duplications)? During such transversal do you 
need to display items in some order?

Your needs are special, so I think you will have to try several 
different data structures before finding the best one. Generally 
linked lists are slow in transversals, have less cache coherence, 
and give troubles to the GC making it work slowly.

A possible data structure for your needs is some kind of array of 
pointers to short fixed sized arrays that also keep a count of 
how many items each of them keeps, and keep them in a freelist. 
But first try something simpler, like a dynamic array with 
periodic holes, like on library shelves.

Bye,
bearophile