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?

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

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.

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.

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.

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

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.