www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Associative array and ranges

reply Nrgyzer <nrgyzer gmail.com> writes:
Hey guys,

I have an associative array like this: T[hash_t] myArray; (T means
the template type).

Is there any chance to cast/convert this array to an indexed array or
is it possible to iterate over specific indices? I know that there is
something like next() for the foreach-statement but when the array
contains some thousand instances and I only want iterate over (for
example) 5 elements I think that's the wrong way. It's for a game and
I think every next()-call influences the fps.

I hope there is any solution for my problem :) - Thanks!
Feb 02 2011
next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Nrgyzer <nrgyzer gmail.com> wrote:

 Hey guys,

 I have an associative array like this: T[hash_t] myArray; (T means
 the template type).

 Is there any chance to cast/convert this array to an indexed array or
 is it possible to iterate over specific indices? I know that there is
 something like next() for the foreach-statement but when the array
 contains some thousand instances and I only want iterate over (for
 example) 5 elements I think that's the wrong way. It's for a game and
 I think every next()-call influences the fps.

 I hope there is any solution for my problem :) - Thanks!

You should probably try aa.byValue: auto o = ["a": 1, "b": 2]; foreach ( e; o.byValue ) { writeln( e ); } It seems from the (somewhat unreadable) source, that the values are stored in an array of pointers to structs holding these values. If this is not fast enough for your needs, I'm afraid you will have to write an AA implementation yourself. (You can replace the code in druntime/src/rt/aaA.d with your own if you still want the nice syntax sugar) -- Simen
Feb 02 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday 02 February 2011 02:11:34 Nrgyzer wrote:
 Hey guys,
 
 I have an associative array like this: T[hash_t] myArray; (T means
 the template type).
 
 Is there any chance to cast/convert this array to an indexed array or
 is it possible to iterate over specific indices? I know that there is
 something like next() for the foreach-statement but when the array
 contains some thousand instances and I only want iterate over (for
 example) 5 elements I think that's the wrong way. It's for a game and
 I think every next()-call influences the fps.
 
 I hope there is any solution for my problem :) - Thanks!

If you know which keys you want, then just have a list of those and iterate over them, and then use them to grab their corresponding values from the AA on each iteration. As far as iterating over the AA itself goes, either you're iterating over the keys, the values, or both. You can't iterate over just part of it. I haven't a clue how such a thing would be implemented anyway. But there's nothing to stop you from iterating over a list of the keys that you want and then using those keys to grab the values from the AA. - Jonathan M Davis
Feb 02 2011
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Nrgyzer:

 Is there any chance to cast/convert this array to an indexed array or
 is it possible to iterate over specific indices? I know that there is
 something like next() for the foreach-statement but when the array
 contains some thousand instances and I only want iterate over (for
 example) 5 elements I think that's the wrong way.

Show a hypothetical code example of what you desire to do, please. Bye, bearophile
Feb 02 2011
next sibling parent reply Nrgyzer <nrgyzer gmail.com> writes:
== Auszug aus bearophile (bearophileHUGS lycos.com)'s Artikel
 Nrgyzer:
 Is there any chance to cast/convert this array to an indexed


 is it possible to iterate over specific indices? I know that


 something like next() for the foreach-statement but when the array
 contains some thousand instances and I only want iterate over (for
 example) 5 elements I think that's the wrong way.

Bye, bearophile

