Prestazioni veloci: ordinamento di array

Stavo implementando un algoritmo in Swift e ho notato che la performance era molto scarsa. Dopo aver scavato più a fondo, mi sono reso conto che uno dei colli di bottiglia era qualcosa di semplice come l’ordinamento degli array. La parte rilevante è qui:

let n = 1000000 var x = [Int](repeating: 0, count: n) for i in 0..<n { x[i] = random() } // start clock here let y = sort(x) // stop clock here 

In C ++, un’operazione simile richiede 0.06 sul mio computer.

In Python ci vogliono 0,6 secondi (senza trucchi, solo y = ordinati (x) per un elenco di numeri interi).

In Swift ci vogliono 6 se lo compilo con il seguente comando:

 xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx` 

E ci vogliono ben 88 se lo compilo con il seguente comando:

 xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx` 

I tempi in Xcode con build “Release” vs “Debug” sono simili.

Cosa c’è di sbagliato qui? Potrei capire alcune perdite di prestazioni rispetto al C ++, ma non un rallentamento di 10 volte rispetto al Python puro.


Edit: mweathers ha notato che il passaggio da -O3 a -Ofast fa funzionare questo codice quasi alla stessa velocità della versione C ++! Tuttavia, -Ofast cambia la semantica della lingua molto – nel mio test, disabilita i controlli per overflow integer e overflow di indicizzazione degli array . Ad esempio, con -Ofast il seguente codice Swift gira in modo silenzioso senza -Ofast (e stampa un po ‘di spazzatura):

 let n = 10000000 print(n*n*n*n*n) let x = [Int](repeating: 10, count: n) print(x[n]) 

Quindi, non è quello che vogliamo; l’intero punto di Swift è che abbiamo le reti di sicurezza sul posto. Ovviamente le reti di sicurezza hanno un impatto sulle prestazioni, ma non dovrebbero rendere i programmi 100 volte più lenti. Ricorda che Java controlla già i limiti dell’array, e nei casi tipici il rallentamento è di un fattore molto inferiore a 2. E in Clang e GCC abbiamo ottenuto -ftrapv per il controllo degli overflow integer (firmati), e non è così lento, .

Da qui la domanda: come possiamo ottenere una prestazione ragionevole in Swift senza perdere le reti di sicurezza?


Modifica 2: ho fatto un po ‘più di benchmarking, con loop molto semplici sulla falsariga di

 for i in 0..<n { x[i] = x[i] ^ 12345678 } 

(Qui l’operazione xor è lì solo per poter trovare più facilmente il loop pertinente nel codice assembly. Ho provato a selezionare un’operazione facile da individuare ma anche “innocua” nel senso che non dovrebbe richiedere alcun controllo correlato to integer overflow.)

Ancora una volta, c’è stata un’enorme differenza nelle prestazioni tra -O3 e -Ofast . Quindi ho dato un’occhiata al codice assembly:

  • Con -Ofast ottengo più o meno quello che mi aspetterei. La parte rilevante è un loop con 5 istruzioni di linguaggio macchina.

  • Con -O3 ottengo qualcosa che andava oltre la mia più sfrenata immaginazione. Il ciclo interno si estende su 88 righe di codice assembly. Non ho cercato di capire tutto, ma le parti più sospette sono 13 invocazioni di “callq _swift_retain” e altre 13 chiamate di “callq _swift_release”. Cioè, 26 chiamate di subroutine nel loop interno !


Modifica 3: nei commenti, Ferruccio ha chiesto dei benchmark che siano equi nel senso che non si basano su funzioni integrate (ad es. Sort). Penso che il seguente programma sia un buon esempio:

 let n = 10000 var x = [Int](repeating: 1, count: n) for i in 0..<n { for j in 0..<n { x[i] = x[j] } } 

Non c’è aritmetica, quindi non dobbiamo preoccuparci di overflow integer. L’unica cosa che facciamo è solo un sacco di riferimenti di matrice. E i risultati sono qui: Swift -O3 perde per fattore quasi 500 in confronto a -Ottimo:

  • C ++ -O3: 0,05 s
  • C ++ -O0: 0,4 s
  • Java: 0,2 s
  • Python con PyPy: 0,5 s
  • Python: 12 s
  • Veloce: veloce: 0,05 s
  • Swift -O3: 23 s
  • Swift -O0: 443 s

(Se sei preoccupato che il compilatore possa ottimizzare completamente i loop senza punti, puoi cambiarlo ad esempio x[i] ^= x[j] e aggiungere un’istruzione print che restituisca x[0] . Questo non cambia nulla ; i tempi saranno molto simili).

E sì, qui l’implementazione di Python è stata una stupida implementazione di Python pura con un elenco di interi e cicli annidati. Dovrebbe essere molto più lento di Swift non ottimizzato. Qualcosa sembra essere seriamente rotto con Swift e l’indicizzazione degli array.


Modifica 4: questi problemi (così come altri problemi di prestazioni) sembrano essere stati risolti in Xcode 6 beta 5.

Per l’ordinamento, ora ho i seguenti tempi:

  • clang ++ -O3: 0,06 s
  • swiftc -Ottimo: 0,1 s
  • swiftc -O: 0,1 s
  • swiftc: 4 s

Per cicli annidati:

  • clang ++ -O3: 0,06 s
  • swiftc: veloce: 0.3 s
  • swiftc -O: 0.4 s
  • swiftc: 540 s

Sembra che non ci sia più alcun motivo per usare il non sicuro -Ofast (aka -Ounchecked ); plain -O produce codice altrettanto buono.

tl; dr Swift ora è veloce come C da questo benchmark utilizzando il livello di ottimizzazione del rilascio predefinito [-O].

Ecco un quicksort sul posto in Swift:

 func quicksort_swift(inout a:CInt[], start:Int, end:Int) { if (end - start < 2){ return } var p = a[start + (end - start)/2] var l = start var r = end - 1 while (l <= r){ if (a[l] < p){ l += 1 continue } if (a[r] > p){ r -= 1 continue } var t = a[l] a[l] = a[r] a[r] = t l += 1 r -= 1 } quicksort_swift(&a, start, r + 1) quicksort_swift(&a, r + 1, end) } 

E lo stesso in C:

 void quicksort_c(int *a, int n) { if (n < 2) return; int p = a[n / 2]; int *l = a; int *r = a + n - 1; while (l <= r) { if (*l < p) { l++; continue; } if (*r > p) { r--; continue; } int t = *l; *l++ = *r; *r-- = t; } quicksort_c(a, r - a + 1); quicksort_c(l, a + n - l); } 

Entrambi funzionano:

 var a_swift:CInt[] = [0,5,2,8,1234,-1,2] var a_c:CInt[] = [0,5,2,8,1234,-1,2] quicksort_swift(&a_swift, 0, a_swift.count) quicksort_c(&a_c, CInt(a_c.count)) // [-1, 0, 2, 2, 5, 8, 1234] // [-1, 0, 2, 2, 5, 8, 1234] 

Entrambi sono chiamati nello stesso programma scritto.

 var x_swift = CInt[](count: n, repeatedValue: 0) var x_c = CInt[](count: n, repeatedValue: 0) for var i = 0; i < n; ++i { x_swift[i] = CInt(random()) x_c[i] = CInt(random()) } let swift_start:UInt64 = mach_absolute_time(); quicksort_swift(&x_swift, 0, x_swift.count) let swift_stop:UInt64 = mach_absolute_time(); let c_start:UInt64 = mach_absolute_time(); quicksort_c(&x_c, CInt(x_c.count)) let c_stop:UInt64 = mach_absolute_time(); 

