swift فائدة - أداء سريع:فرز المصفوفات




في البرمجة (8)

tl؛ dr Swift الآن بالسرعة C من خلال هذا المعيار باستخدام مستوى تحسين الإصدار الافتراضي [-O].

هنا هو quicksort في الموضع في 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

هنا هو فرز مضمون سويفت () ل ن = 10_000 :

Swift_builtin:    0.77865783

هنا [-O] لـ n = 10_000 :

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

كما ترى ، تحسن أداء Swift بعامل قدره 20.

وفقا لإجابة mweathers ، فإن الإعداد [-Fast] يصنع الفرق الحقيقي ، مما يؤدي إلى هذه الأوقات لـ 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

كان سويفت مع عدم وجود تحسينات أبطأ تقريبا من 1000 س في هذا المعيار ، في هذه المرحلة من تطورها. من ناحية أخرى ، يتم ضبط كل من المجمعين على [-Ofast] Swift في الواقع على الأقل إذا لم يكن أفضل بقليل من C.

لقد تمت الإشارة إلى أن [-Fast] يغير دلالات اللغة ، مما يجعلها غير آمنة. هذا ما تنص عليه Apple في ملاحظات الإصدار Xcode 5.0:

مستوى أمثل جديد - سريع ، متوفر في LLVM ، يمكّن من إجراء عمليات تحسين عدوانية. -استرخاء سريع بعض القيود المحافظة ، ومعظمها لعمليات الفاصلة العائمة ، التي هي آمنة لمعظم التعليمات البرمجية. يمكن أن يحقق انتصارات عالية الأداء من المترجم.

انهم جميعا يدافعون عنها. سواء أكان ذلك حكيماً أم لا ، لم أستطع أن أقول ، ولكن من ما أستطيع أن أقوله يبدو معقولاً بما يكفي لاستخدام [-Fast] في إصدار إذا كنت لا تقوم بعمل نقطة عائمة عالية الدقة وأنت لا تثق بأي عدد صحيح أو مجموعة فائض ممكن في البرنامج. إذا كنت بحاجة إلى أداء عالٍ وفحوصات فائضة / حساب دقيق ، فاختر لغة أخرى في الوقت الحالي.

تحديث BETA 3:

n = 10_000 مع [-O] :

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

سريع بشكل عام هو أسرع قليلا ويبدو أن نوع المدمج في سويفت تغيرت بشكل كبير.

تحديث نهائي:

[-Onone] :

Swift:   0.678056695
C:       0.000973914

[-O] :

Swift:   0.001158492
C:       0.001192406

[-Ounchecked] :

Swift:   0.000827764
C:       0.001078914

كنت أقوم بتطبيق خوارزمية في 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 s على جهاز الكمبيوتر الخاص بي.

في بايثون ، يستغرق الأمر 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 مع "الإصدار" مقابل بنيات "Debug" متشابهة.

ما هو الخطأ هنا؟ يمكن أن أفهم بعض فقدان الأداء بالمقارنة مع C ++ ، ولكن ليس تباطؤ 10 أضعاف بالمقارنة مع بيثون النقي.

تحرير: لاحظت -O3 أن تغيير -O3 إلى -Ofast يجعل تشغيل هذا الرمز بنفس سرعة إصدار C ++! ومع ذلك ، -Ofast يغير دلالات اللغة كثيرا - في الاختبار الخاص بي ، أنه تعطيل الشيكات -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 ودول مجلس التعاون الخليجي لدينا -ftrapv لفحص -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: في التعليقات ، طلب Ferruccio لمعايير عادلة بمعنى أنها لا تعتمد على وظائف مدمجة (مثل الفرز). أعتقد أن البرنامج التالي مثال جيد

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 s
  • جافا: 0.2 ثانية
  • بايثون مع PyPy: 0.5 ثانية
  • بايثون: 12 ثانية
  • سويفت - سريع: 0.05 ثانية
  • سويفت -O3: 23 ثانية
  • Swift -O0: 443 s

