C将内存部件移动到位

Question

我正在实现几个数据结构和一个我要使用的原语如下:我有一个内存块A [N](它有一个可变长度,但我的示例需要100)并且在这个块中,有一个较小的部分C长度为K(比方说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 <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);