www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Iterate/sort associative array by value?

reply =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
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. Mnch
http://www.saphirion.com
smarter | better | faster
Apr 07
next sibling parent reply Cym13 <cpicard openmailbox.org> writes:
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?
Apr 07
parent reply =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
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. Mnch http://www.saphirion.com smarter | better | faster
Apr 07
next sibling parent reply Seb <seb wilzba.ch> writes:
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.
Apr 07
next sibling parent reply =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
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. Mnch http://www.saphirion.com smarter | better | faster
Apr 07
next sibling parent reply Dennis <dkorpel gmail.com> writes:
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;
Apr 07
parent reply =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
On 2019-04-07 19:28:02 +0000, Dennis said:

 Did you import it? import std.algorithm;
:-/ of course not... Why does DMD not give a hint, that an import from the standard lib might be missing? I find these explicit import statements very annyoing. DMD should build up a database of stuff it knows about (provided via a config file where to find what) and auto-import just the things I use/need. The current system is legacy based like it is in C since 40 years... Anyway, might be worth a topic on its own... -- Robert M. Mnch http://www.saphirion.com smarter | better | faster
Apr 08
next sibling parent reply Julian <julian.fondren gmail.com> writes:
On Monday, 8 April 2019 at 07:53:23 UTC, Robert M. Münch wrote:
 On 2019-04-07 19:28:02 +0000, Dennis said:

 Did you import it? import std.algorithm;
:-/ of course not... Why does DMD not give a hint, that an import from the standard lib might be missing?
It does do this, so the question should be: why aren't its warnings more extensive? Example: void main() { writeln("Hello, world!"); } Fails to compile with this error: ./missing.d(4): Error: writeln is not defined, perhaps import std.stdio; is needed? That seems to come from src/dmd/expressionsem.d , which uses importHint from src/dmd/imphint.d , which just has this list: shared static this() { // in alphabetic order hints = [ "calloc": "core.stdc.stdlib", "cos": "std.math", "fabs": "std.math", "free": "core.stdc.stdlib", "malloc": "core.stdc.stdlib", "printf": "core.stdc.stdio", "realloc": "core.stdc.stdlib", "sin": "std.math", "sqrt": "std.math", "writefln": "std.stdio", "writeln": "std.stdio", "__va_argsave_t": "core.stdc.stdarg", "__va_list_tag": "core.stdc.stdarg", ]; }
Apr 08
parent =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
On 2019-04-08 08:29:24 +0000, Julian said:

 It does do this, so the question should be: why aren't its warnings
 more extensive?
Ok, I had the impression that I saw such a message in the past but wasn't sure about it... -- Robert M. Mnch http://www.saphirion.com smarter | better | faster
Apr 10
prev sibling parent reply Dennis <dkorpel gmail.com> writes:
On Monday, 8 April 2019 at 07:53:23 UTC, Robert M. Münch wrote:
 Why does DMD not give a hint, that an import from the standard 
 lib might be missing? I find these explicit import statements 
 very annyoing.
There currently are a few hard-coded import hints for common functions: https://github.com/dlang/dmd/blob/master/src/dmd/imphint.d But it definitely could be better. As Sebastian said, you can do `import std.experimental.all;` or from version 2.086 `import std;` to import the entire standard library. If dmd as a library pans out, a language server might automatically suggest imports for unresolved symbols like common Java and C# IDEs do.
Apr 08
next sibling parent reply Seb <seb wilzba.ch> writes:
On Monday, 8 April 2019 at 08:31:33 UTC, Dennis wrote:
 On Monday, 8 April 2019 at 07:53:23 UTC, Robert M. Münch wrote:
 Why does DMD not give a hint, that an import from the standard 
 lib might be missing? I find these explicit import statements 
 very annyoing.
There currently are a few hard-coded import hints for common functions: https://github.com/dlang/dmd/blob/master/src/dmd/imphint.d But it definitely could be better.
Yeah, it's not too hard to improve this. A quick start: https://github.com/dlang/dmd/pull/9576
Apr 08
parent Julian <julian.fondren gmail.com> writes:
On Monday, 8 April 2019 at 17:13:32 UTC, Seb wrote:
 On Monday, 8 April 2019 at 08:31:33 UTC, Dennis wrote:
 On Monday, 8 April 2019 at 07:53:23 UTC, Robert M. Münch wrote:
 Why does DMD not give a hint, that an import from the 
 standard lib might be missing? I find these explicit import 
 statements very annyoing.
There currently are a few hard-coded import hints for common functions: https://github.com/dlang/dmd/blob/master/src/dmd/imphint.d But it definitely could be better.
Yeah, it's not too hard to improve this. A quick start: https://github.com/dlang/dmd/pull/9576
I can't make an issue yet, but since they're asking for a BugZilla issue, a relevant one would be "published D examples fail without import hints". In the very first chapter of the D Programming Language, library changes result in errors for enforce (which you add) and std.algorithm.splitter The book has an errata but the compiler's the very first thing that can communicate "D has helpful error messages" instead of "maybe I should wait for this language to mature a bit more". For more comprehensive hints, isn't the documentation generated? Maybe, patch docgen to generate this table as well.
Apr 08
prev sibling parent =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
On 2019-04-08 08:31:33 +0000, Dennis said:

 As Sebastian said, you can do `import std.experimental.all;` or from 
 version 2.086 `import std;` to import the entire standard library.
