Al cambiar de listas no ordenadas para listas ordenadas ?[optimización]

Question

Tengo que implementar un algoritmo para descomponer volúmenes 3D en voxels.El algoritmo comienza con la identificación que los vértices están en cada lado de la corte, y en un segundo paso, que el borde de atravesar el plan de recorte.

Este proceso puede ser optimizado mediante el beneficio de la lista ordenada.Identificar el punto de división es O log(n).Pero tengo que mantener uno de esos lista ordenada por eje y esto por vértices y aristas.Ya que este va a ser implementado para ser utilizado por GPU también tengo algunas limitantes en la gestión de la memoria (es decir,CUDA).Intrusivo listsM/árboles y C son impuestas.

Con una completa "voxelization" espero endup con ~4000 puntos, y 12000 bordes.Afortunadamente, este puede ser optimizado mediante el uso de una estrategia más inteligente para deshacerse de los procesados voxels y el orden residual de los volúmenes de corte para mantener su número al mínimo.En este caso yo esperaría a tener menos de 100 puntos y 300 bordes.Esto hace el proceso más complejo de administrar, pero podría terminar siendo más eficiente.

La pregunta es, pues, que me ayude a identificar los criterios para determinar cuándo el beneficio de la utilización de un criterio de estructura de datos es la pena el esfuerzo y la complejidad de la sobrecarga en comparación a simple intrusiva en listas enlazadas.

Answer 1

La pregunta que SIEMPRE se reducen a que operador es el más común, el acceso a, o la adición.Si usted tiene una lista desordenada, añadiendo a ella no toma tiempo, y de acceso a determinados elementos de toma de tiempo extra.Si usted tiene una lista ordenada, agregando que toma más tiempo, pero el acceso es más rápido.

La mayoría de las aplicaciones de pasar la mayor parte de su tiempo de acceso a los datos, en lugar de añadir a ella, lo que significa que el (funcionamiento) sobrecarga de tiempo en la creación de una lista ordenada normalmente será equilibrado o cubiertos por el ahorro de tiempo en el acceso a la lista.Si hay una gran cantidad de churn en su base de datos (que no suena como que hay), a continuación, mantener una lista ordenada no es necesariamente recomendable, ya que estará en constante recurrir a la lista, ya considerable el costo de CPU.

La complejidad de las estructuras de datos que sólo importa si se no ser ordenados en una forma útil.Si ellos pueden ser ordenados, entonces usted tendrá que ir por la heurística de

el número de accesos:número de cambios

para determinar si la clasificación es una buena idea.

Answer 2

chmike, esto realmente suena como el tipo de cosa que usted quiere hacer en primer lugar la manera más sencilla, y ver cómo se comporta.Cualquier tipo de GPU voxelization enfoque es bastante frágil a los detalles del sistema una vez que se obtienen en grandes volúmenes de al menos (que no parecen tener).En sus zapatos me gustaría definitivamente desea que la aplicación sencilla en primer lugar, si por ninguna otra razón que para comprobar....

Answer 3

Después de considerar todas las respuestas me enteré de que el método utilizado más tarde para evitar la duplicación de cálculo que acabaría siendo menos eficiente debido a que el esfuerzo para mantener y navegar en la estructura de datos.Además, el inicial, el método es sencillo de poner en paralelo con un par de pequeñas rutinas del núcleo y por lo tanto más apropiado para la ejecución de GPU.

La comprobación de la espalda de mi inicial, el método me pareció también importante la optimización de las oportunidades que deja el volumen de corte método muy por detrás.

Desde que yo tuviera que escoger una respuesta, me eligió devinb porque la respuesta a la pregunta, pero de Simón comentario, respaldado por Tobias Warre comentario, eran tan valioso para mí.

Gracias a todos por ayudarme a ordenar este tema.Desbordamiento de la pila es un servicio impresionante.