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

www.hbu.cn at 163.com www.hbu.cn at 163.com
Fri Apr 21 09:41:08 CDT 2017

```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

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 }

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 *

> 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,
>
> 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*
>
>
>   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>
```