Intereting Posts
Динамическое распределение 2D-массива внутри функции (с помощью указателей для возврата адреса выделенного объекта) можно определить функцию внутри структуры C? Что происходит, когда char присваивается слишком большое значение, чтобы вписать его в байты? встроенный perl в C, perlapio – совместимость с STDIO Почему компиляторы не предупреждают об индексах статического массива вне пределов? Почему я не могу напрямую назначить int int int, как это: int * p = 6 ;? Почему некоторые функции чрезвычайно длинные? (идеи, необходимые для академических исследований!) литеральная константа vs переменная в математической библиотеке Сбивающие с толку ответы: один говорит: * myptr ++ увеличивает указатель сначала, другие говорят * p ++ dereferences старое значение указателя Почему я получаю ошибки «неопределенной ссылки», даже если я включаю правильные файлы заголовков? Функция linux mkdir не может разрешать полное разрешение Обмен переменных с функцией не работает Создание таймера в C предварительно заполнить stdin в C Почему в моей программе есть бесконечный цикл?

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

Я реализую несколько структур данных, и один примитив, который я хочу использовать, следующий: у меня есть кусок памяти A [N] (он имеет переменную длину, но я принимаю 100 для моих примеров), и внутри этого fragmentа есть меньшая часть C длины K (допустим, 30), которую я хочу переместить, не используя никакой дополнительной памяти.

Дополнительной трудностью является то, что A «обертывает», то есть C может начинаться с A [80], а затем первые 20 элементов C являются элементами A [80..100], а последние 10 элементов – это элементы A [ 0..10]. Кроме того, целевой диапазон может также «обертываться» и перекрываться с C любым возможным способом. Кроме того, я не хочу использовать больше, чем постоянное количество дополнительной памяти, все должно происходить на месте. Кроме того, часть A, которая не находится ни в целевом диапазоне, ни в исходном диапазоне, может содержать что-то важное, поэтому оно также не может быть использовано. Таким образом, один случай будет следующим:

A выглядит так:

| 456789ABCDEF0123456789AB | —– | 0123 |

И должно быть преобразовано в это:

| 89AB | —– | 0123456789ABCDEF01234567 |

Просто делегировать его библиотеке или использовать другую библиотеку данных из библиотеки здесь не вариант, я хочу сам понять эту проблему. С первого взгляда я думал, что это может быть не тривиально, но как только вы различаете несколько случаев, это становится ясным, но теперь у меня серьезные проблемы. Конечно, есть тривиальные случаи, если они не перекрываются или не обертываются, но, по крайней мере, если оба происходят одновременно, это становится беспорядочным. Вы можете начать с одного свободного места и переместить часть, которая там есть, но затем вы создаете еще одну свободную часть в другом месте, и вам сложно отслеживать, какие части вы можете использовать.

Возможно, мне что-то не хватает полностью, но даже мой специальный случай, если целевой диапазон не обертывает, имеет почти 100 строк (хотя половина из них – утверждения и комментарии), и я мог бы его обновить, чтобы он также обрабатывал общий случай с некоторыми дополнительными индекс, но если у кого-то есть изящное и короткое решение, я был бы признателен за помощь. Интуитивно я считаю, что это должно быть каким-то тривиальным, но я пока не вижу лучшего решения.

Примечание. Интересный случай, конечно, если C почти такой же большой, как A. Если | C | <N / 2, это тривиально.

edit: использование большего количества дополнительных флагов / индексов считается дополнительной памятью, и я хочу избежать этого, если это возможно.

Некоторые люди хотели увидеть мой код. Мой вопрос довольно абстрактен, поэтому я не хотел его публиковать, но, возможно, кто-то видит, как его улучшить. Это ужасно, он работает только в том случае, если цель начинается с самого начала (однако это легко может быть изменено) и ужасно долго, но это делает работу без дополнительной памяти в 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: Исходные перекрытия с местом назначения не более чем в одном смежном регионе, который меньше целого массива

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

Случай 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) взаимно просты.

Этот алгоритм прост, и он перемещает каждый элемент ровно один раз. Он может быть streamобезопасным (если мы пропустим шаг записи, если не в пределах диапазона назначения). Другим многопоточным преимуществом является то, что каждый элемент может иметь только два значения – значение до «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); 

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

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

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

Проблема заключается в отслеживании того, что вы закончили и что еще предстоит сделать. Это не сразу видно, если есть способ сделать это без 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: источник / dest не перекрываются. Просто используйте memcpy , возможно, разбив его по мере необходимости, когда буфер обернется.

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

  • Случай 3: начало источника находится строго внутри области dest. Сделайте простой цикл прямой копии for (i=0; i

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

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

Вот алгоритм 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]; } } } 

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