¿Inventar factores para un algoritmo ponderado?

Question

Estoy tratando de encontrar un algoritmo ponderado para una aplicación. En la aplicación, hay una cantidad limitada de espacio disponible para diferentes elementos. Una vez que todo el espacio está ocupado, el algoritmo debe elegir los mejores elementos para eliminar para hacer espacio para nuevos elementos.

Existen diferentes atributos que deberían afectar esta decisión. Por ejemplo:

• T: Tiempo desde el último acceso. (Es mejor reemplazar algo que no se ha accedido en mucho tiempo).
• N: Número de veces al que se accede. (Es mejor reemplazar algo que no se ha accedido muchas veces).
• R: Número de elementos que deben eliminarse para hacer espacio para el nuevo elemento. (Es mejor reemplazar la menor cantidad de elementos. Idealmente, esto también debería tener en cuenta los atributos T y N de cada elemento que se reemplaza).

Tengo 2 problemas:

1. Descubrir cuánto peso dar cada uno de estos atributos.
2. Descubrir cómo calcular el peso para un elemento.

(1) Me doy cuenta de que tener el peso para algo como esto es muy subjetivo, pero esperaba que haya un método estándar o algo que pueda ayudarme a decidir cuánto peso dar cada atributo. Por ejemplo, estaba pensando que un método podría ser elaborar un conjunto de dos elementos de muestra y luego comparar manualmente los dos y decidir cuál debería ser elegido en última instancia. Aquí hay un ejemplo:

Elemento A: N = 5, T = 2 horas hace.
Elemento B: N = 4, T = hace 10 minutos.

En este ejemplo, probablemente quisiera que A sea el elemento que se elige para ser reemplazado ya que, aunque se accedió una vez más, no se ha accedido en mucho tiempo en comparación con B. Este método parece tomar Mucho tiempo, e implicaría tomar muchas decisiones difíciles y subjetivas. Además, puede no ser trivial crear los pesos resultantes al final.

Otro método que se me ocurrió fue elegir arbitrariamente pesos para los diferentes atributos y luego usar la aplicación por un tiempo. Si noto algo obviamente mal con el algoritmo, podría entrar y modificar ligeramente los pesos. Este es básicamente un método de "adivinar y verificar".

Ambos métodos no parecen tan geniales y espero que haya una mejor solución.

(2) Una vez que descubro el peso, no estoy seguro de qué camino es mejor calcular el peso. ¿Debería agregar todo? (En estos ejemplos, supongo que cualquier elemento tiene el más alto replacementWeight debería ser el que se reemplazará).

replacementWeight = .4*T - .1*N - 2*R

o multiplicar todo?

replacementWeight = (T) * (.5*N) * (.1*R)

¿Qué tal no usar constantes para los pesos? Por ejemplo, seguro que "tiempo" (t) puede ser importante, pero una vez que ha pasado una cantidad específica de tiempo, comienza a no hacer una gran diferencia. Esencialmente, lo agruparía todo en un contenedor de "mucho tiempo ha pasado". (Por ejemplo, aunque 8 horas y 7 horas tienen una diferencia de hora entre los dos, esta diferencia podría no ser tan significativa como la diferencia entre 1 minuto y 5 minutos ya que estos dos son mucho más recientes) (u otro ejemplo: reemplazar (R ) 1 o 2 elementos está bien, pero cuando empiezo a necesitar reemplazar 5 o 6, eso debería estar muy pesado ... por lo tanto, no debería ser lineal).

replacementWeight = 1/T + sqrt(N) - R*R

Obviamente (1) y (2) están estrechamente relacionados, por lo que espero que haya una mejor manera de encontrar este tipo de algoritmo.

Answer 1

Lo que está describiendo es el problema clásico de elegir un Política de reemplazo de caché. Qué política es mejor para usted, depende de sus datos, pero lo siguiente generalmente funciona bien:

Primero, siempre guarde un nuevo objeto en el caché, desalojando el R peor (s) (s). No hay forma de saber a priori si un objeto debe almacenarse o no. Si el objeto no es útil, volverá a caer del caché pronto.

El popular caché de calamar implementos Los siguientes algoritmos de reemplazo de caché:

• Menos usado recientemente (LRU):
  • replacementKey = -T
• Menos usado con el envejecimiento dinámico (LFUDA):
  • replacementKey = N + C
• Frecuencia de tamaño dual (GDSF):
  • replacementKey = (N/R) + C

C se refiere a un Factor de edad de caché aquí. C es básicamente el replacementKey del artículo que fue desalojado por último (o cero).

Nota: El Reemplazo de Key se calcula cuando se inserta o accede a un objeto, y se almacena junto con el objeto. El objeto con el pequeñísimo Reemplazo Key es desalojado.

LRU es simple y a menudo lo suficientemente bueno. Cuanto más grande sea su caché, mejor se desempeña.

Lfuda y GDSF son compensaciones. Lfuda prefiere mantener objetos grandes, incluso si son menos populares, bajo el supuesto de que un golpe a un objeto grande constituye muchos golpes para objetos más pequeños. GDSF básicamente hace la compensación opuesta, manteniendo muchos objetos más pequeños sobre menos objetos grandes. Por lo que escribes, este último podría ser un buen ajuste.

Si ninguno de estos satisface sus necesidades, puede calcular valores óptimos para T, N y R (y comparar diferentes fórmulas para combinarlas) minimizando lamentar, la diferencia en el rendimiento entre su fórmula y el óptimo algoritmo, usando, por ejemplo, Regresión lineal.

Answer 2

Este es un problema completamente subjetivo, como señala usted mismo. Y una posibilidad clara es que si sus casos de prueba consisten en pares (a, b) donde prefiere A a B, entonces puede encontrar que prefiere A a B, B a C pero también C sobre A - no es un pedido.

Si no tiene cuidado, ¡su función podría no existir!

Si puede definir una función escalar de sus variables de entrada, con varios parámetros para coeficientes y exponentes, es posible que pueda estimar dichos parámetros mediante la regresión, pero necesitará una gran cantidad de datos si tiene muchos parámetros.

Este es el enfoque del estadístico clásico de revisar primero los datos para identificar un modelo, y luego usar ese modelo para estimar una realización particular del modelo. Hay grandes libros sobre este tema.