Algoritmi di ordinamento che accettano un comparatore casuale

https://cs.stackexchange.com/questions/2336

16-10-2019
|

Domanda

generica algoritmi di ordinamento generalmente fa una serie di dati per ordinare e una funzione comparatore che può confrontare due elementi singoli. Se il comparatore è un relation¹ ordine, allora l'uscita dell'algoritmo è una lista / array ordinato.

mi chiedo se gli algoritmi di ordinamento sarebbe in realtà lavoro con un comparatore che non è una relazione cassa (in particolare uno che restituisce un risultato casuale su ogni confronto). Con il termine "lavoro" Voglio dire qui che continuino restituire una permutazione di loro input e corrono al loro complessità temporale tipicamente citato (al contrario di degradante per la peggiore delle ipotesi sempre, o andare in un ciclo infinito, o gli elementi mancanti). L'ordinamento dei risultati sarebbe undefined tuttavia. Ancora meglio, l'ordinamento risultante sarebbe una distribuzione uniforme quando il comparatore è un coin flip.

Dal mio calcolo mentale di massima sembra che un merge sort sarebbe bene con questo e mantenere lo stesso costo di runtime e produrre un giusto ordinamento casuale. Penso che qualcosa di simile a un rapido sorta Sarebbe tuttavia degenerata, forse non finire, e non essere equo.

Quali altri algoritmi di ordinamento (diversi merge sort) funzionerebbero come descritto con un comparatore casuale?

Per riferimento, un comparatore è un rapporto ordine se è una funzione appropriata (deterministica) e soddisfa gli assiomi di una relazione d'ordine:
- è deterministica:. compare(a,b) per un particolare a e b restituisce sempre lo stesso risultato
- è transitiva: compare(a,b) and compare(b,c) implies compare( a,c )
- è compare(a,b) and compare(b,a) implies a == b antisimmetrica

(supponga che tutti gli elementi di input sono distinti, quindi riflessività non è un problema.)

Un comparatore casuale viola tutte queste regole. Ci sono tuttavia comparatori che non sono relazioni d'ordine ancora non sono casuali (per esempio potrebbero violare forse solo una regola, e solo per particolari elementi nel set).

Soluzione

Quindi, in pratica, si vuole sapere se c'è qualche algoritmo di ordinamento che non degrada dalla custodia media se viene data la funzione di confronto simile a:

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

... dove Random.Next () è un metodo che produrrà un numero intero casuale generata tra un determinato inclusiva inferiore e superiore.

La risposta è che la maggior parte algoritmi di ordinamento di base eseguiranno base al loro caso medio, perché obbediscono almeno una delle seguenti due condizioni:

Un confronto tra due elementi unici non viene mai fatta due volte in una sorta, e / o
In ogni iterazione del genere, la corretta posizione di almeno un elemento è determinato e in modo tale elemento è mai confrontata nuovamente.

Per esempio, SelectionSort un'iterazione sottoelenco di elementi indifferenziati, trova l'elemento "minimo" e / o "più" (confrontando ciascuno al più grande finora), posti nella sua posizione corretta e ripete. Di conseguenza, anche con un comparatore non deterministico, alla fine di ogni iterazione dell'algoritmo avrà trovato un valore che riflette è almeno o più grande, swap con l'elemento nella posizione in cui sta cercando di determinare, e non ritiene tale elemento di nuovo, così obbedisce Condizione 2. Tuttavia, una a e B possono essere confrontati più volte durante questo processo (come l'esempio più estremo, considerare diversi passaggi di SelectionSort su un array di scelti in ordine inverso) in modo viola Condizione 1 .

MergeSort obbedisce Condizione 1, ma non 2; come sub-array sono uniti, elementi nello stesso sub-array (sul lato sinistro o destro) non sono confrontate tra loro perché è già stato determinato che gli elementi su quel lato della matrice sono in ordine tra loro; l'algoritmo confronta solo l'elemento almeno unmerged di ogni sottoarray all'altro per determinare quale è minore e dovrebbe andare il prossimo nella lista unito. Ciò significa che qualsiasi due oggetti unici A e B saranno confrontati tra loro un massimo di un tempo, ma indice "finale" qualsiasi dell'elemento nella collezione non è nota fino al completamento dell'algoritmo.

obbedisce InsertionSort unica condizione 1 come bene anche se il suo aspetto strategia globale e la complessità di più come SelectionSort. Ogni elemento indifferenziati viene confrontato con elementi ordinati, più-prime, finché si è trovato che è inferiore dell'elemento ispezionato. l'elemento è inserito in quel punto, e quindi l'elemento successivo viene considerato. Il risultato è che l'ordine relativo di ogni A e B è determinato da un comparatore, e ulteriori confronti tra che A e B vengono mai eseguite, ma la posizione finale di qualsiasi elemento non può essere conosciuto fino a quando tutti gli elementi sono considerati.

QuickSort obbedisce sia Condizioni. Ad ogni livello, un perno è scelto e disposto in modo che la "sinistra" lato contiene elementi meno il perno e la parte "destra" contiene elementi superiori al perno. Il risultato di tale livello è QuickSort (sinistra) + perno + QuickSort (destra) che in pratica significa la posizione dell'elemento di perno è noto (uno più grande indice della lunghezza del lato sinistro), il perno viene mai rispetto a qualsiasi altro elemento dopo che è stato scelto come un perno (esso può essere confrontato con elementi assiali precedenti, ma questi elementi sono anche noti e non sono inclusi in ogni sottoarray) e ogni a e B che finiscono sui lati opposti del perno sono mai rispetto. Nella maggior parte delle implementazioni di puro QuickSort, il caso base è un elemento, al quale punto il suo indice corrente è il suo indice finale e nessun ulteriore confronto sono fatti.

L'ordinamento unica comparativo posso pensare che non obbedire né condizione è una BubbleSort non ottimizzato. Se l'ordinamento non accetta che la X più grandi elementi sono al loro posto dopo l'esecuzione di passaggi X, e / o utilizza un "doppio controllo" passa per verificare l'elenco è ordinato, il genere sarà considerata solo"Done" quando il comparatore casuale è ritornato -1 o 0 per ogni due elementi adiacenti nella lista durante un passaggio e quindi senza swap sono stati eseguiti (un evento che, se veramente casuale, avverrebbe con probabilità $ (2/3) ^ {N-1} $, per una parte relativamente piccola lista di 25 elementi, che è uno nel 2000 possibilità, mentre per 100 elementi la probabilità è 3.7 * 10 ^-18). Poiché il valore massimo assoluto del risultato degli aumenti di confronto, la probabilità per qualsiasi confronto a negativo o nullo ritorno diminuisce verso .5, rendendo la possibilità di terminare l'algoritmo che molto meno probabile (la possibilità di 99 lanci della moneta tutte le teste di atterraggio , che è fondamentalmente ciò che questo si riduce a, è di 1 a 1,2 * 10 ³⁰)

Modifica molto tempo dopo: Ci sono alcuni "tipi" appositamente progettate come esempi di cosa non fare che incorporano un comparatore casuale; forse il più famoso è Stupid Sort. "Dato un elenco, se l'elenco non è in ordine, mischiare la lista e controllare di nuovo". Teoricamente lo farà eventualmente ha colpito a destra permutazione di valori, proprio come il "BubbleSort non ottimizzato" di cui sopra, ma il caso medio è fattoriale-tempo (N! / 2), e per il compleanno problema (dopo il numero sufficiente di permutazioni casuali si diventa più probabile incontrare permutazioni duplicati rispetto a quelli unici) v'è la possibilità diverso da zero dell'algoritmo mai completato a ufficialmente l'algoritmo è tempo illimitato.

Altri suggerimenti

Qualunque algoritmo che confronta gli stessi due elementi due volte non è un algoritmo molto intelligente, e in particolare ad un algoritmo dovrebbe essere meno efficaci rispetto alla più comune ordinamento algoritmi (merge-sort, quicksort, bolla-ordinamento, inserimento-sort). Qualsiasi algoritmo che confronta coppie di elementi di più di una volta ha la stessa (medio) costo runtime indipendentemente dal comportamento della funzione di confronto, se maggiore di e meno che sono risultati equiprobabili . In caso contrario, si può almeno garantire che l'algoritmo di ordinamento non fa peggio del caso peggiore tempo di esecuzione, che è meno di $ O (n ^ 2) $ per qualsiasi algoritmo di ordinamento decente.

Io credo che una domanda più interessante è come e un tale algoritmo avrebbe eseguito se la funzione di confronto ha dato solo la risposta giusta, per esempio, il 90% dei casi in media. In quanto bene avrebbe eseguito intendo di rispondere alla domanda: "Qual è, in media, il numero di elementi fuori luogo durante l'ordinamento di un elenco di dimensioni $ n $ da questo algoritmo"

Edit: Il problema è più interessante in quanto ho pensato, ecco quindi un ulteriore commento:

Supponiamo che il vostro $ confrontare $ funzione è fiera , che è di $ confrontare (x, y) = True $ con probabilità $ 1/2 $ e $ false $ con probabilità anche $ 1/2 $. Ricordiamo il tipo di inserimento (stile funzionale) algoritmo:

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 []

Il tempo di funzionamento di questo algoritmo è quindi $ \ sum_ {k = 1} ^ {n} f (k) $ dove $ n $ è la lunghezza di $ l $ e $ f (k) $ è la media tempo di esecuzione $ inserto $ su una lista di lunghezza $ k $, che è se contiamo solo le applicazioni di $: $ ad avere dei costi (se contiamo distruzioni così, la formula è simile)

Ora, per $ Confrontare $ come descritto in precedenza, questo è abbastanza piccolo: il numero medio di passaggi eseguiti mediante l'inserimento è data da:

$$ \ sum_ {i = 1} ^ {k} i 2 ^ {- i} \ leq \ sum_ {i = 1} ^ {\ infty} i 2 ^ {- i} = 2 $$

Questo dà un tempo medio di funzionamento di $ O (2n) $ per insertion sort, che è significativamente migliore rispetto al $ O (n ^ 2) $ dato da una funzione di confronto "decente".

Sarebbe divertente lavorare i tempi medi di funzionamento per i diversi altri algoritmi dato questa funzione uniforme confrontare.

Mergesort con un comparatore a caso giusto non è giusto. Io non avere una prova, ma ho molto forte evidenza empirica. (Fiera significa uniformemente distribuito.)

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

Una domanda molto relativa di soluzione Tutto tipi di permutazioni (Pearl funzionale) di Christiansen, Danilenko e Dylus. Corrono un algoritmo di ordinamento nel lista monade , che simula essenzialmente non determinismo, restituendo tutte le permutazioni di una data lista di input. La proprietà interessante è che ogni permutazione viene restituito esattamente una volta.

Citando l'abstract:

...

In questo articolo esaminiamo la combinazione di non-determinismo e smistamento in una luce diversa: data una funzione di ordinamento, applichiamo ad un predicato non deterministico per ottenere una funzione che enumera permutazioni della lista di input. Arriviamo al fondo della necessaria proprietà degli algoritmi di ordinamento e predicati in gioco, nonché come discutere variazioni del non determinismo modellato.

In cima a quello, formuliamo e dimostrare un teorema che indica che la importa quale funzione di ordinamento usiamo, la permutazione corrispondente funzione enumera tutte le permutazioni della lista in ingresso. Noi usiamo teoremi liberi, che sono derivati ??dal tipo di una funzione sola, per dimostrare la dichiarazione.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a cs.stackexchange