Questo converte i tempi assoluti in secondi:

 static const uint64_t NANOS_PER_USEC = 1000ULL; static const uint64_t NANOS_PER_MSEC = 1000ULL * NANOS_PER_USEC; static const uint64_t NANOS_PER_SEC = 1000ULL * NANOS_PER_MSEC; mach_timebase_info_data_t timebase_info; uint64_t abs_to_nanos(uint64_t abs) { if ( timebase_info.denom == 0 ) { (void)mach_timebase_info(&timebase_info); } return abs * timebase_info.numer / timebase_info.denom; } double abs_to_seconds(uint64_t abs) { return abs_to_nanos(abs) / (double)NANOS_PER_SEC; } 

Ecco un riepilogo dei livelli di ottimizzazione del compilatore:

 [-Onone] no optimizations, the default for debug. [-O] perform optimizations, the default for release. [-Ofast] perform optimizations and disable runtime overflow checks and runtime type checks. 

Tempo in secondi con [-Onone] per n = 10_000 :

 Swift: 0.895296452 C: 0.001223848 

Ecco l'ordinamento () di Swift per n = 10_000 :

 Swift_builtin: 0.77865783 

Ecco [-O] per n = 10_000 :

 Swift: 0.045478346 C: 0.000784666 Swift_builtin: 0.032513488 

Come puoi vedere, le prestazioni di Swift sono migliorate di un fattore 20.

Come per la risposta di Mweathers , l'impostazione [-Ostast] fa la vera differenza, risultando in questi tempi per n = 10_000 :

 Swift: 0.000706745 C: 0.000742374 Swift_builtin: 0.000603576 

E per n = 1_000_000 :

 Swift: 0.107111846 C: 0.114957179 Swift_sort: 0.092688548 

Per confronto, questo è con [-Onone] per n = 1_000_000 :

 Swift: 142.659763258 C: 0.162065333 Swift_sort: 114.095478272 

Quindi Swift senza ottimizzazioni era quasi 1000x più lento di C in questo benchmark, in questa fase del suo sviluppo. D'altra parte, con entrambi i compilatori impostati su [-Obast] Swift ha effettivamente funzionato almeno altrettanto bene se non leggermente migliore di C.

È stato sottolineato che [-Ottimo] cambia la semantica del linguaggio, rendendolo potenzialmente pericoloso. Questo è ciò che Apple afferma nelle note di rilascio di Xcode 5.0:

Un nuovo livello di ottimizzazione: veloce, disponibile in LLVM, consente ottimizzazioni aggressive. -Fast rilassa alcune restrizioni conservative, principalmente per operazioni in virgola mobile, che sono sicure per la maggior parte del codice. Può produrre importanti vittorie ad alte prestazioni dal compilatore.

Lo fanno tutti ma lo difendono. Che sia saggio o meno non saprei dire, ma da quello che posso dire sembra abbastanza ragionevole da usare [-Fast] in una versione se non stai facendo aritmetica in virgola mobile ad alta precisione e non hai fiducia in numero intero o gli overflow di array sono possibili nel tuo programma. Se hai bisogno di alte prestazioni e controlli di overflow / aritmetica precisa, per il momento scegli un'altra lingua.

AGGIORNAMENTO BETA 3:

n = 10_000 con [-O] :

 Swift: 0.019697268 C: 0.000718064 Swift_sort: 0.002094721 

Swift in generale è un po 'più veloce e sembra che l'ordinamento predefinito di Swift sia cambiato in modo significativo.

AGGIORNAMENTO FINALE:

[-Onone] :

 Swift: 0.678056695 C: 0.000973914 

[-O] :

 Swift: 0.001158492 C: 0.001192406 

[-Ounchecked] :

 Swift: 0.000827764 C: 0.001078914 

TL; DR : Sì, l’unica implementazione della lingua Swift è lenta, al momento . Se hai bisogno di codice veloce, numerico (e altri tipi di codice, presumibilmente), vai con un altro. In futuro, dovresti rivalutare la tua scelta. Potrebbe essere abbastanza buono per la maggior parte del codice applicativo che è scritto ad un livello più alto, però.

