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!

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

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

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

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

== Auszug aus bearophile (bearophileHUGS@lycos.com)'s Artikel
> 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

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

}

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

== Auszug aus Steven Schveighoffer (schveiguy@yahoo.com)'s Artikel
> 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
> > 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
> >
> > 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

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.

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>
> wrote:
>> > == Auszug aus bearophile (bearophileHUGS@lycos.com)'s Artikel
>> >> 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
>> >
>> > 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
>
> 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

== 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>
> > wrote:
> >> > == Auszug aus bearophile (bearophileHUGS@lycos.com)'s Artikel
> >> >> 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
> >> >
> >> > 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
> >
> > 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

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.