Algoritmos de classificação que aceitam um comparador aleatório

22

Os algoritmos de classificação genérica geralmente levam um conjunto de dados para classificar e uma função comparadora que pode comparar dois elementos individuais. Se o comparador for uma relação de ordem¹, a saída do algoritmo será uma lista / matriz classificada.

Gostaria de saber, porém, quais algoritmos de classificação realmente funcionariam com um comparador que não é uma relação de ordem (em particular uma que retorna um resultado aleatório em cada comparação). Por "trabalho", quero dizer aqui que eles continuam retornando uma permutação de suas entradas e rodando em sua complexidade de tempo tipicamente citada (em vez de degradar sempre o pior cenário possível, ou entrar em um loop infinito ou elementos ausentes). A ordenação dos resultados seria indefinida. Melhor ainda, a ordenação resultante seria uma distribuição uniforme quando o comparador for um lançamento de moeda.

Do meu cálculo mental, parece que uma classificação de mesclagem seria boa com isso e manteria o mesmo custo de tempo de execução e produziria uma ordenação aleatória justa. Eu acho que algo como uma classificação rápida, no entanto, degeneraria, possivelmente não terminaria e não seria justo.

Quais outros algoritmos de classificação (exceto a classificação por mesclagem) funcionariam conforme descrito com um comparador aleatório?


  1. Para referência, um comparador é uma relação de ordem, se for uma função adequada (determinística) e satisfizer os axiomas de uma relação de ordem:

    • é determinístico: compare(a,b)para um determinado ae bsempre retorna o mesmo resultado.
    • é transitivo: compare(a,b) and compare(b,c) implies compare( a,c )
    • é anti-simétrico compare(a,b) and compare(b,a) implies a == b

(Suponha que todos os elementos de entrada sejam distintos, portanto a reflexividade não é um problema.)

Um comparador aleatório viola todas essas regras. No entanto, existem comparadores que não são relações de ordem e ainda não são aleatórios (por exemplo, eles podem violar talvez apenas uma regra e apenas para elementos específicos do conjunto).

edA-qa mort-ora-y
fonte
(1) O que você quer dizer com a função de comparação ser estável? (2) "não estável" e "aleatório" são sinônimos?
Tsuyoshi Ito 12/06
"executado na complexidade de tempo tipicamente citada (em oposição a degradar no pior cenário possível" - a complexidade de tempo tipicamente citada é o pior cenário ! ", a ordenação seria uma ordenação aleatória justa" - POR "regular", você quer dizer uniforme? você supor que o comparador é uniforme, também?
Raphael
Talvez não na teoria formal, mas na prática (linguagens de programação) muitas coisas são citadas no tempo amortizado. Por exemplo, quicksort é frequentemente mostrado como mas na verdade é O ( n 2 ) . O(logn)O(n2)
edA-qa mort-ora-y
4
@ edA-qamort-ora-y: (1) Você quer dizer , não O ( log n ) . (2) Não é isso que significa " tempo amortizado "; você quer dizer " hora prevista " ou, menos formalmente, "hora típica". O(nlogn)O(logn)
Jeffe
1
Ninguém abordou a questão (para mim) mais interessante colocada acima: quais algoritmos de classificação (se houver) têm a propriedade de que, se o comparador for um coin flip, o resultado será uma permutação uniforme.
21412 Joe

Respostas:

13

Então, basicamente, você deseja saber se existe algum algoritmo de classificação que não seria degradado do seu caso médio se receber uma função de comparação semelhante a:

int Compare(object a, object b) { return Random.Next(-1,1); }

... em que Random.Next () é um método que produzirá um número inteiro gerado aleatoriamente entre um limite inferior e superior inclusivo especificado.

A resposta é, na verdade, que os algoritmos de classificação mais básicos serão executados de acordo com o caso médio, porque eles obedecem a pelo menos uma das duas condições a seguir:

  1. Uma comparação entre dois elementos únicos nunca é feita duas vezes na classificação e / ou
  2. Em cada iteração da classificação, a posição correta de pelo menos um elemento é determinada e, para que esse elemento nunca seja comparado novamente.

Por exemplo, SelectionSort percorre a sub-lista de elementos não classificados, encontra o elemento "mínimo" e / ou "maior" (comparando cada um com o maior até agora), coloca-o em sua posição correta e repete. Como resultado, mesmo com um comparador não determinístico, no final de cada iteração, o algoritmo encontrou um valor que considera menor ou maior, troca-o pelo elemento na posição que está tentando determinar e nunca considera esse elemento novamente, portanto, ele obedece à condição 2. No entanto, um A e B podem ser comparados várias vezes durante esse processo (como o exemplo mais extremo, considere várias passagens de SelectionSort em uma matriz classificada em ordem inversa), por isso viola a condição 1 .