Da quello che sto vedendo in SIL e LLVM IR, sembra che abbiano bisogno di un sacco di ottimizzazioni per la rimozione di retain e release, che potrebbero essere implementati in Clang (per Objective-C), ma non li hanno ancora portati. Questa è la teoria con cui sto andando (per ora … ho ancora bisogno di confermare che Clang fa qualcosa al riguardo), dal momento che un profiler eseguito sull’ultimo caso di test di questa domanda produce questo risultato “carino”:

Profilazione temporale su -O3Profilazione temporale su -Dast

Come è stato detto da molti altri, -Ofast è assolutamente pericoloso e cambia la semantica della lingua”. Per me, è nella fase “Se lo userai, usa solo un’altra lingua”. Valuterò questa scelta più tardi, se cambierà.

-O3 ci fa un sacco di chiamate swift_retain e swift_release che, onestamente, non sembrano come dovrebbero essere lì per questo esempio. L’ottimizzatore dovrebbe averli elidati (la maggior parte) AFAICT, poiché conosce la maggior parte delle informazioni sull’array e sa di avere (almeno) un forte riferimento ad esso.

Non dovrebbe emettere più ritardi quando non chiama nemmeno funzioni che potrebbero rilasciare gli oggetti. Non penso che un costruttore di array possa restituire un array più piccolo di quello richiesto, il che significa che molti controlli emessi sono inutili. Sa anche che il numero intero non sarà mai superiore a 10k, quindi i controlli di overflow possono essere ottimizzati (non a causa di -Ofast strana -Ofast , ma a causa della semantica del linguaggio (nient’altro sta cambiando quel var né può accedervi e aggiungere a 10k è sicuro per il tipo Int ).

Il compilatore potrebbe non essere in grado di decomprimere l’array o gli elementi dell’array, dato che vengono passati a sort() , che è una funzione esterna e deve ottenere gli argomenti che si aspettano. Questo ci renderà necessario utilizzare i valori Int indirettamente, il che renderebbe un po ‘più lento. Questo potrebbe cambiare se la funzione generica sort() (non nel modo multi-metodo) fosse disponibile per il compilatore e venisse sottolineata.

Questo è un linguaggio (pubblicamente) molto nuovo, e sta passando per quello che presumo sono molti cambiamenti, dal momento che ci sono persone (pesantemente) coinvolte nella lingua Swift che chiedono feedback e tutti dicono che la lingua non è finita e modificare.

Codice utilizzato:

 import Cocoa let swift_start = NSDate.timeIntervalSinceReferenceDate(); let n: Int = 10000 let x = Int[](count: n, repeatedValue: 1) for i in 0..n { for j in 0..n { let tmp: Int = x[j] x[i] = tmp } } let y: Int[] = sort(x) let swift_stop = NSDate.timeIntervalSinceReferenceDate(); println("\(swift_stop - swift_start)s") 

PS: Non sono un esperto di Objective-C, né tutte le strutture di Cocoa , Objective-C o dei runtime di Swift. Potrei anche assumere alcune cose che non ho scritto.

Ho deciso di dare un’occhiata a questo per divertimento, e qui ci sono i tempi che ottengo:

 Swift 4.0.2 : 0.83s (0.74s with `-Ounchecked`) C++ (Apple LLVM 8.0.0): 0.74s 

veloce

 // Swift 4.0 code import Foundation func doTest() -> Void { let arraySize = 10000000 var randomNumbers = [UInt32]() for _ in 0.. 

risultati:

Swift 1.1

 xcrun swiftc --version Swift version 1.1 (swift-600.0.54.20) Target: x86_64-apple-darwin14.0.0 xcrun swiftc -O SwiftSort.swift ./SwiftSort Elapsed time: 1.02204304933548 

Swift 1.2

 xcrun swiftc --version Apple Swift version 1.2 (swiftlang-602.0.49.6 clang-602.0.49) Target: x86_64-apple-darwin14.3.0 xcrun -sdk macosx swiftc -O SwiftSort.swift ./SwiftSort Elapsed time: 0.738763988018036 

Swift 2.0

 xcrun swiftc --version Apple Swift version 2.0 (swiftlang-700.0.59 clang-700.0.72) Target: x86_64-apple-darwin15.0.0 xcrun -sdk macosx swiftc -O SwiftSort.swift ./SwiftSort Elapsed time: 0.767306983470917 

Sembra essere la stessa performance se compilo con -Ounchecked .

Swift 3.0

 xcrun swiftc --version Apple Swift version 3.0 (swiftlang-800.0.46.2 clang-800.0.38) Target: x86_64-apple-macosx10.9 xcrun -sdk macosx swiftc -O SwiftSort.swift ./SwiftSort Elapsed time: 0.939633965492249 xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift ./SwiftSort Elapsed time: 0.866258025169373 

Sembra esserci stata una regressione delle prestazioni da Swift 2.0 a Swift 3.0, e vedo anche una differenza tra -O e -Ounchecked per la prima volta.

Swift 4.0

 xcrun swiftc --version Apple Swift version 4.0.2 (swiftlang-900.0.69.2 clang-900.0.38) Target: x86_64-apple-macosx10.9 xcrun -sdk macosx swiftc -O SwiftSort.swift ./SwiftSort Elapsed time: 0.834299981594086 xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift ./SwiftSort Elapsed time: 0.742045998573303 

Swift 4 migliora di nuovo le prestazioni, mantenendo uno spazio tra -O e -Ounchecked . -O -whole-module-optimization non sembrava fare la differenza.

C ++

 #include  #include  #include  #include  #include  using namespace std; using namespace std::chrono; int main(int argc, const char * argv[]) { const auto arraySize = 10000000; vector randomNumbers; for (int i = 0; i < arraySize; ++i) { randomNumbers.emplace_back(arc4random_uniform(arraySize)); } const auto start = high_resolution_clock::now(); sort(begin(randomNumbers), end(randomNumbers)); const auto end = high_resolution_clock::now(); cout << randomNumbers[0] << "\n"; cout << "Elapsed time: " << duration_cast>(end - start).count() << "\n"; return 0; } 

risultati:

Apple Clang 6.0

 clang++ --version Apple LLVM version 6.0 (clang-600.0.54) (based on LLVM 3.5svn) Target: x86_64-apple-darwin14.0.0 Thread model: posix clang++ -O3 -std=c++11 CppSort.cpp -o CppSort ./CppSort Elapsed time: 0.688969 

Apple Clang 6.1.0

 clang++ --version Apple LLVM version 6.1.0 (clang-602.0.49) (based on LLVM 3.6.0svn) Target: x86_64-apple-darwin14.3.0 Thread model: posix clang++ -O3 -std=c++11 CppSort.cpp -o CppSort ./CppSort Elapsed time: 0.670652 

Apple Clang 7.0.0

 clang++ --version Apple LLVM version 7.0.0 (clang-700.0.72) Target: x86_64-apple-darwin15.0.0 Thread model: posix clang++ -O3 -std=c++11 CppSort.cpp -o CppSort ./CppSort Elapsed time: 0.690152 

Apple Clang 8.0.0

 clang++ --version Apple LLVM version 8.0.0 (clang-800.0.38) Target: x86_64-apple-darwin15.6.0 Thread model: posix clang++ -O3 -std=c++11 CppSort.cpp -o CppSort ./CppSort Elapsed time: 0.68253 

Apple Clang 9.0.0

 clang++ --version Apple LLVM version 9.0.0 (clang-900.0.38) Target: x86_64-apple-darwin16.7.0 Thread model: posix clang++ -O3 -std=c++11 CppSort.cpp -o CppSort ./CppSort Elapsed time: 0.736784 

Verdetto

Al momento della stesura di questo articolo, l'ordinamento di Swift è veloce, ma non ancora veloce come l'ordinamento di C ++ quando compilato con -O , con i compilatori e le librerie di cui sopra. Con -Ounchecked , sembra essere veloce come C ++ in Swift 4.0.2 e Apple LLVM 9.0.0.

Da The Swift Programming Language :

La libreria standard di Sort Function Swift fornisce una funzione chiamata sort, che ordina una matrice di valori di un tipo noto, in base all’output di una chiusura di ordinamento fornita dall’utente. Una volta completato il processo di ordinamento, la funzione di ordinamento restituisce una nuova matrice dello stesso tipo e dimensione di quella precedente, con i suoi elementi nell’ordine ordinato corretto.

La funzione di sort ha due dichiarazioni.

La dichiarazione predefinita che consente di specificare una chiusura di confronto:

 func sort(array: T[], pred: (T, T) -> Bool) -> T[] 

E una seconda dichiarazione che prende solo un singolo parametro (la matrice) ed è “hardcoded per usare il comparatore minore di”.

 func sort(array: T[]) -> T[] Example: sort( _arrayToSort_ ) { $0 > $1 } 

Ho provato una versione modificata del tuo codice in un parco giochi con la chiusura aggiunta in modo da poter controllare la funzione un po ‘più da vicino, e ho trovato che con n impostato su 1000, la chiusura veniva chiamata circa 11.000 volte.

 let n = 1000 let x = Int[](count: n, repeatedValue: 0) for i in 0..n { x[i] = random() } let y = sort(x) { $0 > $1 } 

Non è una funzione efficiente, vorrei raccomandare una migliore implementazione della funzione di ordinamento.

MODIFICARE:

Ho dato un’occhiata alla pagina di wikipedia Quicksort e ho scritto un’implementazione Swift per questo. Ecco il programma completo che ho usato (in un parco giochi)

 import Foundation func quickSort(inout array: Int[], begin: Int, end: Int) { if (begin < end) { let p = partition(&array, begin, end) quickSort(&array, begin, p - 1) quickSort(&array, p + 1, end) } } func partition(inout array: Int[], left: Int, right: Int) -> Int { let numElements = right - left + 1 let pivotIndex = left + numElements / 2 let pivotValue = array[pivotIndex] swap(&array[pivotIndex], &array[right]) var storeIndex = left for i in left..right { let a = 1 // <- Used to see how many comparisons are made if array[i] <= pivotValue { swap(&array[i], &array[storeIndex]) storeIndex++ } } swap(&array[storeIndex], &array[right]) // Move pivot to its final place return storeIndex } let n = 1000 var x = Int[](count: n, repeatedValue: 0) for i in 0..n { x[i] = Int(arc4random()) } quickSort(&x, 0, x.count - 1) // <- Does the sorting for i in 0..n { x[i] // <- Used by the playground to display the results } 

Usando questo con n = 1000, l'ho trovato

  1. quickSort () è stato chiamato circa 650 volte,
  2. sono stati fatti circa 6000 swap,
  3. e ci sono circa 10.000 confronti

Sembra che il metodo di ordinamento incorporato sia (o sia vicino) all'ordinamento rapido ed è molto lento ...

A partire da Xcode 7 è ansible triggersre l’ Fast, Whole Module Optimization . Questo dovrebbe aumentare la tua performance immediatamente.

inserisci la descrizione dell'immagine qui

Rendimento di Swift Array rivisitato:

Ho scritto il mio benchmark confrontando Swift con C / Objective-C. Il mio benchmark calcola i numeri primi. Usa la matrice dei precedenti numeri primi per cercare i fattori primi in ogni nuovo candidato, quindi è abbastanza veloce. Tuttavia, fa tonnellate di lettura di array e meno di scrittura su array.

Inizialmente ho fatto questo punto di riferimento contro Swift 1.2. Ho deciso di aggiornare il progetto ed eseguirlo contro Swift 2.0.

Il progetto ti consente di scegliere tra l’utilizzo di normali array swift e l’uso di buffer di memoria non sicuri Swift usando la semantica dell’array.

Per C / Objective-C, è ansible scegliere di utilizzare gli array NSArrays o C malloc’ed.

I risultati del test sembrano essere molto simili con l’ottimizzazione del codice più veloce, più piccola ([-0s]) o più rapida, aggressiva ([-0fast]).

Le prestazioni di Swift 2.0 sono ancora orribili con l’ottimizzazione del codice distriggersta, mentre le prestazioni di C / Objective-C sono solo moderatamente più lente.

La linea di fondo è che i calcoli basati su array malloc C sono i più veloci, con un margine modesto

Swift con buffer non sicuri richiede circa 1.19X – 1.20X in più rispetto agli array malloc’d C quando si utilizza l’ottimizzazione del codice più rapida e più piccola. la differenza sembra leggermente inferiore con un’ottimizzazione rapida e aggressiva (Swift prende più come 1.18x a 1.16x più lungo di C.

Se si usano array Swift regolari, la differenza con C è leggermente maggiore. (Swift impiega ~ 1,22 a 1,23 in più.)

Gli array Swift regolari sono DRAMATICALLY più veloci di quanto non fossero in Swift 1.2 / Xcode 6. Le loro prestazioni sono così vicine agli array basati su buffer Swift non sicuri che l’utilizzo di buffer di memoria non sicuri non sembra davvero più un problema, che è grande.

A proposito, le prestazioni NSArray dell’Objective-C fa schifo. Se vuoi usare gli oggetti container nativi in ​​entrambe le lingue, Swift è DRAMATICAMENTE più veloce.

Puoi controllare il mio progetto su github su SwiftPerformanceBenchmark

Ha una semplice interfaccia utente che facilita la raccolta delle statistiche.

È interessante notare che l’ordinamento sembra essere leggermente più veloce in Swift che in C ora, ma che questo algoritmo di numero primo è ancora più veloce in Swift.

Il problema principale che viene menzionato da altri ma non chiamato abbastanza è che -O3 non fa nulla in Swift (e non ha mai) quindi quando compilato con esso è effettivamente non ottimizzato ( -Onone ).

I nomi delle opzioni sono cambiati nel tempo, quindi alcune altre risposte hanno contrassegni obsoleti per le opzioni di compilazione. Le opzioni correnti corrette (Swift 2.2) sono:

 -Onone // Debug - slow -O // Optimised -O -whole-module-optimization //Optimised across files 

L’ottimizzazione di tutto il modulo ha una compilazione più lenta ma può essere ottimizzata su tutti i file all’interno del modulo, ad esempio all’interno di ogni framework e all’interno del codice effettivo dell’applicazione, ma non tra di essi. Si dovrebbe usare questo per qualsiasi performance critica

Puoi anche disabilitare i controlli di sicurezza per una velocità ancora maggiore, ma con tutte le asserzioni e le precondizioni non solo disabilitate ma ottimizzate sulla base della loro correttezza. Se hai mai raggiunto un’affermazione, significa che sei in comportamento indefinito. Usare con estrema caucanvas e solo se si determina che l’aumento di velocità è utile per te (testando). Se lo trovi utile per alcuni codici, ti consiglio di separare quel codice in un framework separato e di disabilitare solo i controlli di sicurezza per quel modulo.

 func partition(inout list : [Int], low: Int, high : Int) -> Int { let pivot = list[high] var j = low var i = j - 1 while j < high { if list[j] <= pivot{ i += 1 (list[i], list[j]) = (list[j], list[i]) } j += 1 } (list[i+1], list[high]) = (list[high], list[i+1]) return i+1 } func quikcSort(inout list : [Int] , low : Int , high : Int) { if low < high { let pIndex = partition(&list, low: low, high: high) quikcSort(&list, low: low, high: pIndex-1) quikcSort(&list, low: pIndex + 1, high: high) } } var list = [7,3,15,10,0,8,2,4] quikcSort(&list, low: 0, high: list.count-1) var list2 = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ] quikcSort(&list2, low: 0, high: list2.count-1) var list3 = [1,3,9,8,2,7,5] quikcSort(&list3, low: 0, high: list3.count-1) 

Questo è il mio blog su Quick Sort- Github sample Quick-Sort

Puoi dare un'occhiata all'algoritmo di partizionamento di Lomuto in Partizionare la lista. Scritto in Swift