C将内存部件移动到位

我正在实现几个数据结构和一个我要使用的原语如下:我有一个内存块A [N](它有一个可变长度,但我的示例为100)并且在这个块中,有一个较小的部分长度为K的C(比方说30)我想要移动而不使用任何额外的内存。

另外的困难是,A“包裹”,即C可以从A [80]开始,然后C的前20个元素是元素A [80..100],最后10个元素是元素A [ 0..10]。 此外,目标范围还可以以任何可能的方式“包裹”并与C重叠。 另外,我不想使用超过一定数量的额外内存,一切都应该到位。 此外,既不在目标范围内也不在源范围内的A部分可能包含重要的内容,因此也不能使用。 所以一个案例如下:

A看起来像这样:

| 456789ABCDEF0123456789AB | —– | 0123 |

应该转变为:

| 89AB | —– | 0123456789ABCDEF01234567 |

只是将它委托给一个库或者从库中使用另一个数据结构不是一个选项,我想自己理解这个问题。 在第一眼看来,我认为这可能不是微不足道的,但是一旦你区分了几个案例,它就会变得清晰,但现在我遇到了严重的麻烦。 当然,如果它们不重叠或不包装,则存在微不足道的情况,但至少如果两者同时发生,则会变得混乱。 你可以从一个自由的地方开始并移动属于那里的部分,然后你在其他地方创建另一个免费部分,很难跟踪你可以使用哪些部分。

也许我完全错过了一些东西,但即使我的特殊情况,如果目标范围没有包装也有近100行(虽然它的一半是断言和注释)我可以更新它以便它也处理一般情况下一些额外的索引计算,但如果有人有一个优雅而简短的解决方案,我将不胜感激。 直觉上我认为这应该是微不足道的,但我还没有看到最好的解决方案。

注意:有趣的情况当然是,如果C几乎和A一样大。如果| C | <N / 2,这是微不足道的。

编辑:使用超过一定量的额外标志/索引计数作为额外的内存,我想尽可能避免这种情况。

编辑:有些人想看我的代码。 我的问题相当抽象,所以我不想发布它,但也许有人看到了如何改进它。 这很糟糕,它只适用于目标从头开始(但是,可以很容易地改变)并且非常长的情况,但它可以在O(n)中没有额外的内存。

#include  #include  #include  #include  void move_part(int* A, size_t N, size_t target, size_t source, size_t size, int show_steps) { assert(source + size <= N); assert(target + size <= N); if (show_steps) { printf("Moving size %d from %d to %d.\n", size, source, target); } memmove(A + target, A + source, size * sizeof(int)); } void swap_parts(int* A, size_t N, size_t first_begin, size_t second_begin, size_t size, int show_steps) { if (show_steps) { printf("Swapping size %d at %d and %d.\n", size, first_begin, second_begin); } assert(first_begin + size <= N); assert(second_begin + size <= N); size_t i; for (i = 0; i < size; ++i) { int x = A[first_begin + i]; A[first_begin + i] = A[second_begin + i]; A[second_begin + i] = x; } } void move_to_beginning(int* A, size_t N, size_t begin, size_t size, int show_steps) { assert(begin <= N); assert(size <= N); // Denotes the start of our "working range". Increases during // the algorithm and becomes N size_t part_start = 0; // Note: Keeping the size is crucial since begin == end could // mean that the range is empty or full. size_t end = (begin + size) % N; while (part_start != N) { size_t i; if (show_steps) { for (i = 0; i < N; ++i) { printf("%d ", A[i]); } printf("\n"); printf("part_start %d begin %d end %d size %d\n", part_start, begin, end, size); } // loop invariants assert(part_start < N); // The two pointers are in our range assert(part_start <= begin && begin <= N); assert(part_start <= end && end <= N); // size is valid (wrapped case, non-empty, non-full case) assert(begin = end || end - begin == size); // size is valid (working range is full or empty case) assert(begin != end || size == 0 || part_start + size == N); if (size == 0 || begin == N || begin == part_start) { // ##|1234|# -> 1234### || if (show_steps) { printf("Case 1:\nTerminating\n"); } // #||# -> ## || // 12|##| -> 12## || // |12|## -> 12## || break; /* Not necessary any more, but would be the correct transformation: part_start = N; begin = N; end = N; size = 0;*/ } else if (end == part_start) { // |##|123 -> ##|123| if (show_steps) { printf("Case 2:\n"); printf("Setting end to %d.\n", N); } end = N; } else if (begin  1234### || if (show_steps) { printf("Case 3:\n"); } move_part(A, N, part_start, begin, size, show_steps); break; /* Not necessary any more, but would be the correct transformation: part_start = N; begin = N; end = N; size = 0;*/ } else { size_t end_size = end - part_start; size_t begin_size = N - begin; assert(begin_size + end_size == size); if (end_size >= begin_size) { // 345|#|12 -> 12 5|#|34 if (show_steps) { printf("Case 4:\n"); } swap_parts(A, N, part_start, begin, begin_size, show_steps); assert(begin_size > 0); // Necessary for progress part_start += begin_size; size = end_size; // begin, end remain unchanged } else if (begin - part_start  123 56|#|4 size_t size_moved = begin - part_start; assert(size_moved >= end_size); // else the next step would be more efficient if (show_steps) { printf("Case 5\n"); } swap_parts(A, N, part_start, begin, end_size, show_steps); move_part(A, N, end, begin + end_size, begin - end, show_steps); assert(end_size + (begin - end) == size_moved); size -= size_moved; part_start = begin; begin += size_moved; end += size_moved; } else if (end_size  123 #|45|# if (show_steps) { printf("Case 6\n"); } swap_parts(A, N, part_start, begin, end_size, show_steps); move_part(A, N, end, begin + end_size, begin_size - end_size, show_steps); part_start += begin_size; size = end_size; end = begin + end_size; // begin remains unchanged } else { // No case applies, this should never happen assert(0); } } } } int main() { int N = 20; int A[20]; size_t size = 17; size_t begin = 15; size_t i; for (i = 0; i < size; ++i) { A[(begin + i) % N] = i; } move_to_beginning(A, N, begin, size, 0); for (i = 0; i < size; ++i) { printf("%d ", A[i]); } printf("\n"); return 0; } 

