Entrevista pregunta: factoriales y almacenamiento en caché

Recientemente me encontré con la siguiente pregunta de la entrevista:Entrevista pregunta: factoriales y almacenamiento en caché

que necesita para diseñar un sistema para dar respuesta a los factoriales de entre 1 y 100. Se puede almacenar en caché 10 números. ¿Cómo podría organizar/administrar ese caché, y cuál es el peor caso para la búsqueda en un error de caché ?

¿Cuál crees que sería una respuesta adecuada y cuál sería el razonamiento detrás de esto? Personalmente, almacenaba en caché los primeros diez números para la primera entrada, y luego mantengo un caché LRU basado en la información más reciente porque es más probable que las personas repitan las búsquedas. Sin embargo, no estoy seguro de cuál sería el peor caso para la búsqueda de caché. Probablemente O (n) si usa un enfoque de programación dinámica al implementar la función factorial. ¿Qué piensas?

Fuente

2011-08-28 OckhamsRazor

¿Se proporciona suficiente información para determinar una política de caché? LRU sería una apuesta segura, pero dependería del uso. Es decir, ¿qué sucede si el uso es enumerar de 1 a 100 todas las veces? En ese caso, ¿podría almacenar en caché los diez más caros para calcular? – Smudge202

posteriormente mantener una caché LRU basado en la entrada más reciente, porque la gente es más probable que se repita búsquedas

Eso podría ser una opción de diseño razonable, pero en la entrevista que habíamos frase que más lo una pregunta para el entrevistador: "¿sería razonable suponer que las llamadas serán más parecidas a las realizadas con valores recientes, o hay alguna otra agrupación esperada (se solicitarán grandes cantidades más a menudo que pequeñas o viceversa)?"

Por ejemplo, puede tener sentido almacenar en memoria caché LRU, pero nunca descartar los valores de 10, 20, 30, 40, etc. De esta forma, el peor caso para calcular un factorial una vez que el caché se llena de esos valores es tiene que realizar 10 multiplicaciones.

Otra consideración que podría hacer es que las computadoras pueden tratar muy fácilmente con ciertos factoriales:

12! es el más grande que puede contenerse en una palabra de 32 bits.
20! es el más grande que se puede contener en una palabra de 64 bits.
34! es el más grande que puede contenerse en una palabra de 128 bits.

Dado que las máquinas de hoy en día pueden manejar fácilmente la aritmética de 64 bits (tal vez incluso la aritmética de 128 bits), ¡también puede tener sentido no almacenar nunca en caché un valor de 20! o menos una vez que la memoria caché se llena con valores mayores que eso.

El peor caso para la búsqueda en una pérdida de caché dependerá de cómo se almacena la memoria caché. ¿Es una matriz ordenada por el argumento de la función? (la búsqueda es O (log n)) ¿Es una matriz en orden LRU?(buscar en la falta de caché es O (n)). Creo que también querría dejar en claro que desea que una búsqueda en caché siempre devuelva el valor más alto en la memoria caché que sea menor que lo que está buscando; ese valor de caché representa un trabajo que no tiene que hacer para este cálculo factorial particular.

Fuente

2011-08-28 15:50:57

gracias por su ayuda michael. Me gusta mucho esta respuesta, pero creo que la búsqueda de una falta de caché sería O (1) porque primero buscaste la ranura LRU (suponiendo que hayamos guardado solo 1 ranura LRU). si esto es una falla, entonces puede usar la estructura de la matriz para buscar el elemento correcto (ya que sabe que la matriz contiene elementos separados por 10 cálculos factoriales). – OckhamsRazor

La idea aquí es seleccionar algunos números por lo que es posible calcular otros de ellos. Asumiendo que su sistema hace la multiplicación con velocidad constante y sin división en absoluto, el almacenamiento en caché (o "pre-cálculo") 1! 11 !, 21 !, ¡31 !, 41 !, 51 !, 61 !, 81! 91! permite calcular todos los números restantes con un máximo de 9 multiplicaciones para cada uno.

En realidad, multiplicar números más grandes es más costoso, y también podría hacer división (por ejemplo, 90! = 91!/91), y realmente no necesita 1 !, lo que puede conducir a otra distribución óptima de esos anclajes números.

Fuente

2011-08-28 15:36:33

No creo que la multiplicación de valores más grandes sea lenta, especialmente cuando son menores que 100. Y no es bueno usar la división porque puede ser varias veces más lenta que la multiplicación. –

¡El punto es que a partir de alrededor de 13! el resultado no cabe en un número de 32 bits, ¡de alrededor de 21! no cabe en un número de 64 bits. Entonces, necesitamos números más grandes de todos modos, y con números grandes, el tiempo de multiplicación depende del tamaño. –

Cómo sobre el uso de las ranuras 9 de caché para el factorial de 10, 20, 30, 40, 50, 60, 70, 80, y 90? La décima ranura podría ser LRU. La peor búsqueda de casos es entonces O (10) o tiempo constante.

Fuente

2011-08-28 15:38:21

Dado un algoritmo de LRU determinista, un adversario puede llegar al peor de los casos solicitando siempre la página que acaba de ser desalojada. –

Mi idea es algo así como ConnorDoyle's, almacenaría todos los múltiplos de 10. Sin tener idea del tipo de llamadas que los usuarios harían esto te dejaría en el peor de los casos con 7 multiplicaciones/divisiones, incluyendo el dos originales para encontrar los dígitos de las unidades y decenas, o tiempo constante.

Una rápida pseudo-algoritmo de la parte superior de mi cabeza:

total; 
mod = input%10; 
div = input/10; 
if(input%10 == 0) 
    output(cache[input/10]); 
else{ 
    if(mod < 5) { 
     total = cache[div]; 
     for(i = 1; i<=mod; i++) 
      total = total * (cache[div] + i); 
    } 
    else { 
     total = cache[div + 1]; 
     for(i = 9; i>mod; i--) 
      total = total/(cache[div] + i); 
    } 
    output(total); 
}

peor de los casos podría ser cualquier cosa con un 5 en el dígito de las unidades.

Fuente

2011-08-30 18:45:34 SomeoneRandom

Entrevista pregunta: factoriales y almacenamiento en caché

Respuesta

Cuestiones relacionadas