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. Münch
http://www.saphirion.com
smarter | better | faster
Apr 07 2019
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 2019
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. Münch
http://www.saphirion.com
smarter | better | faster
Apr 07 2019
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 2019
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. Münch
http://www.saphirion.com
smarter | better | faster
Apr 07 2019
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 2019
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. Münch
http://www.saphirion.com
smarter | better | faster
Apr 08 2019
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 2019
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. Münch
http://www.saphirion.com
smarter | better | faster
Apr 10 2019
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
Apr 08 2019
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 2019
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 2019
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 



Yep, good approach too.

-- 
Robert M. Münch
http://www.saphirion.com
smarter | better | faster
Apr 10 2019
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 2019
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 2019
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 2019
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 2019
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 2019
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 2019
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 2019
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. Münch
http://www.saphirion.com
smarter | better | faster
Apr 07 2019
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 2019