Just pickin' yall's smart brains:

Given an array A and a set of indices into the array, is there a fast algorithm for rearranging A in-place so that the elements at the given indices are moved to the front?

E.g.: A = [ 0, 1, 2, 3, 4, 5 ], index = [ 1, 3, 5 ]

The result should have 1, 3, and 5 at the front of the array (the exact
order is unimportant).

For efficiency considerations, assume the size of the index is relatively small, but the array itself may be quite large, so scanning the entire array or copying large chunks of it is undesirable.


T

-- 
Customer support: the art of getting your clients to pay for your own incompetence.

On Thursday, 28 May 2020 at 23:47:50 UTC, H. S. Teoh wrote:
> Just pickin' yall's smart brains:
>
> Given an array A and a set of indices into the array, is there a fast algorithm for rearranging A in-place so that the elements at the given indices are moved to the front?
>
> E.g.: A = [ 0, 1, 2, 3, 4, 5 ], index = [ 1, 3, 5 ]
>
> The result should have 1, 3, and 5 at the front of the array (the exact
> order is unimportant).
>
> For efficiency considerations, assume the size of the index is relatively small, but the array itself may be quite large, so scanning the entire array or copying large chunks of it is undesirable.

If you don’t care the remaining elements’ order, just swap the head N elements with the index array’s pointing to. (unstable swap, linear to N=index.length)

If you need to keep them still in the original order, first grab those indexed elements and mark their place as holes, then scan from arr[max(index)] backwards to arr[0] move the un-indexed elements to fill those holes, finally set the head elements with the indexed elements. (stable move, linear to max(index))

On Friday, 29 May 2020 at 00:32:13 UTC, mw wrote:

>
> If you don’t care the remaining elements’ order, just swap the head N elements with the index array’s pointing to. (unstable swap, linear to N=index.length)

Note: If index[i] < index.length, don’t swap that element.

On Thursday, 28 May 2020 at 23:47:50 UTC, H. S. Teoh wrote:
> Just pickin' yall's smart brains:
>
> Given an array A and a set of indices into the array, is there a fast algorithm for rearranging A in-place so that the elements at the given indices are moved to the front?
>
> E.g.: A = [ 0, 1, 2, 3, 4, 5 ], index = [ 1, 3, 5 ]
>
> The result should have 1, 3, and 5 at the front of the array (the exact
> order is unimportant).
>
> For efficiency considerations, assume the size of the index is relatively small, but the array itself may be quite large, so scanning the entire array or copying large chunks of it is undesirable.
>
>
> T

Here's a version that preserves the order of the rest of the array:

void cutToFront(T)(scope T[] queue, scope size_t[] cutterXs ...) {
    // Sort cutterXs:
    import std.algorithm : move, sort;
    sort(cutterXs);

    // Convert cutterXs into a set:
    size_t cutterCount = 0, lastCutterX = 0;
    for(size_t cutterXX = 0; cutterXX < cutterXs.length; ++cutterXX) {
        const cutterX = cutterXs[cutterXX];
        if(cutterX != lastCutterX) {
            lastCutterX = cutterX;
            cutterXs[cutterCount] = cutterX;
            ++cutterCount;
        }
    }
    cutterXs = cutterXs[0 .. cutterCount];

    if(cutterCount > 0) {
        // Validate the indices:
        if(lastCutterX >= queue.length)
            assert(0);

        // Pull the cutters out of the queue temporarily, sliding other items back as needed:
        const(size_t) lastCutterXX = cutterCount - 1;
        size_t gap = 0, oldX = lastCutterX, oldCutterX = cutterXs[lastCutterXX];
        T[] cutters = new T[cutterXs.length];
        while(true) {
            T* dest;
            if(oldX == oldCutterX) {
                dest = &(cutters[lastCutterXX - gap]);
                ++gap;
                if(gap <= lastCutterXX)
                    oldCutterX = cutterXs[lastCutterXX - gap];
            } else {
                const newX = oldX + gap;
                dest = &(queue[newX]);
            }
            move(queue[oldX], *dest);

            if(oldX <= 0)
                break;
            --oldX;
        }

        // Finally, place the cutters at the front of the line:
        for(size_t x = 0; x < cutterCount; ++x)
            move(cutters[x], queue[x]);
    }
}

Performance is O(maxElement(cutterXs) + cutterXs.length * log(cutterXs.length)). It could be made pure @safe nothrow @nogc fairly easily, except that maintaining proper attribute inference based on the attributes of implicitly called methods of T is a pain.

On Friday, 29 May 2020 at 03:29:05 UTC, tsbockman wrote:
> It could be made pure @safe nothrow @nogc fairly easily, except that maintaining proper attribute inference based on the attributes of implicitly called methods of T is a pain.

