Быстрая производительность: сортировка массивов

Я реализовал алгоритм в Swift и заметил, что производительность очень плохая. После углубления я понял, что одно из узких мест было чем-то таким же простым, как сортировка массивов. Соответствующая часть здесь:

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 

В C ++ аналогичная операция занимает 0.06 с на моем компьютере.

В Python требуется 0,6 с (без трюков, просто y = отсортировано (x) для списка целых чисел).

В Swift требуется 6 секунд, если я скомпилирую его с помощью следующей команды:

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

И это займет до 88 секунд, если я скомпилирую его с помощью следующей команды:

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

Сроки в Xcode с assemblyми «Release» и «Debug» аналогичны.

Что здесь не так? Я мог понять некоторую потерю производительности по сравнению с C ++, но не в 10-кратном замедлении по сравнению с чистым Python.


Изменить: mweathers заметили, что изменение -O3 на -Ofast делает этот код запущенным почти так же быстро, как версия на C ++! Тем не менее, -Ofast изменяет семантику языка – в моем тестировании он отключил проверки на переполнение целых чисел и переполнение индексирования массива . Например, с -Ofast следующий код Swift работает без сбоев (и выдает некоторые мусор):

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

Так что -Ofast не то, что мы хотим; весь смысл Свифта заключается в том, что у нас есть системы безопасности на месте. Конечно, сети безопасности оказывают определенное влияние на производительность, но они не должны делать программы в 100 раз медленнее. Помните, что Java уже проверяет границы массива, а в типичных случаях замедление происходит намного меньше, чем 2. И в Clang и GCC мы получили -ftrapv для проверки (подписанного) целочисленного переполнения, и это не так медленно, либо ,

Отсюда вопрос: как мы можем получить разумную производительность в Свифт, не потеряв системы безопасности?


Редактирование 2: я сделал еще несколько бенчмаркинга с очень простыми петлями вдоль линий

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

(Здесь операция xor существует только для того, чтобы я мог легче найти соответствующий цикл в коде сборки. Я попытался выбрать операцию, которую легко заметить, но также и «безвредную» в том смысле, что она не должна требовать каких-либо проверок для целых переполнений.)

Опять же, была огромная разница в производительности между -O3 и -Ofast . Поэтому я посмотрел на код сборки:

  • С -Ofast я получаю в значительной степени то, что ожидаю. Соответствующая часть представляет собой цикл с 5 инструкциями машинного языка.

  • С -O3 я получаю то, что было выше моего дикого воображения. Внутренняя петля охватывает 88 строк кода сборки. Я не пытался понять все это, но самые подозрительные части – это 13 вызовов «callq _swift_retain» и еще 13 вызовов «callq _swift_release». То есть, 26 вызовов подпрограмм во внутреннем цикле !


Редактировать 3: В комментариях Ферруччио попросил, чтобы тесты были справедливыми в том смысле, что они не полагаются на встроенные функции (например, сортировка). Я думаю, что следующая программа – довольно хороший пример:

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

Арифметики нет, поэтому нам не нужно беспокоиться о переполнении целых чисел. Единственное, что мы делаем, это просто множество ссылок на массивы. И результаты здесь: Swift -O3 проигрывает почти в 500 раз по сравнению с -Ofast:

  • C ++ -O3: 0,05 с
  • C ++ -O0: 0,4 с
  • Java: 0,2 с
  • Python с PyPy: 0,5 с
  • Python: 12 с
  • Swift -Ofast: 0,05 с
  • Swift -O3: 23 с
  • Swift -O0: 443 с

(Если вас беспокоит, что компилятор полностью оптимизирует целые бессмысленные циклы, вы можете изменить его, например, x[i] ^= x[j] , и добавить инструкцию печати, которая выводит x[0] . Это ничего не меняет , тайминги будут очень похожи.)

И да, здесь реализация Python была глупой чистой реализацией Python со списком int и вложенными для циклов. Он должен быть намного медленнее, чем неоптимизированный Swift. Кажется, что что-то серьезно нарушено с Swift и индексированием массива.


Изменить 4: Эти проблемы (как и некоторые другие проблемы с производительностью), похоже, были исправлены в Xcode 6 beta 5.

Для сортировки у меня теперь есть следующие тайминги:

  • clang ++ -O3: 0,06 с
  • swiftc -Ofast: 0,1 с
  • swiftc -O: 0,1 с
  • swiftc: 4 с

Для вложенных циклов:

  • clang ++ -O3: 0,06 с
  • swiftc -Ofast: 0,3 с
  • swiftc -O: 0,4 с
  • swiftc: 540 с

