Quale algoritmo di ordinamento implementa Swift per la sua libreria standard?



algorithm sorting (2)

Mi chiedo come sia implementata la funzione di sort di Swift. Quale algoritmo di ordinamento utilizza: è un mergesort, quicksort o qualcosa di completamente diverso? Quali sono le garanzie di tempistica / complessità fornite da questa funzione?

Non riesco a trovare alcuna indicazione di come sia implementato online o nella documentazione ufficiale.


Answer #1

Non una risposta definitiva, solo congetture - solo il team di sviluppatori di Swift std lib può dirlo e loro no (grattalo, @ martin-r mostra come puoi dirlo tramite il debugger! È un ordinamento ibrido di introsort / insertion):

I documenti per l' sort non dichiarano la complessità. Affermano che non è stabile (cioè che non è garantito che elementi uguali rimangano nel loro ordine originale), il che suggerisce che non è un tipo di unione (che di solito è stabile).

Esistono diverse funzioni nella libreria di librerie Swift che sembrano essere lì come aiutanti per altre funzioni nella libreria. C'è una funzione di partition , che è un elemento chiave per ordinare rapidamente. Nelle primissime beta di Swift, c'erano due tipi oltre a quello senza marchio: quickSort e insertionSort .

L'implementazione GNU dell'ordinamento della libreria std C ++ usa un ibrido di un introsort (che è esso stesso un ibrido di quicksort e heapsort) a volte combinato con un ordinamento di inserzione. Quindi è possibile che queste due varianti siano state originariamente implementate come blocchi predefiniti per l'effettiva funzione di ordinamento.

quickSort e insertionSort scomparsi nei beta successivi: se l'ordinamento fosse un ibrido di entrambi i casi, sarebbe quickSort uno. partition è ancora lì, presumibilmente poiché è utile come funzione autonoma.


Answer #2

Aggiornamento 2: Come possiamo vedere in Sort.swift , sort() ora utilizza un "timsort modificato" in Swift 5. Timsort è un

... algoritmo di ordinamento stabile ibrido, derivato dall'unione dell'ordinamento e dall'ordinamento dell'inserzione

Nel peggiore dei casi, Timsort prende i confronti O (n log n) per ordinare una matrice di n elementi. Nel migliore dei casi, che si verifica quando l'ingresso è già ordinato, viene eseguito in tempo lineare, il che significa che è un algoritmo di ordinamento adattivo.

Ciò significa che sort() sembra essere un ordinamento stabile in Swift 5, ma è comunque un dettaglio di implementazione. La documentazione di MutableCollection.sort afferma che

Non è garantito che l'algoritmo di ordinamento sia stabile. Un ordinamento stabile conserva l'ordine relativo degli elementi che si equivalgono.

Vedi anche L' ordinamento () è stabile in Swift 5? nel forum Swift:

L'algoritmo è stato reso stabile solo di recente in preparazione di una proposta per renderlo garantito come tale.

Aggiornamento: Swift è open source ora e in

si può vedere che l'ordinamento di una raccolta viene effettuato utilizzando introsort con una profondità di ricorsione massima di 2 * piano (log_2 (N)). Passa all'ordinamento di inserzione per le partizioni con meno di 20 elementi o all'hortort se viene raggiunta la profondità di ricorsione.

Vecchia risposta: definizione di una struttura Comparable personalizzata e impostazione nel punto di interruzione in < :

struct MyStruct : Comparable {
    let val : Int
}

func ==(x: MyStruct, y: MyStruct) -> Bool {
    println("\(x.val) ==  \(y.val)")
    return x.val == y.val
}
func <(x: MyStruct, y: MyStruct) -> Bool {
    println("\(x.val) < \(y.val)")
    return x.val < y.val // <--- SET BREAKPOINT HERE
}

var array = [MyStruct]()
for _ in 1 ... 30 {
    array.append(MyStruct(val: Int(arc4random_uniform(1000))))
}
sort(&array)

mostra il seguente backtrace dello stack:

(lldb) bt
* thread #1: tid = 0x5a00, 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
  * frame #0: 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22
    frame #1: 0x00000001001cb62b sort`protocol witness for Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool in conformance sort.MyStruct : Swift._Comparable + 27 at main.swift:20
    frame #2: 0x00000001000f5a98 sort`Swift._partition (inout A, Swift.Range) -> A.Index + 3224
    frame #3: 0x00000001000f756a sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 2138
    frame #4: 0x00000001000f6c01 sort`Swift._introSort (inout A, Swift.Range) -> () + 1233
    frame #5: 0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607
    frame #6: 0x000000010013ea77 sort`partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183
    frame #7: 0x000000010013eaf8 sort`partial apply forwarder for reabstraction thunk helper  from @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) to @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out ()) + 56
    frame #8: 0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475
    frame #9: 0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157
    frame #10: 0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29
    frame #11: 0x00000001001cbdca sort`main + 42 at main.swift:0
    frame #12: 0x00007fff8aa9a5fd libdyld.dylib`start + 1

e più tardi

(lldb) bt
* thread #1: tid = 0x5a00, 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
  * frame #0: 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22
    frame #1: 0x00000001001cb62b sort`protocol witness for Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool in conformance sort.MyStruct : Swift._Comparable + 27 at main.swift:20
    frame #2: 0x00000001000f449e sort`Swift._insertionSort (inout A, Swift.Range) -> () + 2958
    frame #3: 0x00000001000f730e sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 1534
    frame #4: 0x00000001000f797d sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 3181
    frame #5: 0x00000001000f6c01 sort`Swift._introSort (inout A, Swift.Range) -> () + 1233
    frame #6: 0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607
    frame #7: 0x000000010013ea77 sort`partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183
    frame #8: 0x000000010013eaf8 sort`partial apply forwarder for reabstraction thunk helper  from @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) to @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out ()) + 56
    frame #9: 0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475
    frame #10: 0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157
    frame #11: 0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29
    frame #12: 0x00000001001cbdca sort`main + 42 at main.swift:0
    frame #13: 0x00007fff8aa9a5fd libdyld.dylib`start + 1

Ciò conferma la congettura della risposta di Airspeed secondo cui l' introsort viene utilizzato in combinazione con l'ordinamento di inserzione per le gamme più piccole.

Se l'array ha meno di 20 elementi, viene utilizzato solo l'ordinamento per inserzione. Ciò potrebbe indicare che la soglia per passare dall'introsort all'ordinamento di inserzione è 20.

Naturalmente l'implementazione potrebbe cambiare in futuro.





time-complexity