¿Cómo debo cambiar mi estructura Gráfico (inserción muy lento)?

Question

Este programa que estoy haciendo es acerca de una red social, lo que significa que son los usuarios y sus perfiles. La estructura de los perfiles es UserProfile.

Ahora, hay varias implementaciones posibles Gráfico y no creo que estoy usando la mejor. Tengo una estructura Graph y en el interior, hay un puntero a una lista enlazada de tipo Vertex. Cada elemento tiene un valor Vertex, un puntero a la siguiente Vertex y un puntero a una lista enlazada de tipo Edge. Cada elemento tiene un valor Edge (para que pueda definir los pesos y todo lo que sea necesario), un puntero a la siguiente Edge y un puntero al propietario Vertex.

Tengo un 2 archivos de ejemplo con datos de proceso (en el estilo de CSV) y se insertan en el gráfico. La primera es la de datos de usuario (un usuario por línea); el segundo es las relaciones de usuario (por el gráfico). El primer archivo se inserta rápidamente en el gráfico porque siempre inserto en la cabeza y no hay como ~ 18000 usuarios. El segundo archivo lleva mucho tiempo, pero todavía insertar los bordes a la cabeza. El archivo cuenta con alrededor de ~ 520.000 líneas de relaciones con los usuarios y tarda entre 13-15mins para insertar en el gráfico. Hice una prueba rápida y la lectura de los datos es bastante rápido, instantáneamente realmente. El problema es en la inserción.

Este problema existe porque tengo un gráfico implementado con listas enlazadas para los vértices. Cada vez que tengo que insertar una relación, necesito las operaciones de búsqueda para 2 vértices, para que pueda unirlos. Este es el problema ... Hacer esto para las relaciones ~ 520000, toma un tiempo.

¿Cómo debería solucionar esto?

Solución 1) Algunas personas me recomendaron para implementar el Gráfico (la parte vértices) como una matriz en lugar de una lista enlazada. De esta manera me tiene acceso directo a cada vértice y la inserción es probablemente va a bajar considerablemente. Sin embargo, no me gusta la idea de asignar una matriz con [18000] elementos. Cómo prácticamente es esto? Mis datos de muestra tiene ~ 18000, pero lo que si necesito mucho menos o mucho más? El enfoque de lista enlazada tiene esa flexibilidad, que puede tener cualquier tamaño que desee, siempre y cuando no hay memoria para él. Sin embargo, la matriz no, ¿cómo voy a manejar esta situación? ¿Cuáles son sus sugerencias?

El uso de listas enlazadas no es bueno para la complejidad del espacio, pero malo para la complejidad del tiempo. Y el uso de una matriz es bueno para la complejidad del tiempo, pero malo para la complejidad del espacio.

¿Qué te parace esta solución?

Solución 2) Este proyecto también exige que tengo algún tipo de estructuras de datos que permite búsqueda rápida en base a un índice de nombres y un índice de identificación. Para ello, decidí utilizar tablas hash. Mis tablas se implementan con encadenamiento separado como de resolución de colisiones y cuando un factor de carga de 0,70 alcance es, normalmente crear la tabla. Me base al siguiente tamaño de la tabla en este http://planetmath.org/encyclopedia/GoodHashTablePrimes.html.

En la actualidad, ambas tablas hash mantenga un puntero a la UserProfile en lugar de la duplicación del perfil de usuario en sí. Eso sería una estupidez, los datos cambiantes requerirían 3 cambios y es muy tonto para hacerlo de esa manera. Así que sólo ahorro el puntero a la UserProfile. El puntero del mismo perfil de usuario también se guarda como valor en cada Vertex Gráfico.

Por lo tanto, tengo 3 estructuras de datos, un gráfico y dos Tablas Hash y cada uno solo de ellos apuntan a la misma UserProfile exacta. La estructura gráfico servirá el propósito de encontrar el camino más corto y cosas por el estilo, mientras que las tablas hash sirven como índice rápido por su nombre e ID.

Lo que estoy pensando para resolver mi problema gráfico es, en lugar de tener el punto de valor Hash Tables a la UserProfile, señalo a la Vertex correspondiente. Es todavía un puntero, no más y no se usa menos espacio, lo jucambio st lo señalo.

Al igual que esto, puede buscar fácilmente y rápidamente para cada necesidad Vértice I y vincularlos entre sí. Esto insertará los ~ 520000 relaciones con bastante rapidez.

I pensado en esta solución porque ya tengo las tablas hash y tengo que tener, entonces, ¿por qué no aprovecharse de ellos para la indexación de los vértices del gráfico en lugar del perfil de usuario? Es básicamente la misma cosa, todavía puedo acceder a la UserProfile bastante rápido, sólo tiene que ir a la Vertex y luego a la UserProfile.

Pero, ¿ves alguna contras en esta segunda solución en relación con el primero? O sólo los pros que dominar a los pros y los contras de la primera solución?

Otra Solución) Si tiene cualquier otra solución, soy todo oídos. Pero, por favor explicar los pros y los contras de esta solución con respecto al anterior 2. Realmente no tengo mucho tiempo para estar perdiendo con esto ahora mismo, tengo que seguir adelante con este proyecto, por lo que, si estoy haciendo para hacer tal un cambio, necesito entender exactamente qué hay que cambiar y si ese es realmente el camino a seguir.

Con suerte nadie se quedó dormido leyendo esto y cierra el navegador, lo siento por el gran testamento. Pero realmente necesito para decidir qué hacer acerca de esto y que realmente necesita para hacer un cambio.

P.S:. Al contestar mis soluciones propuestas, por favor enumerarlos como lo hice, así que sé exactamente lo que está hablando y no hay que confundir mi yo más de lo que ya soy

Answer 1

El primer enfoque es la velocidad Dado que el principal problema aquí es, yo prefiero el enfoque de matriz.

Usted debe, por supuesto, mantener la tabla hash para la búsqueda de nombre-índice.

Si he entendido bien, sólo se procesa el tiempo que uno de los datos. Así que no hay inserción de datos dinámico.

Para hacer frente al problema de la asignación de espacio, yo recomendaría:

1 -. Leer vez que el archivo, para obtener el número de vértices

2 - asignar ese espacio

Si los datos son dinámicos, se podría implementar algún método sencillo para incrementar el tamaño de la matriz en pasos de 50%.

3 - En los bordes, que sustituir lista enlazada de una matriz. Esta matriz debe ser incrementado de forma dinámica con pasos de 50%.

Incluso con el espacio "extra" asignado, cuando se incrementa el tamaño en intervalos de 50%, el tamaño total utilizado por la matriz debe ser sólo marginalmente más grande que el tamaño de la lista enlazada.

Espero que pueda ayudar.