Во-первых, несколько общих замечаний по бенчмаркингу:
- Используйте оптимизированные сборки (что, я полагаю, вы делаете, но я упоминаю только для полноты)
- Повтортесты много раз
- Рандомизируйте порядок выполнения тестов и сравните несколько прогонов.(Я лично использую модульные тесты с включенной функцией «Randomize Execution Order».)
Во-вторых, я должен сказать, что разница между представлениями кортежей и swapAt была очень незначительной.Я перебрал миллиард раз (массив из 1000 элементов, повторял миллион раз), и разница по-прежнему составляла доли секунды.
В-третьих, я обнаружил, что использование кортежей для замены было немного быстрее, чем использование swapAt при работе с большим набором рандомизированных данных, где 10% точек данных были нулями, но немного медленнее, когда действительно требовалось очень мало свопов.
Этот последний момент имеет смысл, поскольку swapAt пропустит операцию подкачки, если в этом нет необходимости : «Вызов swapAt(_:_:) с тем же индексом, что и для i и j, не имеет никакого эффекта». Мы можем видеть , что swapAt имеетранний выход из i и j одинаков:
@inlinable
public mutating func swapAt(_ i: Index, _ j: Index) {
guard i != j else { return }
let tmp = self[i]
self[i] = self[j]
self[j] = tmp
}
Если вы измените свою процедуру кортежа для выполнения той же проверки, разница будет уменьшена:
func moveZeroesTuple(_ nums: inout [Int]) {
var j = 0
for i in 0..<nums.count where nums[i] != 0 {
if i != j {
(nums[i], nums[j]) = (nums[j], nums[i])
}
j += 1
}
}
ОткровенноЯ был немного удивлен, что подход, основанный на кортежах, был таким же быстрым, как и раньше, но, глядя на сборку, оптимизатор проделал огромную работу, доведя это до чего-то довольно обтекаемого:
0x100b5fb70 <+192>: movq 0x20(%rbx,%rdx,8), %rsi ; retrieve nums[i]
0x100b5fb75 <+197>: testq %rsi, %rsi ; is it zero?
0x100b5fb78 <+200>: je 0x100b5fb98 ; <+232> [inlined] protocol witness for Swift.Strideable.advanced(by: A.Stride) -> A in conformance Swift.Int : Swift.Strideable in Swift
0x100b5fb7a <+202>: cmpq %rcx, %rdx ; is i = j?
0x100b5fb7d <+205>: je 0x100b5fb93 ; <+227> [inlined] MyAppTests.MyAppTests.moveZeroesTuple(inout Swift.Array<Swift.Int>) -> () + 66 at MyAppTests.swift:120
0x100b5fb7f <+207>: cmpq (%rax), %rcx ; are we done?
0x100b5fb82 <+210>: jae 0x100b5fbc7 ; <+279> [inlined] generic specialization <Swift.Int> of Swift.Array._getElement(_: Swift.Int, wasNativeTypeChecked: Swift.Bool, matchingSubscriptCheck: Swift._DependenceToken) -> A
0x100b5fb84 <+212>: movq 0x20(%rbx,%rcx,8), %rdi ; retrieve nums[j]
0x100b5fb89 <+217>: movq %rdi, 0x20(%rbx,%rdx,8) ; save it in nums[i]
0x100b5fb8e <+222>: movq %rsi, 0x20(%rbx,%rcx,8) ; save previously retrieved nums[i] in nums[j]
0x100b5fb93 <+227>: incq %rcx ; j += 1
0x100b5fb96 <+230>: jo 0x100b5fbc5 ; <+277> [inlined] MyAppTests.MyAppTests.moveZeroesTuple(inout Swift.Array<Swift.Int>) -> () at MyAppTests.swift:120
0x100b5fb98 <+232>: incq %rdx ; i += 1
0x100b5fb9b <+235>: cmpq %rdx, %r12 ; repeat for loop
0x100b5fb9e <+238>: jne 0x100b5fb70 ; <+192> [inlined] generic specialization <Swift.Int> of Swift.Array._getElement(_: Swift.Int, wasNativeTypeChecked: Swift.Bool, matchingSubscriptCheck: Swift._DependenceToken) -> A + 15
Оптимизированная swapAt сборка была почти такой же (благодаря вставке), но с несколькими дополнительными инструкциями:
0x100b5d920 <+192>: movq 0x20(%rbx,%rdx,8), %rsi
0x100b5d925 <+197>: testq %rsi, %rsi
0x100b5d928 <+200>: je 0x100b5d955 ; <+245> [inlined] protocol witness for Swift.Strideable.advanced(by: A.Stride) -> A in conformance Swift.Int : Swift.Strideable in Swift
0x100b5d92a <+202>: cmpq %rcx, %rdx
0x100b5d92d <+205>: je 0x100b5d950 ; <+240> [inlined] MyAppTests.MyAppTests.moveZeroesSwapAt(inout Swift.Array<Swift.Int>) -> () + 79 at MyAppTests.swift:128
0x100b5d92f <+207>: movq (%rax), %rdi
0x100b5d932 <+210>: cmpq %rdi, %rdx
0x100b5d935 <+213>: jae 0x100b5d984 ; <+292> [inlined] generic specialization <Swift.Int> of Swift.Array._getElement(_: Swift.Int, wasNativeTypeChecked: Swift.Bool, matchingSubscriptCheck: Swift._DependenceToken) -> A
0x100b5d937 <+215>: cmpq %rdi, %rcx
0x100b5d93a <+218>: jae 0x100b5d986 ; <+294> [inlined] generic specialization <Swift.Int> of Swift.Array._getElement(_: Swift.Int, wasNativeTypeChecked: Swift.Bool, matchingSubscriptCheck: Swift._DependenceToken) -> A + 2
0x100b5d93c <+220>: movq 0x20(%rbx,%rcx,8), %rdi
0x100b5d941 <+225>: movq %rdi, 0x20(%rbx,%rdx,8)
0x100b5d946 <+230>: cmpq (%rax), %rcx
0x100b5d949 <+233>: jge 0x100b5d988 ; <+296> [inlined] generic specialization <Swift.Int> of Swift._ArrayBuffer._checkInoutAndNativeTypeCheckedBounds(_: Swift.Int, wasNativeTypeChecked: Swift.Bool) -> ()
0x100b5d94b <+235>: movq %rsi, 0x20(%rbx,%rcx,8)
0x100b5d950 <+240>: incq %rcx
0x100b5d953 <+243>: jo 0x100b5d982 ; <+290> [inlined] MyAppTests.MyAppTests.moveZeroesSwapAt(inout Swift.Array<Swift.Int>) -> () at MyAppTests.swift:128
0x100b5d955 <+245>: incq %rdx
0x100b5d958 <+248>: cmpq %rdx, %r12
0x100b5d95b <+251>: jne 0x100b5d920 ; <+192> [inlined] generic specialization <Swift.Int> of Swift.Array._getElement(_: Swift.Int, wasNativeTypeChecked: Swift.Bool, matchingSubscriptCheck: Swift._DependenceToken) -> A + 15
Тем не менее, эти несколько дополнительных инструкцийПохоже, что у подхода к кортежу было небольшое преимущество в сценарии «много перестановок».
Итог, в моих тестах разница между ними незначительна во всем, кроме самых необычно больших наборов данных, и нестоит беспокоиться, иначе.И характеристики производительности зависят от природы набора данных, и в общем случае нет явного победителя.И, честно говоря, если ваш набор данных был на самом деле достаточно большим, чтобы оправдать выбор одного над другим, вам действительно все равно следует рассмотреть другой алгоритм.
Если вам интересно, вот моимодульные тесты, протестированные со сборкой «release», с включенным «рандомизированным порядком выполнения»:
import XCTest
class MyAppTests: XCTestCase {
static var originalArray: [Int]!
let iterations = 1_000_000
// fyi, use static to make sure all tests use the same original array
// eliminating any discrepancies between different tests, within the same
// test run, having different data and therefore different number of swaps.
override static func setUp() {
print("building array")
// scenario 1: no swapping needed
//
// Array with 1000 integers, 10% which are zeros and the rest are non-zero
originalArray = (0..<900).map { _ in Int.random(in: 1..<10) } + [Int](repeating: 0, count: 100)
// scenario 2: some swapping needed
//
// if you don't want them randomized, comment the following line
originalArray.shuffle()
// scenario 3: since all zeros are at the start, the maximum amount of swapping
//
// if you want zeros at start, uncomment the following line
//
// originalArray.sort()
}
func moveZeroesTuple(_ nums: inout [Int]) {
var j = 0
for i in 0..<nums.count where nums[i] != 0 {
if i != j {
(nums[i], nums[j]) = (nums[j], nums[i])
}
j += 1
}
}
func moveZeroesShiftManual(_ nums: inout [Int]) {
var i = 0
let count = nums.count
while i < count, nums[i] != 0 {
i += 1
}
var j = i
while i < count {
if nums[i] != 0 {
nums[j] = nums[i]
j += 1
}
i += 1
}
while j < count {
nums[j] = 0
j += 1
}
}
func moveZeroesSwapManual(_ nums: inout [Int]) {
var j = 0
for i in 0..<nums.count where nums[i] != 0 {
if i != j {
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
j += 1
}
}
func moveZeroesSwapAt(_ nums: inout [Int]) {
var j = 0
for i in 0 ..< nums.count where nums[i] != 0 {
nums.swapAt(i, j)
j += 1
}
}
// a quick test to make sure all solutions generate the same result
func testLogic() {
var arrayTuple = MyAppTests.originalArray!
moveZeroesTuple(&arrayTuple)
var arraySwapAt = MyAppTests.originalArray!
moveZeroesSwapAt(&arraySwapAt)
var arrayShiftManual = MyAppTests.originalArray!
moveZeroesShiftManual(&arrayShiftManual)
var arraySwapManual = MyAppTests.originalArray!
moveZeroesSwapManual(&arraySwapManual)
XCTAssertEqual(arrayTuple, arrayShiftManual)
XCTAssertEqual(arrayTuple, arraySwapManual)
XCTAssertEqual(arrayTuple, arraySwapAt)
}
// now the performance tests
func testTuple() {
measure {
for _ in 0 ..< iterations {
var array = MyAppTests.originalArray!
moveZeroesTuple(&array)
}
}
}
func testSwapAt() {
measure {
for _ in 0 ..< iterations {
var array = MyAppTests.originalArray!
moveZeroesSwapAt(&array)
}
}
}
func testShiftManual() {
measure {
for _ in 0 ..< iterations {
var array = MyAppTests.originalArray!
moveZeroesShiftManual(&array)
}
}
}
func testSwapManual() {
measure {
for _ in 0 ..< iterations {
var array = MyAppTests.originalArray!
moveZeroesSwapManual(&array)
}
}
}
}
Как правило, при выполнении тестов в сборке релиза я буду что-то делать с результатами, просто чтобы убедиться, что некоторыекритическая часть кода не была полностью оптимизирована компилятором.Мне не нужно было делать это здесь только потому, что я тщательно рассмотрел сборку для различных подходов и знаю, что все сохранилось.
