www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Algorithm question: in-place multi-bringToFront?

reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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.
May 28
next sibling parent reply mw <mingwu gmail.com> writes:
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))
May 28
parent mw <mingwu gmail.com> writes:
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.
May 28
prev sibling next sibling parent reply tsbockman <thomas.bockman gmail.com> writes:
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.
May 28
parent tsbockman <thomas.bockman gmail.com> writes:
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. } } }
May 28
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.
May 29
prev sibling parent wjoe <invalid example.com> writes:
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 }
May 29