| import TestsUtils |
| |
| // This benchmark aims to measuare heapSort path of stdlib sorting function. |
| // Datasets in this benchmark are influenced by stdlib partition function, |
| // therefore if stdlib partion implementation changes we should correct these |
| // datasets or disable/skip this benchmark |
| public let SortIntPyramids = [ |
| BenchmarkInfo( |
| name: "SortIntPyramid", |
| runFunction: run_SortIntPyramid, |
| tags: [.validation, .api, .algorithm]), |
| BenchmarkInfo( |
| name: "SortAdjacentIntPyramids", |
| runFunction: run_SortAdjacentIntPyramids, |
| tags: [.validation, .api, .algorithm]), |
| ] |
| |
| // let A - array sorted in ascending order, |
| // A^R - reversed array A, + - array concatenation operator |
| // A indices are in range 1...A.length |
| // define the pyramid as A + A^R |
| // define pyramid height as A[A.length] |
| |
| // On 92% of following dataset stdlib sorting function will use heapSort. |
| // number of ranges sorted by heapSort: 26 |
| // median heapSort range length: 198 |
| // maximum -||-: 1774 |
| // average -||-: 357 |
| |
| // pyramid height |
| let pH = 5000 |
| let pyramidTemplate: [Int] = (1...pH) + (1...pH).reversed() |
| |
| // let A - array sorted in ascending order, |
| // A^R - reversed array A, + - array concatenation operator, |
| // A indices are in range 1...A.length. |
| // define adjacent pyramid as A + A^R + A + A^R, |
| // defne adjacent pyramid hight as A[A.length]. |
| |
| |
| // On 25% of following dataset stdlib sorting function will use heapSort. |
| // number of ranges sorted by heapSort: 71 |
| // median heapSort range length: 28 |
| // maximum -||-: 120 |
| // average -||-: 36 |
| |
| // adjacent pyramids height. |
| let aPH = pH / 2 |
| let adjacentPyramidsTemplate: [Int] = (1...aPH) + (1...aPH).reversed() |
| + (1...aPH) + (1...aPH).reversed() |
| |
| @inline(never) |
| public func run_SortIntPyramid(_ N: Int) { |
| for _ in 1...25*N { |
| var pyramid = pyramidTemplate |
| |
| // sort pyramid in place. |
| pyramid.sort() |
| |
| // Check whether pyramid is sorted. |
| CheckResults(pyramid[0] <= pyramid[pyramid.count/2]) |
| } |
| } |
| |
| @inline(never) |
| public func run_SortAdjacentIntPyramids(_ N: Int) { |
| for _ in 1...25*N { |
| var adjacentPyramids = adjacentPyramidsTemplate |
| adjacentPyramids.sort() |
| // Check whether pyramid is sorted. |
| CheckResults( |
| adjacentPyramids[0] <= adjacentPyramids[adjacentPyramids.count/2]) |
| } |
| } |