(إذا كنت قلقًا من أن المحول البرمجي قد يعمل على تحسين الحلقات التي لا معنى لها تمامًا ، فيمكنك تغييرها على سبيل المثال x[i] ^= x[j] ، وإضافة عبارة الطباعة التي تخرج x[0] ، وهذا لا يغير أي شيء ؛ ستكون التوقيتات متشابهة جدًا.)

ونعم ، هنا كان تنفيذ بايثون تنفيذ بيثون خالص غبي مع قائمة من النتوء ومتداخلة من أجل الحلقات. يجب أن يكون أبطأ بكثير من سويفت غير المفيد. يبدو أن شيء ما قد تم كسره بشكل خطير باستخدام فهرسة Swift و array.

تحرير 4: يبدو أن هذه المشكلات (بالإضافة إلى بعض مشكلات الأداء الأخرى) قد تم إصلاحها في الإصدار Xcode 6 beta 5.

للفرز ، لدي الآن التوقيتات التالية:

  • clang ++ -O3: 0.06 s
  • swiftc -Ofast: 0.1 s
  • swiftc -O: 0.1 s
  • سويفتك: 4 ثوان

للحلقات المتداخلة:

  • clang ++ -O3: 0.06 s
  • swiftc -Ofast: 0.3 s
  • swiftc -O: 0.4 s
  • سويفتك: 540 ثانية

يبدو أنه لم يعد هناك أي سبب لاستخدام غير آمن -Ofast (aka -Ounchecked ) ؛ عادي -O تنتج رمز جيد على قدم المساواة.


TL ؛ DR : نعم ، تطبيق اللغة سويفت الوحيد بطيء ، في الوقت الحالي . إذا كنت تحتاج إلى شفرة سريعة رقمية (وأنواع أخرى من التعليمات البرمجية ، يفترض أن تكون شيفرة) ، فما عليك سوى استخدام شفرة أخرى. في المستقبل ، يجب عليك إعادة تقييم اختيارك. قد تكون جيدة بما يكفي لمعظم التعليمات البرمجية للتطبيق المكتوبة على مستوى أعلى ، بالرغم من ذلك.

من ما أراه في SIL و LLVM IR ، يبدو أنهم يحتاجون إلى مجموعة من التحسينات لإزالة الإزالة والإطلاقات ، والتي يمكن تنفيذها في Clang (لـ Objective-C) ، لكنهم لم يقوموا بنقلها بعد. هذه هي النظرية التي أذهب إليها (في الوقت الحالي ... ما زلت أحتاج إلى تأكيد أن كلانج تفعل شيئًا حيال ذلك) ، نظرًا لأن اختبار البروفيتر في آخر اختبار لهذا السؤال ينتج عنه هذه النتيجة "الجميلة":

كما قال العديد من الآخرين ، -Ofast غير آمنة تماما وتغيير دلالات اللغة. بالنسبة لي ، في مرحلة "إذا كنت ستستخدم ذلك ، استخدم مجرد لغة أخرى". سأعيد تقييم هذا الاختيار لاحقًا ، إذا تغير.

-O3 يحصل لنا مجموعة من المكالمات swift_release و swift_release ، بصراحة ، لا تبدو كما ينبغي أن يكون هناك لهذا المثال. يجب أن يكون المحسن قد سعى (معظمهم) AFAICT ، لأنه يعرف معظم المعلومات حول الصفيف ، ويعرف أنه يحتوي (على الأقل) على إشارة قوية إليه.

