precio - tag uhf
C mueve las partes de la memoria a su lugar (6)
Caso 1: la fuente se solapa con el destino como máximo en una sola región contigua, que es más pequeña que toda la matriz
La explicación detallada de este caso se encuentra en la primera respuesta de R .. No tengo nada que agregar aquí.
Caso 2: O bien la fuente se superpone con el destino en dos regiones contiguas o rotamos la matriz completa
El enfoque más sencillo sería siempre rotar todo el conjunto. Esto también mueve algunos elementos innecesarios del rango de destino, pero como en este caso K > N/2 , esto no hace que el número de operaciones sea más del doble de lo necesario.
Para rotar la matriz, use el algoritmo de ciclo líder: tome el primer elemento de la matriz (A [0]) y cópielo a la posición de destino; El contenido anterior de esta posición se mueve nuevamente a su posición correcta; continuar hasta que algún elemento se mueva a la posición inicial.
Continúe aplicando el algoritmo de líder de ciclo para las siguientes posiciones de inicio: A [1], A [2], ..., A [GCD (N, d) - 1], donde d es la distancia entre la fuente y el destino.
Después de los pasos de GCD(N,d) , todos los elementos están en sus posiciones correctas. Esto funciona porque:
- Las posiciones 0, 1, ..., GCD (N, d) - 1 pertenecen a ciclos diferentes, porque todos estos números son diferentes (módulo
GCD(N,d)). - Cada ciclo tiene una longitud
N / GCD(N,d), porqued / GCD(N,d)yN / GCD(N,d)son primos relativos.
Este algoritmo es simple y mueve cada elemento exactamente una vez. Puede ser seguro para subprocesos (si omitimos el paso de escritura a menos que esté dentro del rango de destino). Otra ventaja relacionada con los múltiples subprocesos es que cada elemento puede tener solo dos valores: el valor antes de "mover" y el valor después de "mover" (no es posible ningún valor intermedio temporal).
Pero no siempre tiene un rendimiento óptimo. Si element_size * GCD(N,d) es comparable al tamaño de línea del caché, podríamos tomar todas las posiciones iniciales de GCD(N,d) y procesarlos juntos. Si este valor es demasiado grande, podemos dividir las posiciones de inicio en varios segmentos contiguos para reducir los requisitos de espacio a O (1).
El problema es cuando element_size * GCD(N,d) es mucho más pequeño que el tamaño de línea del caché. En este caso obtenemos una gran cantidad de errores de caché y degrada el rendimiento. La idea de gusbro de intercambiar temporalmente las piezas del arreglo con alguna región de "intercambio" (de tamaño d ) sugiere un algoritmo más eficiente para este caso. Se puede optimizar más si usamos la región de "intercambio", que cabe en el caché, y copiamos las áreas no superpuestas con memcpy.
Un algoritmo más. No sobrescribe los elementos que no están en el rango de destino. Y es caché amigable. La única desventaja es: mueve cada elemento exactamente dos veces.
La idea es mover dos punteros en direcciones opuestas e intercambiar elementos puntiagudos. No hay ningún problema con las regiones superpuestas porque las regiones superpuestas simplemente se invierten. Después del primer paso de este algoritmo, todos los elementos de origen se han movido al rango de destino, pero en orden inverso. Así que la segunda pasada debería revertir el rango de destino:
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);
Estoy implementando varias estructuras de datos y una primitiva que quiero usar es la siguiente: Tengo un fragmento de memoria A [N] (tiene una longitud variable, pero tomo 100 para mis ejemplos) y dentro de este fragmento, hay una parte más pequeña C de longitud K (digamos 30) que quiero mover sin usar memoria adicional.
La dificultad adicional es que A "envuelve", es decir, C puede comenzar en A [80] y luego los primeros 20 elementos de C son los elementos A [80..100] y los últimos 10 elementos son los elementos A [ 0..10]. Además, el rango objetivo también puede "ajustarse" y superponerse con C de cualquier forma posible. Además, no quiero usar más que una cantidad constante de memoria adicional, todo debería suceder en su lugar. Además, la parte de A que no está en el rango objetivo ni en el rango de origen puede contener algo importante, por lo que tampoco se puede usar. Así que un caso sería el siguiente:
A se ve así:
| 456789ABCDEF0123456789AB | ----- | 0123 |
Y debe ser transformado a esto:
| 89AB | ----- | 0123456789ABCDEF01234567 |
Simplemente delegarlo en una biblioteca o usar otra estructura de datos de una biblioteca no es una opción aquí, quiero entender el problema por mí mismo. A primera vista, pensé que podría no ser trivial, pero tan pronto como distingue algunos casos, queda claro, pero ahora estoy teniendo serios problemas. Por supuesto, hay casos triviales si no se superponen o no se ajustan, pero al menos si ambos suceden al mismo tiempo, se complica. Podría comenzar con un lugar libre y mover la parte que pertenece a ese lugar, pero luego crea otra parte libre en otro lugar y es difícil hacer un seguimiento de las partes que aún puede usar.
Tal vez me esté perdiendo algo por completo, pero incluso mi caso especial si el rango de destino no se ajusta tiene casi 100 líneas (aunque la mitad son afirmaciones y comentarios) y podría actualizarlo para que también maneje el caso general con algunos detalles adicionales. Cálculos de índice, pero si alguien tiene una solución elegante y corta, agradecería alguna ayuda. Intuitivamente, creo que esto debería ser algo trivial, pero aún no veo la mejor solución.
Nota: El caso interesante es, por supuesto, si C es casi tan grande como A. Si | C | <N / 2, es trivial.
edición: el uso de más de una cantidad constante de marcas / índices adicionales cuenta como memoria adicional y quiero evitar eso si es posible.
Edición: Algunas personas querían ver mi código. Mi pregunta es bastante abstracta, así que no quise publicarla, pero tal vez alguien vea cómo mejorarla. Es terrible, solo funciona en el caso de que el objetivo comience desde el principio (sin embargo, se puede cambiar fácilmente) y es terriblemente largo, pero hace el trabajo sin memoria adicional en 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;
}
** Esto solo funciona si la longitud de C es <= la mitad de la longitud de A. Pero lo dejo aquí con la esperanza de arreglarlo. **
** Esta solución no conservará ninguno de los contenidos del rango objetivo, un comportamiento que creo que coincide con la redacción de la pregunta original **
;; 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)
Aquí hay un algoritmo O (n 2 ) que es bastante sencillo: simplemente rote todo el búfer un solo byte y luego repítalo tantas veces como desee:
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;
}
}
No será rápido, pero se hará el trabajo y solo con almacenamiento temporal constante.
Editar:
Si necesita rotar solo una parte parcial del búfer en relación con un ''fondo'' estático subyacente, como se explica a continuación en los comentarios, puede hacer algo como esto:
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];
}
}
}
Creo que podría tener un problema si necesita rotar todo el búfer, pero en ese caso podría simplemente recurrir al código anterior.
De acuerdo, si es como memmove pero con un buffer circular, esta es la manera de hacerlo:
Caso 1: fuente / destino no se superponen. Solo use
memcpy, posiblementememcpysegún sea necesario donde se envuelve el búfer.Caso 2: fuente / destino son iguales. Hacer nada.
Caso 3: el inicio de la fuente se encuentra estrictamente dentro de la región de destino. Haga un simple bucle de copia hacia adelante,
for (i=0; i<k; i++) A[(dest+i)%N] = A[(src+i)%N];Caso 4: el inicio del destino se encuentra estrictamente dentro de la región de origen. Haga un simple bucle de copia hacia atrás,
for (i=K; i; i--) A[(dest+i-1)%N] = A[(src+i-1)%N];
Edición: esta respuesta solo funciona cuando K es a lo sumo N / 2; De lo contrario, es posible que la fuente y el destino empiecen uno dentro del otro. No tengo una solución inmediata, pero puede ser posible elegir un desplazamiento inicial y una dirección que solucione el problema ...
Esta no es una respuesta completa todavía, pero creo que puede ser la idea correcta.
Comience con un elemento del rango de origen y considere la posición de destino a la que se asignará. Esa posición está dentro del rango fuente o fuera de él. Si está fuera del rango de origen, solo puede copiar, y ya ha terminado con ese elemento. Por otro lado, si se asigna a una posición de destino dentro del rango de origen, puede copiarlo, pero debe guardar el valor anterior que está sobrescribiendo y realizar el proceso anterior de forma iterativa con este nuevo elemento de la fuente.
Esencialmente, estás operando en los ciclos de una permutación.
El problema es hacer un seguimiento de lo que ha terminado y lo que queda por hacer. No es evidente de inmediato si hay una manera de hacerlo sin O (n) espacio de trabajo.
Esta solución es O (N) y utiliza las ubicaciones de origen ya procesadas como espacio para usar cuando los rangos se superponen. Intercambiará los contenidos de origen y destino hasta el punto en que alcance el inicio del destino, luego procederá a copiar desde el espacio de scratch generado anteriormente. El segundo bucle restaura la región obstruida después de usar cada carácter del espacio de borrador.
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--;
}
}