Algorithms package: iterating through deeply nested Product2Sequence is very slow

Using Swift
1

I try to solve digits to letters combinations problem using Algorithms package's product(...). I'm seeing very slow iteration through the resulting deeply nested Product2Sequence:

static func digitsToLetters(_ first: Int, _ second: Int, _ third: Int, _ forth: Int, _ fifth: Int, _ sixth: Int, _ seventh: Int, _ eighth: Int, _ ninth: Int, _ tenth: Int, _ eleventh: Int) -> [String] {
    let product = product(product(product(product(product(product(product(product(product(product(first.letters, second.letters), third.letters), forth.letters), fifth.letters), sixth.letters), seventh.letters), eighth.letters), ninth.letters), tenth.letters), eleventh.letters)
    // this is going through only 419904 elements for my test input
    // why is this slow? this map/loop takes several seconds (debug compile)
    return product.map { t, e in            // <== map here is very slow
        let (((((((((p10, p9), p8), p7), p6), p5), p4), p3), p2), p1) = t
        return String([p10, p9, p8, p7, p6, p5, p4, p3, p2, p1, e])
    }
}

The type of product is:

Product2Sequence<Product2Sequence<Product2Sequence<Product2Sequence<Product2Sequence<Product2Sequence<Product2Sequence<Product2Sequence<Product2Sequence<Product2Sequence<Array<Character>, Array<Character>>, Array<Character>>, Array<Character>>, Array<Character>>, Array<Character>>, Array<Character>>, Array<Character>>, Array<Character>>, Array<Character>>, Array<Character>>

Iterating through this sequence with .map is very slow. Add .lazy to the sequence doesn't make any difference.

Complete macOS command line test 
import Foundation
import ArgumentParser
import Algorithms

extension Int {
    static let digitToLetters = ["~", "~", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"].map { $0.map { $0} }

    // using [Character] as collection to calculate product is not any faster than String to iterate through the resulting Product2Sequence
    var letters: [Character] {
        precondition(self >= 0 && self <= 9)
        return Self.digitToLetters[self]
    }
}

extension Array where Element == Int {
    func letterCombinations() -> [String] {
        let digits = filter { $0 >= 2 }     // first remove 0 or 1
        // we can handle up to 11 digits, all digits must be 2 - 9
        precondition(digits.count <= 11 && digits.allSatisfy { $0 >= 2 && $0 <= 9 })
        switch digits.count {
        case 0:
            return []
        case 1:
            return Self.digitsToLetters(digits[0])
        case 2:
            return Self.digitsToLetters(digits[0], digits[1])
        case 3:
            return Self.digitsToLetters(digits[0], digits[1], digits[2])
        case 4:
            return Self.digitsToLetters(digits[0], digits[1], digits[2], digits[3])
        case 5:
            return Self.digitsToLetters(digits[0], digits[1], digits[2], digits[3], digits[4])
        case 6:
            return Self.digitsToLetters(digits[0], digits[1], digits[2], digits[3], digits[4], digits[5])
        case 7:
            return Self.digitsToLetters(digits[0], digits[1], digits[2], digits[3], digits[4], digits[5], digits[6])
        case 8:
            return Self.digitsToLetters(digits[0], digits[1], digits[2], digits[3], digits[4], digits[5], digits[6], digits[7])
        case 9:
            return Self.digitsToLetters(digits[0], digits[1], digits[2], digits[3], digits[4], digits[5], digits[6], digits[7], digits[8])
        case 10:
            return Self.digitsToLetters(digits[0], digits[1], digits[2], digits[3], digits[4], digits[5], digits[6], digits[7], digits[8], digits[9])
        case 11:
            return Self.digitsToLetters(digits[0], digits[1], digits[2], digits[3], digits[4], digits[5], digits[6], digits[7], digits[8], digits[9], digits[10])
        default:
            fatalError()
        }
    }

    // all the Int parameters must be 2 - 9
    static func digitsToLetters(_ first: Int) -> [String] {
        return first.letters.map { String($0) }
    }

    static func digitsToLetters(_ first: Int, _ second: Int) -> [String] {
        let product = product(first.letters, second.letters)
        return product.map { String([$0, $1]) }
    }

    static func digitsToLetters(_ first: Int, _ second: Int, _ third: Int) -> [String] {
        let product = product(product(first.letters, second.letters), third.letters)
        return product.map({ t, e in
            String([t.0, t.1, e])
        })
    }

    static func digitsToLetters(_ first: Int, _ second: Int, _ third: Int, _ forth: Int) -> [String] {
        let product = product(product(product(first.letters, second.letters), third.letters), forth.letters)
        return product.map { t, e in
            let ((p3, p2), p1) = t
            return String([p3, p2, p1, e])
        }
    }

