Algoritmos de clasificación que aceptan un comparador aleatorio

22

Los algoritmos de clasificación genéricos generalmente toman un conjunto de datos para clasificar y una función de comparación que puede comparar dos elementos individuales. Si el comparador es una relación de orden¹, la salida del algoritmo es una lista / matriz ordenada.

Sin embargo, me pregunto qué algoritmos de clasificación funcionarían realmente con un comparador que no es una relación de orden (en particular, uno que devuelve un resultado aleatorio en cada comparación). Por "trabajo" quiero decir aquí que continúan devolviendo una permutación de su entrada y se ejecutan en su complejidad de tiempo típicamente citada (en lugar de degradarse al peor de los casos siempre, o entrar en un bucle infinito o elementos faltantes). Sin embargo, el orden de los resultados sería indefinido. Aún mejor, el orden resultante sería una distribución uniforme cuando el comparador es un lanzamiento de moneda.

Según mi cálculo mental aproximado, parece que un tipo de fusión estaría bien con esto y mantendría el mismo costo de tiempo de ejecución y produciría un orden aleatorio justo. Sin embargo, creo que algo así como un tipo rápido degeneraría, posiblemente no terminaría y no sería justo.

¿Qué otros algoritmos de clasificación (además de la combinación de clasificación) funcionarían como se describe con un comparador aleatorio?


  1. Como referencia, un comparador es una relación de orden si es una función propia (determinista) y satisface los axiomas de una relación de orden:

    • es determinista: compare(a,b)para un particular ay bsiempre devuelve el mismo resultado.
    • es transitivo: compare(a,b) and compare(b,c) implies compare( a,c )
    • es antisimétrico compare(a,b) and compare(b,a) implies a == b

(Suponga que todos los elementos de entrada son distintos, por lo que la reflexividad no es un problema).

Un comparador aleatorio viola todas estas reglas. Sin embargo, existen comparadores que no son relaciones de orden pero que no son aleatorios (por ejemplo, podrían violar tal vez solo una regla y solo para elementos particulares del conjunto).

edA-qa mort-ora-y
fuente
(1) ¿Qué quiere decir con que la función de comparación sea estable? (2) ¿Son "no estables" y "aleatorios" sinónimos?
Tsuyoshi Ito
"ejecutar en su complejidad de tiempo típicamente citada (en lugar de degradarse al peor de los casos" - ¡la complejidad de tiempo típicamente citada es el peor de los casos! "el orden sería un orden aleatorio justo" - POR "justo" quieres decir uniforme? ¿Asumes que el comparador también es uniforme?
Raphael
Quizás no en la teoría formal, pero en la práctica (lenguajes de programación) se citan muchas cosas en tiempo amortizado. Por ejemplo, la clasificación rápida a menudo se muestra como pero en realidad es O ( n 2 ) . O(Iniciar sesiónnorte)O(norte2)
edA-qa mort-ora-y
44
@ edA-qamort-ora-y: (1) Te refieres a , no O ( log n ) . (2) Eso no es lo que significa " tiempo amortizado "; quieres decir " tiempo esperado ", o menos formalmente, "tiempo típico". O(norteIniciar sesiónnorte)O(Iniciar sesiónnorte)
JeffE
1
Nadie ha abordado la pregunta (para mí) más interesante planteada anteriormente: qué algoritmos de clasificación (si los hay) tienen la propiedad de que si el comparador es un lanzamiento de moneda, el resultado es una permutación uniforme.
Joe

Respuestas:

13

Entonces, básicamente, desea saber si hay algún algoritmo de clasificación que no se degradaría de su caso promedio si se le da una función de comparación similar a:

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

... donde Random.Next () es un método que producirá un número entero generado aleatoriamente entre un límite inferior y superior inclusivo especificado.

La respuesta es en realidad que los algoritmos de clasificación más básicos funcionarán de acuerdo con su caso promedio, porque obedecen al menos una de las siguientes dos condiciones:

  1. Una comparación entre dos elementos únicos nunca se hace dos veces en el orden, y / o
  2. En cada iteración de la clasificación, se determina la posición correcta de al menos un elemento y, por lo tanto, ese elemento nunca se vuelve a comparar.

