¿Cómo realizo una ordenación de matriz eficiente en memoria en java?

Estoy queriendo ordenar una gran variedad de cadenas (notablemente File.list(), que no puedo externalizar o reducir más) sin usar [mucha] memoria extra.¿Cómo realizo una ordenación de matriz eficiente en memoria en java?

Arrays.sort() dice que hace un tipo de fusión, y la wikipedia dice que algunas implementaciones asignan el tamaño de la matriz original para almacenar la salida ordenada. (Esto parece ser compatible con la referencia System.arraycopy en el método).

¿Existe un algoritmo de clasificación en el lugar que pueda usar y que sea eficiente desde el punto de vista de la memoria?

Fuente

2011-05-13 Stephen

¿Qué tan complejo es un algoritmo de ordenamiento que desea escribir a mano, y desea que sea estable (lo que significa que elementos de igual valor aparecen en la matriz final en el mismo orden en que parecían comenzar)? No es que realmente puedas notar la diferencia con String a menos que comiences a buscar 'System.identityHashcode' o lo que sea. –

quicksort está en su lugar y es muy rápido. Ver here.

Fuente

2011-05-13 02:41:36 dlev

Ok, eso es genial; ¿Apache o Google tienen una lib con un quicksort? (Estoy seguro de haber visto uno antes ...) – Stephen

quicksort es muy rápido, pero también es uno de los más caros, el de memoria –

@Sam Quicksort se puede implementar in situ, lo cual creo que lo hace bien en memoria. –

Puede escribir un algoritmo de ordenamiento de montones para la clasificación en contexto.

Fuente

2011-05-13 02:47:28

String es inmutable en Java. Por lo tanto, cuando se duplica la matriz de String s en su pregunta, no requieren tanto espacio como usted espera. En realidad, la sobrecarga puede ser bastante mínima.

En otras palabras, Java Arrays#sort() puede ser muy bien para su solución. Puede probar el rendimiento usted mismo.

Para su título de la pregunta, la respuesta de Ankit y dlev están bien.

Fuente

2011-05-13 03:26:51

Para ser claros, lo que se duplicará es solo la matriz de referencias * de objeto * (típicamente 4 u 8 bytes por cadena), no los objetos String en sí mismos, y por lo tanto no las matrices de caracteres dentro de cada Cadena. –

¿Cómo realizo una ordenación de matriz eficiente en memoria en java?

Respuesta

Cuestiones relacionadas