Low efficiency multidimensional array problem


(Hbucius Smith) #1

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 *


(Saagar Jha) #2

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@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Jaden Geller) #3

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@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@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


#4

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@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@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@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution