Curto-circuito espécie

Question

Eu entendo que:

head (map (2**) [1..999999])

Só vai realmente avaliar 2 ** 1, e nenhum dos restantes, mas o livro que estou lendo diz que:

head (sort somelist)

só precisa encontrar o menor item na lista, porque isso é tudo o que é usado. Como é que isso funciona? Tanto quanto eu posso dizer, isso seria impossível com os algoritmos de ordenação que eu conheço (como bolha de classificação).

A única maneira que eu posso pensar que isso iria funcionar é se o algoritmo de classificação foram para percorrer a lista inteira procurando o menor item, e em seguida, recurse na lista sem esse item. Para mim, isso soa muito lento.

É assim que as obras função de classificação, ou há outra algoritmo de classificação Eu não sei sobre o que permitiria curto-circuito como é?

Answer 1

Este:

só precisa encontrar o menor item na lista, porque isso é tudo o que é usado.

... realmente deve dizer que a função só precisa fazer o mínimo de trabalho que o algoritmo de ordenação requer para encontrar o menor elemento.

Por exemplo, se estamos usando quicksort como nosso algoritmo subjacente a classificação, então head . quicksort é equivalente ao ideal seleção algoritmo conhecido como ' QuickSelect ', o que é pior caso linear. Além disso, podemos implementar k -quickselect meramente por take k . quicksort.

notas Wikipédia em seu artigo sobre algoritmos de seleção de que (o sublinhado é meu):

Como suporte de idioma para ordenação é mais onipresente, é preferível a abordagem simplista de triagem seguido de indexação em muitos ambientes, apesar de sua desvantagem na velocidade. De fato, para línguas preguiçosos, esta abordagem simplista pode até dar-lhe o melhor complexidade possível para o k menor / maior classificadas (com máximo / mínimo como um caso especial) se o seu tipo é bastante preguiçoso.

Quicksort funciona bem neste cenário, enquanto que o padrão tipo em Haskell (merge sort) não compõe muito bem, como faz mais trabalho do que o estritamente necessário para retornar cada elemento da lista ordenada. Como este post na lista de discussão Haskell notas:

quicksort preguiçoso é capaz de produzir o lote do primeiro k menores elementos em

O (n + k log k) o tempo total de [1]

Enquanto as necessidades mergesort preguiçoso

O (n + k log n) o tempo total de [2]

Por mais que você pode gostar de ler este post .

Answer 2

Se você criar uma função de comparação que traça seus argumentos, como este na linha de comando do GHCi:

> :module + Data.List Debug.Trace
> let myCompare x y = trace ("\tCmp " ++ show x ++ " " ++ show y) $ compare x y

então você pode ver o comportamento se:

> sortBy myCompare "foobar"

"     Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
a     Cmp 'b' 'r'
b     Cmp 'f' 'o'
      Cmp 'f' 'r'
f     Cmp 'o' 'o'
      Cmp 'o' 'r'
o     Cmp 'o' 'r'
or"

Haskell está avaliando a corda preguiçosamente, um carácter de cada vez. A coluna da esquerda está sendo impresso como cada caractere é encontrado, com a gravação da coluna do lado direito as comparações necessárias, como impresso por "trace".

Note que se você compilar este, especialmente com otimizações sobre, você pode obter um resultado diferente. O otimizador executa um analisador de rigor que irá provavelmente aviso de que toda a cadeia será impresso, por isso seria mais eficiente para avaliá-lo ansiosamente.

Em seguida, tente

> head $ sortBy myCompare "foobar"

      Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
'a'

Se você quer entender como isso funciona, procure o código-fonte para a função de classificar e avaliar 'tipo 'foobar'' manualmente em papel.

qsort [] = []
qsort (x:xs) = qsort less ++ [x] ++ qsort greater
   where (less, greater) = partition (< x) xs

Assim

   qsort ('f':"oobar")
 = qsort ('b':"a") ++ "f" ++ qsort ('o':"or")
 = ("a" ++ "b") ++ "f" ++ qsort ('o':"or")

E agora nós temos feito o suficiente para descobrir que 'a' é o primeiro item no resultado sem ter que avaliar a outra chamada para "qsort". Omiti a comparação real, porque a sua escondido dentro da chamada para "partição". Na verdade "partição" também é preguiçoso, por isso, de fato, o argumento para o outro "qsort" não foi avaliada, tanto quanto eu mostrei-lo.

Answer 3

O algoritmo que você acabou de descrever tem um nome específico: "tipo selecção". É de O (n ² ) para que ele não é bem a coisa mais rápida que você poderia fazer. No entanto, se você quiser que os primeiros elementos "k" na matriz classificada, a complexidade seria O (kn) que é bom se "k" é pequeno o suficiente (como o seu exemplo).

Note que você está usando uma função pura em uma linguagem funcional. O compilador é provável que seja capaz de gerar código otimizado para sort em ambos os casos por olhar para a forma como as funções são compostas. Ele pode facilmente inferir que você deseja que o elemento mínimo quando você head compor e sort.