C 将内存部件移动到位

Question

我正在实现几个数据结构，我想使用的一个原语如下:我有一个内存块 A[N](它的长度是可变的，但我的例子是 100)，在这个 block 内，有我想在不使用任何额外内存的情况下移动长度为 K(假设为 30)的较小部分 C。

额外的困难是，A“换行”，即 C 可以从 A[80] 开始，然后 C 的前 20 个元素是元素 A[80..100]，最后 10 个元素是元素 A[0..10]。此外，目标范围也可以以任何可能的方式与C“环绕”和重叠。此外，我不想使用超过恒定数量的额外内存，一切都应该发生。此外，A 中既不在目标范围内也不在源范围内的部分可能包含一些重要的东西，因此也不能使用它。所以一种情况如下:

A 看起来像这样:

|456789ABCDEF0123456789AB|-----|0123|

而且应该改成这样:

|89AB|-----|0123456789ABCDEF01234567|

只是将它委托(delegate)给一个库或使用库中的另一个数据结构不是一个选择，我想自己理解这个问题。乍一看，我认为这可能不是一件小事，但只要你区分几个案例，就清楚了，但现在我遇到了严重的麻烦。当然，如果它们不重叠或不换行，也有一些微不足道的情况，但至少如果两者同时发生，它就会变得困惑。您可以从一个空闲位置开始并移动属于该位置的部分，但随后您在其他位置创建另一个空闲部分，并且很难跟踪您仍然可以使用哪些部分。

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

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

编辑:使用超过恒定数量的额外标志/索引算作额外内存，如果可能，我想避免这种情况。

编辑:有些人想看我的代码。我的问题相当抽象，所以我不想发布它，但也许有人看到如何改进它。太糟糕了，它只适用于目标从头开始(但是可以轻松更改)并且非常长的情况，但是它在 O(n) 中没有额外内存的情况下完成了这项工作。

#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

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 || (N - begin) + (end - part_start) == size);
    // size is valid (non 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 < end) {
      // ##|1234|# -> 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 <= begin_size) {
    // 56|#|1234 -> 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 <= begin_size) {
    // 45|##|123 -> 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;
}

Answer 1

案例1:源与目标最多在单个连续区域内重叠，小于整个数组

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)是相对质数。

---

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

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

问题是当element_size * GCD(N,d)远小于缓存行大小。在这种情况下，我们会遇到很多缓存未命中并且性能下降。 gusbro 用一些“交换”区域(大小为 d)临时交换数组片段的想法为这种情况提出了更有效的算法。如果我们使用适合缓存的“交换”区域，并使用 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);