Когда я играл с быстрым учебником, я начал писать собственный isPrime
метод, чтобы проверить, является ли данный Int
простым или нет.
После записи я понял, что он работает нормально, но обнаружил, что он немного медленнее выполнять isPrime
на некоторых довольно больших числах (все еще намного ниже Int.max
).
Итак, я написал тот же кусок кода в objc, и код был выполнен намного быстрее (коэффициент 66x).
Вот быстрый код:
class Swift {
class func isPrime(n:Int) -> Bool {
let sqr : Int = Int(sqrt(Double(n))) + 1
for i in 2...sqr {
if n % i == 0 {
return false
}
}
return true;
}
class func primesInRange(start:Int, end:Int) -> Int[] {
var primes:Int[] = Int[]()
for n in start...end {
if self.isPrime(n) {
primes.append(n)
}
}
return primes;
}
}
И код objc:
@implementation Utils
+ (BOOL)isPrime:(NSUInteger)n {
NSInteger sqr = (NSUInteger)(sqrt(n))+1;
for (NSUInteger i = 2; i < sqr; ++i) {
if (n % i == 0) {
return false;
}
}
return YES;
}
+ (NSArray*)primesInRange:(NSUInteger)start end:(NSUInteger)end {
NSMutableArray* primes = [NSMutableArray array];
for (NSUInteger i = start; i <= end; ++i) {
if ([self isPrime:i])
[primes addObject:@(i)];
}
return primes.copy;
}
@end
И в main.swift
:
let startDateSwift = NSDate.date()
let swiftPrimes = Swift.primesInRange(1_040_101_022_000, end: 1_040_101_022_200)
let elapsedSwift = NSDate.date().timeIntervalSinceDate(startDateSwift)*1000
let startDateObjc = NSDate.date()
let objcPrimes = Utils.primesInRange(1_040_101_022_000, end: 1_040_101_022_200)
let elapsedObjc = NSDate.date().timeIntervalSinceDate(startDateObjc)*1000
println("\(swiftPrimes) took: \(elapsedSwift)ms");
println("\(objcPrimes) took: \(elapsedObjc)ms");
Это дает:
[1040101022027, 1040101022039, 1040101022057, 1040101022099, 1040101022153] took: 3953.82004976273ms
[1040101022027, 1040101022039, 1040101022057, 1040101022099, 1040101022153] took: 66.4250254631042ms
Я знаю, что я мог бы использовать extension
on Int
здесь, чтобы проверить, является ли число простым, но я хотел, чтобы оба кода были очень похожими.
Может ли кто-нибудь сказать мне, почему этот быстрый код намного медленнее? 66x фактор довольно пугающий и только ухудшается по мере увеличения диапазона.