Похоже, что нет никакой причины использовать небезопасную -Ofast (aka -Ounchecked ); plain -O производит одинаково хороший код.

tl; dr Swift теперь работает так же быстро, как и C, с использованием уровня оптимизации выпуска по умолчанию [-O].

Вот быстрая сортировка на месте в 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) } 

И то же самое в 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); } 

Обе работы:

 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] 

Оба вызываются в той же программе, что и в письменной форме.

 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(); 

Это преобразует абсолютное время в секунды:

 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; } 

Ниже приведен краткий обзор уровней оптимизации компилятора:

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

Время в секундах с [-Onone] для n = 10_000 :

 Swift: 0.895296452 C: 0.001223848 

Вот встроенный тип Swift () для n = 10_000 :

 Swift_builtin: 0.77865783 

Здесь [-O] для n = 10_000 :

 Swift: 0.045478346 C: 0.000784666 Swift_builtin: 0.032513488 

Как вы можете видеть, производительность Swift улучшилась в 20 раз.

По мнению мейзеров , установка [-Ofast] делает реальную разницу, приводящую к этим временам для n = 10_000 :

 Swift: 0.000706745 C: 0.000742374 Swift_builtin: 0.000603576 

И для n = 1_000_000 :

 Swift: 0.107111846 C: 0.114957179 Swift_sort: 0.092688548 

Для сравнения это с [-Onone] для n = 1_000_000 :

 Swift: 142.659763258 C: 0.162065333 Swift_sort: 114.095478272 

Таким образом, Swift без оптимизаций был почти на 1000 раз медленнее, чем C в этом тесте, на этом этапе его разработки. С другой стороны, оба компилятора, установленные на [-Ofast] Swift, фактически выполняются, по крайней мере, если не немного лучше C.

Было указано, что [-Ofast] изменяет семантику языка, делая его потенциально опасным. Это то, что Apple заявляет в примечаниях к выпуску Xcode 5.0:

Новый уровень оптимизации -Ofast, ansible в LLVM, обеспечивает агрессивную оптимизацию. -Ofast расслабляет некоторые консервативные ограничения, в основном для операций с плавающей запятой, которые безопасны для большинства кодов. Это может привести к значительным выигрышам от компилятора.

Они почти защищают его. Независимо от того, насколько это разумно или нет, я не мог сказать, но из того, что я могу сказать, достаточно разумно использовать [-Ofast] в выпуске, если вы не выполняете арифметику с высокой точностью с плавающей запятой, и вы уверены, что нет целого или переполнение массива возможно в вашей программе. Если вам нужны проверки высокой производительности и переполнения / точная арифметика, выберите другой язык.

ОБНОВЛЕНИЕ BETA 3:

n = 10_000 с [-O] :

 Swift: 0.019697268 C: 0.000718064 Swift_sort: 0.002094721 

Swift в целом немного быстрее, и похоже, что встроенный сорт Swift значительно изменился.

ЗАКЛЮЧИТЕЛЬНОЕ ОБНОВЛЕНИЕ:

[-Одно] :

 Swift: 0.678056695 C: 0.000973914 

[-O] :

 Swift: 0.001158492 C: 0.001192406 

[-Окнопка] :

 Swift: 0.000827764 C: 0.001078914 

TL; DR : Да, единственная реализация языка Swift выполняется медленно, прямо сейчас . Если вам нужен быстрый, числовой (и другие типы кода, предположительно) код, просто перейдите к другому. В будущем вы должны переоценить свой выбор. Это может быть достаточно для большинства кода приложения, написанного на более высоком уровне.

Из того, что я вижу в SIL и LLVM IR, похоже, им нужна куча оптимизаций для удаления сохранений и выпусков, которые могут быть реализованы в Clang (для Objective-C), но они еще не портировали их. Это теория, с которой я иду (на данный момент … мне все еще нужно подтвердить, что Clang что-то делает), поскольку профайлер, запущенный в последнем тестовом случае этого вопроса, дает этот «красивый» результат:

Профилирование времени на -O3Профилирование времени на -Ofast

Как было сказано многими другими, -Ofast совершенно небезопасен и изменяет семантику языка. Для меня это на этапе «Если вы собираетесь использовать это, просто используйте другой язык». Я буду переоценивать этот выбор позже, если он изменится.

-O3 дает нам кучу swift_retain и swift_release которые, честно говоря, не выглядят так, как будто они должны быть там для этого примера. Оптимизатор должен был удалить (большинство из них) AFAICT, так как он знает большую часть информации о массиве и знает, что он имеет (по крайней мере) сильную ссылку на него.

