Ordenação de vetores gigantes

Programação Java
#1

Buenas!

Pessoal to com um probleminha.
Tenho um arquivo txt de 100Mb com 1 zilhão de números(int) para serem ordenados.
A quantidade de números é tão absurda que não consigo carrega-los em um vetor. Estou tentando com um List.
Alguém tem alguma ideia de como posso fazer isto sem explodir a ram e nem fazer o computador travar? rsrsrs

Obrigado

#2

Você está lendo este arquivo?

Mostre o método de leitura para podermos ver!

#3

Acho que você teria que usar o disco como se fosse memória, tipo persistindo os dados que ficaria na memória em disco.

Se não for um pré-requisito, ser um programa java, use um de terceiro, aqui o pessoal costuma usar o nsort a sintaxe é similiar ao sort!

Boa sort!! rs

Abraço,

Marcelo Gomes

#4

Se seu arquivo tem 100 MB, ele deve conter mais ou menos uns 100.000.000 / 6 = 17 milhões de números inteiros, supondo que você tenha em média 5 dígitos e um espaço para cada um dos números. No pior caso, você teria 100.000.000 / 2 = 50 milhões de números inteiros. (1 dígito e 1 espaço).

Como você deve saber, em 32 bits você pode ter um vetor com o tamanho máximo de 2GB, e em 64 bits você pode ter um vetor com no máximo 2 bilhões de posições. Ou seja, seu problema não é impossível de fazer.

Criar um vetor de 50 milhões de posições ocupa 50.000.000 * 4 = 200 MB. Portanto, para ordenar esse array, basta você reservar mais ou menos 250 MB para a máquina virtual Java. Use a opção -Xmx250m para iniciar seu programa.

Eu indicaria fazer o seguinte>
a) Ler o arquivo só para contar quantos inteiros há nesse arquivo. Não vá acrescentando os valores em um ArrayList porque vai estourar mesmo. (Não se esqueça de fechar o arquivo - o garbage collector não é feito para fechar arquivos, mas para limpar memória não referenciada).
b) Dimensionar um int[] com o número exato de inteiros que você leu.
c) Leia NOVAMENTE o mesmo arquivo, só que agora você vai pondo os inteiros lidos no array.Você vai ver que reler o arquivo é super-rápido porque o Windows ou o Linux já estão com uma boa parte desse arquivo no cache de disco, então a releitura será bem rápida, já que o disco não será acessado novamente (a menos que a quantidade de memória de seu computador seja realmente muito pequena).
d) Agora você pode chamar Arrays.sort para ordenar esse int[].

OK?

#5