adaptativos Mapas en Scala (o Java) Preservar la Orden de Inserción

Me gustaría encontrar y reutilizar (si es posible) una implementación mapa que tiene los siguientes atributos:adaptativos Mapas en Scala (o Java) Preservar la Orden de Inserción

Mientras que el número de entradas es pequeño, digamos < 32, el almacenamiento subyacente debe realizarse en una matriz como esta [clave0, val0, clave1, val1, ...] Este esquema de almacenamiento evita muchos objetos de Entrada pequeños y proporciona búsquedas extremadamente rápidas (¡incluso si son escaneos secuenciales!) en las CPU modernas debido a que la memoria caché de la CPU no se invalida y la falta de direccionamiento indirecto de los punteros se convierte en un montón.
El mapa debe mantener el orden de inserción de pares clave/valor, independientemente del número de entradas similares a LinkedHashMap

Estamos trabajando en una representación en memoria de enormes (millones de nodos/bordes) Los gráficos en Scala y tener dicho mapa nos permitirían almacenar atributos Node/Edge y Edges por nodo de una manera mucho más eficiente para el 99% + de Nodos y Bordes que tienen pocos atributos o vecinos mientras preservamos el orden cronológico de inserción para ambos atributos y bordes.

Si alguien sabe de un mapa de Scala o Java con tales características estaría muy agradecido.

Gracias

Fuente

2010-09-02 Alex Kravets

Como referencia, estoy notando que el OP no encontró satisfactoria mi solución y solicité que la eliminara. En resumen, la idea era colocar todo en arreglos indexados, al estilo de Fortran, pero luego escribir bonitos envoltorios alrededor de esta estructura para que fuera agradable tratar con ellos. La ventaja de este método es que es increíblemente rápido (debido principalmente al uso primitivo) y preserva naturalmente el orden de inserción (porque solo agrega 1 a su índice cuando necesita una nueva entrada). Mucho trabajo gráfico en Fortran y C se ha hecho de esta manera, pero estoy de acuerdo en que no he identificado el mapa deseado. –

Dado que ya está pensando en la implementación, ¿por qué no escribe la suya? No puede ser tan difícil escribir un contenedor alrededor de una matriz o un LinkedHashMap. – starblue

Usted está utilizando su colección para un caso especial. por lo tanto, no debería molestarse en una forma de ahorro tan normal. sería interesante crear su propia datastrukture, para obtener un mayor rendimiento. puedes optimizar tu estructura para tu caso, porque parece que sabes mucho de tu gráfica. así que debes pensar en árboles, listas, lo que sea, para obtener el mayor rendimiento posible. tal vez obtengas un rendimiento runtine de O (n * logn) o menos ...;) –

Bajo Java Puede mantener una matriz 2D (hoja de cálculo). Escribí un programa que básicamente define una matriz de 2 d con 3 columnas de datos y 3 columnas para buscar los datos. los tres coloumns son testID, SubtestID y Mode. Esto me permite básicamente buscar un valor por testid y modo o cualquier combinación, o también puedo hacer referencia por ubicación estática. La tabla se carga en la memoria al inicio y el programa hace referencia a ella. Es infinitamente ampliable y se pueden agregar nuevos valores según sea necesario.

Si está interesado, puedo publicar un ejemplo de código fuente esta noche.

Otra idea puede ser mantener una base de datos en su programa. Las bases de datos están diseñadas para organizar grandes cantidades de datos.

Fuente

2010-10-06 18:59:58

Esta respuesta no aborda mi pregunta específica estrecha de tener un Mapa Adaptativo. Consideramos otras representaciones gráficas, pero por muchas razones técnicas no puedo entrar, debemos mantener un diseño "localizado" donde los Nodos de gráficos, los Bordes, etc. (todos los Átomos realmente) tienen que tener sus propios objetos de mapas de atributos. De nuevo, quiero evitar un patrón común de tener muchos pequeños objetos similares a Map.Entry para pequeños (<32 entry maps) para guardar en la memoria y mantener la ubicación del caché en la CPU (es decir, el escaneo a través de una matriz pequeña siempre es más rápido en práctica que seguir una cadena de punteros de montón). –

Si bien no conozco ninguna implementación que se ajuste exactamente a sus requisitos, puede interesarle echar un vistazo al Flat3Map (source) en la biblioteca de Jakarta Commons.

Desafortunadamente, las bibliotecas de Yakarta son bastante obsoletas (por ejemplo, no hay soporte para genéricos en la última versión estable, aunque es prometedor ver que esto está cambiando en el tronco) y generalmente prefiero Google Collections, pero podría valer la pena tu tiempo para ver cómo Apache implementó cosas.

Flat3Map no conserva el orden de las teclas, lamentablemente, pero tengo una sugerencia con respecto a su publicación original. En lugar de almacenar las claves y los valores en una sola matriz como [key0, val0, key1, val1, ...], recomiendo usar matrices paralelas; es decir, una matriz con [key0, key1, ...] y otra con [val0, val1, ...]. Normalmente no soy un defensor de matrices paralelas, pero al menos de esta manera puede tener una matriz de tipo K, su tipo de clave y otra de tipo V, su tipo de valor. En el nivel de Java, este tiene su propio conjunto de verrugas ya que no puede usar la sintaxis K[] keys = new K[32]; en cambio, necesitarás usar a bit of typecasting.

Fuente

2010-10-10 06:14:26 ide

Ahora este * es * un tipo de respuesta que estaba buscando. En mi trabajo anterior, encontré que los mapas "planos" (como apache ppl los llaman) se vuelven más lentos que los mapas hash estándar solo después de 32 o incluso 64 entradas, probablemente debido a que las CPU modernas tienen muy buenos cachés centrales y la indirección del puntero en el montón causando puestos de memoria. Idealmente, el cambio de un mapa "plano" a uno estándar ocurriría según un umbral configurable. Renuncié a esta respuesta, pero eso eliminará la pregunta de la lista de espera no activada :-) Quiero mantener la pregunta prominente por un tiempo más. Gracias por tu respuesta. –

¿Ha medido con Profiler si LinkedHashMap es demasiado lento para usted? Tal vez no necesites ese nuevo mapa: la optimización prematura es la raíz de todo mal. De todos modos, para procesar millones o más datos en un segundo, incluso el mapa mejor optimizado puede ser demasiado lento, ya que cada llamada al método también disminuye el rendimiento en esos casos. Entonces, todo lo que puede hacer es reescribir sus algoritmos de las colecciones de Java a las matrices (es decir, int -> mapas de objetos).

Fuente

2010-10-12 10:26:22 iirekm

El problema no es la velocidad o, más bien, no solo la velocidad, sino también la cantidad de pequeños objetos Emtry asignados, retenidos y sometidos a GC. –

Pero el tiempo de asignación se suma a la lentitud: cuantos más objetos se asigne al programa más lento, menos se reduce a la medición del rendimiento por parte del generador de perfiles. – iirekm

Hoy en día, donde la mayoría de las computadoras tienen 4 GB de memoria, las optimizaciones de uso raramente tienen sentido. Sin embargo, cuando lo haya hecho, generalmente es mejor usar el patrón Flyweight. Un ejemplo se puede encontrar en TreeModel de Java Swing. en lugar de node.getAttribute (key) = node.attributeMap.get (key) use algo como node.getAttribute (key) = graph.attributeModel.getAttribute (node) – iirekm

adaptativos Mapas en Scala (o Java) Preservar la Orden de Inserción

Respuesta

Cuestiones relacionadas