Swift Beta Performance: Sorting Arrays

Swift Beta performance: sorting arrays

tl;dr Swift 1.0 is now as fast as C by this benchmark using the default release optimisation level [-O].


Here is an in-place quicksort in Swift Beta:

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

And the same 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);
}

Both work:

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]

Both are called in the same program as written.

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

This converts the absolute times to seconds:

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

Here is a summary of the compiler's optimazation levels:

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

Time in seconds with [-Onone] for n=10_000:

Swift:            0.895296452
C: 0.001223848

Here is Swift's builtin sort() for n=10_000:

Swift_builtin:    0.77865783

Here is [-O] for n=10_000:

Swift:            0.045478346
C: 0.000784666
Swift_builtin: 0.032513488

As you can see, Swift's performance improved by a factor of 20.

As per mweathers' answer, setting [-Ofast] makes the real difference, resulting in these times for n=10_000:

Swift:            0.000706745
C: 0.000742374
Swift_builtin: 0.000603576

And for n=1_000_000:

Swift:            0.107111846
C: 0.114957179
Swift_sort: 0.092688548

For comparison, this is with [-Onone] for n=1_000_000:

Swift:            142.659763258
C: 0.162065333
Swift_sort: 114.095478272

So Swift with no optimizations was almost 1000x slower than C in this benchmark, at this stage in its development. On the other hand with both compilers set to [-Ofast] Swift actually performed at least as well if not slightly better than C.

It has been pointed out that [-Ofast] changes the semantics of the language, making it potentially unsafe. This is what Apple states in the Xcode 5.0 release notes:

A new optimization level -Ofast, available in LLVM, enables aggressive optimizations. -Ofast relaxes some conservative restrictions, mostly for floating-point operations, that are safe for most code. It can yield significant high-performance wins from the compiler.

They all but advocate it. Whether that's wise or not I couldn't say, but from what I can tell it seems reasonable enough to use [-Ofast] in a release if you're not doing high-precision floating point arithmetic and you're confident no integer or array overflows are possible in your program. If you do need high performance and overflow checks / precise arithmetic then choose another language for now.

BETA 3 UPDATE:

n=10_000 with [-O]:

Swift:            0.019697268
C: 0.000718064
Swift_sort: 0.002094721

Swift in general is a bit faster and it looks like Swift's built-in sort has changed quite significantly.

FINAL UPDATE:

[-Onone]:

Swift:   0.678056695
C: 0.000973914

[-O]:

Swift:   0.001158492
C: 0.001192406

[-Ounchecked]:

Swift:   0.000827764
C: 0.001078914

Need to sort array based on alphabetically and based on Upper and followed by lower case

You could try NSString.CompareOptions.literal out -

Exact character-by-character equivalence.

let names = ["Alpha", "alpha1", "Alpha1", "alpha2", "beta", "Beta1"]
let sortedNames = names.sorted { $0.compare($1, options: [.literal]) == .orderedAscending }

This gives you -

▿ 6 elements
- 0 : "Alpha"
- 1 : "Alpha1"
- 2 : "Beta1"
- 3 : "alpha1"
- 4 : "alpha2"
- 5 : "beta"

As you can see, it will sort precisely based on char-by-char basis. However it will still keep all UPPERCASE ones at the start and lowercase ones in the end.


What you need is a custom implementation where you have the full control on comparison algorithm -

Code

extension Array where Element == String {

/// This is a very limited logic that compares values based on following two distinctions only -
///
/// 1. Letters - See docs for `Character.isLetter`
/// - "A" (U+0041 LATIN CAPITAL LETTER A)
/// - "é" (U+0065 LATIN SMALL LETTER E, U+0301 COMBINING ACUTE ACCENT)
/// - "ϴ" (U+03F4 GREEK CAPITAL THETA SYMBOL)
/// - "ڈ" (U+0688 ARABIC LETTER DDAL)
/// - "日" (U+65E5 CJK UNIFIED IDEOGRAPH-65E5)
/// - "ᚨ" (U+16A8 RUNIC LETTER ANSUZ A)
///
/// 2. Whole Numbers - See docs for `Character.isWholeNumber`
/// - "1" (U+0031 DIGIT ONE) => 1
/// - "५" (U+096B DEVANAGARI DIGIT FIVE) => 5
/// - "๙" (U+0E59 THAI DIGIT NINE) => 9
/// - "万" (U+4E07 CJK UNIFIED IDEOGRAPH-4E07) => 10_000
///
func sortedAlphabeticallyNumericallyCaseSensitive() -> [String] {
return self.sorted { s1, s2 in
for (i1, c1) in s1.enumerated() {
let i2 = s2.index(s2.startIndex, offsetBy: i1)
if i2 < s2.endIndex {
let c2: Character = s2[i2]

/// 1. Support for `Letters`
if c1.isLetter, let c1Int = c1.asciiValue,
c2.isLetter, let c2Int = c2.asciiValue {
if c1Int == c2Int {
continue
}
if (c1.isUppercase && c2.isUppercase) || (c1.isLowercase && c2.isLowercase) {
return c1Int < c2Int
}
else if c1.isUppercase {
return c1Int <= (c2.uppercased().first?.asciiValue ?? 0)
}
else {
return (c1.uppercased().first?.asciiValue ?? 0) < c2Int
}
}

/// 2. Support for Whole Numbers
else if c1.isWholeNumber, let c1NumberValue = c1.wholeNumberValue,
c2.isWholeNumber, let c2NumberValue = c2.wholeNumberValue {
if c1NumberValue == c2NumberValue {
continue
}
return c1NumberValue < c2NumberValue
}

/// 1x2
else if c1.isWholeNumber, c2.isLetter {
return true
}
else if c1.isLetter, c2.isWholeNumber {
return false
}

/// You are welcome to add any other criteria
}
else {
return s1.count < s2.count
}
}
return s1.count < s2.count
}
}

Usage

let names = ["alpha58", "Zebra", "Alpha", "alpha55", "alpha5", "alpha", "ALPHA", "alpha1", "Alpha1", "alpha2", "beta", "Beta1"]
let sortedNames = names.sortedAlphabeticallyNumericallyCaseSensitive()

(lldb) po sortedNames
▿ 12 elements
- 0 : "ALPHA"
- 1 : "Alpha"
- 2 : "Alpha1"
- 3 : "alpha"
- 4 : "alpha1"
- 5 : "alpha2"
- 6 : "alpha5"
- 7 : "alpha55"
- 8 : "alpha58"
- 9 : "Beta1"
- 10 : "beta"
- 11 : "Zebra"

Notes

  1. It does not limit the comparison to just the first character. It keeps comparing two strings char-by-char until it has a conclusion on which one comes first.
  2. This will most likely have performance issues while sorting large lists. it's best that this sorting happens on a background thread so UI doesn't freeze.


Update

More often than not, in the apps we are dealing with record types that contain these string values. For example a Person record.

Above implementation can be adapted to work with any record type like following -

struct Person {
let id: String
let name: String
init(id: String = UUID().uuidString, name: String) {
self.id = id
self.name = name
}
}

extension Array where Element == Person {

func sortedAlphabeticallyNumericallyCaseSensitive() -> [Element] {
return self.sorted { p1, p2 in
let s1 = p1.name
let s2 = p2.name
/// same as above implementation
}
}
}

Swift sorted(by:) method doesn't correctly sort an array of struct based on integer

The predicate to Array.sorted(by:) requires that you

return true if its first argument should be ordered before its second argument; otherwise, false.

The order of the arguments passed to the predicate can be given in either order ((a, b) or (b, a)) depending on how the list has been sorted so far, but the predicate must give a consistent result in either order or else you'll get nonsense results.

In your predicate, you're checking the first element's user ID to prioritize it, but not the second; i.e., you're handling (a, b) but not (b, a). If you update your predicate to

myArray.sorted(by: {
// The order of the checking here matters. Specifically, the predicate
// requires a `<` relationship, not a `<=` relationship. If both $0 and $1
// have the same `user_id`, we need to return `false`. Checking $1.user_id
// first hits two birds with one stone.
if $1.user_id == 40 {
return false
} else if $0.user_id == 40 {
return true
}

return $0.user_id < $1.user_id
})

then you'll get consistent results.

Alternatively, if the element is known ahead of time, you can avoid this by extracting it from the list and sorting the remaining results.

Swift sorting nest String Array by Numbered Array Sort

You can get an index from one array and sort using values from the second array:

let a = [["ddd"],["aaa"],["ggg"]]
let b = [557, 147, 355]

let sortedA = a.sorted { b[a.firstIndex(of: $0)!] < b[a.firstIndex(of: $1)!] }
// prints [["aaa"], ["ggg"], ["ddd"]]

let sortedB = b.sorted()
// prints [147, 355, 557]

This one-liner:

let sortedA = a.sorted { b[a.firstIndex(of: $0)!] < b[a.firstIndex(of: $1)!] }

is a shorter form of this:

let sortedA = a.sorted { item1, item2 in
let item1Index = a.firstIndex(of: item1)!
let item2Index = a.firstIndex(of: item2)!
return b[item1Index] < b[item2Index]
}

Swift 3 sorting large amounts of data in arrays

You can go like this.

let filterArray = result.indices.flatMap { $0 % 2 != 0 ? nil : result[$0] }
print(filterArray)

Edit: If you want to store output of filter in same array try like this.

var result = contentArray[1].components(separatedBy: ",")
result = result.indices.flatMap { $0 % 2 != 0 ? nil : result[$0] }
print(result)

Sorting arrays of file attributes by their creation date in Swift

You should not use multiple arrays for this but instead wrap your values in a custom struct

struct FileInfo {
let url: URL
let name: String
let path: String //this is not really needed, you can get it from the url
let date: Date
}

and have one array for this

var files: [FileInfo]()

and create your struct instance and append it

files.append(FileInfo(url: fileURL, name: name, path: path, date: date)

Sorting will now be trivial so after the for loop you do

files.sort(by: { $0.date < $1.date })

This sorts in ascending order, not sure which one you want.



Related Topics



Leave a reply



Submit