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.gel...@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-evolut...@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-evolut...@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-evolut...@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution > > > _______________________________________________ > swift-evolution mailing list > swift-evolut...@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution > > >
_______________________________________________ swift-users mailing list swift-users@swift.org https://lists.swift.org/mailman/listinfo/swift-users