لا ينبغي أن تصدر المزيد من عمليات الإبقاء عندما لا تتصل حتى بالوظائف التي قد تحرر الكائنات. لا أعتقد أن مُصممًا صفيفًا يمكنه إرجاع صفيف أصغر مما كان مطلوبًا ، مما يعني أن الكثير من عمليات التحقق التي تم إصدارها غير مجدية. كما يعرف أن العدد الصحيح لن يتجاوز 10 كيلو بايت ، لذا يمكن تحسين فحوصات الفائض (ليس بسبب الغرابة -Ofast ، ولكن بسبب دلالات اللغة (لا شيء آخر يغير ذلك var ولا يمكنه الوصول إليه ، ويضيف إلى 10K آمن للنوع Int ).

قد لا يتمكن المحول البرمجي من فك المصفوفة أو عناصر الصفيف ، على الرغم من ذلك ، حيث يتم تمريرها sort() ، وهي وظيفة خارجية ويجب أن تحصل على الحجج التي تتوقعها. هذا سيجعلنا نحتاج إلى استخدام قيم Int بشكل غير مباشر ، مما يجعلها تسير أبطأ قليلاً. يمكن أن يتغير هذا إذا كانت الوظيفة sort() العامة (وليس بالطريقة متعددة الأساليب) متاحة للمُجمّع وحصلت على محاذاة.

هذه لغة جديدة جدًا (علنية) ، وهي تمر بما أفترضه كثيرًا من التغييرات ، نظرًا لوجود أشخاص (كثيرين) متورطين بلغة 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")

ملاحظة: أنا لست خبيرا في Objective-C أو جميع المرافق من Cocoa ، أو الهدف C ، أو أوقات التشغيل السريع. قد أفترض أيضًا بعض الأشياء التي لم أكتبها.


من The Swift Programming Language :

توفر المكتبة القياسية في Sort Function Swift وظيفة تسمى sort ، والتي تقوم بترتيب صف من القيم لنوع معروف ، بناءً على مخرجات إغلاق الفرز الذي تقدمه. بمجرد اكتمال عملية الفرز ، تقوم دالة الفرز بإرجاع صفيف جديد من نفس النوع والحجم مثل نفس النوع القديم ، مع عناصره في الترتيب الصحيح الذي تم فرزه.

لدى الدالة sort تعريفات اثنين.

التعريف الافتراضي الذي يسمح لك بتحديد إغلاق المقارنة:

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

والإعلان الثاني أن تأخذ فقط معلمة واحدة (الصفيف) و "hardcoded لاستخدام أقل من المقارنة."

func sort<T : Comparable>(array: T[]) -> T[]

Example:
sort( _arrayToSort_ ) { $0 > $1 }

لقد اختبرت نسخة معدلة من شفرتك في ملعب مع الإغلاق المضاف حتى أتمكن من مراقبة الوظيفة عن كثب أكثر ، ووجدت أنه مع ضبط n على 1000 ، تم استدعاء الإغلاق حوالي 11000 مرة.

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
}

باستخدام هذا مع ن = 1000 ، وجدت ذلك

  1. تم استدعاء quickSort () حوالي 650 مرة ،
  2. حوالي 6000 مقايضة كانت مصنوعة ،
  3. وهناك حوالي 10،000 مقارنات

يبدو أن أسلوب الفرز المدمج هو (أو هو قريب من) النوع السريع ، وبطء حقا ...


قررت أن ألقي نظرة على هذا من أجل المتعة ، وهنا هي التوقيتات التي أحصل عليها:

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..<arraySize {
        randomNumbers.append(arc4random_uniform(UInt32(arraySize)))
    }

    let start = Date()
    randomNumbers.sort()
    let end = Date()

    print(randomNumbers[0])
    print("Elapsed time: \(end.timeIntervalSince(start))")
}

doTest()

النتائج:

سويفت 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

سويفت 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

سويفت 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 .

سويفت 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 للمرة الأولى.

سويفت 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 <chrono>
#include <iostream>
#include <vector>
#include <cstdint>
#include <stdlib.h>

using namespace std;
using namespace std::chrono;

int main(int argc, const char * argv[]) {
    const auto arraySize = 10000000;
    vector<uint32_t> 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<duration<double>>(end - start).count() << "\n";

    return 0;
}

النتائج:

أبل كلانج 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

أبل كلانج 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

أبل كلانج 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

أبل كلانج 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

أبل كلانج 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

حكم

في وقت كتابة هذه السطور ، كان فرز سويفت سريعًا ، ولكن ليس سريعًا مثل تصنيف C ++ عند تجميعها مع -O ، مع المترجمين والمكتبات أعلاه. مع -Ounchecked ، يبدو أن سرعة C ++ في Swift 4.0.2 و Apple LLVM 9.0.0.


تمت إعادة أداء أداء صفيف سريع:

كتبت معياري الخاص مقارنة سويفت مع C / Objective-C. يحسب معي المؤشر الأساسي الأعداد الأولية. ويستخدم مجموعة من الأعداد الأولية السابقة للبحث عن العوامل الأولية في كل مرشح جديد ، لذلك فهو سريع للغاية. ومع ذلك ، فإنه يفعل TONS من القراءة الصفيف ، وأقل الكتابة إلى المصفوفات.

أنا فعلت هذا المؤشر في الأصل ضد سويفت 1.2. قررت تحديث المشروع وتشغيله ضد Swift 2.0.

يتيح لك المشروع الاختيار بين استخدام صفائف سريعة عادية واستخدام مخازن الذاكرة المؤقتة غير الآمنة من Swift باستخدام دلالات الصفيف.

بالنسبة لـ C / Objective-C ، يمكنك إما اختيار استخدام NSArrays أو صفيف C malloc'ed.

يبدو أن نتائج الاختبار مشابهة إلى حدٍ ما مع أسرع التحسينات في الشفرة ([-s-0]) أو أسرع ، العدوانية ([-0fast]) الأمثل.

لا يزال أداء Swift 2.0 رهيباً مع إيقاف تشغيل تحسين الكود ، في حين أن أداء C / Objective-C أبطأ بشكل معتدل.

خلاصة القول هي أن الحسابات القائمة على المصفوفة من طراز malloc'd C هي الأسرع ، بهامش متواضع

يستغرق التخزين السريع مع المخازن المؤقتة غير الآمنة حوالي 1.19X - 1.20X أطول من صفائف malloc'd C عند استخدام التحسين الأصغر والأسرع للرمز. يبدو الفرق أقل بقليل مع تحسين سريع وفعال (يأخذ Swift أكثر مثل 1.18x إلى 1.16x أطول من C.

إذا كنت تستخدم صفائف Swift العادية ، يكون الفرق مع C أكبر قليلاً . (تستغرق سويفت من 1.22 إلى 1.23).

مصفوفات Swift العادية بشكل DRAMATICALLY أسرع مما كانت عليه في Swift 1.2 / Xcode 6. كان أداءها قريبًا جدًا من صفائف Swift المؤقتة غير الآمنة التي لا تستخدم المخازن المؤقتة للذاكرة غير الآمنة حقاً تستحق العناء أكثر من ذلك ، وهي كبيرة.

راجع للشغل ، والهدف C أداء NSArray ينتن. إذا كنت ستستخدم كائنات الحاوية الأصلية بكلتا اللغتين ، فسيكون Swift أسرع بشكل دراماتيكي .

يمكنك التحقق من مشروعي على جيثب في SwiftPerformanceBenchmark

يحتوي على واجهة مستخدم بسيطة تجعل عملية جمع الإحصائيات سهلة جدًا.

من المثير للاهتمام أن الفرز يبدو أسرع قليلاً في Swift عنه في C الآن ، لكن هذه الخوارزمية الأولية لا تزال أسرع في Swift.


اعتبارًا من Xcode 7 ، يمكنك تشغيل " Fast, Whole Module Optimization . هذا من شأنه أن يزيد من أدائك على الفور.


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

يمكنك إلقاء نظرة على خوارزمية تقسيم Lomuto في تقسيم القائمة. مكتوب في سويفت


كان يمكن تحقيق ذلك من خلال دالة فرز بسيطة ذات قيمة واحدة () . شغّل مقتطف الرمز أدناه لمشاهدة العرض التوضيحي.

var homes = [
    {
        "h_id": "3",
        "city": "Dallas",
        "state": "TX",
        "zip": "75201",
        "price": "162500"
    }, {
        "h_id": "4",
        "city": "Bevery Hills",
        "state": "CA",
        "zip": "90210",
        "price": "319250"
    }, {
        "h_id": "5",
        "city": "New York",
        "state": "NY",
        "zip": "00010",
        "price": "962500"
    }
];

console.log("To sort descending/highest first, use operator '<'");

homes.sort(function(a,b) { return a.price.valueOf() < b.price.valueOf();});

console.log(homes);

console.log("To sort ascending/lowest first, use operator '>'");

homes.sort(function(a,b) { return a.price.valueOf() > b.price.valueOf();});

console.log(homes);





swift algorithm performance sorting