情况1:源在一个连续区域中最多与目标重叠,该区域小于整个arrays

这个案例的详细解释在R的第一个答案中给出。我在这里没有任何补充。

情况2:两个源在两个连续区域中与目标重叠,或者我们旋转整个数组

最简单的方法是始终旋转整个数组。 这也会从目标范围移动一些不需要的元素,但由于在这种情况下K > N/2 ,这不会使操作次数超过必要的两倍。

要旋转数组,请使用循环引导算法:获取数组的第一个元素(A [0])并将其复制到目标位置; 此位置的先前内容再次移至其正确位置; 继续,直到某个元素移动到起始位置。

继续对下一个起始位置应用循环前导算法:A [1],A [2],…,A [GCD(N,d) – 1],其中d是源和目标之间的距离。

GCD(N,d)步骤之后,所有元素都处于其正确的位置。 这是因为:

  1. 位置0,1,…,GCD(N,d)-1属于不同的周期 – 因为所有这些数字都不同(模GCD(N,d) )。
  2. 每个周期具有长度N / GCD(N,d) – 因为d / GCD(N,d)N / GCD(N,d)是相对质数。

这个算法很简单,它只移动每个元素一次。 它可以是线程安全的(如果我们跳过写入步骤,除非在目标范围内)。 其他与multithreading相关的优点是每个元素可能只有两个值 – “移动”之前的值和“移动”之后的值(不可能存在临时中间值)。

但它并不总是具有最佳性能。 如果element_size * GCD(N,d)与高速缓存行大小相当,我们可以采用所有GCD(N,d)起始位置并将它们一起处理。 如果此值太大,我们可以将起始位置拆分为几个连续的段,以将空间要求降低到O(1)。

问题是element_size * GCD(N,d)远小于缓存行大小。 在这种情况下,我们会遇到大量缓存未命中和性能下降。 gusbro想要暂时交换具有一些“交换”区域(大小为d )的arrays片段,这表明这种情况下的算法效率更高。 如果我们使用适合缓存的“交换”区域,并使用memcpy复制非重叠区域,则可以对其进行更优化。


还有一种算法。 它不会覆盖不在目标范围内的元素。 它是缓存友好的。 唯一的缺点是:它将每个元素移动两次。

我们的想法是在相反的方向移动两个指针并交换尖头元素。 重叠区域没有问题,因为重叠区域正好相反。 在第一次通过此算法后,我们将所有源元素移动到目标范围,但顺序相反。 所以第二遍应该反转目的地范围:

 for (d = dst_start, s = src_end - 1; d != dst_end; d = (d + 1) % N, s = (s + N - 1) % N) swap(s, d); for (d = dst_start, s = dst_end - 1; d != dst_end; d = (d + 1) % N, s = (s + N - 1) % N) swap(s, d); 