Он не должен выделять больше сохранений, когда он даже не вызывает функции, которые могут освобождать объекты. Я не думаю, что конструктор массива может вернуть массив, который меньше запрашиваемого, что означает, что много проверок, которые были выбраны, бесполезны. Он также знает, что целое число никогда не будет превышать 10 тыс., Поэтому проверки переполнения могут быть оптимизированы (не из-за -Ofast странности, а из-за семантики языка (ничто другое не меняет этот var и не может получить к нему доступ, до 10k безопасно для типа Int ).

Компилятор, возможно, не сможет распаковать массив или элементы массива, хотя, поскольку они передаются sort() , который является внешней функцией и должен получать аргументы, которые он ожидает. Это заставит нас косвенно использовать значения Int , которые заставили бы его пойти немного медленнее. Это может измениться, если универсальная функция sort() (не в методе с несколькими методами) была доступна компилятору и была встроена.

Это очень новый (общеansible) язык, и он проходит через то, что я предполагаю, это множество изменений, так как люди (в большой степени) вовлечены в язык Swift, предлагая обратную связь, и все говорят, что язык не закончен и будет изменение.

Используемый код:

 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: Я не специалист по Objective-C, а также все возможности от Cocoa , Objective-C или Swift. Я мог бы также предположить некоторые вещи, которые я не писал.

Я решил посмотреть на это для удовольствия, и вот время, которое я получаю:

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

стриж

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

Результаты:

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 

Кажется, что такая же производительность, если я компилирую с -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 

Кажется, была регрессия производительности от Swift 2.0 до Swift 3.0, и я также вижу разницу между -O и -Ounchecked в первый раз.

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 снова улучшает производительность, сохраняя разрыв между -O и -Ounchecked . -O -whole-module-optimization , похоже, не -O -whole-module-optimization ситуацию.

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; } 

Результаты:

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 

решение суда

На момент написания этой статьи, вид Swift был быстрым, но не таким быстрым, как у C ++, при компиляции с -O , с указанными выше компиляторами и библиотеками. С -Ounchecked он выглядит так же быстро, как C ++ в Swift 4.0.2 и Apple LLVM 9.0.0.

С The Swift Programming Language :

Стандартная библиотека Sort Function Swift предоставляет функцию под названием sort, которая сортирует массив значений известного типа, основываясь на выводе, который вы предоставляете. После завершения процесса сортировки функция сортировки возвращает новый массив того же типа и размера, что и старый, с его элементами в правильном порядке сортировки.

Функция sort имеет два объявления.

Объявление по умолчанию, которое позволяет вам указать закрытие сравнения:

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

И второе объявление, которое принимает только один параметр (массив) и «жестко запрограммировано для использования меньше, чем компаратор».

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

Я протестировал модифицированную версию вашего кода на игровой площадке с добавленным закрытием, чтобы я мог немного контролировать функцию, и я обнаружил, что с n установленным до 1000, закрытие вызывалось примерно 11 000 раз.

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

Это не эффективная функция, я бы рекомендовал использовать более эффективную реализацию функции сортировки.

РЕДАКТИРОВАТЬ:

Я взглянул на страницу Quicksort wikipedia и написал для нее реализацию Swift. Вот полная программа, которую я использовал (на детской площадке)

 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 } 

Используя это при n = 1000, я обнаружил, что

  1. quickSort () получил вызов около 650 раз,
  2. было сделано около 6000 свопов,
  3. и существует около 10000 сравнений

Кажется, что встроенный метод сортировки (или близок к) быстро сортируется, и он очень медленный ...

Начиная с Xcode 7 вы можете включить Fast, Whole Module Optimization . Это должно немедленно увеличить производительность.

введите описание изображения здесь

Быстрая работа массива:

Я написал собственный тест, сравнивающий Swift с C / Objective-C. В моем тесте вычисляются простые числа. Он использует массив предыдущих простых чисел для поиска простых факторов в каждом новом кандидате, поэтому он довольно быстро. Тем не менее, он делает TONS чтения массива и меньше записывает в массивы.

Я изначально сделал этот тест против Swift 1.2. Я решил обновить проект и запустить его против Swift 2.0.

Проект позволяет выбирать между использованием обычных быстрых массивов и использованием буферов небезопасной памяти Swift с использованием семантики массива.

Для C / Objective-C вы можете либо выбрать NSArrays, либо C malloc’ed массивы.

Результаты тестов, похоже, очень похожи на самую быструю, минимальную оптимизацию кода ([-0s]) или самую быструю, агрессивную ([-0fast]) оптимизацию.