Example: ... class Example(T : Drawable) : Drawable { T[hash_t] pObjectsToDraw; uint pFrom, pTo; void setLimit(from, to) { pFrom = from; pTo = to; } void remove(T objToRemove) { pObjectsToDraw.remove(objToRemove.toHash()); } override void draw() { for (uint i = pFrom; i < pTo; i++) { pOjectsToDraw[i].draw(); // cannot call because pObjectsToDraw is an associative and no static or dynamic array } } }
Feb 03 2011
parent reply Nrgyzer <nrgyzer gmail.com> writes:
== Auszug aus Steven Schveighoffer (schveiguy yahoo.com)'s Artikel
 On Thu, 03 Feb 2011 09:35:44 -0500, Nrgyzer <nrgyzer gmail.com>

 == Auszug aus bearophile (bearophileHUGS lycos.com)'s Artikel
 Nrgyzer:
 Is there any chance to cast/convert this array to an indexed


 is it possible to iterate over specific indices? I know that


 something like next() for the foreach-statement but when the




 contains some thousand instances and I only want iterate over




 example) 5 elements I think that's the wrong way.




 Bye,
 bearophile

Example: ... class Example(T : Drawable) : Drawable { T[hash_t] pObjectsToDraw; uint pFrom, pTo; void setLimit(from, to) { pFrom = from; pTo = to; } void remove(T objToRemove) { pObjectsToDraw.remove(objToRemove.toHash()); } override void draw() { for (uint i = pFrom; i < pTo; i++) { pOjectsToDraw[i].draw(); // cannot call because pObjectsToDraw is an associative and no static or dynamic array } } }


 you expect to accomplish except "give me (pTo - pFrom) random

  from the array"
 Second, you can use a foreach loop to get data out of an AA, and

 break when you've retrieved enough elements.
 Again, I'm not sure what the point is of starting in the middle of

 array.  Are you expecting something different from a hashtable?
 -Steve

I know that hashes aren't stored in any order... but lets take the LinkedHashSet in Java. The LinkedHashSet/Map stores the hashes in order of inserting. With the toArray()-method I can loop over specific elements/indices... but I can also remove the elements by their hash. I'm looking for a similar technique in D - you can find an Java example on http://www.java2s.com/Code/JavaAPI/java.util/ LinkedHashSettoArray.htm.
Feb 03 2011
parent reply Nrgyzer <nrgyzer gmail.com> writes:
== Auszug aus Steven Schveighoffer (schveiguy yahoo.com)'s Artikel
 On Thu, 03 Feb 2011 10:41:16 -0500, Nrgyzer <nrgyzer gmail.com> wrote:
 == Auszug aus Steven Schveighoffer (schveiguy yahoo.com)'s Artikel
 On Thu, 03 Feb 2011 09:35:44 -0500, Nrgyzer <nrgyzer gmail.com>

 == Auszug aus bearophile (bearophileHUGS lycos.com)'s Artikel
 Nrgyzer:
 Is there any chance to cast/convert this array to an indexed


 is it possible to iterate over specific indices? I know that


 something like next() for the foreach-statement but when the




 contains some thousand instances and I only want iterate over




 example) 5 elements I think that's the wrong way.




 Bye,
 bearophile

Example: ... class Example(T : Drawable) : Drawable { T[hash_t] pObjectsToDraw; uint pFrom, pTo; void setLimit(from, to) { pFrom = from; pTo = to; } void remove(T objToRemove) { pObjectsToDraw.remove(objToRemove.toHash()); } override void draw() { for (uint i = pFrom; i < pTo; i++) { pOjectsToDraw[i].draw(); // cannot call because pObjectsToDraw is an associative and no static or dynamic array } } }


 you expect to accomplish except "give me (pTo - pFrom) random

  from the array"
 Second, you can use a foreach loop to get data out of an AA, and

 break when you've retrieved enough elements.
 Again, I'm not sure what the point is of starting in the middle of

 array.  Are you expecting something different from a hashtable?
 -Steve

I know that hashes aren't stored in any order... but lets take the LinkedHashSet in Java. The LinkedHashSet/Map stores the hashes in order of inserting. With the toArray()-method I can loop over specific elements/indices... but I can also remove the elements by their hash. I'm looking for a similar technique in D - you can find an Java example on http://www.java2s.com/Code/JavaAPI/java.util/ LinkedHashSettoArray.htm.

(there is one in dcollections). Note that your worry about performance when iterating the AA is completely negated by the toArray call -- this allocates space for your temporary array, and necessarily iterates all elements, even if you only want 5. You are better off not to do things this way. Incidentally, I do plan on adding a Link*Set/Map to dcollections, because I really like the array type in php (same thing). But this will not provide constant access to the nth element, so it still will fail your requirements. The only thing I can think of is to store the elements in an array alongside the hash map (do you need to look up elements by hash_t? If not, why not just use an array directly?) to store the order of insertion. This only works if you rarely remove elements (removal in an array is an O(n) operation). -Steve

I already thought about using an dynamic array like T[] (which contains all elements that should be drawn) and a second like uint[hash_t] which contains the indices in the first array. But it does only shit the problem that I can't remove an index from a dynamic array. Thanks for your suggestions.
Feb 03 2011
parent reply Nrgyzer <nrgyzer gmail.com> writes:
== Auszug aus Stanislav Blinov (blinov loniir.ru)'s Artikel
 03.02.2011 19:34, Nrgyzer пишет:
 == Auszug aus Steven Schveighoffer (schveiguy yahoo.com)'s Artikel
 This only works if you rarely remove elements (removal in an
 array is an O(n) operation).
 -Steve



 elements that should be drawn) and a second like uint[hash_t]


 the indices in the first array. But it does only shit the problem


 remove an index from a dynamic array.

 Thanks for your suggestions.

You can: 1) Get an index i from hash, do arr = arr[0..i] ~ arr[i+1..$] and

 reindex all arr[i..$] elements. This is costly, because, as Steven
 mentioned, such removal is O(n) plus you have to iterate all

 with index >= i, and this traversal is O(n) in the worst case.
 2) Use unstable removal. Since you store indices separately, you can
 just swap an element to be removed with last element in the array,
 shrink array using slicing (arr = arr[0..$-1]) and reindex a single
 element (the one that was previously last in the array). The

 that this approach doesn't preserve order of elements in the array.

Ah, okay... I already tried some things with [0..i] ~ [i + 1..$] but there was always an error and I thought, it must be done more simply. I'm just using a simple, dynamic array and use a for-loop to remove them. I don't need remove() often, but I thought there is any way to do it in O(1).
Feb 03 2011
parent reply Stanislav Blinov <stanislav.blinov gmail.com> writes:
On 02/03/2011 08:01 PM, Nrgyzer wrote:
 == Auszug aus Stanislav Blinov (blinov loniir.ru)'s Artikel
 03.02.2011 19:34, Nrgyzer пишет:
 == Auszug aus Steven Schveighoffer (schveiguy yahoo.com)'s Artikel
 This only works if you rarely remove elements (removal in an
 array is an O(n) operation).
 -Steve



 elements that should be drawn) and a second like uint[hash_t]


 the indices in the first array. But it does only shit the problem


 remove an index from a dynamic array.

 Thanks for your suggestions.

You can: 1) Get an index i from hash, do arr = arr[0..i] ~ arr[i+1..$] and

 reindex all arr[i..$] elements. This is costly, because, as Steven
 mentioned, such removal is O(n) plus you have to iterate all

 with index>= i, and this traversal is O(n) in the worst case.
 2) Use unstable removal. Since you store indices separately, you can
 just swap an element to be removed with last element in the array,
 shrink array using slicing (arr = arr[0..$-1]) and reindex a single
 element (the one that was previously last in the array). The

 that this approach doesn't preserve order of elements in the array.

Ah, okay... I already tried some things with [0..i] ~ [i + 1..$] but there was always an error and I thought, it must be done more simply.

There is no possible simplier way of removing an arbitrary element from an array than doing that. Well, maybe there is: if your data is POD you could use a memmove with subsequent slice-shrink, but I see we're talking about storing references in this case.
 I'm just using a simple, dynamic array and use a for-loop to remove
 them. I don't need remove() often, but I thought there is any way to
 do it in O(1).

Actually, method (2) is O(1) if you discount hash lookup and possible postblit (which is absent in case of references). You could even employ intrusive indexing (when objects store indices), if that is suitable for your application, thus discarding hash table entirely.
Feb 03 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Stanislav Blinov:

 Nrgyzer:
 Ah, okay... I already tried some things with [0..i] ~ [i + 1..$] but
 there was always an error and I thought, it must be done more simply.

There is no possible simplier way of removing an arbitrary element from an array than doing that. Well, maybe there is: if your data is POD you could use a memmove with subsequent slice-shrink, but I see we're talking about storing references in this case.

~ performs a memory allocation, while generally moving items inside an array doesn't require it. Bye, bearophile
Feb 03 2011
parent reply Stanislav Blinov <stanislav.blinov gmail.com> writes:
On 02/04/2011 12:48 AM, bearophile wrote:
 Stanislav Blinov:

 Nrgyzer:
 Ah, okay... I already tried some things with [0..i] ~ [i + 1..$] but
 there was always an error and I thought, it must be done more simply.

There is no possible simplier way of removing an arbitrary element from an array than doing that. Well, maybe there is: if your data is POD you could use a memmove with subsequent slice-shrink, but I see we're talking about storing references in this case.

~ performs a memory allocation, while generally moving items inside an array doesn't require it.

Certainly. Forgot to mention that, thanks.
Feb 03 2011
parent Stanislav Blinov <stanislav.blinov gmail.com> writes:
On 02/04/2011 01:19 AM, Stanislav Blinov wrote:
 On 02/04/2011 12:48 AM, bearophile wrote:
 Stanislav Blinov:

 Nrgyzer:
 Ah, okay... I already tried some things with [0..i] ~ [i + 1..$] but
 there was always an error and I thought, it must be done more simply.

There is no possible simplier way of removing an arbitrary element from an array than doing that. Well, maybe there is: if your data is POD you could use a memmove with subsequent slice-shrink, but I see we're talking about storing references in this case.

~ performs a memory allocation, while generally moving items inside an array doesn't require it.

Certainly. Forgot to mention that, thanks.

Hmm... Come to think of it, is it ever bad to memmove a reference? I wouldn't think so. I think I got C++ classes in mind when I wrote that.
Feb 03 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 03 Feb 2011 09:35:44 -0500, Nrgyzer <nrgyzer gmail.com> wrote:

 == Auszug aus bearophile (bearophileHUGS lycos.com)'s Artikel
 Nrgyzer:
 Is there any chance to cast/convert this array to an indexed


 is it possible to iterate over specific indices? I know that


 something like next() for the foreach-statement but when the array
 contains some thousand instances and I only want iterate over (for
 example) 5 elements I think that's the wrong way.

Bye, bearophile

Example: ... class Example(T : Drawable) : Drawable { T[hash_t] pObjectsToDraw; uint pFrom, pTo; void setLimit(from, to) { pFrom = from; pTo = to; } void remove(T objToRemove) { pObjectsToDraw.remove(objToRemove.toHash()); } override void draw() { for (uint i = pFrom; i < pTo; i++) { pOjectsToDraw[i].draw(); // cannot call because pObjectsToDraw is an associative and no static or dynamic array } } }

First, hashes are not stored in any particular order, so I'm not sure what you expect to accomplish except "give me (pTo - pFrom) random elements from the array" Second, you can use a foreach loop to get data out of an AA, and then break when you've retrieved enough elements. Again, I'm not sure what the point is of starting in the middle of the array. Are you expecting something different from a hashtable? -Steve
Feb 03 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 03 Feb 2011 10:41:16 -0500, Nrgyzer <nrgyzer gmail.com> wrote:

 == Auszug aus Steven Schveighoffer (schveiguy yahoo.com)'s Artikel
 On Thu, 03 Feb 2011 09:35:44 -0500, Nrgyzer <nrgyzer gmail.com>

 == Auszug aus bearophile (bearophileHUGS lycos.com)'s Artikel
 Nrgyzer:
 Is there any chance to cast/convert this array to an indexed


 is it possible to iterate over specific indices? I know that


 something like next() for the foreach-statement but when the




 contains some thousand instances and I only want iterate over




 example) 5 elements I think that's the wrong way.




 Bye,
 bearophile

Example: ... class Example(T : Drawable) : Drawable { T[hash_t] pObjectsToDraw; uint pFrom, pTo; void setLimit(from, to) { pFrom = from; pTo = to; } void remove(T objToRemove) { pObjectsToDraw.remove(objToRemove.toHash()); } override void draw() { for (uint i = pFrom; i < pTo; i++) { pOjectsToDraw[i].draw(); // cannot call because pObjectsToDraw is an associative and no static or dynamic array } } }


 you expect to accomplish except "give me (pTo - pFrom) random

  from the array"
 Second, you can use a foreach loop to get data out of an AA, and

 break when you've retrieved enough elements.
 Again, I'm not sure what the point is of starting in the middle of

 array.  Are you expecting something different from a hashtable?
 -Steve

I know that hashes aren't stored in any order... but lets take the LinkedHashSet in Java. The LinkedHashSet/Map stores the hashes in order of inserting. With the toArray()-method I can loop over specific elements/indices... but I can also remove the elements by their hash. I'm looking for a similar technique in D - you can find an Java example on http://www.java2s.com/Code/JavaAPI/java.util/ LinkedHashSettoArray.htm.

The AA does not do that. Note that there is no builtin 'set' type in D (there is one in dcollections). Note that your worry about performance when iterating the AA is completely negated by the toArray call -- this allocates space for your temporary array, and necessarily iterates all elements, even if you only want 5. You are better off not to do things this way. Incidentally, I do plan on adding a Link*Set/Map to dcollections, because I really like the array type in php (same thing). But this will not provide constant access to the nth element, so it still will fail your requirements. The only thing I can think of is to store the elements in an array alongside the hash map (do you need to look up elements by hash_t? If not, why not just use an array directly?) to store the order of insertion. This only works if you rarely remove elements (removal in an array is an O(n) operation). -Steve
Feb 03 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 02 Feb 2011 05:11:34 -0500, Nrgyzer <nrgyzer gmail.com> wrote:

 Hey guys,

 I have an associative array like this: T[hash_t] myArray; (T means
 the template type).

 Is there any chance to cast/convert this array to an indexed array or
 is it possible to iterate over specific indices? I know that there is
 something like next() for the foreach-statement but when the array
 contains some thousand instances and I only want iterate over (for
 example) 5 elements I think that's the wrong way. It's for a game and
 I think every next()-call influences the fps.

 I hope there is any solution for my problem :) - Thanks!

dcollections contains more functionality than builtin AAs. The equivalent type in dcollections would be HashMap!(hash_t, T): http://www.dsource.org/projects/dcollections You might find this helps solve some problems. I don't really understand what you are asking for, if you want to iterate over "specific" indexes, wouldn't you just use those indexes to look up the elements you desire? i.e.: foreach(i; specific_indexes) // specific_indexes is an array of the indexes you wish to use { auto elem = myArray[i]; ... } -Steve
Feb 03 2011
prev sibling next sibling parent Stanislav Blinov <blinov loniir.ru> writes:
03.02.2011 19:34, Nrgyzer пишет:
 == Auszug aus Steven Schveighoffer (schveiguy yahoo.com)'s Artikel
 This only works if you rarely remove elements (removal in an
 array is an O(n) operation).
 -Steve

elements that should be drawn) and a second like uint[hash_t] which contains the indices in the first array. But it does only shit the problem that I can't remove an index from a dynamic array. Thanks for your suggestions.

You can: 1) Get an index i from hash, do arr = arr[0..i] ~ arr[i+1..$] and then reindex all arr[i..$] elements. This is costly, because, as Steven mentioned, such removal is O(n) plus you have to iterate all elements with index >= i, and this traversal is O(n) in the worst case. 2) Use unstable removal. Since you store indices separately, you can just swap an element to be removed with last element in the array, shrink array using slicing (arr = arr[0..$-1]) and reindex a single element (the one that was previously last in the array). The drawback is that this approach doesn't preserve order of elements in the array.
Feb 03 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/03/2011 04:29 PM, Steven Schveighoffer wrote:
 Again, I'm not sure what the point is of starting in the middle of the array.
 Are you expecting something different from a hashtable?

Maybe what he needs is a plain Lisp-like symbol table (in D, an array of (key value) pairs)? Denis -- _________________ vita es estrany spir.wikidot.com
Feb 03 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 02/03/2011 04:41 PM, Nrgyzer wrote:
 == Auszug aus Steven Schveighoffer (schveiguy yahoo.com)'s Artikel
 On Thu, 03 Feb 2011 09:35:44 -0500, Nrgyzer<nrgyzer gmail.com>

 == Auszug aus bearophile (bearophileHUGS lycos.com)'s Artikel
 Nrgyzer:
 Is there any chance to cast/convert this array to an indexed


 is it possible to iterate over specific indices? I know that


 something like next() for the foreach-statement but when the




 contains some thousand instances and I only want iterate over




 example) 5 elements I think that's the wrong way.




 Bye,
 bearophile

Example: ... class Example(T : Drawable) : Drawable { T[hash_t] pObjectsToDraw; uint pFrom, pTo; void setLimit(from, to) { pFrom = from; pTo = to; } void remove(T objToRemove) { pObjectsToDraw.remove(objToRemove.toHash()); } override void draw() { for (uint i = pFrom; i< pTo; i++) { pOjectsToDraw[i].draw(); // cannot call because pObjectsToDraw is an associative and no static or dynamic array } } }


 you expect to accomplish except "give me (pTo - pFrom) random

   from the array"
 Second, you can use a foreach loop to get data out of an AA, and

 break when you've retrieved enough elements.
 Again, I'm not sure what the point is of starting in the middle of

 array.  Are you expecting something different from a hashtable?
 -Steve

I know that hashes aren't stored in any order... but lets take the LinkedHashSet in Java. The LinkedHashSet/Map stores the hashes in order of inserting. With the toArray()-method I can loop over specific elements/indices... but I can also remove the elements by their hash. I'm looking for a similar technique in D - you can find an Java example on http://www.java2s.com/Code/JavaAPI/java.util/ LinkedHashSettoArray.htm.

Ruby hashes are like that, but I don't think it would be easy to do in D. You'd better maintain the insertion order yourself in a // array of keys, or make elements link list nodes. Denis -- _________________ vita es estrany spir.wikidot.com
Feb 03 2011