这还不是一个完整的答案,但我认为这可能是正确的想法。

从源范围的元素开始,并考虑它将映射到的目标位置。 该位置位于源范围内或外部。 如果它在源范围之外,您可以复制,并且您已完成该元素。 另一方面,如果它映射到源范围内的目标位置,则可以复制它,但是必须保存要覆盖的旧值,并使用源的新元素迭代地执行上述过程。

从本质上讲,你是在一个排列的循环上运作。

问题在于跟踪你已经完成的工作以及还有待完成的工作。 没有O(n)工作空间,如果有办法做到这一点并不是很明显。

此解决方案为O(N),并使用已处理的源位置作为临时空间,以便在范围重叠时使用。 它会将源和目标的内容交换到目的地开始时的点,然后它将从之前生成的临时空间开始复制。 第二个循环在使用临时空间的每个字符之后恢复被破坏的区域。

 move(A,N, src_idx, dst_idx, len) { first_dst_idx=dst_idx; first_src_idx=src_idx; mlen=0; while(src_idx != first_dst_idx && len > 0) { temp = A[dst_idx]; A[dst_idx] = A[src_idx]; A[src_idx] = temp; src_idx=(src_idx+1) mod N; dst_idx=(dst_idx+1) mod N; len--; mlen++; } src_idx = first_src_idx; while(len > 0) { A[dst_idx] = A[src_idx]; A[src_idx] = A[first_dst_idx]; src_idx=(src_idx+1) mod N; dst_idx=(dst_idx+1) mod N; first_dst_idx=(first_dst_idx+1) mod N; len--; } while(mlen > 0) { // restore reamining scratch space A[src_idx] = A[first_dst_idx]; src_idx=(src_idx+1) mod N; first_dst_idx=(first_dst_idx+1) mod N; mlen--; } } 

**这只有在C的长度<= A长度的一半时才有效。但是我把它留在这里是为了修复它。**

**此解决方案不会保留目标范围的任何内容,我认为这种行为符合原始问题的措辞**

 ;; A function that wraps an out-of-bounds index to its proper location. mod'(i): return (i + length(A)) mod length(A) ;; shifts the range A[i]..A[i + n] to A[i - delta]..A[i - delta + n] move_backward (i,delta,n): A[mod'(i - delta)] = A[mod'(i)] if (n > 0): move_backward (i + 1, delta, n - 1) ;; shifts the range A[i - n]..A[i] to A[i - n + delta]..A[i + delta] move_forward (i, delta, n): A[mod'(i + delta)] = A[mod'(i)] if (n > 0): move_forward (i - 1, delta, n - 1) shift_range (source_first, source_last, target_first): n = mod'(source_last - source_first) delta = mod'(target_first - source_first) if (delta > length(A) / 2): move_backward (source_first, length(A) - delta, n) else move_forward (source_last, delta, n) 

好吧,如果它像memmove但是有一个循环缓冲区,这就是这样做的方法:

  • 情况1:source / dest不重叠。 只需使用memcpy ,可能需要在缓冲区包装时将其分解。

  • 案例2:source / dest相等。 没做什么。

  • 情况3:源的开始严格位于dest区域内。 做一个简单的正向复制循环, for (i=0; i

  • 案例4:dest的开始严格位于源区域内。 做一个简单的反向复制循环, for (i=K; i; i--) A[(dest+i-1)%N] = A[(src+i-1)%N];

编辑:此答案仅在K最多为N / 2时有效; 否则,源和目标都可能在彼此内部开始。 我没有立即修复,但可以选择一个起始偏移和方向来解决问题...

这里的O(n 2 )算法非常简单 – 只需将整个缓冲区旋转一个字节,然后重复多次,就像你想要的那样:

 void rotateBuffer(char *buffer, int size, int steps) { char tmp; int i; for (i = 0; i < steps; i++) { tmp = buffer[size - 1]; memmove(buffer + 1, buffer, size - 1); buffer[0] = tmp; } } 

它不会很快,但它可以完成工作,只需要不断的临时存储。

编辑:

如果您需要相对于静态底层“背景”仅旋转缓冲区的子部分,如下面评论中所述,您可以执行以下操作:

 void rotateBuffer(int count, int start, int length) { int i; int j; int index; // rotate 'count' bytes for (i = 0; i < count; i++) { // rotate by a single byte for (j = length - 1; j >= 0; j--) { index = start + i + j; buf[(index + 1) % SIZE] = buf[index % SIZE]; } } } 

我认为如果你需要旋转整个缓冲区可能有问题,但在这种情况下你可以回到上面的代码。