www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Help with Ranges

reply Charles <charles email.sometld> writes:
Suppose I have the following line of code where arr is an array, 
doSomething is some predicate that does a lot of processing on 
each element, sort must come after the mapping, and there are 
more operations done to the range after sort:

arr.map!doSomething.sort. ...;

Sort fails to instantiate because the range it's receiving 
doesn't support element swapping. This may and might be resolved 
by calling array:

arr.map!doSomething.array.sort. ...;

However, this might trigger an allocation, and there's still more 
to do! Is there something I'm missing with regards to ranges that 
could help me make the first line work without using array, or is 
it more of an issue with my code's design?
Jul 26 2020
next sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 7/26/20 3:10 AM, Charles wrote:

 Suppose I have the following line of code where arr is an array, 
 doSomething is some predicate that does a lot of processing on each 
 element, sort must come after the mapping, and there are more operations 
 done to the range after sort:
 
 arr.map!doSomething.sort. ...;
 
 Sort fails to instantiate because the range it's receiving doesn't 
 support element swapping. This may and might be resolved by calling array:
 
 arr.map!doSomething.array.sort. ...;
 
 However, this might trigger an allocation, and there's still more to do! 
 Is there something I'm missing with regards to ranges that could help me 
 make the first line work without using array, or is it more of an issue 
 with my code's design?


That is what you need to do.

A map that returns an lvalue would be sortable, but you would be sorting 
the processed elements, and probably not the original elements.

I have found this handy tool quite useful in my code where I need a 
temporary array:

// creates a concrete range (std.container.array.Array range) out of the
// original range that is eagerly fetched, and then can be processed, 
without
// allocating extra garbage on the heap.
auto concreteRange(Range)(Range r)
{
     import std.range : ElementType;
     import std.container.array : Array;
     return Array!(ElementType!Range)(r)[];
}

Slicing an Array will keep the reference count correctly, and destroy 
the memory automatically after you're done using it. So it's perfect for 
temporary arrays in pipelining.

-Steve
Jul 26 2020
parent reply Charles <charles email.sometld> writes:
On Sunday, 26 July 2020 at 14:56:35 UTC, Steven Schveighoffer 
wrote:

 A map that returns an lvalue would be sortable, but you would 
 be sorting the processed elements, and probably not the 
 original elements.


Indeed, but that's what I want: sort the process elements. 
Otherwise, I'd place sort before the transformations.


 I have found this handy tool quite useful in my code where I 
 need a temporary array:

 // creates a concrete range (std.container.array.Array range) 
 out of the
 // original range that is eagerly fetched, and then can be 
 processed, without
 // allocating extra garbage on the heap.
 auto concreteRange(Range)(Range r)
 {
     import std.range : ElementType;
     import std.container.array : Array;
     return Array!(ElementType!Range)(r)[];
 }

 Slicing an Array will keep the reference count correctly, and 
 destroy the memory automatically after you're done using it. So 
 it's perfect for temporary arrays in pipelining.

 -Steve


This works well, and it's rather nifty. Still, I'm confused 
since, as far as I know, map wraps its source, i.e. the array in 
this case, which is sortable. It seems to me the only reason I 
can't sort MapResult is because it doesn't have the proper 
interface.

I'm obviously missing something.
Jul 27 2020
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 7/27/20 1:10 PM, Charles wrote:


 Still, I'm confused since, as 
 far as I know, map wraps its source, i.e. the array in this case, which 
 is sortable. It seems to me the only reason I can't sort MapResult is 
 because it doesn't have the proper interface.


Let's talk about a concrete example, so you can see why:

int[] arr = [21, 83, 45, 60];

auto m = arr.map!(a => a % 10);

Sort is going to look at m as a random-access range of integers. But the 
integer you get from m[2] for instance is going to be 5. So you can 
compare e.g. m[2] and m[3] (5 and 0), but how do you *WRITE* back to the 
original array? All you have as an interface is non-writable 5 and 0, 
not the original array members 45 and 60. In other words, if you swapped 
5 and 0, map can't do the inverse transform here (and even if it could, 
0 and 5 map to millions of possible original values).

What it seems like you are possibly interested in doing is to sort the 
original array based on a transformation. But in your original post you 
said "doSomething is some predicate that does a lot of processing on 
each element", so I assumed, e.g. something like this is not valid for 
your use case:

arr.sort!((a, b) => doSomething(a) < doSomething(b))

as it would be very expensive assuming doSomething is expensive.

You can use H.S. Teoh's suggestion and use schwartzSort (in fact, it 
does something almost exactly the same as what I wrote, except it sorts 
the original elements).

However, for something like a % 10, I'd much rather just do it without 
allocating another array.

So it really depends on what your requirements are, which you haven't 
fully identified.

-Steve
Jul 27 2020
parent Charles <charles email.sometld> writes:
On Monday, 27 July 2020 at 18:15:26 UTC, Steven Schveighoffer 
wrote:

 On 7/27/20 1:10 PM, Charles wrote:


 [...]


 Let's talk about a concrete example, so you can see why:

 int[] arr = [21, 83, 45, 60];

 [...]


I had very incorrect model of how ranges function, and after 
reading your post along with map's source, I think I know how to 
proceed from here. I really appreciate your patience, and next 
time I'll clearly explain my constraints.

Thank you, gentlemen.
Jul 27 2020
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sun, Jul 26, 2020 at 07:10:41AM +0000, Charles via Digitalmars-d-learn wrote:

 Suppose I have the following line of code where arr is an array,
 doSomething is some predicate that does a lot of processing on each
 element, sort must come after the mapping, and there are more
 operations done to the range after sort:
 
 arr.map!doSomething.sort. ...;


[...]

As Steven said, you cannot sort a range that doesn't support swapping
elements, and most ranges cannot unless they're backed by actual
storage, like an array. (*Something* has got to keep track of where the
elements are, after all.)

In this particular case, though, if the contents of your original
doesn't need to be preserved, perhaps .schwartzSort might be what you're
looking for?

If you cannot modify the original array for whatever reason, then an
allocation is probably unavoidable -- either you'll have to create an
array of your mapped elements, or you could create an index and sort
that instead (see .makeIndex or std.range.zip for different approaches).


T

-- 
Those who don't understand Unix are condemned to reinvent it, poorly.
Jul 27 2020
parent Charles <charles email.sometld> writes:
On Monday, 27 July 2020 at 16:52:51 UTC, H. S. Teoh wrote:

 On Sun, Jul 26, 2020 at 07:10:41AM +0000, Charles via 
 Digitalmars-d-learn wrote:

 Suppose I have the following line of code where arr is an 
 array, doSomething is some predicate that does a lot of 
 processing on each element, sort must come after the mapping, 
 and there are more operations done to the range after sort:
 
 arr.map!doSomething.sort. ...;


 [...]

 As Steven said, you cannot sort a range that doesn't support 
 swapping elements, and most ranges cannot unless they're backed 
 by actual storage, like an array. (*Something* has got to keep 
 track of where the elements are, after all.)


But in my example, isn't the output of map backed by actual 
storage? After all, it's taking in an array.


 In this particular case, though, if the contents of your 
 original doesn't need to be preserved, perhaps .schwartzSort 
 might be what you're looking for?

 If you cannot modify the original array for whatever reason, 
 then an allocation is probably unavoidable -- either you'll 
 have to create an array of your mapped elements, or you could 
 create an index and sort that instead (see .makeIndex or 
 std.range.zip for different approaches).


 T


I'll take a look at both of these, since I need to be aware of 
both cases. I'm trying to find the most efficient way of building 
a pipeline for my own betterment. Thank you.
Jul 27 2020