Perto algoritmos de ordenação - Quando usar?

Question

De vez em quando eu navegar na web e olhar para algoritmos interessantes e datastructures para colocar no meu saco de truques. Um ano atrás, me deparei com a macia Heap -estrutura de dados e aprendeu sobre a classificação próximo.

A idéia por trás disso é que é possível para quebrar a O (n log n) espécie de barreira com base comparar se você pode viver com o fato de que o algoritmo de ordenação engana um pouco. Você obterá uma lista quase classificado, mas você tem que viver com alguns erros também.

Eu brinquei com os algoritmos em um environement teste, mas nunca encontrou um uso para eles.

Portanto, a pergunta: Alguém já usado perto de classificação na prática? Se assim for, em que tipo de aplicações? você pode pensar em um caso de uso onde perto de ordenação é a coisa certa a fazer?

Answer 1

Há uma série de heurísticas "gananciosos", onde você seleciona periodicamente o mínimo de um conjunto. A heurística gulosa não é perfeito, por isso mesmo se você pegar o mínimo que você não está garantido para chegar à melhor resposta final. Na verdade, o GRASP meta-heurística, você introduzir intencionalmente erro aleatório para que você obtenha múltipla final soluções e escolher a melhor delas. Nesse caso, a introdução de algum erro em sua rotina de classificação em troca de velocidade seria um bom comércio off.

Answer 2

Esta é uma suposição voando total, mas dada a subjetividade inerente de medidas de "relevância" ao ordenar os resultados de pesquisa, eu me arrisco que ele realmente não importa se ou não eles estão perfeitamente ordenada. O mesmo poderia ser dito para recomendações. Se você pode de alguma forma organizar que qualquer outra parte do seu algoritmo para essas coisas é O (n), então você pode olhar para evitar uma espécie.

Esteja ciente também que, no pior caso do seu "quase classificadas" dados não se reúnem uma idéia intuitiva possível de "quase classificadas", o que é que ele tem apenas um pequeno número de inversões. A razão para isso é simplesmente que, se os seus dados tem apenas O (n) inversões, então você pode acabar classificando-o em tempo O (n) usando ordenação por inserção ou cocktail tipo (ou seja, de duas vias bubble sort). Segue-se que você não pode, eventualmente, ter chegado a este ponto de completamente indiferenciado, em O (n) tempo (usando comparações). Então você está olhando para aplicações onde um subconjunto maioria dos dados são classificados eo restante está espalhado, não para aplicações que exigem que cada elemento está perto de sua posição correta.

Answer 3

Apenas especulando aqui, mas uma coisa que eu imagino é a otimização de consulta de banco de dados.

Uma consulta de banco de dados em uma linguagem declarativa, como SQL tem de ser traduzido em um programa passo-a-passo chamado um "plano de execução". Uma consulta SQL geralmente pode ser traduzido para um número de tais planos de execução, que todos dão o mesmo resultado, mas pode ter um desempenho muito variável. O otimizador de consulta tem de encontrar o mais rápido, ou pelo menos um que é razoavelmente rápido.

otimizadores de consulta baseado em custo têm uma "função de custo", que eles usam para estimar o tempo de execução de um determinado plano. otimizadores exaustivos passar por todos os planos possíveis (para alguns valor de "todos os possíveis") e selecionar o mais rápido. Para consultas complicadas o número de possíveis planos podem ser proibitivamente grande, levando a tempos de otimização excessivamente longos (antes mesmo de começar a busca no banco de dados!) Assim também há otimizadores não exaustivas. Eles só olhar para alguns dos planos, talvez com um elemento aleatório na escolha de quais. Isso funciona, pois geralmente há um grande número de "boas" planos, e isso pode não ser tão importante encontrar o absolutamente melhor - provavelmente é melhor escolher um 5-segundo plano em vez do 2 segundos plano ideal , se requer vários minutos de otimização para encontrar a 2 segundos plano.

Alguns algoritmos de otimização usar uma fila ordenada "promissores" planos (parciais). Se ele realmente não importa se você encontrar o absolutamente melhor plano, talvez você poderia usar uma fila de quase-ordenada?

Outra idéia (e eu ainda estou apenas especulando) é um agendador para processos ou threads em um sistema de tempo compartilhado, onde ele pode não ser importante se um determinado processo ou thread recebe o intervalo de tempo de alguns milissegundos mais tarde do que se estritamente ordenados por prioridade.

Answer 4

Uma aplicação comum para near-ordenação é quando um ser humano está fazendo comparativos emparelhados e você não quer ter que pedir-lhes como muitas perguntas.

Digamos que você tenha um monte de itens que você gostaria de um humano para classificar através de comparação par a par. Você pode reduzir significativamente o número de comparações que você precisa deles para fazer se você estiver disposto a aceitar que ordenação não será exata. Você pode, por exemplo, não importa se os itens adjacentes foram trocados um longo como os itens preferidos estão no topo.

Answer 5

Em qualquer lugar

1. você é suposto para reagir rápido,
2. você não está prometendo comportamento exato para o cliente,
3. mas internamente você tem algumas regras

Você pode usá-lo. Que tal "não é tão rigorosa" fila de prioridade baseado em regras? Onde isso seria útil? Talvez thread / processo / agendamento de recursos. Na programação thread / processo que você realmente não estão prometendo qualquer um segmento está indo para ir primeiro, segundo ou último, mas geralmente você quer dar a todos alguma chance. Você pode querer impor regra solto por isso é de preferência, prioridade, blabla ..

Uma programação de recursos exemplo seria responder a entrega de pizza ou transportar caixas de livros para as pessoas etc Você não pode usá-lo onde resultado determinista é esperado, mas há muitas exemplo na vida real, onde as coisas não são / tão determinista previsíveis.

Answer 6

O (n log n) já é bastante rápido. Eu não acho que alguém jamais começar usando um algoritmo de quase-tipo. Você poderia começar com um código que só faz uma espécie completa (desde sua linguagem de programação de escolha provável fornece uma função sort e não uma função nearsort), e quando você descobriu empiricamente que a espécie estava demorando demais, você começaria a questão de saber se seus dados realmente precisa ser totalmente ordenados, e considerar o uso de um quase-tipo.

Basicamente, você nunca sequer considerar o uso de um próximo tipo a menos que você descoberto pela primeira vez a classificação a ser um gargalo grave em seu programa.