MergeSort obedece à condição 1, mas não 2; À medida que as sub-matrizes são mescladas, os elementos na mesma sub-matriz (no lado esquerdo ou direito) não são comparados entre si porque já foi determinado que os elementos desse lado da matriz estão em ordem entre si; o algoritmo compara apenas o elemento menos imerso de cada sub-matriz com o outro para determinar qual é menor e deve seguir em seguida na lista mesclada. Isso significa que quaisquer dois objetos exclusivos A e B serão comparados entre si no máximo uma vez, mas o índice "final" de qualquer elemento na coleção completa não será conhecido até que o algoritmo esteja completo.

O InsertionSort obedece apenas à Condição 1, apesar de sua estratégia e complexidade gerais parecerem mais com SelectionSort. Cada elemento não classificado é comparado aos elementos classificados, o maior primeiro, até encontrar um que seja menor que o elemento sob inspeção. o elemento é inserido nesse ponto e, em seguida, o próximo elemento é considerado. O resultado é que a ordem relativa de qualquer A e B é determinada por uma comparação e nunca são realizadas comparações adicionais entre A e B, mas a posição final de qualquer elemento não pode ser conhecida até que todos os elementos sejam considerados.

O QuickSort obedece a ambosCondições. Em cada nível, um pivô é escolhido e organizado de forma que o lado "esquerdo" contenha elementos menos que o pivô e o lado "direito" contenha elementos maiores que o pivô. O resultado desse nível é QuickSort (esquerda) + pivô + QuickSort (direita), o que basicamente significa que a posição do elemento pivô é conhecida (um índice maior que o comprimento do lado esquerdo); o pivô nunca é comparado a qualquer outro elemento depois de ter sido escolhido como um pivô (ele pode ter sido comparado com elementos de pivô anteriores, mas esses elementos também são conhecidos e não estão incluídos em nenhum sub-arranjo) E os A e B que terminam em lados opostos do pivô nunca são comparado. Na maioria das implementações do QuickSort puro, o caso base é um elemento; nesse momento, o índice atual é o índice final e nenhuma comparação adicional é feita.

(2/3)N1) À medida que o valor absoluto máximo do resultado do comparador aumenta, a probabilidade de qualquer comparação retornar negativo ou zero diminui para 0,5, tornando a chance de terminar o algoritmo muito menos provável (a chance de 99 moedas vira todas as cabeças de aterrissagem , que é basicamente o que isso se resume, é 1 em 1,2 * 10 30 )

EDITAR MUITO TEMPO DEPOIS: Existem alguns "tipos" projetados especificamente como exemplos do que não fazer que incorporam um comparador aleatório; talvez o mais famoso seja o BogoSort. "Dada uma lista, se a lista não estiver em ordem, embaralhe a lista e verifique novamente". Teoricamente, acabará atingindo a permutação correta de valores, assim como o "BubbleSort não otimizado" acima, mas o caso médio é de fatorial (N! / 2) e devido ao problema de aniversário (após permutações aleatórias suficientes maior probabilidade de encontrar permutações duplicadas do que as únicas) existe uma possibilidade diferente de zero de o algoritmo nunca concluir para oficialmente o algoritmo não ter limite de tempo.

KeithS
fonte
A condição 2 também abrangeria a classificação rápida? Ou seria mais uma terceira condição sobre cada iteração ser menor que a anterior.
edA-qa mort-ora-y
O QuickSort, em minha opinião, seria coberto pelas duas condições. No QuickSorts eficiente, você escolhe o pivô, depois compara cada elemento com ele e troca os elementos que estão no "lado" errado do pivô. Depois que os elementos são organizados, a função retorna QuickSort (esquerda) + pivô + QuickSort (direita) e o pivô não é passado para níveis mais baixos. Então, ambas as condições são verdadeiras; você nunca compara nenhum a e b exclusivo mais de uma vez e determinou o índice do pivô no momento em que termina de organizar os outros elementos.
Keiths
Ótima resposta, mas não concordo com você sobre o BubbleSort. Ao usar um comparador consistente, na i-ésima iteração, o BubbleSort sabe que os últimos elementos do i-1 estão em seu lugar final e qualquer implementação razoável do BubbleSort passará por menos elementos a cada iteração, portanto, também deve parar após n iterações .
Boris Trayvas
Depois de pensar um pouco mais, eu tenderia a concordar com você; após X passa, os maiores valores de X estão em seu devido lugar, para que você possa reduzir o espaço do problema em cada passagem e assim por um algoritmo eficiente obedeceria Condição 2. Vou editar
Keiths
Você precisaria ter cuidado com a implementação do Quicksort. Pode-se supor que uma pesquisa por um elemento não menor que o pivô termine quando encontrarmos o pivô ou um elemento maior que o pivô; esse não seria o caso necessariamente.
gnasher729
10

O(n2)

n


Edit: O problema é mais interessante como eu pensava, então aqui está um comentário adicional:

