• Andrew Klaassen (10/10) Dec 11 2014 In theory, it should be possible to do a "popFront" equivalent
• =?UTF-8?B?QWxpIMOHZWhyZWxp?= (16/19) Dec 11 2014 Correct. keys() is eager. For O(1) you want byKey(), which returns a
• H. S. Teoh via Digitalmars-d-learn (18/27) Dec 11 2014 [...]
• bearophile (6/13) Dec 11 2014 In general the associative array table can have many empty slots,
• H. S. Teoh via Digitalmars-d-learn (10/12) Dec 11 2014 [...]
• Steven Schveighoffer (6/15) Dec 11 2014 Just want to say that until recently, byKey was NOT O(1). A recent
• Andrew Klaassen (1/1) Dec 11 2014 Thanks everyone!

"Andrew Klaassen" <clawsoon yahoo.com> writes:

In theory, it should be possible to do a "popFront" equivalent 
for a hash that has O(1) average complexity, so long as you don't 
care about order.  I.e., "give me any key from the hash, I don't 
care which one, and then delete it from the hash".  Is that 
correct?

If it is correct, is there any way to do it in D?

Do I assume correctly that "myarray.keys[0]" would not meet the 
O(1) requirement?

Thanks.

Andrew

=?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:

On 12/11/2014 10:27 AM, Andrew Klaassen wrote:

 If it is correct, is there any way to do it in D?

 Do I assume correctly that "myarray.keys[0]" would not meet the O(1)
 requirement?

Correct. keys() is eager. For O(1) you want byKey(), which returns a 
lazy range but the code is less than pretty:

import std.stdio;

void main()
{
     auto aa = [ 1 : "one", 2 : "two" ];

     while (true) {
         auto keys = aa.byKey;

         if (keys.empty) {
             break;
         }

         aa.remove(keys.front);
     }
}

Ali

"H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:

On Thu, Dec 11, 2014 at 06:27:06PM +0000, Andrew Klaassen via
Digitalmars-d-learn wrote:
 In theory, it should be possible to do a "popFront" equivalent for a
 hash that has O(1) average complexity, so long as you don't care about
 order.  I.e., "give me any key from the hash, I don't care which one,
 and then delete it from the hash".  Is that correct?
 
 If it is correct, is there any way to do it in D?
 
 Do I assume correctly that "myarray.keys[0]" would not meet the O(1)
 requirement?

[...]

AA.keys will walk the entire hash table and return an array of keys.
That's totally wasteful of what you want, and is definitely not O(1).

On the other hand, AA.byKey() will return a *lazy* sequence of keys
(i.e., it won't actually walk the AA unless you want it to), so doing
this ought to be O(1):

	auto mykey = myarray.byKey().front;
	myarray.remove(mykey);

Be careful that you do not attempt to continue using the lazy sequence
returned by byKey() once you have invoked .remove, though, because
modifying a container while iterating over it almost always leads to
counterintuitive (and sometimes outright buggy) behaviour. Repeatedly
retrieving the first key and then removing it, as above, is OK, since
you're starting over with a new sequence of keys each time.


T

-- 
Computers aren't intelligent; they only think they are.

"bearophile" <bearophileHUGS lycos.com> writes:

H. S. Teoh:

 On the other hand, AA.byKey() will return a *lazy* sequence of 
 keys
 (i.e., it won't actually walk the AA unless you want it to), so 
 doing
 this ought to be O(1):

 	auto mykey = myarray.byKey().front;
 	myarray.remove(mykey);

In general the associative array table can have many empty slots, 
so byKey.front is not always O(1). But AAs were recently 
improved, now byKey.front is much faster.

Bye,
bearophile

"H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:

On Thu, Dec 11, 2014 at 10:36:02AM -0800, H. S. Teoh via Digitalmars-d-learn
wrote:
[...]
 	auto mykey = myarray.byKey().front;
 	myarray.remove(mykey);

[...]

Ah, I forgot that you need to check .empty on the range returned by
byKey before accessing .front. Thanks to Ali for pointing that out. :-)
In this case, though, you *could* just check myarray.empty directly
instead.


T

-- 
Why are you blatanly misspelling "blatant"? -- Branden Robinson

Steven Schveighoffer <schveiguy yahoo.com> writes:

On 12/11/14 1:41 PM, H. S. Teoh via Digitalmars-d-learn wrote:
 On Thu, Dec 11, 2014 at 10:36:02AM -0800, H. S. Teoh via Digitalmars-d-learn
wrote:
 [...]
 	auto mykey = myarray.byKey().front;
 	myarray.remove(mykey);

 [...]

 Ah, I forgot that you need to check .empty on the range returned by
 byKey before accessing .front. Thanks to Ali for pointing that out. :-)
 In this case, though, you *could* just check myarray.empty directly
 instead.

Just want to say that until recently, byKey was NOT O(1). A recent 
optimization caches the first used bucket, which makes it O(1).

I would recommend checking for array.empty, because that allows you to 
avoid keeping the byKey range in a variable.

-Steve

"Andrew Klaassen" <clawsoon yahoo.com> writes:

Thanks everyone!