void cutToFront(T)(scope T[] queue, scope const(size_t[]) cutterXs ...) {
    import core.bitop : bsr;
    import core.memory : pureCalloc, pureFree;
    import std.algorithm : move, moveEmplace, sort;

    // Allocate scratch space:
    const(size_t) memSize = (cutterXs.length + 1) * (size_t.sizeof + T.sizeof);
    void* mem = () @trusted { return pureCalloc(memSize, 1); }();
    if(mem == null)
        assert(0, "Allocation failed - possibly out of memory?");
    scope(exit) { () @trusted {
        /* IMPORTANT: T must not throw from inside move or moveEmplace, below,
        because it's too hard to figure out which item's destructors should be called for cutters. */
        pureFree(mem);
    }(); }

    // Prepare scratch slices:
    size_t[] cutterXSet = () @trusted {
        static assert(size_t.alignof == size_t(1) << bsr(size_t.alignof));
        auto ptr = cast(size_t*) ((size_t.alignof - 1 + cast(size_t) mem) & -size_t.alignof);
        return ptr[0 .. cutterXs.length];
    }();
    T[] cutters = () @trusted {
        static assert(T.alignof == size_t(1) << bsr(T.alignof));
        auto ptr = cast(T*) ((((cutterXSet.length + 1) * size_t.sizeof) + T.alignof - 1 + cast(size_t) mem) & -T.alignof);
        return ptr[0 .. cutterXSet.length];
    }();
    assert((cutterXSet.length * typeof(cutterXSet[0]).sizeof + cast(void*) cutterXSet.ptr) < cast(void*) cutters.ptr
          && (cutters.length * typeof(cutters[0]).sizeof + cast(void*) cutters.ptr) < (memSize + mem));

    // Sort cutterXs:
    cutterXSet[] = cutterXs[];
    sort(cutterXSet);

    // Convert cutterXs into a set:
    size_t cutterCount = 0, lastCutterX = 0;
    for(size_t cutterXX = 0; cutterXX < cutterXSet.length; ++cutterXX) {
        const cutterX = cutterXSet[cutterXX];
        if(cutterX != lastCutterX) {
            lastCutterX = cutterX;
            cutterXSet[cutterCount] = cutterX;
            ++cutterCount;
        }
    }
    cutterXSet = cutterXSet[0 .. cutterCount];

    if(cutterCount > 0) {
        // Validate the indices:
        if(lastCutterX >= queue.length)
            assert(0, "Invalid cutter index.");

        // Pull the cutters out of the queue temporarily, sliding other items back as needed:
        const(size_t) lastCutterXX = cutterCount - 1;
        size_t gap = 0, oldX = lastCutterX, oldCutterX = cutterXSet[lastCutterXX];
        while(true) {
            T* dest;
            if(oldX == oldCutterX) {
                // If T makes moveEmplace!T unsafe, then the move!T call below should also be unsafe.
                () @trusted nothrow { moveEmplace(queue[oldX], cutters[lastCutterXX - gap]); }();
                ++gap;
                if(gap <= lastCutterXX)
                    oldCutterX = cutterXSet[lastCutterXX - gap];
            } else {
                const newX = oldX + gap;
                () nothrow { move(queue[oldX], queue[newX]); }();
            }

            if(oldX <= 0)
                break;
            --oldX; // Iterate backwards to avoid overwriting later entries before they have been moved elsewhere.
        }

        // Finally, place the cutters at the front of the line:
        size_t x = lastCutterXX;
        while(true) {
            () nothrow { move(cutters[x], queue[x]); }();
            if(x <= 0)
                break;
            --x; // Iterate through queue[newX] in the same direction as the loop above to avoid confusing the prefetcher.
        }
    }
}

On 5/28/20 7:47 PM, H. S. Teoh wrote:
> Just pickin' yall's smart brains:
> 
> Given an array A and a set of indices into the array, is there a fast
> algorithm for rearranging A in-place so that the elements at the given
> indices are moved to the front?
> 
> E.g.: A = [ 0, 1, 2, 3, 4, 5 ], index = [ 1, 3, 5 ]
> 
> The result should have 1, 3, and 5 at the front of the array (the exact
> order is unimportant).
> 
> For efficiency considerations, assume the size of the index is
> relatively small, but the array itself may be quite large, so scanning
> the entire array or copying large chunks of it is undesirable.

Is that the complement of https://dlang.org/library/std/algorithm/mutation/remove.html? In that case it should be adaptable from it with ease.

On Thursday, 28 May 2020 at 23:47:50 UTC, H. S. Teoh wrote:
> Just pickin' yall's smart brains:
>
> Given an array A and a set of indices into the array, is there a fast algorithm for rearranging A in-place so that the elements at the given indices are moved to the front?
>
> E.g.: A = [ 0, 1, 2, 3, 4, 5 ], index = [ 1, 3, 5 ]
>
> The result should have 1, 3, and 5 at the front of the array (the exact
> order is unimportant).
>
> For efficiency considerations, assume the size of the index is relatively small, but the array itself may be quite large, so scanning the entire array or copying large chunks of it is undesirable.
>
>
> T

I would just sort index[], to have more cache-friendly access to A[], and then swap the elements in order, e.g. pseudo-code:

foreach (i, ref i_index; index.sort)
{
  swap(A[i], A[i_index]);
  i_index = i; // if necessary; update the index in the index array
}