Время выполнить функциональное отображение Swift

Question

Я играю с ситом Эратосфена

Если я заменю свою линию:

primes.index(of: i).map {primes.remove(at: $0)}

на

if let indx = primes.index(of: i) {
primes.remove(at: indx)
}

, завершая сито простых чисел до1000 идет от 2,817 секунд до 1,501 секунды.

Я хочу знать, почему.

Весь мой код:

func sieve(_ num: Int) -> [Int]{
    var primes = Array (2...num)
    func generateSieve(_ num: Int){
        let max = primes.max()!
        if max == num {return}
        else{
            for i in stride(from: (2 * num), to: max+1, by: num) {

                if let indx = primes.index(of: i) {
                    primes.remove(at: indx)
                }
//                primes.index(of: i).map {primes.remove(at: $0)}
            }
            for j in primes {
                if j>num
                {
                    generateSieve(j)
                    return
                }
            }
        }
    }
    generateSieve(2)
    return primes
}

Answer 1

Развертывание необязательного файла с if let или Optional.map имеет сопоставимое время.

Разница заключается в том, что Optional.map имеет возвращаемое значение.И не забывайте, что Array.remove(at:) возвращает удаленный элемент.

В .map {primes.remove(at: $0)} есть два возвращаемых значения, которые отбрасываются.Принимая во внимание, что при вашем втором подходе отбрасывается только один результат: primes.remove(at: indx).И, следовательно, лучшая производительность последнего подхода.

Answer 2

Следующие строки:

var primes = Array (2...20)

func generateSieve(_ num: Int){
    let max = primes.max()!
    if max == num {return}
    else{
        for i in stride(from: (2 * num), to: max+1, by: num) {

            if let indx = primes.index(of: i) {
                primes.remove(at: indx)
            }
            //                primes.index(of: i).map {primes.remove(at: $0)}
        }
        for j in primes {
            if j>num
            {
                generateSieve(j)
                return
            }
        }
    }
}

generateSieve(2)

