digitalmars.D - Algorithm question: in-place multi-bringToFront?
- H. S. Teoh (13/13) May 28 2020 Just pickin' yall's smart brains:
- mw (9/21) May 28 2020 If you don’t care the remaining elements’ order, just swap the
- mw (2/5) May 28 2020 Note: If index[i] < index.length, don’t swap that element.
- tsbockman (55/68) May 28 2020 Here's a version that preserves the order of the rest of the
- tsbockman (91/94) May 28 2020 void cutToFront(T)(scope T[] queue, scope const(size_t[])
- Andrei Alexandrescu (4/18) May 29 2020 Is that the complement of
- wjoe (9/22) May 29 2020 I would just sort index[], to have more cache-friendly access to
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 2020
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 2020
mw <mingwu gmail.com> 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 2020
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. THere'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 2020
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 2020
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 2020
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. TI 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 2020