    static func digitsToLetters(_ first: Int, _ second: Int, _ third: Int, _ forth: Int, _ fifth: Int) -> [String] {
        let product = product(product(product(product(first.letters, second.letters), third.letters), forth.letters), fifth.letters)
        return product.map { t, e in
            let (((p4, p3), p2), p1) = t
            return String([p4, p3, p2, p1, e])
        }
    }

    static func digitsToLetters(_ first: Int, _ second: Int, _ third: Int, _ forth: Int, _ fifth: Int, _ sixth: Int) -> [String] {
        let product = product(product(product(product(product(first.letters, second.letters), third.letters), forth.letters), fifth.letters), sixth.letters)
        return product.map { t, e in
            let ((((p5, p4), p3), p2), p1) = t
            return String([p5, p4, p3, p2, p1, e])
        }
    }

    static func digitsToLetters(_ first: Int, _ second: Int, _ third: Int, _ forth: Int, _ fifth: Int, _ sixth: Int, _ seventh: Int) -> [String] {
        let product = product(product(product(product(product(product(first.letters, second.letters), third.letters), forth.letters), fifth.letters), sixth.letters), seventh.letters)
        return product.map { t, e in
            let (((((p6, p5), p4), p3), p2), p1) = t
            return String([p6, p5, p4, p3, p2, p1, e])
        }
    }

    static func digitsToLetters(_ first: Int, _ second: Int, _ third: Int, _ forth: Int, _ fifth: Int, _ sixth: Int, _ seventh: Int, _ eighth: Int) -> [String] {
        let product = product(product(product(product(product(product(product(first.letters, second.letters), third.letters), forth.letters), fifth.letters), sixth.letters), seventh.letters), eighth.letters)
        return product.map { t, e in
            let ((((((p7, p6), p5), p4), p3), p2), p1) = t
            return String([p7, p6, p5, p4, p3, p2, p1, e])
        }
    }

    static func digitsToLetters(_ first: Int, _ second: Int, _ third: Int, _ forth: Int, _ fifth: Int, _ sixth: Int, _ seventh: Int, _ eighth: Int, _ ninth: Int) -> [String] {
        let product = product(product(product(product(product(product(product(product(first.letters, second.letters), third.letters), forth.letters), fifth.letters), sixth.letters), seventh.letters), eighth.letters), ninth.letters)
        return product.map { t, e in
            let (((((((p8, p7), p6), p5), p4), p3), p2), p1) = t
            return String([p8, p7, p6, p5, p4, p3, p2, p1, e])
        }
    }

    static func digitsToLetters(_ first: Int, _ second: Int, _ third: Int, _ forth: Int, _ fifth: Int, _ sixth: Int, _ seventh: Int, _ eighth: Int, _ ninth: Int, _ tenth: Int) -> [String] {
        let product = product(product(product(product(product(product(product(product(product(first.letters, second.letters), third.letters), forth.letters), fifth.letters), sixth.letters), seventh.letters), eighth.letters), ninth.letters), tenth.letters)
        return product.map { t, e in
            let ((((((((p9, p8), p7), p6), p5), p4), p3), p2), p1) = t
            return String([p9, p8, p7, p6, p5, p4, p3, p2, p1, e])
        }
    }

    static func digitsToLetters(_ first: Int, _ second: Int, _ third: Int, _ forth: Int, _ fifth: Int, _ sixth: Int, _ seventh: Int, _ eighth: Int, _ ninth: Int, _ tenth: Int, _ eleventh: Int) -> [String] {
        let product = product(product(product(product(product(product(product(product(product(product(first.letters, second.letters), third.letters), forth.letters), fifth.letters), sixth.letters), seventh.letters), eighth.letters), ninth.letters), tenth.letters), eleventh.letters)
        // this is going through only 419904 elements for my test input
        // why is this slow? this map/loop takes several seconds
        return product.map { t, e in            // <== map here is very slow
            let (((((((((p10, p9), p8), p7), p6), p5), p4), p3), p2), p1) = t
            return String([p10, p9, p8, p7, p6, p5, p4, p3, p2, p1, e])
        }
    }
}

@main
struct ProductDemo: ParsableCommand {
    mutating func run() throws {
        let digits = [7, 2, 3, 4, 5, 6, 7, 8, 9, 4, 6]
        let answer = digits.letterCombinations()
        print(digits.count, answer.count)
        print(answer.prefix(10))
    }
}

Another problem: Product2Sequence use tuple. So the only way to use its result is accessing the tuple. Which mean statically know at compile time. So where is no way to different length of products algorithmically? I have to make separate func handling digit count 1 - 11.

2

You mentioned you're doing a debug build. That's expected to be quite slow. Is it slow in an optimized build?

3

:scream: Run optimized build, it's instantaneous!

What's making debug build run so slow?

4

Swift relies very heavily on the optimizer for performance. Debug builds tend to be pretty slow, though I couldn't guess what specifically is slowing your case down without profiling. Probably unwanted copies-on-write and/or lack of necessary inlining though.

4 Likes