comparecompare(x,y)=true1/2false1/2

insert x [] = [x]
insert x y:ys = if x < y then x:y:ys
                else y:insert x ys

sort_aux l e = match l with
                 [] -> e
                 x:xs -> sort_aux xs (insert x ys)

sort l = sort_aux l []

k=1nf(k)nlf(k)insertk:

compare

i=1ki2ii=1i2i=2

O(2n)O(n2)

Seria divertido calcular os tempos médios de execução para os outros algoritmos, dada essa função de comparação uniforme.

cody
fonte
O Quicksort pode repetir comparações se o mesmo elemento for escolhido como pivô mais de uma vez (isso pode ocorrer várias vezes na lista).
Raphael
2
@ Rafael: Minha escolha de palavras foi ruim: eu quis dizer comparações repetidas entre ocorrências de elementos, que não ocorrem mais de uma vez no Quicksort.
Cody
1
@ Gilles: Posso estar errado, mas não acredito que a transitividade da comparação seja crucial para o tempo de execução da maioria dos algoritmos de classificação; correção , certamente, mas esse não era o objetivo da questão.
Cody
@ Gilles: O OP não está perguntando sobre algoritmos que realmente classificam. Ele está perguntando sobre o que acontece com os algoritmos de classificação padrão quando todas as comparações são substituídas por lançamentos de moedas. Os algoritmos resultantes não são classificados (exceto com pequena probabilidade), mas ainda são algoritmos bem definidos.
Jeffe
@ Jeffe Eu entendo isso agora. Não foi assim que li a pergunta inicialmente, mas, considerando os comentários do autor, foi isso que quis dizer.
Gilles 'SO- stop be evil'
2

A fusão com um comparador aleatório justo não é justa. Não tenho prova, mas tenho evidências empíricas MUITO fortes. (Justo significa distribuído uniformemente.)

module Main where

import Control.Monad
import Data.Map (Map)
import qualified Data.Map as Map
import System.Random (randomIO)

--------------------------------------------------------------------------------

main :: IO ()
main = do
  let xs = [0..9]
  xss <- replicateM 100000 (msortRand xs)
  print $ countFrequencies xss

msortRand :: [a] -> IO [a]
msortRand = msort (\_ _ -> randomIO)

countFrequencies :: (Ord a) => [[a]] -> [Map a Int]
countFrequencies [] = []
countFrequencies xss = foldr (\k m -> Map.insertWith (+) k 1 m) Map.empty ys : countFrequencies wss
  where
    ys = map head xss
    zss = map tail xss
    wss = if head zss == []
      then []
      else zss

--------------------------------------------------------------------------------

msort :: (Monad m) => (a -> a -> m Bool) -> [a] -> m [a]
msort (<) [] = return []
msort (<) [x] = return [x]
msort (<) xs = do
  ys' <- msort (<) ys
  zs' <- msort (<) zs
  merge (<) ys' zs'
  where
    (ys, zs) = split xs

merge :: (Monad m) => (a -> a -> m Bool) -> [a] -> [a] -> m [a]
merge (<) [] ys = return ys
merge (<) xs [] = return xs
merge (<) (x:xs) (y:ys) = do
  bool <- x < y
  if bool
    then liftM (x:) $ merge (<) xs (y:ys)
        else liftM (y:) $ merge (<) (x:xs) ys

split :: [a] -> ([a], [a])
split [] = ([], [])
split [x] = ([x], [])
split (x:y:zs) = (x:xs, y:ys)
  where
    (xs, ys) = split zs
Thomas Eding
fonte
Haskell ou Caml estão na moda agora?
Yai0Phah
Eu não faço ideia. Mas Haskell é o meu idioma favorito, então eu programei isso nele; a correspondência de padrões tornou isso mais fácil.
Thomas Eding
0

Uma pergunta muito relacionada é respondida em Todos os tipos de permutações (pérola funcional) por Christiansen, Danilenko e Dylus. Eles executam um algoritmo de classificação na mônada da lista , que simula essencialmente o não determinismo, retornando todas as permutações de uma determinada lista de entrada. A propriedade interessante é que cada permutação é retornada exatamente uma vez.

Citando o resumo:

...

Neste artigo, examinamos a combinação de não determinismo e classificação de uma maneira diferente: dada uma função de classificação, aplicamos a um predicado não determinístico para obter uma função que enumera permutações da lista de entrada. Chegamos ao fundo das propriedades necessárias dos algoritmos e predicados de classificação em jogo, bem como discutimos variações do não determinismo modelado.

Além disso, formulamos e provamos um teorema declarando que, independentemente da função de classificação que usamos, a função de permutação correspondente enumera todas as permutações da lista de entrada. Usamos teoremas livres, derivados apenas do tipo de uma função, para provar a afirmação.

Petr Pudlák
fonte