Производительность Swift 2.0 по-прежнему ужасна, когда оптимизация кода отключена, тогда как производительность C / Objective-C только умеренно медленная.

Суть в том, что вычисления на основе массива C malloc’d являются самыми быстрыми, с небольшим запасом

Swift с небезопасными буферами занимает около 1,19X – 1,20X длиннее массивов C malloc’d при использовании самой быстрой и минимальной оптимизации кода. разница немного меньше с быстрой, агрессивной оптимизацией (Swift больше похож на 1,18x на 1,16x больше, чем на C.

Если вы используете регулярные массивы Swift, разница с C немного больше. (Swift занимает ~ 1.22 до 1.23 дольше.)

Регулярные массивы Swift DRAMATICALLY быстрее, чем они были в Swift 1.2 / Xcode 6. Их производительность настолько близка к небезопасным буферизированным массивам Swift, что использование небезопасных буферов памяти на самом деле больше не стоит того, что является большим.

BTW, Objective-C производительность NSArray воняет. Если вы собираетесь использовать собственные объекты контейнера на обоих языках, Swift DRAMATICALLY быстрее.

Вы можете проверить мой проект на github в SwiftPerformanceBenchmark

У этого есть простой интерфейс, который делает сбор статистики довольно легким.

Интересно, что сортировка, по-видимому, немного быстрее в Swift, чем в C, но этот алгоритм с простым числом еще быстрее в Swift.

Основная проблема, которая упоминается другими, но не -O3 достаточно, заключается в том, что -O3 вообще ничего не делает в Swift (и никогда не имеет), поэтому при компиляции с тем, что она эффективно не оптимизирована ( -Onone ).

Имена опций со временем менялись, поэтому некоторые другие ответы имеют устаревшие флаги для вариантов сборки. Правильные текущие параметры (Swift 2.2):

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

Оптимизация всего модуля имеет более медленную компиляцию, но может оптимизировать все файлы в модуле, то есть в пределах каждой структуры и внутри реального кода приложения, но не между ними. Вы должны использовать это для любой критической производительности)

Вы также можете отключить проверки безопасности еще быстрее, но со всеми утверждениями и предпосылками, которые не только отключены, но и оптимизированы на основе их правильности. Если вы когда-либо делаете это, это означает, что вы находитесь в неопределенном поведении. Используйте с особой осторожностью и только если вы определите, что ускорение скорости стоит для вас (путем тестирования). Если вы считаете это ценным для некоторого кода, я рекомендую разделить этот код на отдельную структуру и отключить проверку безопасности этого модуля.

 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) 

Это мой блог о Quick Sort- Github sample Quick-Sort

Вы можете взглянуть на алгоритм разбиения Ломуто в разделе Разбиение списка. Написано в Swift

  • Естественный порядок сортировки в C #
  • Swift - сортировка массива объектов с несколькими критериями
  • Как сортировать массив по нескольким столбцам?
  • Mysql: выберите строки из таблицы, которые не находятся в другом
  • В чем разница между `sorted (list)` vs `list.sort ()`?
  • Как сортировать массивы с помощью vbscript?
  • Marshal.PtrToStructure (и обратно) и общее решение для сводной привязки
  • Сортировка списка точек с помощью Java
  • Как отсортировать NSMutableArray с помощью sortedArrayUsingDescriptors?
  • Как разрешить sortedArrayUsingSelector использовать целое число для сортировки вместо String?
  • Как реализовать автоматическую сортировку DataGridView?
  • Interesting Posts

    Как делать снимки с камеры без предварительного просмотра, когда начнется мое приложение?

    Как сделать Ubuntu VM в VirtualBox доступным из Интернета?

    Как отключить jquery-ui draggable?

    Использует ли #pragma warning push / pop правильный способ временного изменения уровня предупреждения?

    Как удалить приложения из моего списка в магазине Windows 8?

    Android Динамически загружает Listview в конец прокрутки?

    Интроспекция и дженерики Swift

    Как отключить буферизацию stdout в C

    NTFS жесткий диск не смонтирован, как переформатировать в Journaled HFS + и сохранить данные

    Как сгенерировать Makefile с источником в подкаталогах, используя только один make-файл

    Удалить , равное удалению?

    Как правильно выйти из веб-приложения Java EE 6 после входа в систему

    Преобразовать строку в int в Rust?

    Как «вырезать» файл на OS X?

    Есть ли способ отключить диалоговые окна, показанные при первом открытии приложения?

    Давайте будем гением компьютера.