Thread overview | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
April 07, 2019 Iterate/sort associative array by value? | ||||
---|---|---|---|---|
| ||||
I have an AA int[ulong] and would like to traverse the AA from biggest to smallest by value. Is there an elegant way to do this?
The only way I can imagine is to create an "reverse" AA of the form ulong[int] and than sort by keys. Traverse this AA and use the value as the lookup key in the orginial array. But this feels all a bit wired...
--
Robert M. Münch
http://www.saphirion.com
smarter | better | faster
|
April 07, 2019 Re: Iterate/sort associative array by value? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert M. Münch | On Sunday, 7 April 2019 at 15:41:51 UTC, Robert M. Münch wrote:
> I have an AA int[ulong] and would like to traverse the AA from biggest to smallest by value. Is there an elegant way to do this?
>
> The only way I can imagine is to create an "reverse" AA of the form ulong[int] and than sort by keys. Traverse this AA and use the value as the lookup key in the orginial array. But this feels all a bit wired...
You could use sort to gather the indexes in order then traverse from there:
aa.byKey.array.sort!((a, b) => aa[a]<aa[b])
With a wrapper caching that order and making it transparent as well as update on insertion (which should be in log(n) since you know have an ordered list of indexes, you can use dichotomy to update the indexes without walking all your AA again) I think you could have a nice little container.
However if double entry is necessary maybe a simpler 2D array would be easier to work with?
|
April 07, 2019 Re: Iterate/sort associative array by value? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Cym13 | On 2019-04-07 16:24:52 +0000, Cym13 said: > You could use sort to gather the indexes in order then traverse from there: > > aa.byKey.array.sort!((a, b) => aa[a]<aa[b]) That doesn't work: Error: no property array for type Result > > With a wrapper caching that order and making it transparent as well as update on insertion (which should be in log(n) since you know have an ordered list of indexes, you can use dichotomy to update the indexes without walking all your AA again) I think you could have a nice little container. However if double entry is necessary maybe a simpler 2D array would be easier to work with? At the point where I need this sorted array, nothing will change it. It's a log output. So, not necessary to make things more complex. -- Robert M. Münch http://www.saphirion.com smarter | better | faster |
April 07, 2019 Re: Iterate/sort associative array by value? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert M. Münch | On Sunday, 7 April 2019 at 16:44:01 UTC, Robert M. Münch wrote:
> On 2019-04-07 16:24:52 +0000, Cym13 said:
>
>> You could use sort to gather the indexes in order then traverse from there:
>>
>> aa.byKey.array.sort!((a, b) => aa[a]<aa[b])
>
> That doesn't work: Error: no property array for type Result
>>
>> With a wrapper caching that order and making it transparent as well as update on insertion (which should be in log(n) since you know have an ordered list of indexes, you can use dichotomy to update the indexes without walking all your AA again) I think you could have a nice little container. However if double entry is necessary maybe a simpler 2D array would be easier to work with?
>
> At the point where I need this sorted array, nothing will change it. It's a log output. So, not necessary to make things more complex.
Then you can do:
---
["a": 1].byPair.array.sort!((a, b) => a.value < a.value).release.each!writeln;
---
You'll have a sorted array with key and value props.
|
April 07, 2019 Re: Iterate/sort associative array by value? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert M. Münch | On Sunday, 7 April 2019 at 16:44:01 UTC, Robert M. Münch wrote:
> On 2019-04-07 16:24:52 +0000, Cym13 said:
>
>> You could use sort to gather the indexes in order then traverse from there:
>>
>> aa.byKey.array.sort!((a, b) => aa[a]<aa[b])
>
> That doesn't work: Error: no property array for type Result
>>
>> With a wrapper caching that order and making it transparent as well as update on insertion (which should be in log(n) since you know have an ordered list of indexes, you can use dichotomy to update the indexes without walking all your AA again) I think you could have a nice little container. However if double entry is necessary maybe a simpler 2D array would be easier to work with?
>
> At the point where I need this sorted array, nothing will change it. It's a log output. So, not necessary to make things more complex.
Import std.array
|
April 07, 2019 Re: Iterate/sort associative array by value? | ||||
---|---|---|---|---|
| ||||
Posted in reply to bauss | On 2019-04-07 17:35:23 +0000, bauss said: > Import std.array :-/ Thanks... -- Robert M. Münch http://www.saphirion.com smarter | better | faster |
April 07, 2019 Re: Iterate/sort associative array by value? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Seb | On 2019-04-07 17:16:12 +0000, Seb said: > Then you can do: > > --- > ["a": 1].byPair.array.sort!((a, b) => a.value < a.value).release.each!writeln; > --- > > You'll have a sorted array with key and value props. This seems to be really tricky: int[uint] myArray; foreach(key, value; myArray.byPair.array.sort!((a, b) => a.value < a.value)){...} Error: no property sort for type Tuple!(uint, "key", int, "value")[] -- Robert M. Münch http://www.saphirion.com smarter | better | faster |
April 07, 2019 Re: Iterate/sort associative array by value? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert M. Münch | On Sunday, 7 April 2019 at 18:22:00 UTC, Robert M. Münch wrote:
> Error: no property sort for type Tuple!(uint, "key", int, "value")[]
Did you import it?
import std.algorithm;
|
April 07, 2019 Re: Iterate/sort associative array by value? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert M. Münch | On Sunday, 7 April 2019 at 18:22:00 UTC, Robert M. Münch wrote:
> On 2019-04-07 17:16:12 +0000, Seb said:
>
>> Then you can do:
>>
>> ---
>> ["a": 1].byPair.array.sort!((a, b) => a.value < a.value).release.each!writeln;
>> ---
>>
>> You'll have a sorted array with key and value props.
>
> This seems to be really tricky:
>
> int[uint] myArray;
>
> foreach(key, value; myArray.byPair.array.sort!((a, b) => a.value < a.value)){...}
>
> Error: no property sort for type Tuple!(uint, "key", int, "value")[]
You forgot to import std.algorithm.
In doubt, use std.experimental.all or with 2.086 it will just be `import STD;`
|
April 07, 2019 Re: Iterate/sort associative array by value? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Seb | On Sunday, 7 April 2019 at 20:02:15 UTC, Seb wrote:
> On Sunday, 7 April 2019 at 18:22:00 UTC, Robert M. Münch wrote:
>> On 2019-04-07 17:16:12 +0000, Seb said:
>>
>>> Then you can do:
>>>
>>> ---
>>> ["a": 1].byPair.array.sort!((a, b) => a.value < a.value).release.each!writeln;
>>> ---
>>>
>>> You'll have a sorted array with key and value props.
>>
>> This seems to be really tricky:
>>
>> int[uint] myArray;
>>
>> foreach(key, value; myArray.byPair.array.sort!((a, b) => a.value < a.value)){...}
>>
>> Error: no property sort for type Tuple!(uint, "key", int, "value")[]
>
> You forgot to import std.algorithm.
> In doubt, use std.experimental.all or with 2.086 it will just be `import STD;`
*import std;
(auto-correct from my phone was too eager.)
|
Copyright © 1999-2021 by the D Language Foundation