Перевести на эти инструкции:

    test`main:
    0x100001e30 <+0>:   pushq  %rbp
    0x100001e31 <+1>:   movq   %rsp, %rbp
    0x100001e34 <+4>:   subq   $0x60, %rsp
    0x100001e38 <+8>:   movl   %edi, -0x34(%rbp)
    0x100001e3b <+11>:  movq   %rsi, -0x40(%rbp)
    0x100001e3f <+15>:  jmp    0x100001e41               ; <+17> at main.swift:12
    0x100001e41 <+17>:  movq   $0x2, -0x18(%rbp)
    0x100001e49 <+25>:  movq   $0x14, -0x20(%rbp)
    0x100001e51 <+33>:  movq   -0x18(%rbp), %rdi
    0x100001e55 <+37>:  movq   -0x20(%rbp), %rsi
    0x100001e59 <+41>:  callq  0x100023cd0               ; generic specialization <Swift.Int> of Swift.ClosedRange.init(uncheckedBounds: (lower: A, upper: A)) -> Swift.ClosedRange<A>
    0x100001e5e <+46>:  movq   %rax, -0x10(%rbp)
    0x100001e62 <+50>:  movq   %rdx, -0x8(%rbp)
    0x100001e66 <+54>:  xorl   %eax, %eax
    0x100001e68 <+56>:  movl   %eax, %edi
    0x100001e6a <+58>:  leaq   -0x30(%rbp), %rcx
    0x100001e6e <+62>:  movq   -0x10(%rbp), %rdx
    0x100001e72 <+66>:  movq   -0x8(%rbp), %rsi
    0x100001e76 <+70>:  movq   %rdx, -0x30(%rbp)
    0x100001e7a <+74>:  movq   %rsi, -0x28(%rbp)
    0x100001e7e <+78>:  movq   %rcx, -0x48(%rbp)
    0x100001e82 <+82>:  callq  0x100001ed0               ; type metadata accessor for Swift.ClosedRange<Swift.Int> at <compiler-generated>
    0x100001e87 <+87>:  movq   %rax, -0x50(%rbp)
    0x100001e8b <+91>:  movq   %rdx, -0x58(%rbp)
    0x100001e8f <+95>:  callq  0x100001f60               ; lazy protocol witness table accessor for type Swift.ClosedRange<Swift.Int> and conformance < where A: Swift.Strideable, A.Stride: Swift.SignedInteger> Swift.ClosedRange<A> : Swift.Sequence in Swift at <compiler-generated>
    0x100001e94 <+100>: leaq   0x56e035(%rip), %rsi      ; type metadata for Swift.Int
    0x100001e9b <+107>: movq   -0x48(%rbp), %rdi
    0x100001e9f <+111>: movq   -0x50(%rbp), %rdx
    0x100001ea3 <+115>: movq   %rax, %rcx
    0x100001ea6 <+118>: callq  0x1000f74a0               ; Swift.Array.init<A where A == A1.Element, A1: Swift.Sequence>(A1) -> Swift.Array<A>
    0x100001eab <+123>: movl   $0x2, %r8d
    0x100001eb1 <+129>: movl   %r8d, %edi
    0x100001eb4 <+132>: movq   %rax, 0x5865a5(%rip)      ; test.primes : Swift.Array<Swift.Int>
->  0x100001ebb <+139>: callq  0x100001fc0               ; test.generateSieve(Swift.Int) -> () at main.swift:13
    0x100001ec0 <+144>: xorl   %eax, %eax
    0x100001ec2 <+146>: addq   $0x60, %rsp
    0x100001ec6 <+150>: popq   %rbp
    0x100001ec7 <+151>: retq   

и эти:

    var primes = Array (2...20)
func generateSieve(_ num: Int){
    let max = primes.max()!
    if max == num {return}
    else{
        for i in stride(from: (2 * num), to: max+1, by: num) {

//            if let indx = primes.index(of: i) {
//                primes.remove(at: indx)
//            }
               primes.index(of: i).map {primes.remove(at: $0)}
        }
        for j in primes {
            if j>num
            {
                generateSieve(j)
                return
            }
        }
    }
}

generateSieve(2)

в:

  test`main:
    0x100001ae0 <+0>:   pushq  %rbp
    0x100001ae1 <+1>:   movq   %rsp, %rbp
    0x100001ae4 <+4>:   subq   $0x60, %rsp
    0x100001ae8 <+8>:   movl   %edi, -0x34(%rbp)
    0x100001aeb <+11>:  movq   %rsi, -0x40(%rbp)
    0x100001aef <+15>:  jmp    0x100001af1               ; <+17> at main.swift:12
    0x100001af1 <+17>:  movq   $0x2, -0x18(%rbp)
    0x100001af9 <+25>:  movq   $0x14, -0x20(%rbp)
    0x100001b01 <+33>:  movq   -0x18(%rbp), %rdi
    0x100001b05 <+37>:  movq   -0x20(%rbp), %rsi
    0x100001b09 <+41>:  callq  0x100023ca0               ; generic specialization <Swift.Int> of Swift.ClosedRange.init(uncheckedBounds: (lower: A, upper: A)) -> Swift.ClosedRange<A>
    0x100001b0e <+46>:  movq   %rax, -0x10(%rbp)
    0x100001b12 <+50>:  movq   %rdx, -0x8(%rbp)
    0x100001b16 <+54>:  xorl   %eax, %eax
    0x100001b18 <+56>:  movl   %eax, %edi
    0x100001b1a <+58>:  leaq   -0x30(%rbp), %rcx
    0x100001b1e <+62>:  movq   -0x10(%rbp), %rdx
    0x100001b22 <+66>:  movq   -0x8(%rbp), %rsi
    0x100001b26 <+70>:  movq   %rdx, -0x30(%rbp)
    0x100001b2a <+74>:  movq   %rsi, -0x28(%rbp)
    0x100001b2e <+78>:  movq   %rcx, -0x48(%rbp)
    0x100001b32 <+82>:  callq  0x100001b80               ; type metadata accessor for Swift.ClosedRange<Swift.Int> at <compiler-generated>
    0x100001b37 <+87>:  movq   %rax, -0x50(%rbp)
    0x100001b3b <+91>:  movq   %rdx, -0x58(%rbp)
    0x100001b3f <+95>:  callq  0x100001c10               ; lazy protocol witness table accessor for type Swift.ClosedRange<Swift.Int> and conformance < where A: Swift.Strideable, A.Stride: Swift.SignedInteger> Swift.ClosedRange<A> : Swift.Sequence in Swift at <compiler-generated>
    0x100001b44 <+100>: leaq   0x56e3a5(%rip), %rsi      ; type metadata for Swift.Int
    0x100001b4b <+107>: movq   -0x48(%rbp), %rdi
    0x100001b4f <+111>: movq   -0x50(%rbp), %rdx
    0x100001b53 <+115>: movq   %rax, %rcx
    0x100001b56 <+118>: callq  0x1000f7470               ; Swift.Array.init<A where A == A1.Element, A1: Swift.Sequence>(A1) -> Swift.Array<A>
    0x100001b5b <+123>: movl   $0x2, %r8d
    0x100001b61 <+129>: movl   %r8d, %edi
    0x100001b64 <+132>: movq   %rax, 0x586915(%rip)      ; test.primes : Swift.Array<Swift.Int>
->  0x100001b6b <+139>: callq  0x100001c70               ; test.generateSieve(Swift.Int) -> () at main.swift:13
    0x100001b70 <+144>: xorl   %eax, %eax
    0x100001b72 <+146>: addq   $0x60, %rsp
    0x100001b76 <+150>: popq   %rbp
    0x100001b77 <+151>: retq 

---

версия с:

primes.index(of: i).map {primes.remove(at: $0)}

имеет 39 строк инструкций (в ASM)

версия с:

if let indx = primes.index(of: i) {
   primes.remove(at: indx)
}

имеет 36 строк инструкций (в ASM)

Кминимизируйте разницу, проверьте уровень оптимизации вашего проекта: от [- Onone] до [- O -whole-module-оптимизация]