matriz de caché de búsqueda hacia delante ajeno

Question

Estoy tratando de entender caché simipiled gama de búsqueda hacia delante ajeno que se describe en here, y desde la página 35 de this presentation

Análisis de Inserción en simplificado Árbol del fractal:

1. El costo de combinar 2 matrices de tamaño X es O (X = B) E/S de bloques. Merge es muy E/S eficiente.
2. El costo por elemento para fusionar es O (1/B) ya que los elementos O (X) fueron combinados.
3. El número máximo de veces que se combina cada elemento es O (logN).
4. costo promedio del inserto es O (logN/B)

puedo understhand # 1, # 2 y # 3, pero no puedo entender # 4, del papel, fusionar puede considerarse como carga adicional binaria, por ejemplo, (31) B podría presentarse: al insertar un nuevo artículo (más 1), debe haber 5 = registro (32) fusión (5 acarreos). Pero, en esta situación, ¡tenemos que unir 32 elementos! Además, si cada vez que tenemos más 1, ¿cuántos carryies se realizarán de 0 a 2^k? El awser debe ser 2^k - 1. En otras palabras, ¡una fusión por inserción!

entonces ¿Cómo se calcula el # 4?

Answer 1

Mientras se encuentra a la derecha en tanto que el número de elementos fusionados (y por lo transferencias) es N, en el peor caso y que el número de fusiones totales es también del mismo orden, el costo de inserción promedio todavía es logarítmica. Proviene de dos hechos: las fusiones varían en costo, y el número de fusiones de bajo costo es mucho más alto que el número de costos altos.

Puede ser más fácil verlo con el ejemplo.
Vamos a establecer B = 1 (es decir, 1 elemento por bloque, el peor caso de cada fusión tiene un costo) y N = 32 (por ejemplo, insertamos 32 elementos en una matriz inicialmente vacía).
La mitad de las inserciones (16) ponen un elemento en el subcampo vacío de tamaño 1, por lo que no provocan una fusión. De las inserciones restantes, una (la última) necesita fusionar (mover) 32 elementos, una (16ª) mueve 16, dos (8ª y 24ª) mover 8 elementos, cuatro mover 4 elementos y ocho mover 2 elementos. Por lo tanto, el número total de movimientos de elementos es 96, dando un promedio de 3 movimientos por inserción.

Espero que ayude.

Answer 2

En general, el número amortizado de bits modificados por incremento es 2 = O (1).

Aquí hay una prueba de lógica/razonamiento. http://www.cs.princeton.edu/courses/archive/spr11/cos423/Lectures/Binary%20Counting.pdf

Aquí hay una "prueba" por experimentación. http://codepad.org/0gWKC3rW

Answer 3

Los primeros niveles de registro B caben en (una sola página de) memoria, por lo que cualquier cosa que ocurra en esos niveles no incurrirá en una E/S. (Esto también soluciona el problema con el análisis de rrenaud de que hay O (1) fusiones por inserción, ya que solo comienza a pagarlas después de que se fusiona el primer registro B.)

Una vez que fusiona al menos elementos B, entonces Hecho 2 patadas en.

Considere el trabajo desde el punto de vista de un elemento. Se combina con O (log N) veces. Se carga O (1/B) cada vez que eso sucede. Su costo total de inserción es O ((log N)/B) (necesita los paréntesis adicionales para diferenciarse de O (log N/B), lo que sería un rendimiento de inserción bastante malo, incluso peor que un B-tree).

El costo "promedio" es realmente el costo amortizado, es la cantidad que le cobra a ese elemento por su inserción. Un poco más formalmente es el trabajo total para insertar N elementos, luego se divide por N. Un costo amortizado de O ((log N)/B) realmente significa que la inserción de N elementos es O ((N log N)/B) I/Os - para toda la secuencia. Esto se compara bastante favorable con árboles B, que para las inserciones N hacen un total de O ((N log N)/log B) E/S. Dividir por B es obviamente mucho mejor que dividir por el registro B.

Puede quejarse de que el trabajo es abultado, que a veces hace una inserción que provoca una gran cascada de fusiones. Está bien. No carga todas las fusiones hasta la última inserción. Todos pagan su propia pequeña cantidad por cada combinación en la que participen. Dado que (log N)/B normalmente será mucho menor que 1, a todos se les carga menos de una E/S en el transcurso de todas las fusiones. participa en.

¿Qué pasa si no me gusta el análisis amortizado, y se dice que, aunque el rendimiento de inserción sube por un par de órdenes de magnitud, que no les gusta cuando una sola inserción puede causar una gran cantidad de trabajo? Aha! Existen formas estándar para desamortizar dicha estructura de datos, donde se puede fusionar de forma preventiva durante cada inserción. Obtiene la misma complejidad de E/S (tendrá que creer lo que yo digo), pero es algo bastante estándar para las personas que se preocupan por el análisis amortizado y desamortizan el resultado.

Descripción completa: Soy uno de los autores del artículo de COLA. Además, rrenaud estaba en mi clase de algoritmos. Además, soy un fundador de Tokutek.