11

Estava pesquisando sobre a diferença entre algoritmos de ordenação de memória externa e interna e encontrei a seguinte reposta no quora:

"Nos casos em que temos de classificar mais dados do que pode caber na memória principal, precisamos de uma classificação externa algoritmo. Em vez de fazer toda a classificação na memória, nós classificar pedaços de os dados na memória de cada vez, despejar os resultados para um arquivo, e assim por diante até que tenhamos um arquivo totalmente ordenada."

Até ai deu para entender o conceito, estou com dificuldade para entender qual algoritmo de ordenação que e usado em cada tipo, existem vários tipos de ordenação mas como vou saber se esse algoritmo de ordenação se trata de memória primária ou secundária?

2
  • 1
    Acho que isso pode depender de cada SO. Você está olhando para algum SO em específico? (Windows, OS X, etc) Commented 18/11/2016 às 11:42
  • Na verdade não , só quero saber distinguir os que são usados para cada tipo mesmo.
    – stringnome
    Commented 18/11/2016 às 11:48

2 Respostas 2

10

Na verdade pode-se dizer que são os mesmos tanto para uso externo quanto interno. É provável que algum algoritmo seja um pouco melhor em um caso do que outros algoritmos. Não vou analisar um por um para chegar nessa conclusão.

A escolha do algoritmo mais adequado depende de uma série de fatores. Costuma-se dizer que o Quicksort é o mais adequado para o caso geral. O que não quer dizer que ele seja o melhor sempre. Ele foi criado para uso em memória RAM. Mas nada impede que seja usado em armazenamento secundário.

Quando vai para o armazenamento secundário é de extrema importância acessar o disco o mínimo de vezes possível. Então em tese precisaria achar um algoritmo que minimize isso, mesmo que tenha outros custos mais altos.

Porém isso é uma ingenuidade. Na prática todo algoritmo de classificação que precise de muita performance combinará técnicas diferentes para atingir o objetivo. É óbvio que uma dessas técnicas é colocar o máximo de dados possível em memória e classificar o que dá ali e ir organizando todas as porções. Se conseguir colocar tudo que está na memória secundária para a primária, o melhor algoritmo para aquele caso funcionará bem na memória. Se não puder colocar tudo, precisa gerenciar a carga da forma mais inteligente possível. Isso tem pouco a ver com o algoritmo de sort em si.

Note que a quantidade de memória que os computadores tem hoje e o advento do SSD melhorou bastante a condição de um algoritmo não tão otimizado conseguir bons resultados. Se tiver vários processadores a escolha pode tender mais para um algoritmo específico que faça uso do paralelismo. De fato o hardware adequado fará muita diferença, provavelmente mais que o algoritmo mais adequado, desde que não use um muito ruim para qualquer caso.

Pode-se fazer isso transparentemente. Pode-se usar um memory mapped file e fazer na memória tudo o que se espera fazer em arquivo. O sistema operacional gerencia o que deve estar na memória e o que precisa fica em disco. Desta forma pode se concentrar no algoritmo e o gerenciamento da memória fica por conta do sistema operacional. Ler e grava é algo que teria que fazer mesmo. Claro que será muito eficiente se couber tudo na memória ou os dados permitirem poucas trocas de página. Claro que essa facilidade por ter um custo, com o algoritmo certo pode controlar melhor como quer fazer a paginação, ou pode fazer muito pior que o sistema operacional faria. MMF é mais usado em computação do que imagina. Todos seus executáveis são carregados na memória assim. Toda memória virtual funciona assim. De fato qualquer alocação de memória, de uma forma ou de outra acaba chamando um MMF.

Se realmente o hardware for muito restrito me lembro que o MergeSort costuma ser bom em casos assim. Andei pesquisando e parece que o BucketSort é melhor ainda, e tem algumas variantes que podem ajudar melhor cada caso. Tem um estudo que parece confirmar isso.

Coloquei no GitHub para referência futura.

8

Os pontos expostos por @Maniero são certeiros. Uma imagem talvez ajude a visualizar como um processo desses funcionaria.

Qualquer algoritmo de ordenação pode ser utilizado tanto em memória primária quanto em memória secundária se você segmentar seus dados. No exemplo a seguir temos um computador que pode carregar e manipular 6 endereços de memória principal, e uma estrutura de memória secundária que suporta 12 endereços.

  • MP - Memória principal
  • MS - Memória secundária
  • RO - Resultado da Ordenação

inserir a descrição da imagem aqui

No primeiro ciclo, 6 endereços (1 - 6) são carregados para a memória principal, ordenados e devolvidos para a memória secundária. (Na imagem acima os endereços que sofreram alteração estão marcados com um fundo azul-claro.)

No segundo ciclo, os 3 endereços finais da operação anterior (4-6) mais 3 (7-9) sofrem a mesma operação de carga, ordenação e armazenamento.

Isso acontece sucessivamente até todos os endereços da memória secundária serem carregados, ordenados e escritos de volta. Após toda a memória secundária ser ordenada, o processo avalia se o ciclo deve ser executado de novo; se houve ao menos uma mudança, então o processo será repetido.

A memória secundária pode ser considerada ordenada se nenhuma operação de ordenação em memória primária resultar em mudanças de endereço durante um ciclo completo:

inserir a descrição da imagem aqui

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .