C перемещает части памяти на место

Ответ 1

Случай 1: Исходные перекрытия с точкой назначения не более чем в одной смежной области, которая меньше цельного массива

Подробное объяснение этого случая дается в первом ответе R.. Мне нечего добавить сюда.

Случай 2: оба источника перекрываются с пунктом назначения в двух смежных областях или мы вращаем весь массив

Самый простой подход - это всегда вращать весь массив. Это также перемещает некоторые ненужные элементы из диапазона назначения, но поскольку в этом случае K > N/2, это не делает число операций более чем в два раза по мере необходимости.

Чтобы повернуть массив, используйте алгоритм лидера цикла: возьмите первый элемент массива (A [0]) и скопируйте его в место назначения; предыдущее содержимое этой позиции снова переходит в правильное положение; продолжайте, пока какой-либо элемент не будет перемещен в исходное положение.

Продолжайте применять алгоритм лидерства цикла для следующих стартовых позиций: A [1], A [2],..., A [GCD (N, d) - 1], где d - расстояние между источником и назначения.

После шагов GCD(N,d) все элементы находятся на правильных позициях. Это работает, потому что:

• Позиции 0, 1,..., GCD (N, d) - 1 принадлежат разным циклам - потому что все эти числа различны (по модулю GCD(N,d)).
• Каждый цикл имеет длину N / GCD(N,d) - потому что d / GCD(N,d) и N / GCD(N,d) являются относительно простыми.

Этот алгоритм прост, и он перемещает каждый элемент ровно один раз. Он может быть потокобезопасным (если мы пропустим шаг записи, если не в пределах диапазона назначения). Другим многопоточным преимуществом является то, что каждый элемент может иметь только два значения - значение до "move" и значение после "move" (без временных промежуточных значений).

Но он не всегда имеет оптимальную производительность. Если element_size * GCD(N,d) сопоставимо с размером строки кеша, мы можем взять все начальные позиции GCD(N,d) и обработать их вместе. Если это значение слишком велико, мы можем разбить начальные позиции на несколько смежных сегментов, чтобы уменьшить требования к пространству обратно на O (1).

Проблема в том, что element_size * GCD(N,d) намного меньше размера строки кэша. В этом случае мы получаем много недостатков в кэше и ухудшаем производительность. Идея gusbro для временного обмена массивами с некоторой областью "swap" (размером d) предлагает более эффективный алгоритм для этого случая. Его можно оптимизировать, если мы используем область "swap", которая подходит в кеше, и скопируйте неперекрывающиеся области с помощью 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);

Ответ 2

Это еще не полный ответ, но я думаю, что это может быть правильная идея.

Начните с элемента исходного диапазона и рассмотрите позицию назначения, на которую будет отображаться. Эта позиция находится либо внутри исходного диапазона, либо вне его. Если он находится за пределами исходного диапазона, вы можете просто скопировать, и вы закончили с этим элементом. С другой стороны, если он отображается в позицию назначения внутри исходного диапазона, вы можете скопировать его, но вам нужно сохранить старое значение, которое вы переписываете, и выполнить вышеуказанный процесс итеративно с помощью этого нового элемента источника.

По существу, вы работаете с циклами перестановки.

Проблема заключается в отслеживании того, что вы закончили и что еще предстоит сделать. Не сразу видно, есть ли способ сделать это без O (n) рабочего пространства.

Ответ 3

Это решение - 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--;
  }
}

Ответ 4

** это работает только в том случае, если длина 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)

Ответ 5

ОК, если он похож на memmove, но с круговым буфером, вот как это сделать:

• Случай 1: источник /dest не перекрываются. Просто используйте memcpy, возможно разбив его по мере необходимости, где обертывает буфер.

• Случай 2: источник /dest равны. Ничего не делайте.

• Случай 3: начало источника находится строго внутри области dest. Сделайте простой цикл прямой копии, for (i=0; i<k; i++) A[(dest+i)%N] = A[(src+i)%N];

• Случай 4: начало разрушения лежит строго внутри области источника. Сделайте простой цикл обратной копии, for (i=K; i; i--) A[(dest+i-1)%N] = A[(src+i-1)%N];

Изменить: Этот ответ работает только тогда, когда K не более N/2; в противном случае возможно, что источник и dest начинаются внутри друг друга. У меня нет немедленного исправления, но может быть возможно выбрать начальное смещение и направление, которые устранят проблему...

Ответ 6

Здесь алгоритм O (n ²) довольно прост - просто поверните весь буфер на один байт, а затем повторите это столько раз, сколько хотите:

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;
    }
}

Он не будет быстрым, но он выполнит задание и с постоянным временным хранилищем.

Edit:

Если вам нужно повернуть только часть части буфера относительно статического базового "фона", как описано ниже в комментариях, вы можете сделать что-то вроде этого:

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];
        }
    }
}

Я думаю, что может возникнуть проблема, если вам нужно повернуть весь буфер, но в этом случае вы можете просто вернуться к приведенному выше коду.