[swift-users] [swift-evolution] Low efficiency multidimensional array problem

[www.hbu.cn at 163.com]

Hi Jaden Geller, Saagar ,

   Thanks for the reply and advice. Array2D is really faster than the
default two dimension. But I think as a general language, Swift should
provide default efficient ways for multiple dimension array.

  I found this problem when I write an algorithm. It is a DP problem and
the description is here
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

My code is as following, a little long. It define Array3D, including two
 strategies to implement  it. One is with default Array way: another is,
like Jaden said, using one dimension array. The second one is twice faster
comparing to the first one. I think swift should optimize swift array.
Implementing the very basic multiple dimension array is not developer
friendly.

import Foundation

enum Strategy {

    case defaultImpletions

    case useOneDemensionArray

}

class Solution {

    static func maxProfit(_ k: Int, _ prices: [Int], strategy:Strategy) ->
Int {

        if (k <= 0 || prices.count <= 1) {

            return 0

        }

        if (k >= prices.count) {

            return quickSolve(prices)

        }

        let profit = Array3D<Int>(x: 2, y: k + 1, z: 2, value: 0, strategy:
strategy)

        for j in 0 ... k { profit[0, j, 1] = -prices[0] }

        for i in 1 ... prices.count - 1 {

            for j in 0 ... k {

                profit[i & 1, j, 0] = max(profit[(i - 1) & 1, j, 0],  j > 0
? profit[(i - 1) & 1 , j - 1, 1] + prices[i] : 0)

                profit[i & 1, j, 1] = max(profit[(i - 1) & 1, j, 1], profit[(i
- 1) & 1, j, 0] - prices[i])

            }

        }

        return profit[(prices.count - 1) & 1, k, 0]

    }



    static func quickSolve(_ prices:[Int]) -> Int {

        var sum = 0

        for i in 1 ... prices.count - 1 {

            if prices[i] - prices[i - 1] > 0 {

                sum += prices[i] - prices[i - 1]

            }

        }

        return sum

    }



    static func randomArrayWithCount(count: Int) -> [Int] {

        var result = [Int]()

        for _ in 0 ... count - 1 {

            result.append(Int(arc4random() % UInt32(1000)))

        }

        return result

    }

}


class Array3D <T> {

    let x: Int

    let y: Int

    let z: Int

    var array: [T]!

    var threeDemsionArray: [[[T]]]!

    var strategy: Strategy

    init(x:Int, y:Int, z:Int, value: T, strategy: Strategy) {

        self.x = x

        self.y = y

        self.z = z

        self.strategy = strategy

        if strategy == .useOneDemensionArray {

            array = Array.init(repeating: value, count: x * y * z)

        } else {

            threeDemsionArray = Array(repeating: Array(repeating:
Array(repeating:
value, count: z), count: y), count: x)

        }

    }



    subscript(i:Int, j:Int, k: Int) -> T {

        get {

            if strategy == .useOneDemensionArray {

                return array[offset(i: i, j: j, k: k)]

            } else {

                return threeDemsionArray[i][j][k]

            }

        }

        set {

            if strategy == .useOneDemensionArray {

                array[offset(i: i, j: j, k: k)] = newValue

            } else {

                threeDemsionArray[i][j][k] = newValue

            }

        }

    }



    func offset(i: Int, j: Int, k: Int) -> Int {

        var offset = i * y * z

        offset += j * z

        offset += k

        return offset

    }

}


var count = 10

for i in 1 ... 5 {

    let array = Solution.randomArrayWithCount(count: count)

    var lastDate = Date()

    _ = Solution.maxProfit(6, array, strategy: .useOneDemensionArray)

    let oneDemensionArrayRunTime = Date().timeIntervalSince(lastDate) * 1000

    lastDate = Date()

    _ = Solution.maxProfit(6, array, strategy: .defaultImpletions)

    let defaultImpletionsRuntime = Date().timeIntervalSince(lastDate) * 1000

    print("count: \(count) run time: oneDemension: \(
oneDemensionArrayRunTime), defaultImpl:\(defaultImpletionsRuntime)
ratio:\(defaultImpletionsRuntime
/ oneDemensionArrayRunTime)")

    count *= 10

}



*best wishes for you *

2017-04-19 17:55 GMT+08:00 Jaden Geller <jaden.geller at gmail.com>:

> Hi Hbucius,
>
> You can define your own `Array2D` type that uses a 1-dimensional array as
> backing (for fast performance) but exposes a high-level 2-dimensional array
> API.
>
> Here’s a really primitive starting point I found on GitHub:
> https://github.com/raywenderlich/swift-algorithm-club/blob/master/Array2D/
> Array2D.swift
>
> Cheers,
> Jaden Geller
>
> On Apr 18, 2017, at 11:39 PM, Saagar Jha via swift-evolution <
> swift-evolution at swift.org> wrote:
>
> It might be helpful if you showed a bit more of the code you’re working
> on, so that we can better see what you’re trying to do. Is there any
> operation in particular that is slow?
>
> Also, CC’ing swift-users since I think it belongs there.
>
> Saagar Jha
>
> On Apr 18, 2017, at 22:57, Hbucius Smith via swift-evolution <
> swift-evolution at swift.org> wrote:
>
> Hello Swift community,
>
>
>     When I used multidimensional array in swift, I found it is very low
> efficiency.
>
>
>     I used in the following way :
>
>
> *    var array = Array.init(repeating: Array.init(repeating: 0, count: 5),
> count: 5)*
>
> *    array[0][0] = 0*
>
>
>   I have read some posts in stack overflow. It suggests using one
> dimension to fake multidimensional array. I think it is too ugly. DO we
> have better choice for this ?
>
>
>
>
>
>
> *best wishes for you *
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20170421/fd8430de/attachment.html>