Re: Iterate/sort associative array by value?
On 2019-04-08 08:31:33 +, 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. Münch http://www.saphirion.com smarter | better | faster
Re: Iterate/sort associative array by value?
On 2019-04-08 08:29:24 +, 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. Münch http://www.saphirion.com smarter | better | faster
Re: Iterate/sort associative array by value?
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.
Re: Iterate/sort associative array by value?
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.
Re: Iterate/sort associative array by value?
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.
Re: Iterate/sort associative array by value?
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.
Re: Iterate/sort associative array by value?
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
Re: Iterate/sort associative array by value?
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}
Re: Iterate/sort associative array by value?
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.
Re: Iterate/sort associative array by value?
On Monday, 8 April 2019 at 07:53:23 UTC, Robert M. Münch wrote: On 2019-04-07 19:28:02 +, 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", ]; }
Re: Iterate/sort associative array by value?
On 2019-04-07 19:28:02 +, 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. Münch http://www.saphirion.com smarter | better | faster
Re: Iterate/sort associative array by value?
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
Re: Iterate/sort associative array by value?
On Sunday, 7 April 2019 at 18:22:00 UTC, Robert M. Münch wrote: On 2019-04-07 17:16:12 +, 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;`
Re: Iterate/sort associative array by value?
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 +, 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.)
Re: Iterate/sort associative array by value?
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;
Re: Iterate/sort associative array by value?
On 2019-04-07 17:16:12 +, 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
Re: Iterate/sort associative array by value?
On 2019-04-07 17:35:23 +, bauss said: Import std.array :-/ Thanks... -- Robert M. Münch http://www.saphirion.com smarter | better | faster
Re: Iterate/sort associative array by value?
On Sunday, 7 April 2019 at 16:44:01 UTC, Robert M. Münch wrote: On 2019-04-07 16:24:52 +, Cym13 said: You could use sort to gather the indexes in order then traverse from there: aa.byKey.array.sort!((a, b) => aa[a] 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
Re: Iterate/sort associative array by value?
On Sunday, 7 April 2019 at 16:44:01 UTC, Robert M. Münch wrote: On 2019-04-07 16:24:52 +, Cym13 said: You could use sort to gather the indexes in order then traverse from there: aa.byKey.array.sort!((a, b) => aa[a] 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.
Re: Iterate/sort associative array by value?
On 2019-04-07 16:24:52 +, Cym13 said: You could use sort to gather the indexes in order then traverse from there: aa.byKey.array.sort!((a, b) => aa[a] 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
Re: Iterate/sort associative array by value?
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]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?
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