El modelo de caché de dosqueues mencionado en este artículo se refiere al modelo de datos de caché en la memoria.
No importa qué idioma, es posible que deba poner algunos datos en la memoria para evitar operaciones repetidas y lectura. El escenario más común es el selector de jQuery. La selección de algunos elementos DOM lleva mucho tiempo. Esperamos almacenar en caché estos datos sin tener que volver a atravesar el árbol DOM cada vez que llamamos.
Guárdelo, ¡pero debe haber una cantidad! No puede poner todos los datos históricos en la memoria. Después de todo, la capacidad de memoria actual sigue siendo bastante lamentable. Incluso si la memoria es lo suficientemente grande, la memoria asignada por cada hilo en teoría todavía es limitada.
Entonces, la pregunta es, ¿cómo podemos almacenar en caché de manera eficiente los datos verdaderamente útiles? Esto implica algoritmos de eliminación, y los datos basura deben eliminarse para preservar datos útiles.
Hay varias ideas comunes:
FIFO: Es una cola en primer lugar, los primeros datos en caché, y se eliminó primero. Este modelo se utiliza dentro del famoso marco jQuery.
LRU: Estructura de lista doble vinculada, cada vez que se almacenan nuevos datos, se coloca directamente en el encabezado de la lista vinculada; Los datos a los que se accede cada vez también se transfieren al encabezado de la lista vinculada. De esta manera, los datos al final de la lista vinculada son algo que no se ha utilizado recientemente y se eliminarán.
Twoqueues: FIFO+ LRU. FIFO almacena principalmente datos almacenados por primera vez, y el LRU almacena datos de punto caliente que se han utilizado al menos dos veces. Este algoritmo tiene una alta tasa de golpe, una fuerte adaptabilidad y baja complejidad.
Hay muchos otros algoritmos de eliminación, pero solo hay dos tipos de ellos que se usan más en la práctica. Debido a que sus algoritmos no son complejos, fáciles de implementar, la alta eficiencia de ejecución y la tasa de accesorios de caché es aceptable en la mayoría de las ocasiones. Después de todo, el algoritmo de caché también requiere el consumo de CPU. Si es demasiado complejo, aunque la tasa de golpes se ha mejorado, no vale la pena la pérdida. Imagínense, si obtiene datos del caché, lleva más tiempo que obtener desde la ubicación original. ¿Cuál es el uso de caché?
No hablaré sobre las teorías específicas. Hay algunos en línea, pero no los entiendo mucho. Hoy compartiré con ustedes la versión JavaScript del modelo de caché de Twoqueues.
Hablemos de cómo usarlo primero, es muy simple.
El método de uso básico es el siguiente:
[/código]
var tq = inittWoqueues (10);
tq.set ("clave", "valor");
tq.get ("clave");
[/código]
Al inicializar, simplemente especifique la capacidad de caché. Cabe señalar que dado que FIFO+LRU se implementa internamente, la capacidad real es el doble de la capacidad especificada. El ejemplo anterior especifica 10 (pares de valor clave), que en realidad pueden almacenar 20.
El tamaño de la capacidad debe determinarse de acuerdo con el escenario de aplicación real. Si es demasiado pequeño, la tasa de golpes es baja, la eficiencia es baja y el extremo es lo contrario, y debe medirla usted mismo.
Durante el proceso de desarrollo, para revisar el efecto de caché, el grupo de caché se puede inicializar en la versión de desarrollo:
La copia del código es la siguiente:
var tq = inittWoqueues (10, verdadero);
tq.hitratio ();
Simplemente agregue un parámetro al final y simplemente es cierto. El grupo de caché inicializado de esta manera contará automáticamente la tasa de aciertos, y la tasa de golpes se puede obtener a través del método HITRATIO. Si no se agrega este parámetro, la tasa de acertas obtenida por el método HITRATIO siempre es 0.
La tasa estadística de éxito definitivamente consumirá recursos, por lo que no se recomienda activar en entornos de producción.
Es hora de compartir el código:
La copia del código es la siguiente:
(función (exportaciones) {
/**
* Clase pura para la herencia
* @constructor
*/
función fn () {}
Fn.prototype = Elimination.prototype;
/**
* Algoritmo de eliminación de la clase principal de la caché basado en la lista vinculada
* @param maxlength cache capacidad
* @constructor
*/
Eliminación de la función (maxLength) {
this.container = {};
this.length = 0;
this.maxLength = maxLength || 30;
this.linkhead = this.BuildNode ("", "");
this.linkhead.head = true;
this.linktail = this.BuildNode ("", "");
this.linktail.tail = true;
this.linkhead.next = this.linktail;
this.linktail.prev = this.linkhead;
}
Elimination.prototype.get = function (key) {
arrojar un nuevo error ("¡Este método debe ser anulado!");
};
Elimation.prototype.set = function (key, value) {
arrojar un nuevo error ("¡Este método debe ser anulado!");
};
/**
* Crear nodos en la lista vinculada
* @param Datos Los datos contenidos en el nodo, es decir, el valor de los datos en caché
* @Param Key El identificador único del nodo, es decir, la tecla caché
* @returns {{}}
*/
Elimination.prototype.BuildNode = function (data, key) {
var nodo = {};
node.data = data;
node.key = key;
nodo.use = 0;
nodo de retorno;
};
/**
* Un nodo aparece desde el encabezado de la lista vinculada
* @returns {*}
*/
Elimination.prototype.shift = function () {
var nodo = nulo;
if (! this.linkhead.next.tail) {
nodo = this.linkhead.next;
this.linkhead.next = node.next;
node.next.prev = this.linkhead;
Eliminar este.container [node.key];
this.length--;
}
nodo de retorno;
};
/**
* Inserte un nodo en el encabezado de la lista vinculada
* @param nodo objeto de nodo
* @returns {*}
*/
Elimation.prototype.unshift = function (nodo) {
node.next = this.linkhead.next;
this.linkhead.next.prev = node;
this.linkhead.next = nodo;
node.prev = this.linkhead;
this.container [node.key] = node;
this.length ++;
nodo de retorno;
};
/**
* Inserte un nodo desde el final de la lista vinculada
* @param nodo objeto de nodo
* @returns {*}
*/
Elimation.prototype.append = function (nodo) {
this.linktail.prev.next = node;
node.prev = this.linktail.prev;
node.next = this.linktail;
this.linktail.prev = node;
this.container [node.key] = node;
this.length ++;
nodo de retorno;
};
/**
* Un nodo aparece desde el final de la lista vinculada
* @returns {*}
*/
Elimination.prototype.pop = function () {
var nodo = nulo;
if (! this.linktail.prev.head) {
nodo = this.linktail.prev;
node.prev.next = this.linktail;
this.linktail.prev = node.prev;
Eliminar este.container [node.key];
this.length--;
}
nodo de retorno;
};
/**
* Eliminar el nodo especificado de la lista vinculada
* @param nodo objeto de nodo
* @returns {*}
*/
Elimination.prototype.remove = function (nodo) {
node.prev.next = node.next;
node.next.prev = node.prev;
Eliminar este.container [node.key];
this.length--;
nodo de retorno;
};
/**
* El procesamiento que se debe realizar cuando se accede a un nodo es mover el nodo al encabezado de la lista vinculada
* @param nodo
*/
Elimination.prototype.use = function (nodo) {
this.remove (nodo);
this.unshift (nodo);
};
/**
* Implementación del algoritmo de eliminación de caché LRU
* @constructor
*/
función lru () {
Elimination.apply (esto, argumentos);
}
Lru.prototype = new fn ();
Lru.prototype.get = function (key) {
var nodo = indefinido;
nodo = this.container [clave];
if (nodo) {
this.use (nodo);
}
nodo de retorno;
};
Lru.prototype.set = function (clave, valor) {
var nodo = this.BuildNode (valor, clave);
if (this.length === this.maxLength) {
this.pop ();
}
this.unshift (nodo);
};
/**
* Implementación del algoritmo de eliminación de caché FIFO
* @constructor
*/
función fifo () {
Elimination.apply (esto, argumentos);
}
Fifo.prototype = new fn ();
Fifo.prototype.get = function (key) {
var nodo = indefinido;
nodo = this.container [clave];
nodo de retorno;
};
Fifo.prototype.set = function (clave, valor) {
var nodo = this.BuildNode (valor, clave);
if (this.length === this.maxLength) {
this.shift ();
}
this.append (nodo);
};
/**
* La encapsulación del algoritmo LRU y FIFO se ha convertido en el nuevo algoritmo de eliminación de caché de dosqueues
* @param maxlength
* @constructor
*/
Function Agent (maxLength) {
this.getCount = 0;
this.hitCount = 0;
this.lir = new Fifo (maxLength);
this.hir = new Lru (maxLength);
}
Agent.prototype.get = function (key) {
var nodo = indefinido;
nodo = this.lir.get (clave);
if (nodo) {
node.use ++;
if (node.use> = 2) {
this.lir.remove (nodo);
this.hir.set (node.key, node.data);
}
}demás{
nodo = this.hir.get (clave);
}
nodo de retorno;
};
Agent.prototype.getx = function (key) {
var nodo = indefinido;
this.getCount ++;
nodo = this.get (clave);
if (nodo) {
this.hitCount ++;
}
nodo de retorno;
};
Agent.prototype.set = function (key, value) {
var nodo = nulo;
nodo = this.lir.container [clave] || this.hir.container [clave];
if (nodo) {
node.data = valor;
}demás{
this.lir.set (clave, valor);
}
};
/**
* Obtenga la tasa de éxito
* @returns {*}
*/
Agente.prototype.hitratio = function () {
var ret = this.getCount;
if (ret) {
ret = this.hitCount / this.getCount;
}
regreso de regreso;
};
/**
* Interfaz externa
* @param maxlength cache capacidad
* @param dev si se trata de un entorno de desarrollo, el entorno de desarrollo contará la tasa de aciertos, de lo contrario no
* @returns {{get, set: function, hitratio: function}}
*/
exports.inittwoqueues = function (maxLength, dev) {
var api = nuevo agente (maxLength);
devolver {
Get: (function () {
if (dev) {
Función de retorno (clave) {
var retir = api.getx (clave);
return ret && ret.data;
};
}demás{
Función de retorno (clave) {
var ret = api.get (clave);
return ret && ret.data;
};
}
} ()),
set: function () {
api.set.apply (API, argumentos);
},
HITRATIO: function () {
return api.hitratio.apply (API, argumentos);
}
};
};
}(este));
Finalmente, me gustaría recordarle nuevamente que el algoritmo de caché debe combinarse con escenarios de aplicación reales. Sin un algoritmo universal, ¡el mejor es el mejor!