Por ejemplo, SelectionSort itera a través de la sublista de elementos sin clasificar, encuentra el elemento "menor" y / o "mayor" (al comparar cada uno con el mayor hasta ahora), lo coloca en su posición correcta y se repite. Como resultado, incluso con un comparador no determinista, al final de cada iteración, el algoritmo habrá encontrado un valor que considera menor o mayor, lo intercambia con el elemento en la posición que está tratando de determinar, y nunca lo considera ese elemento nuevamente, por lo tanto, obedece la Condición 2. Sin embargo, un A y B se pueden comparar varias veces durante este proceso (como el ejemplo más extremo, considere varios pases de SelectionSort en una matriz que está ordenada en orden inverso) por lo que viola la Condición 1 .

MergeSort obedece la Condición 1 pero no 2; a medida que se fusionan los subconjuntos, los elementos en el mismo subconjunto (en el lado izquierdo o derecho) no se comparan entre sí porque ya se ha determinado que los elementos en ese lado del conjunto están en orden entre sí; el algoritmo solo compara el elemento menos no combinado de cada subconjunto con el otro para determinar cuál es menor y debe ir a continuación en la lista combinada. Esto significa que dos objetos únicos A y B se compararán entre sí un máximo de una vez, pero el índice "final" de cualquier elemento dado en la colección completa no se conoce hasta que el algoritmo esté completo.

InsertionSort también obedece solo a la Condición 1 a pesar de que su estrategia y complejidad generales se parecen más a SelectionSort. Cada elemento sin clasificar se compara con los elementos ordenados, el más grande primero, hasta que se encuentra uno que es menor que el elemento bajo inspección. el elemento se inserta en ese punto y luego se considera el siguiente elemento. El resultado es que el orden relativo de cualquier A y B se determina mediante una comparación, y nunca se realizan más comparaciones entre A y B, pero la posición final de cualquier elemento no puede conocerse hasta que se consideren todos los elementos.

QuickSort obedece a ambosCondiciones. En cada nivel, se elige un pivote y se dispone de manera que el lado "izquierdo" contenga elementos menores que el pivote y el lado "derecho" contenga elementos mayores que el pivote. El resultado de ese nivel es QuickSort (izquierda) + pivote + QuickSort (derecha), lo que básicamente significa que se conoce la posición del elemento pivote (un índice mayor que la longitud del lado izquierdo), el pivote nunca se compara con ningún otro elemento después de que se haya elegido como pivote (puede haber sido comparado con elementos de pivote anteriores, pero esos elementos también se conocen y no se incluyen en ninguna submatriz), y cualquier A y B que terminen en lados opuestos del pivote nunca comparado. En la mayoría de las implementaciones de QuickSort puro, el caso base es un elemento, en cuyo punto su índice actual es su índice final y no se hacen más comparaciones.

(2/ /3)norte-1) A medida que aumenta el valor absoluto máximo del resultado del comparador, la probabilidad de que cualquier comparación regrese negativa o cero disminuye hacia .5, lo que hace que la posibilidad de finalizar el algoritmo sea mucho menos probable (la posibilidad de que la moneda 99 arroje todas las cabezas de aterrizaje) , que es básicamente lo que se reduce a esto, es 1 en 1.2 * 10 30 )

EDITE MUCHO TIEMPO DESPUÉS: Hay algunos "tipos" diseñados específicamente como ejemplos de lo que no se debe hacer que incorporan un comparador aleatorio; Quizás el más famoso es BogoSort. "Dada una lista, si la lista no está en orden, baraje la lista y verifique nuevamente". Teóricamente, finalmente alcanzará la permutación correcta de valores, al igual que el "BubbleSort no optimizado" anterior, pero el caso promedio es tiempo factorial (N! / 2), y debido al problema del cumpleaños (después de suficientes permutaciones aleatorias, usted es más probable que encuentre permutaciones duplicadas que las únicas) existe una posibilidad distinta de cero de que el algoritmo nunca se complete para oficialmente que el algoritmo no tenga límites de tiempo.

KeithS
fuente
¿La condición 2 también cubriría la clasificación rápida? ¿O sería más una tercera condición de que cada iteración sea más pequeña que la anterior?
edA-qa mort-ora-y
QuickSort, en mi opinión, estaría cubierto por ambas condiciones. En QuickSorts eficientes, usted elige el pivote, luego compara cada elemento con él e intercambia los elementos que están en el "lado" incorrecto del pivote. Una vez que los elementos están ordenados, la función devuelve QuickSort (izquierda) + pivote + QuickSort (derecha) y el pivote no se pasa a niveles inferiores. Entonces, ambas condiciones son ciertas; nunca compara ningún ayb más de una vez, y ha determinado el índice del pivote cuando termina de organizar los otros elementos.
KeithS
Gran respuesta, pero no estoy de acuerdo contigo sobre BubbleSort. Cuando se usa un comparador consistente, en la iteración i-ésima BubbleSort sabe que los últimos elementos i-1 están en su lugar final, y cualquier implementación razonable de BubbleSort pasará por menos elementos en cada iteración, por lo que también debería detenerse después de n iteraciones .
Boris Trayvas
Después de pensarlo un poco más, estaría de acuerdo contigo; después de que X pasa, los valores de X más grandes están en su lugar correcto, por lo que puede reducir el espacio del problema en cada pase y así un algoritmo eficiente obedecería la Condición 2.
Editaré
Debería tener cuidado con la implementación de Quicksort. Puede suponerse que la búsqueda de un elemento no menor que el pivote finalizará cuando encontremos el pivote o un elemento mayor que el pivote; ese no sería el caso necesariamente.
gnasher729
10

O(norte2)

norte


Editar: El problema es más interesante como lo pensé por primera vez, así que aquí hay otro comentario:

doometropagsunarmidoometropagsunarmi(X,y)=trtumi1/ /2Funalsmi1/ /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=1norteF(k)nortelF(k)yonortesmirtk:

doometropagsunarmi

yo=1kyo2-yoyo=1yo2-yo=2

O(2norte)O(norte2)

Sería divertido calcular los tiempos de ejecución promedio para los diferentes algoritmos dados esta función de comparación uniforme.

cody
fuente
Quicksort puede repetir comparaciones si se elige el mismo elemento como pivote más de una vez (puede aparecer varias veces en la lista).
Raphael
2
@Raphael: Mi elección de palabras fue pobre: ​​quise decir repetir comparaciones entre ocurrencias de elementos, que no ocurren más de una vez en Quicksort.
cody
1
@Gilles: Puedo estar equivocado, pero no creo que la transitividad de la comparación sea crucial para el tiempo de ejecución de la mayoría de los algoritmos de clasificación; la corrección seguramente, pero ese no era el objeto de la pregunta.
cody
@Gilles: El OP no pregunta sobre algoritmos que realmente ordenan. Está preguntando qué sucede con los algoritmos de clasificación estándar cuando todas las comparaciones se reemplazan con lanzamientos de monedas. Los algoritmos resultantes no se ordenan (excepto con poca probabilidad), pero siguen siendo algoritmos bien definidos.
JeffE
@JeffE Entiendo eso ahora. No es así como leí la pregunta inicialmente, pero dados los comentarios del autor de la pregunta, eso era lo que quería decir.
Gilles 'SO- deja de ser malvado'
2

Combinar con un comparador aleatorio justo no es justo. No tengo una prueba, pero tengo evidencia empírica MUY fuerte. (Justo significa distribuido 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
fuente
¿Haskell o Caml están de moda ahora?
Yai0Phah
No tengo idea. Pero Haskell es mi idioma favorito, así que programé esto en él; la coincidencia de patrones lo hizo más fácil.
Thomas Eding
0

Christiansen, Danilenko y Dylus responden una pregunta muy relacionada en Todos los tipos de permutaciones (Pearl funcional) . Ejecutan un algoritmo de clasificación en la mónada de la lista , que esencialmente simula el no determinismo, devolviendo todas las permutaciones de una lista de entrada dada. La propiedad interesante es que cada permutación se devuelve exactamente una vez.

Citando del resumen:

...

En este artículo, analizamos la combinación de no determinismo y clasificación de una manera diferente: dada una función de clasificación, la aplicamos a un predicado no determinista para obtener una función que enumera las permutaciones de la lista de entrada. Llegamos al fondo de las propiedades necesarias de los algoritmos de clasificación y los predicados en juego, así como discutimos las variaciones del no determinismo modelado.

Además de eso, formulamos y probamos un teorema que establece que no importa qué función de clasificación usemos, la función de permutación correspondiente enumera todas las permutaciones de la lista de entrada. Utilizamos teoremas libres, que se derivan solo del tipo de una función, para probar el enunciado.

Petr Pudlák
fuente