Java e .NET: Por que diferentes algoritmos de classificação são usados ​​por padrão?

19

Apenas querendo saber por que Javae .NET Frameworkusa algoritmo de classificação diferente por padrão.

Em Java, Array.Sort() usa o algoritmo Merge Sort por padrão e como Wikipedia.com diz:

Em Java, os métodos Arrays.sort () usam classificação de mesclagem ou uma classificação rápida ajustada, dependendo dos tipos de dados e, para eficiência da implementação, alterne para a classificação de inserção quando menos de sete elementos da matriz estiverem sendo classificados

No .NET Framework, a Classificação RápidaArray.Sort/List.Sort() usa o algoritmo de classificação padrão ( MSDN ):

List.Sort () usa Array.Sort, que usa o algoritmo QuickSort. Essa implementação executa uma classificação instável; isto é, se dois elementos forem iguais, sua ordem poderá não ser preservada. Por outro lado, uma classificação estável preserva a ordem dos elementos que são iguais.

Observando a excelente tabela "Comparação de algoritmos" , podemos ver que os dois algoritmos têm um comportamento bastante diferente das perspectivas de pior caso e uso de memória:

insira a descrição da imagem aqui

Ambas Javae .NETsão ótimas estruturas para o desenvolvimento de soluções corporativas, ambas possuem plataformas para desenvolvimento incorporado. Então, por que eles estão usando um algoritmo de classificação diferente por padrão, alguma opinião?

sll
fonte
1
Para uma discussão mais aprofundada sobre uma comparação entre esses dois tipos, consulte stackoverflow.com/q/680541/866022
yoozer8

Respostas:

10

Por mais deterministas que sejam os computadores, a engenharia de computadores não é uma ciência exata. Duas pessoas, no mesmo domínio do problema, farão uma análise e desenvolverão duas soluções diferentes que satisfazem todas as restrições do problema. Pode ser difícil ou impossível determinar empiricamente qual deles é "melhor" no caso geral.

Meu palpite é que o .NET QuickSort está em camadas sobre algo nas APIs do MFC ou do Windows e provavelmente é herdado de versões muito mais antigas do Windows, nas quais a vantagem multiencadeada do MergeSort nem sequer era considerada para os computadores de Windows. o dia. ( EDIT: não é, embora os desenvolvedores da Microsoft sejam fanboys do QuickSort há muito tempo, como evidenciado por essa escolha de implementação de classificação desde o MS-DOS).

O Java, que não pode usar nenhuma implementação específica da plataforma porque o Java foi projetado do zero para ser completamente independente da plataforma, seguiu um caminho diferente. Quem sabe por que o MergeSort saiu por cima; meu palpite é que a implementação ganhou algum tipo de competição de desempenho em comparação com outros tipos criados pelos desenvolvedores, ou que um MergeSort no espaço O (n) ficou com a melhor aparência no papel em termos de melhor ou pior desempenho (O MergeSort não possui o calcanhar de Aquiles relacionado à seleção de elementos, como o QuickSort, e o melhor dos casos é uma lista quase ordenada, embora seja frequentemente o pior do QuickSort). Duvido que os benefícios de multithreading tenham sido considerados inicialmente, mas a implementação atual pode muito bem ser multithread.

KeithS
fonte
1
List<T>.Sortno .NET usa um método nativo implementado no CLR (se você não usar um comparador personalizado), mas não tem dependências nas bibliotecas do SO.
Joey
1
@ Keith - .NET não está em camadas sobre nada e foi projetado para ser independente de plataforma. Você pode ver a implementação aqui: github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/...
Robert MacLean
@RobertMacLean - "O .NET não está em camadas de nada" não é uma afirmação verdadeira, embora você tenha demonstrado que a função Sort em questão é um código totalmente "gerenciado". Grande parte do .NET, incluindo suporte a criptografia, bibliotecas da GUI da área de trabalho do Windows, interoperabilidade da API do Windows (incluindo controle de processos e de encadeamento), tudo é baseado no código não gerenciado preexistente, incluindo os MFCs. Eles simplesmente precisam ser; O próprio Windows tem apenas um componente .NET muito menor de sua base de código, o resto é unmanaged
Keiths
Permanece que os desenvolvedores da Microsoft são fanboys comprovados do QuickSort em relação a outras implementações, pois o QuickSort tem sido o algoritmo de escolha desde o MS-DOS, e isso teria influenciado sua decisão de implementar a classificação do .NET com esse algoritmo.
Keiths
Esta resposta é tão errada que estou sinceramente chocado.
User9993 12/12/19
17

Diferentes equipes de desenvolvimento em duas empresas diferentes chegaram a conclusões diferentes sobre o caso de uso usual de suas estruturas e componentes e decidiram implementar de acordo.

Essencialmente, cada empresa fez sua análise, analisou sua base de clientes e tomou diferentes decisões de acordo.

Você não pode esperar que análises de diferentes empresas e equipes, usando diferentes suposições e dados brutos, cheguem à mesma conclusão.

Oded
fonte
5
Ou mesmo as mesmas suposições e dados brutos. . .
Wyatt Barnett
Sim, foi provavelmente apenas a força do hábito - a Microsoft estava acostumado a usar o quicksort (instável), java queria ir com o tipo estável ... e merge sort foi o mais rápido estável conhecido ...
rogerdpack
12

Esta questão está um pouco desatualizada, já que o Java agora usa o Timsort (a partir do Java 7)

Dos algoritmos específicos mencionados:

  • O Quicksort tem desempenho desfavorável em O (n ^ 2), mas é um pouco mais leve / consome menos memória, oferecendo melhor desempenho em um caso típico.

  • O Mergesort garante desempenho de pior caso em O (n log n), mas carrega um pouco mais de sobrecarga e requisitos de memória. Também é automaticamente estável (ou seja, mantém elementos iguais na mesma ordem).

Os designers de Java parecem, em geral, ser um pouco mais conservadores / focados na "coisa certa", por isso não é de surpreender que tenham escolhido o Mergesort entre os dois, pois oferece melhores garantias.

Não sabe por que a Microsoft escolheu o Quicksort, talvez eles os fizessem parecer melhores em alguns micro-benchmarks?

Mikera
fonte