editar:
así que claramente no lo expliqué bien, así que déjenme intentarlo nuevamente con ejemplos. Tengo una 'tubería' de un tamaño determinado con señales enrutadas a través de ella en desplazamientos determinados. La tubería puede fragmentarse con señales en diferentes desplazamientos, lo que hace imposible ajustar una nueva señal. Quiero un algoritmo que me diga cómo organizar las señales para desfragmentar la tubería; ¡pero con un número mínimo de señales que realmente se mueven! Entonces, para el ejemplo ...
Digamos que tengo una tubería de tamaño 16. Tiene las siguientes señales con los tamaños y las compensaciones descritas.
offset 0: A (size of 4; fills slots 0-3)
offset 5: C (size of 2, fills slot 5-6)
offset 8: B (size of 4, fills 8-11)
offset 14: D (size 2, fills 14-15)
Pipe: AAAA_CC_BBBB__DD
En este caso, tengo 1 ranura abierta en los desplazamientos 4 y 7, y dos en el desplazamiento 12-13. Ahora digamos que quiero agregar una señal de tamaño 4 a esta tubería. No hay espacio continuo para ello ahora, pero sé que tengo suficiente espacio si lo desfragmento. La solución 'obvia' es agrupar todas las señales en la 'parte superior' de esta manera:
offset 0: A (size 4, fills 0-3)
offset 4: B (size 4, fills 4-7)
offset 8: C (size 2, fills 8-9)
offset 10: D (size 2, fills 10-11)
Pipe: AAAABBBBCCDD____
Esto deja las ranuras 12-15 libres para mi nueva señal. Sin embargo, para hacer esto, reposicioné 3 señales (BD). Para cada señal que moví, tengo que enviar comandos al hardware y esperar una cantidad de tiempo no trivial.
Si fuera más inteligente podría darme cuenta de que hay otro enfoque. Podría reposicionar así:
offset 0: A(size 4, fills 0-3)
offset 8: B(size 4, fills 8-11)
offset 12: C(size 2, fills 12-13)
offset 14: D(size 2, fills 14-15).
Pipe: AAAA____BBBBCCDD
Ahora puedo ajustar mi nueva señal en desplazamientos 4-7; Y solo tuve que reposicionar una señal (B). Ahorrando así en llamadas de hardware.
Me pregunto si hay un buen algoritmo para detectar situaciones como esta; donde puedo 'encajar' una señal en una tubería con el mínimo número de señales movidas. El problema que me viene a la mente es una N! algoritmo; que básicamente equivale a "generar todas las distribuciones posibles, calcular cuántos movimientos resultó". Estoy buscando un acercamiento más rápido.
La aproximación no tiene que ser 100% perfecta, estoy buscando principalmente minimizar el caso promedio, siempre que el peor de los casos no sea demasiado horrendo. Sé que nunca tendré más de 255 señales en una tubería determinada; ¡así que puedo 'escaparme' con N! tan malo como suena También sé que el tamaño de cada señal es una potencia de 2, al igual que el tamaño de la tubería.
Además, ¿existen algoritmos brillantes para la colocación de señales que minimicen la fragmentación?
Pregunta contestada; vea abajo.
Quería ampliar un poco la respuesta para explicar mejor cómo ocurriría la desfragmentación para cualquiera que lea; amigo lo explica. Quería señalar un enfoque más simple para conceptualizar y explicar la parte de defraudación con más detalle ya que esa era la pregunta original.
Estoy explicando mi enfoque, que es un enfoque ligeramente diferente / más simple pero que efectivamente mantiene el concepto de "amigo". No estoy precalculando bloques o etiquetándolos, esto es demasiado esfuerzo para implementar y mantener. Para mí, el costo de la CPU de calcular a dónde irá una señal es bastante trivial en comparación con la colocación / eliminación real de señales; así que puedo permitirme perder una pequeña cantidad lineal de CPU al no precomputar para simplificar mi lógica. Entonces el proceso es:
para la inserción:
Todas las señales se mantienen en límites de señal iguales al tamaño de la señal, por lo que una señal comenzará en desplazamiento donde offest% senaliza = 0. Para el desplazamiento real, recorremos y calculamos los intervalos que mantienen esta frontera. Entonces, si mi señal es de tamaño 4 en una tubería de tamaño 16, miraré los intervalos 0-4, 5-7, 8-11, 12-15.
Para cada intervalo, verifique si todo el espacio en ese intervalo es libre. En el caso simple, tenemos un intervalo sin señales y simplemente colocamos la señal en ese intervalo. Importante, miramos los intervalos en orden y colocamos nuestra señal en el primer intervalo libre , esto asegura que rompamos el 'bloque' más pequeño posible (usando términos de amigos) cuando agregamos nuestra señal. Esto debería ser equivalente al enfoque de amigo descrito por im3l96; excepto sin precomputación de bloques.
Si ningún intervalo es completamente libre, tenemos que desfragmentar. Para esto, encontramos la señal con las ranuras más no utilizadas. Si los intervalos múltiples tienen el mismo número de ranuras sin usar, seleccione el primer intervalo. Luego encontramos la señal más grande en este intervalo y recurrimos recursivamente al mismo algoritmo de inserción para la señal más pequeña (excepto marcar el intervalo que seleccionamos para insertar nuestra primera señal como no disponible de alguna manera). Esto mueve la señal a otro lugar que encajará. Luego encontramos la siguiente señal más pequeña en nuestro intervalo seleccionado y hacemos lo mismo hasta que hayamos movido todas las señales. El peor caso de 2 ^ n-1 señales movidas; donde N es el número de tamaños de señal potenciales <= nuestra señal (suponiendo que las señales son múltiples de 2, entonces N = log2 (signalSize)).
Aquí hay un ejemplo. * representa un espacio marcado como no disponible cuando llamamos recursivamente a este método (es decir, el intervalo en el que el método de llamada quería colocar su señal, y por lo tanto no quiere que la llamada recursiva intente colocar una señal)
Aquí hay un caso simple y simple que se me ocurrió que aún demuestra una complejidad completa. Nota: la siguiente estructura sería difícil de crear, pero podría resultar de la aproximación de amigos si alguien lo intentara muy, muy duro.
FFFFFFFF__AA_B__EEEE_HGGCC_DII_J
Alguien pasa una señal Z de tamaño 8
seleccionamos offset 8:
defragInsert (z, tamaño 8)
effective structure: FFFFFFFF__AA_B__EEEE_HGGCC_DII_J
placing signal in interval: __AA_B__
defragInput (A, tamaño 2)
effective structure: FFFFFFFF********EEEE_HGGCC_DII_J
place signal in interval (offset 20) _H
defragInput (H, size1)
effective structure: FFFFFFFF********EEEE**GGCC_DII_J
place signal between C & D
return defragInput (H, size1)
effective structure: FFFFFFFF********EEEE__GGCCHDII_J
place H at offset 20 now that it's open
return defragInput (A, tamaño 2)
estructura efectiva: FFFFFFFF_ _ _B__EEEEAAGGCCHDII_J mover B ahora ...
defragInput (B, size1)
estructura efectiva: FFFFFFFF * ** * EEEEAAGGCCHDII_J lugar B entre I y J
return defragInput (B, size1)
estructura efectiva: FFFFFFFF_ __ _EEEEAAGGCCHDIIBJ add B
return defragInsert (z, tamaño 8)
fianl structure: FFFFFFFFzzzzzzzzEEEEAAGGCCHDIIBJ
fuente
Respuestas:
El problema es similar a la asignación de memoria, por lo que mi solución propuesta es utilizar http://en.wikipedia.org/wiki/Buddy_memory_allocation . El uso del asignador de amigos minimiza la fragmentación en primer lugar al elegir el espacio libre contiguo más pequeño en la tubería para una señal.
Usando el ejemplo, así es como se asignará el espacio para la tubería de tamaño 8:
Liberar espacio es una cuestión de verificar el "amigo" del espacio que se libera; Si Buddy también es libre, entonces pueden fusionarse para formar un espacio contiguo más grande. Entonces, si el espacio se libera en el orden de las señales que entran, entonces se verá así:
También es bastante simple y rápido porque solo hay poca fragmentación, especialmente porque el tamaño de las señales es potencia de 2.
Si realmente es necesario, la desfragmentación / compactación también se puede hacer fácilmente, solo es cuestión de encontrar bloques asignados del mismo tamaño con amigos libres y fusionarlos (mover un bloque asignado creará un bloque libre más grande).
fuente
Bueno, antes de buscar una respuesta, primero debe definir claramente lo que desea minimizar, es decir, qué tipo de reposicionamiento de señal está permitido.
tomar una (y solo una) señal de la tubería y agregarla en otro lugar sin solapamientos (y repetir ese paso n veces)?
o para tomar n señales simultáneamente de su tubo y volver a insertarlas luego sin superposiciones (contadas como n movimientos)?
Obviamente, esta primera alternativa es mucho más restringida, ofreciéndole un espacio de búsqueda mucho más pequeño. Por ejemplo, para pasar de
AAAA_CC_BBBB__DDaAAAA_CC___DDBBBB, se necesitarán al menos 4 movimientos si no se permiten reposicionamientos simultáneos, y 2 movimientos si se permiten.Supongo que tiene el primer problema en mente (por favor confirme eso), así que aquí está mi sugerencia para esto:
haga de esto un problema de búsqueda de gráficos. Para una tubería de entrega, cada configuración de señal define un vértice de su gráfico, y los bordes entre esos vértices son los posibles reposicionamientos.
asigne un valor a cada vértice: la longitud de la secuencia de ranura continua más larga
Ahora debería ser fácil usar una técnica de búsqueda de gráficos estándar como la búsqueda de amplitud primero o la búsqueda A * para encontrar el número más pequeño de pasos hasta llegar a una configuración de tubería que tenga suficiente espacio para la nueva señal que desea agregar.
fuente
Debe tomar una muestra representativa de sus datos reales y simular diferentes algoritmos de reempaque. Por el momento, no tengo suficiente información para simular el sistema, por lo que no pude comprobar cómo funcionaba ningún algoritmo.
fuente