lista - recorrer array de objetos javascript
escritura a mano asm.js: ¿cómo se puede hacer un seguimiento de los objetos javascript en el montón? (4)
Esto se siente mal. La idea de lanzar un int a una cadena para hacer una búsqueda en el mundo de Javascript es simplemente errónea. Un punto clave para escribir estructuras de datos de bucle interno en asm.js es evitar crear basura.
No hay necesidad de lanzar un int a una cadena aquí. Debería tener una matriz JS que asigne índices a objetos JS, luego, su indexación con un entero debería optimizarse en los motores JS para que sea un uso directo de ese entero. Sabrán cuándo la tabla de búsqueda es una matriz y cuándo los valores que fluyen son enteros.
Así es como emscripten (tanto en el modo de salida asm.js como en el modo de salida no asm.js) maneja cosas como punteros de función. Tiene un ID entero y hay una matriz JS que asigna esos ID a los objetos relevantes. Por ejemplo,
var FUNCTION_TABLE = [function zero() {}, function one() {}];
luego llamado con
FUNCTION_TABLE[i]();
Es importante mantener la matriz correctamente optimizada, lo que básicamente significa comenzar sus valores en 0 y no tener agujeros. De lo contrario, se puede implementar como un diccionario en lugar de una lista plana rápida.
Estoy escribiendo colas de prioridad y octetos en el subconjunto de Javascript de asm.js para exprimir el último rendimiento posible de ellos.
Sin embargo, ¿cómo almacena las referencias a los objetos de Javascript en el búfer del heap la función asm.js?
En este momento, mis estructuras en el montón tienen que tener un ID entero para el objeto de Javascript al que hacen referencia, y necesito un objeto clásico de Javascript para actuar como un dictador entre estas entradas y los objetos de Javascript.
Por ejemplo, tengo un octree de asm.js con el que se expone una función de adición como add(x1,y1,z1,x2,y2,z2,object_id) donde object_id es entero. Y la función de find(x1,y1,z1,x2,y2,z2) devuelve una lista de todos los object_ids que están dentro de los límites. Esto significa que tengo que mantener un diccionario de objetos a object_ids en Javascript para poder determinar los objetos reales que están en ese cuadro; El mapeo de object_ids a objetos.
Esto se siente mal . La idea de lanzar un int a una cadena para hacer una búsqueda en el mundo de Javascript es simplemente errónea . Un punto clave para escribir estructuras de datos de bucle interno en asm.js es evitar crear basura.
(Estoy apuntando a Chrome tanto como a Firefox; espero que el código estricto de asm.js se ejecute más rápido en ambos. Sí, haré un perfil).
No importa cuántas propiedades pueda materializar en el montón de asm.js (la posición y las dimensiones de un objeto, por ejemplo), por lo general, también necesita asociar algunos objetos de Javascript con el elemento. cadenas y objetos webGL y objetos DOM y así sucesivamente.
¿Hay una forma mejor para que el montón de asm.js contenga punteros a objetos de Javascript? Y si utiliza asignaciones de ID de enteros, ¿es mejor que utilice matrices u objetos como diccionarios, por ejemplo?
Después de leer las especificaciones de asm.js varias veces y experimentar con Firefox, estoy de acuerdo con bks:
un programa asm.js solo puede interactuar indirectamente con datos externos a través de manejadores numéricos
Sin embargo, esto no plantea un problema importante. Ya que asm.js es un subconjunto de JavaScript, no podrá usar muchas construcciones de JavaScript en asm.js, incluyendo:
- Objetos de JavaScript
- Arrays dinámicos
- Funciones de orden superior
Sin embargo, asm.js proporciona una forma de llamar a funciones de JavaScript utilizando la Interfaz de función externa (FFI). Este es un mecanismo muy poderoso, ya que le permite recuperar JavaScript desde asm.js (lo que le permite crear procedimientos parcialmente escritos en asm.js y parcialmente escritos en JavaScript).
Es importante distinguir qué partes de su código se pueden convertir a asm.js y se beneficiarán del uso de asm.js. Por ejemplo, asm.js es ideal para el procesamiento de gráficos, ya que requiere muchos cálculos. Sin embargo, no es adecuado para la manipulación de cadenas. JavaScript simple sería mejor para ese propósito.
Volviendo al tema, el problema al que se enfrenta es que necesita hacer referencia a los objetos de JavaScript desde el código asm.js. Como la única forma de hacer esto es usar manejadores numéricos (lo que no desea), solo veo otra solución:
En lugar de hacer referencia a objetos de JavaScript desde asm.js, haga referencia a las estructuras de asm.js desde dentro de JavaScript.
Hay muchas razones por las que este método es mejor:
- Dado que JavaScript es un superconjunto de asm.js, ya puede utilizar las estructuras asm.js en JavaScript tal como están.
- Puesto que JavaScript es más poderoso que asm.js, es más fácil hacer que las estructuras asm.js se comporten como objetos JavaScript.
- Al importar las estructuras asm.js en JavaScript, su código asm.js se vuelve más simple, más cohesivo y menos unido.
Basta de hablar, veamos un ejemplo. Tomemos el algoritmo de ruta más corto de Dijkstra . Por suerte, ya tengo una demostración de trabajo (tuve que implementar el algoritmo de Dijkstra para una asignación universitaria):
El código vinculado a lo anterior está completamente implementado en JavaScript antiguo. Tomemos algunas partes de este código y lo convertimos a asm.js (teniendo en cuenta que las estructuras de datos se implementarán en asm.js y luego se exportarán a JavaScript).
Para comenzar con algo concreto, esta es la forma en que estoy creando un gráfico en JavaScript:
var graph = new Graph(6)
.addEdge(0, 1, 7)
.addEdge(0, 2, 9)
.addEdge(0, 3, 14)
.addEdge(1, 2, 10)
.addEdge(1, 4, 15)
.addEdge(2, 3, 2)
.addEdge(2, 4, 11)
.addEdge(3, 5, 9)
.addEdge(4, 5, 6);
Queremos mantener la misma interfaz. De ahí que lo primero que hay que modificar es el constructor Graph . Así es como se implementa actualmente:
function Graph(v) {
this.v = --v;
var vertices = new Array(v);
for (var i = 0, e; e = v - i; i++) {
var edges = new Array(e);
for (var j = 0; j < e; j++)
edges[j] = Infinity;
vertices[i] = edges;
}
this.vertices = vertices;
}
No me molestaré en explicar todo el código en profundidad, pero se requiere una comprensión general:
- Lo primero que hay que tener en cuenta es que supongo que estoy creando un gráfico que consta de 4 vértices, luego solo creo una matriz de 3 vértices. El último vértice no es obligatorio.
- A continuación, para cada vértice creo una nueva matriz (que representa los bordes) entre dos vértices. Para una gráfica con 4 vértices:
- El primer vértice tiene 3 aristas.
- El segundo vértice tiene 2 nuevos bordes.
- El tercer vértice tiene 1 borde nuevo .
- El cuarto vértice tiene 0 bordes nuevos (por lo que solo necesitamos una matriz de 3 vértices).
En general, una gráfica de n vértices tiene n * (n - 1) / 2 bordes. Por lo tanto, podemos representar el gráfico en un formato tabular de la siguiente manera (la tabla a continuación es para el gráfico en la demostración anterior):
+-----+-----+-----+-----+-----+-----+
| | f | e | d | c | b |
+-----+-----+-----+-----+-----+-----+
| a | | | 14 | 9 | 7 |
+-----+-----+-----+-----+-----+-----+
| b | | 15 | | 10 |
+-----+-----+-----+-----+-----+
| c | | 11 | 2 |
+-----+-----+-----+-----+
| d | 9 | |
+-----+-----+-----+
| e | 6 |
+-----+-----+
Esta es la estructura de datos que necesitamos implementar en el módulo asm.js. Ahora que sabemos cómo se ve, vamos a implementarlo:
var Graph = (function (constant) {
function Graph(stdlib, foreign, heap) { /* asm.js module implementation */ }
return function (v) {
this.v = --v;
var heap = new ArrayBuffer(4096);
var doubleArray = this.doubleArray = new Float62Array(heap);
var graph = this.graph = Graph(window, {}, heap);
graph.init(v);
var vertices = { length: v };
for (var i = 0, index = 0, e; e = v - i; i++) {
var edges = { length: e };
for (var j = 0; j < e; j++) Object.defineProperty(edges, j, {
get: element(index++)
});
Object.defineProperty(vertices, i, {
get: constant(edges)
});
}
this.vertices = vertices;
function element(i) {
return function () {
return doubleArray[i];
};
}
};
}(constant));
Como puede ver, nuestro constructor de Graph ha vuelto mucho más complicado. Además de v y vertices , tenemos dos nuevas propiedades públicas, doubleArray y graph , que se requieren para exponer la estructura de datos y las operaciones de datos desde el módulo asm.js, respectivamente.
La propiedad de los vertices es particular ahora se implementa como un objeto en lugar de una matriz, y utiliza captadores para exponer la estructura de datos asm.js. Así es como hacemos referencia a las estructuras de datos asm.js desde JavaScript.
El montón es simplemente un ArrayBuffer y puede operarse mediante el código asm.js o el JavaScript antiguo. Esto le permite compartir estructuras de datos entre el código asm.js y JavaScript. En el lado de JavaScript, puede envolver esta estructura de datos en un objeto y usar captadores y configuradores para actualizar dinámicamente el montón. En mi humilde opinión, esto es mejor que usar manejadores numéricos.
Conclusión: como ya he respondido a su pregunta y demostrado cómo importar estructuras de datos asm.js a JavaScript, concluiría que esta respuesta es completa. Sin embargo, me gustaría dejar una demostración de trabajo como una prueba de concepto. Sin embargo, esta respuesta ya es demasiado grande. Escribiré una publicación de blog sobre este tema y publicaré un enlace aquí tan pronto como sea posible.
JSFiddle para el algoritmo de ruta de algoritmo más corto de Dijkstra implementado en asm.js próximamente.
Mientras leo la especificación de asm.js en http://asmjs.org/spec/latest/ y las preguntas frecuentes en http://asmjs.org/faq.html , la respuesta corta es que no puede almacenar referencias de objetos JS en el montón de asmjs. Citando de las preguntas frecuentes:
P. ¿Puede asm.js servir como una máquina virtual para idiomas administrados, como la JVM o CLR?
A. En este momento, asm.js no tiene acceso directo a los datos recolectados en la basura; un programa asm.js solo puede interactuar indirectamente con datos externos a través de manejadores numéricos. En futuras versiones, tenemos la intención de introducir recolección de basura y datos estructurados basados en la API de datos binarios estructurados ES6, lo que hará que asm.js sea un destino aún mejor para los idiomas administrados.
Por lo tanto, su método actual de almacenamiento de un mapa de identificación de objeto externo parece ser la forma recomendada actual para resolver su problema, siempre y cuando se preocupe por las instancias del objeto en lugar de solo por su contenido. De lo contrario, creo que la idea es que desmaterialice los objetos almacenados: almacene el contenido completo de cada objeto en su ranura en la cola de prioridad y vuelva a convertirlo en un verdadero objeto JS solo cuando se recupere. Pero eso solo funciona si tus objetos son seguros para recrearlos a pedido.
Probablemente no haya entendido completamente su pregunta, pero puede ser posible usar la cola de prioridad de la biblioteca estándar de C ++ y luego compilarla con emscripten para crear un módulo javascript de asm.js.
Por ejemplo el código followinf:
#include <queue>
#include <iostream>
class MyClass {
private:
int priority;
int someData;
public:
MyClass():priority(0), someData(0){}
MyClass(int priority, int data):priority(priority), someData(data){}
int getPriority() const { return this->priority;}
int getData() const { return this->someData;}
void setData(int data){ this->someData = data;}
inline bool operator<(const MyClass & other) const{
return this->getPriority() < other.getPriority();
}
};
int main(){
std::priority_queue<MyClass> q;
q.push(MyClass(50, 500));
q.push(MyClass(25, 250));
q.push(MyClass(75, 750));
q.push(MyClass(10, 100));
std::cout << "Popping elements: " << std::endl;
while(!q.empty()){
std::cout << q.top().getData() << std::endl;
q.pop();
}
std::cout << "Queue empty" << std::endl;
return 0;
};
Compilado como
emcc queue.cpp -s ASM_JS=1 -O2 -o queue.js
Luego se puede ejecutar con nodejs, produciendo el siguiente resultado:
$ nodejs queue.js
Popping elements:
750
500
250
100
Queue empty
También se puede compilar para crear un archivo html y cargarlo en el navegador como:
$ emcc queue.cpp -s ASM_JS=1 -O2 -o queue.html
No sé si esta es una opción para usted, pero escribir el código asmjs manualmente es bastante complejo.