Well, that's more like a brute force approach. So it would be always best to use "import *" :-) I like selective imports, because it gives a clear hint where things are coming from. I don't like that I have to do it manually. Maybe a 2-pass approach would help: DMD spitting out the minimal selective import statements at the end, which you could cut & paste into your code.
 If dmd as a library pans out, a language server might automatically 
 suggest imports for unresolved symbols like common Java and C# IDEs do.
Yep, good approach too. -- Robert M. Mnch http://www.saphirion.com smarter | better | faster
Apr 10
prev sibling parent reply Seb <seb wilzba.ch> writes:
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;`
Apr 07
parent Seb <seb wilzba.ch> writes:
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.)
Apr 07
prev sibling next sibling parent diniz <diniz posteo.net> writes:
Le 07/04/2019 à 19:16, Seb via Digitalmars-d-learn a écrit :
 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.
That's what I would do: just operating on an array of {k,v} pairs. -- diniz {la vita e estranj}
Apr 08
prev sibling parent reply kdevel <kdevel vogtner.de> writes:
On Sunday, 7 April 2019 at 17:16:12 UTC, Seb wrote:
 ---
 ["a": 1].byPair.array.sort!((a, b) => a.value < 
 a.value).release.each!writeln;
 ---
What's the purpose of .release? The documentation in https://dlang.org/phobos/std_range.html#.SortedRange.release is rather monosyllabic.
Apr 08
next sibling parent Dennis <dkorpel gmail.com> writes:
On Monday, 8 April 2019 at 18:04:28 UTC, kdevel wrote:
 What's the purpose of .release? The documentation in 
 https://dlang.org/phobos/std_range.html#.SortedRange.release is 
 rather monosyllabic.
The sort function returns a SortedRange, which is usually an array wrapper with the extra type information that its content is sorted, enabling certain algorithms like lowerBound and upperBound with help of binary search. "Ranges whose elements are sorted afford better efficiency with certain operations. For this, the assumeSorted function can be used to construct a SortedRange from a pre-sorted range. The std.algorithm.sorting.sort function also conveniently returns a SortedRange. SortedRange objects provide some additional range operations that take advantage of the fact that the range is sorted." (https://dlang.org/phobos/std_range.html) When you release it, you get it back as a normal slice without the type information that it is sorted, so you can assign it to regular old array variables. As mentioned in the quote, you can get it back as sortedRange with assumeSorted.
Apr 08
prev sibling parent Seb <seb wilzba.ch> writes:
On Monday, 8 April 2019 at 18:04:28 UTC, kdevel wrote:
 On Sunday, 7 April 2019 at 17:16:12 UTC, Seb wrote:
 ---
 ["a": 1].byPair.array.sort!((a, b) => a.value < 
 a.value).release.each!writeln;
 ---
What's the purpose of .release? The documentation in https://dlang.org/phobos/std_range.html#.SortedRange.release is rather monosyllabic.
As others have already explained, you'll get the original range back (instead of the SortedRange). Sometimes, this is useful. The obvious example is assigning back to the original range: --- import std.experimental.all; void main() { auto arr = ["a": 1].byPair.array; arr = arr.sort!((a, b) => a.value < a.value); } --- https://run.dlang.io/is/8sFxVb OTOH this works: --- import std.experimental.all; void main() { auto arr = ["a": 1].byPair.array; arr = arr.sort!((a, b) => a.value < a.value).release; } --- https://run.dlang.io/is/TgXUZj In the example where I used it, you won't need it. Sorry for the confusion, but as it's often every now and then pretty useful, I thought it is a nice idea to give it more spotlight as it's one of the lesser known parts of Phobos.
Apr 08
prev sibling parent reply bauss <jj_1337 live.dk> writes:
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
Apr 07
parent =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
On 2019-04-07 17:35:23 +0000, bauss said:

 Import std.array
:-/ Thanks... -- Robert M. Mnch http://www.saphirion.com smarter | better | faster
Apr 07
prev sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 04/07/2019 08:41 AM, 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?
Because associative array is a data structure to use when the order is not important, it comes down to getting the values and then sorting. Since there is already a .values that returns a copy of the values, I would just sort that one: auto arr = aa.values; sort(arr); use(arr); I think that method might be faster than others because .values is provided by the AA implementation but I shouldn't say that without testing. :) So, with dmd v2.085.0, .values is 4 times faster than .byValues: import std.algorithm; import std.stdio; import std.array; import std.range; import std.typecons; import std.format; enum aaElementCount = 100_000; enum testCount = 100; ulong expectedResult; // So that the whole operation is not optimized out void use(int[] aa) { const result = aa.sum; if (expectedResult == 0) { expectedResult = result; } // Make sure that all methods produce the same result assert(expectedResult != 0); assert(result == expectedResult, format!"%s != %s"(result, expectedResult)); } void main() { auto aa = aaElementCount.iota.map!(i => tuple(i, i)).assocArray(); import std.datetime.stopwatch; auto measurements = benchmark!( { auto arr = aa.byValue.array; // sort(arr); use(arr); }, { auto arr = aa.values; // sort(arr); use(arr); }, )(testCount); writefln("%(%s\n%)", measurements); } 450 ms, 424 μs, and 8 hnsecs <-- .byValue.array 108 ms, 124 μs, and 6 hnsecs <-- .values Of course the difference is much less when we comment-in the sort() lines. Ali
Apr 07