Reputation: 449
The most efficient way to build tree from dictionary data
I have a dictionary with the following structure: [Point:[Line]], where:
- Point - custom data structure that contains two coordinates (X, Y)
- Line - tuple (Point, Point) that contains the first and last points of the line.
- Key - first point of the line.
So, it is a dictionary of lines grouped by their first point, like following:
[a: [(a,b),(a,c)], b: [(b,c), (b,d)], c: [(c,d)] ]
The goal is to convert this dictionary into a list of data structures like following:
- (a,b) -> (b,c) -> (c,d)
- (a,b) -> (b,d)
- (a,c) -> (c,d)
So, basically a tree with the root at the first point.
I tried to use builder pattern and stack to perform this operation, so I created a builder using first point and put in into stack, then started a while loop until stack is empty and then in the loop was removing current builder and creating new ones based on last & first points, the code looked like following:
import Foundation
typealias ProcessedLine = (UUID, [LineModel])
typealias LinePointDict = [Point: [Line]]
class LineAggregator {
var builderStack: Stack<LineModel.LineModelBuilder>
let startPointMap: LinePointDict
var result: ProcessedLine
var currentBuilder: (Point, LineModel.LineModelBuilder)?
let startPoint: Point
init(LineUid: UUID, startPointMap: LinePointDict, startPoint: Point) {
self.builderStack = Stack<LineModel.LineModelBuilder>()
self.startPointMap = startPointMap
self.result = (LineUid, [])
self.startPoint = startPoint
self.currentBuilder = nil
}
func getLineAggregation() -> ProcessedLine {
for Line in startPointMap[startPoint]! {
var bldr = LineModel.LineModelBuilder(initialLineUuid: result.0)
bldr = bldr.addLine(Line: Line)
builderStack.push(bldr)
}
return aggregateModels()
}
func aggregateModels() -> ProcessedLine {
while !builderStack.isEmpty() {
takeBuilderFromStack()
aggregateLine()
}
return result
}
/**
* This functions pops Builder object from stack if the stack is not empty and sets it as a Current object to be processed.
* @param object
* @return
*/
private func takeBuilderFromStack() {
if(!builderStack.isEmpty()) {
let curBuilder = builderStack.pop()!
currentBuilder = (curBuilder.getLastElement(), curBuilder)
}
}
private func aggregateLine() {
if currentBuilder?.1.isLastAdded() ?? true {
//If there is only one Line in the Line model
if(currentBuilder!.1.isLastAddedLineLast()) {
result.1.append(currentBuilder!.1.build())
return
}
if(!builderStack.isEmpty()) {
print("ERROR: Empty builder stack! Such situation should not happen. Pay attention at it.");
builderStack.removeAll()
}
return
}
if currentBuilder != nil {
for Line in startPointMap[currentBuilder!.0]! {
var newBuilder = LineModel.LineModelBuilder(builder: currentBuilder!.1)
newBuilder = newBuilder.addLine(Line: Line)
if Line.isLast {
result.1.append(newBuilder.build())
} else {
builderStack.push(newBuilder)
}
}
}
}
}
This solution is a very straightforward one. It works, but I have a very large amount of data in the dictionary, and the number of combinations is even larger, so this algorithm is extremely slow and not memory efficient.
The main slowness is caused by adding and retrieving data to/from stack which has following implementation:
import Foundation
protocol Stackable {
associatedtype Element
func peek() -> Element?
mutating func push(_ element: Element)
@discardableResult mutating func pop() -> Element?
}
extension Stackable {
var isEmpty: Bool { peek() == nil }
}
struct Stack<Element>: Stackable where Element: Equatable {
private var storage = [Element]()
func peek() -> Element? { storage.first }
mutating func push(_ element: Element) { storage.append(element) }
mutating func pop() -> Element? { storage.popLast() }
func size() -> Int { storage.count }
func isEmpty() -> Bool { storage.isEmpty }
mutating func removeAll() { storage.removeAll() }
}
extension Stack: Equatable {
static func == (lhs: Stack<Element>, rhs: Stack<Element>) -> Bool { lhs.storage == rhs.storage }
}
extension Stack: CustomStringConvertible {
var description: String { "\(storage)" }
}
extension Stack: ExpressibleByArrayLiteral {
init(arrayLiteral elements: Self.Element...) { storage = elements }
}
And another bottleneck is related to copying data and deinit method.
I was trying to find a better solution, but couldn't find anything yet. Would be grateful for any suggestions. Thanks.
Upvotes: 0
Views: 463
Answers (1)
Reputation: 2805
While the builder pattern is useful, I think in this case it just complicates the straight-forward solution, although as you'll see, I'll present a couple that are more complicated, but those are based on increased performance optimizations on the first simple solution.
As you you noted, initializing and deinitializing classes is kind of slow. Actually the worst part is the dynamic memory allocation. Classes are powerful and definitely have their uses, but they're not the fastest tool in the Swift toolbox. Unless you make methods final, calling them can require a virtual dispatch. That can happen with protocols too depending on the particulars of their declaration, though in that case it's called "witness table thunking". But the worst part about classes is that their instances can be littered pretty much anywhere in memory. That's hell on the processor's on-chip cache. So for performance try to avoid dynamic dispatch, and reference types (ie, classes), and when you do need to allocate memory (such as Array or Dictionary), try to allocate all you need at once, and reuse it as much as possible. In Swift that requres some thought because of copy-on-write. You can easily end up allocating memory when you didn't intend to.
I present three solutions. Each one is more complicated, but also (hopefully) faster than the previous one. I'll explain why, and what to look out for. I should mention that I am not including the simplest solution. It is much like my first solution but with local variable arrays. The performance would not be especially good, and you're question makes it clear that performance is an issue.
First there's some boiler plate. To code it up and test it, I needed to define your Point and Line types, plus a few others I use for convenience, as well as some extensions purely for generating output. This code is common to all three solutions. Substitue your own definitions for Point and Line.
struct Point: Hashable
{
// This is just to give the points uniqueness, and letter names
static private let pointNames = [Character]("abcdefghijklmnopqrstuvwxyz")
static private var curNameIndex = 0
static private var nextID: Character
{
defer { curNameIndex += 1 }
return pointNames[curNameIndex]
}
let id = nextID
}
typealias Line = (Point, Point)
typealias Graph = [Point: [Line]]
typealias Path = [Line]
// Now we add some extensions for convenient output
extension Point: CustomStringConvertible {
var description: String { "\(id)" }
}
extension String.StringInterpolation
{
mutating func appendInterpolation(_ line: Line) {
appendLiteral("(\(line.0),\(line.1))")
}
mutating func appendInterpolation(_ lines: [Line]) {
appendLiteral(lines.map { "\($0)" }.joined(separator: "->"))
}
}
You mention that Point has an X and Y, but for this problem it doesn't matter. You just need unique "things" to serve as end-points for your Line instances.
Then I declared the inputs from your example:
let (a, b, c, d) = (Point(), Point(), Point(), Point())
let input = [ a: [(a,b),(a,c)], b: [(b,c), (b,d)], c: [(c,d)] ]
With the common code out of the way, here are the actual solutions:
Solution 1
Although the recursion introduces overhead all by itself, the main problem with the most straight-forward solution is that it requres local arrays that are allocated and deallocated up and down the call stack. The dynamic memory allocations and deallocations for them are actually the main performance problem with the simple recursive solution.
The solution is to attempt to pre-allocate working storage, and re-use it all through-out the recursion, or at least make reallocations rare.
One way would be to allocate the working arrays at the top level and pass them in as inout parameters. Another is to make them mutable properties of a struct (actually, a class wouldn't be too bad in this case, because you only allocate one instance). I chose the latter approach.
As I mentioned in my comment, I think of this problem as a graph theory problem.. Point = node. Line = edge. Though it's not explicitly stated, I assume there are no cycles. Putting in code to detect cycles isn't that hard, but would complicate the solution slightly. I also assume that the output should not contain entries with just one Line, because your example doesn't include any examples of that.
struct PathFinderVersion1
{
private let graph: Graph
private var pathList = [Path]()
private var currentPath = Path()
private init(for graph: Graph)
{
self.graph = graph
self.pathList.reserveCapacity(graph.count)
self.currentPath.reserveCapacity(graph.count)
}
static func pathList(for graph: Graph) -> [Path]
{
var pathFinder = Self(for: graph)
return pathFinder.makePathLists()
}
private mutating func makePathLists() -> [Path]
{
for src in graph.keys
{
for edge in graph[src]!
{
assert(edge.0 == src, "sanity check failed")
currentPath.append(edge)
appendAllPaths()
currentPath.removeLast()
}
}
return pathList
}
private mutating func appendAllPaths()
{
assert(currentPath.count > 0, "currentPath must not be empty on entry")
guard let src = currentPath.last?.1 else { return }
guard let edges = graph[src] else
{
if currentPath.count > 1 {
pathList.append(currentPath)
}
return
}
for edge in edges
{
assert(edge.0 == src, "sanity check failed")
currentPath.append(edge)
appendAllPaths()
currentPath.removeLast()
}
}
}
Apart from the init, and static wrapper function, pathList(for:), the algorithm is really just two functions. The initializer is where I pre-allocate the working storage. Assuming there is an entry in the graph Dictionary for each Point, no path can ever be longer than there entries keys in the graph ... at least not without cycles, so currentPath is initialized with that much capacity. Similar thinking applies to the other working arrays. The pathList is likely to be be larger than graph.count, but unless there are a lot of unconnected Lines, it will need to be at least as big as graph is.
makePathLists() is the part that gets thing started, extracting the Point and array of Line for each of its entries. It initializes the first entry in a currentPath, then calls appendAllPaths() to recursively append new Line instances to currentPath on the way down. When it reaches the end, it has found a complete path, so it adds the currentPath to the pathList. On the way back up, it removes the entry it added from currentPath so that it's in a state that it can be reused again to go down another path in the graph.
Once makePathLists() has iterated over all its keys and appendAllPaths() has recursed for each one, pathList contains the result. I'm not 100% sure it's in the format you want. It's basically a flat list of all the paths it found. So it's kind of one data structure. But all the paths will be grouped together according to the starting point in the line, so splitting it into smaller lists is easy enough, if that's what you actually want.
In any case, the re-use of existing storage is where this version gets most of its performance.
You can call it like this:
print("Version 1")
for path in PathFinderVersion1.pathList(for: input) {
print("\(path)")
}
And here's the output for the data I set up as input:
Version 1
(b,c)->(c,d)
(a,b)->(b,c)->(c,d)
(a,b)->(b,d)
(a,c)->(c,d)
The exact order changes slightly from run-to-run because Dictionary doesn't necessarily hand out its keys in an order that is consistent from run to run, even if they are inserted exactly the same way every time. I tested each version to verify they all emit the same output (and so should you), but I won't include the output again for the other versions.
Solution 2
This version is based on solution 1, so everything about it applies to this version too. What's different is the addition of the dynamic programming technique of caching intermediate values. Basically I cache paths along the way, so that when I encounter them again, I don't have do all that recursion. I can just used the cached path instead.
There is one snag with this caching, it requres allocating some local caches, which introduces dynamic memory allocation again. However hope is not lost. For starters, assuming lots of nodes in the graph have multiple input edges (ie, lots of different lines connect to the same line), the result should be a win overall from being able to avoid a vast amount of recursion. Additionally i, re-use the local caches, so I only ever have to actually allocate a new one when I recurse deeper than the previous maximum depth reached. So while some allocation does happen, it's minimized.
All that cache handling makes the code longer, but faster.
To make the code more readable I put the local caching in nested struct. Here's the code for version 2:
struct PathFinderVersion2
{
private typealias CachedPath = Path.SubSequence
private typealias CachedPaths = Array<CachedPath>
private let graph: Graph
private var pathList = [Path]()
private var currentPath = Path()
private var pathCache = [Point: CachedPaths]()
private struct LocalPathCache
{
var cache = [CachedPath]()
var pathListIndex: Int
var curPathLength: Int
mutating func updateLocalPathCache(from pathList: [Path])
{
while pathListIndex < pathList.endIndex
{
let pathToCache =
pathList[pathListIndex][curPathLength...]
cache.append(pathToCache)
pathListIndex += 1
}
}
mutating func update(
mainCache: inout [Point: CachedPaths],
for src: Point)
{
if cache.count > 0 {
mainCache[src] = cache
}
}
}
private var localCaches = [LocalPathCache]()
private mutating func getLocalCache(
pathListIndex: Int,
curPathLength: Int) -> LocalPathCache
{
if var cache = localCaches.last
{
localCaches.removeLast()
cache.cache.removeAll(keepingCapacity: true)
cache.pathListIndex = pathListIndex
cache.curPathLength = curPathLength
return cache
}
return LocalPathCache(
pathListIndex: pathListIndex,
curPathLength: curPathLength
)
}
private mutating func freeLocalCache(_ cache: LocalPathCache) {
localCaches.append(cache)
}
private init(for graph: Graph)
{
self.graph = graph
self.pathList.reserveCapacity(graph.count)
self.currentPath.reserveCapacity(graph.count)
self.pathCache.reserveCapacity(graph.count)
}
static func pathList(for graph: Graph) -> [Path]
{
var pathFinder = Self(for: graph)
return pathFinder.makePathLists()
}
private mutating func makePathLists() -> [Path]
{
for src in graph.keys
{
for edge in graph[src]!
{
assert(edge.0 == src, "sanity check failed")
currentPath.append(edge)
appendAllPaths()
currentPath.removeLast()
}
}
return pathList
}
private mutating func appendAllPaths()
{
assert(currentPath.count > 0, "currentPath must not be empty on entry")
guard let src = currentPath.last?.1 else { return }
if updatePathListFromCache(for: src) { return }
guard let edges = graph[src] else
{
if currentPath.count > 1 {
pathList.append(currentPath)
}
return
}
var localCache = getLocalCache(
pathListIndex: pathList.endIndex,
curPathLength: currentPath.endIndex
)
defer { freeLocalCache(localCache) }
for edge in edges
{
assert(edge.0 == src, "sanity check failed")
currentPath.append(edge)
appendAllPaths()
currentPath.removeLast()
localCache.updateLocalPathCache(from: pathList)
}
localCache.update(mainCache: &pathCache, for: src)
}
mutating func updatePathListFromCache(for src: Point) -> Bool
{
if let cachedPaths = pathCache[src]
{
let curPathIndex = currentPath.endIndex
for path in cachedPaths
{
currentPath.append(contentsOf: path)
pathList.append(currentPath)
currentPath.removeSubrange(curPathIndex...)
}
return true
}
return false
}
}
Solution 3
Solutions 1 and 2 still use recursion. Recursion is elegant, and nice to think about, because you can express a problem as a slightly simpler problem plus a bit. But unless it's tail-recursive, compilers can't optimize it particularly well. So the solution to that problem is to use iteration instead of recursion.
Turning a recursive algorithm into an iterative one is not always so easy, and can result in ugly code. That is the definitely the case here. There might be a simpler iterative algorithm, but I don't know it. So I basically replaced recursion with a state machine + stack. I've used this technique before for recursive code the desperately needed to be faster, and it does work. The code is a total pain for a human to read and maintain, but compilers can optimize the hell out of it.
This version still uses the cached intermediate solutions from version 2.
struct PathFinderVersion3
{
private typealias CachedPath = Path.SubSequence
private typealias CachedPaths = Array<CachedPath>
private let graph: Graph
private var pathList = [Path]()
private var currentPath = Path()
private var pathCache = [Point: CachedPaths]()
private struct LocalPathCache
{
var cache = [CachedPath]()
var pathListIndex: Int
var curPathLength: Int
mutating func updateLocalPathCache(from pathList: [Path])
{
while pathListIndex < pathList.endIndex
{
let pathToCache =
pathList[pathListIndex][curPathLength...]
cache.append(pathToCache)
pathListIndex += 1
}
}
mutating func update(
mainCache: inout [Point: CachedPaths],
for src: Point)
{
if cache.count > 0 {
mainCache[src] = cache
}
}
}
private var localCaches = [LocalPathCache]()
private mutating func getLocalCache(
pathListIndex: Int,
curPathLength: Int) -> LocalPathCache
{
if var cache = localCaches.last
{
localCaches.removeLast()
cache.cache.removeAll(keepingCapacity: true)
cache.pathListIndex = pathListIndex
cache.curPathLength = curPathLength
return cache
}
return LocalPathCache(
pathListIndex: pathListIndex,
curPathLength: curPathLength
)
}
private mutating func freeLocalCache(_ cache: LocalPathCache) {
localCaches.append(cache)
}
private init(for graph: Graph)
{
self.graph = graph
self.pathList.reserveCapacity(graph.count)
self.currentPath.reserveCapacity(graph.count)
self.pathCache.reserveCapacity(graph.count)
}
static func pathList(for graph: Graph) -> [Path]
{
var pathFinder = Self(for: graph)
return pathFinder.makePathLists()
}
private mutating func makePathLists() -> [Path]
{
for src in graph.keys
{
for edge in graph[src]!
{
assert(edge.0 == src, "sanity check failed")
currentPath.append(edge)
appendAllPaths()
currentPath.removeLast()
}
}
return pathList
}
struct Stack<T>
{
var storage: [T] = []
var isEmpty: Bool { storage.isEmpty }
var count: Int { storage.count }
init(capacity: Int) { storage.reserveCapacity(capacity) }
mutating func push(_ element: T) { storage.append(element) }
mutating func pop() -> T? { storage.popLast() }
}
private mutating func appendAllPaths()
{
assert(currentPath.count > 0, "currentPath must not be empty on entry")
enum State
{
case entry
case inLoopPart1
case inLoopPart2
case exit
}
var state: State = .entry
typealias StackElement =
(Point, Int, Line, [Line], LocalPathCache, State)
var stack = Stack<StackElement>(capacity: graph.count)
var src: Point! = nil
var edges: [Line]! = nil
var edgeIndex: Int = 0
var edge: Line! = nil
var localCache: LocalPathCache! = nil
outer: while true
{
switch state
{
case .entry:
if let s = currentPath.last?.1 {
src = s
}
else
{
state = .exit
continue outer
}
if updatePathListFromCache(for: src)
{
state = .exit
continue outer
}
if let e = graph[src] { edges = e }
else
{
if currentPath.count > 1 {
pathList.append(currentPath)
}
state = .exit
continue outer
}
localCache = getLocalCache(
pathListIndex: pathList.endIndex,
curPathLength: currentPath.endIndex
)
edgeIndex = edges.startIndex
state = .inLoopPart1
continue outer
case .inLoopPart1:
if edgeIndex < edges.endIndex
{
edge = edges[edgeIndex]
assert(edge.0 == src, "sanity check failed")
currentPath.append(edge)
// Simulate function call
stack.push((src, edgeIndex, edge, edges, localCache, .inLoopPart2))
state = .entry
continue outer
}
localCache.update(mainCache: &pathCache, for: src)
state = .exit
case .inLoopPart2:
localCache.updateLocalPathCache(from: pathList)
edgeIndex += 1
state = .inLoopPart1 // Simulate goto top of inner loop
case .exit: // Simulate return
if let c = localCache { freeLocalCache(c) }
if let savedState = stack.pop()
{
(src, edgeIndex, edge, edges, localCache, state) = savedState
currentPath.removeLast()
}
else { break outer }
}
}
assert(stack.isEmpty)
}
mutating func updatePathListFromCache(for src: Point) -> Bool
{
if let cachedPaths = pathCache[src]
{
let curPathIndex = currentPath.endIndex
for path in cachedPaths
{
currentPath.append(contentsOf: path)
pathList.append(currentPath)
currentPath.removeSubrange(curPathIndex...)
}
return true
}
return false
}
}
Ummm... yeah, there it is in all its ugly glory. It works. It's fast. Good luck maintaining it.
The question is whether the speed is worth it when weighed against the readability issues and maintenance headaches, and that all depends on the application requirements. In my opinion that speed would have to be pretty darn important to put up with maintaining this version, and I'm normally fine with putting up with some ugliness to get speed in critical code. Somehow, this version, written in a language that doesn't even have a goto statement is nonetheless a poster-child for why goto is considered bad in the first place.
Solution 4 (Bonus)
Originally I just mentioned that you could parallelize it, but I didn't implement it. I decided that for completeness, a parallelization example really should be included.
I chose to parallelize solution 1, but all three of the previous solutions can be parallelized in exactly the same way. The changes that have to be made are to add the split method, and modify the static pathList(for:) method as well as the private makePathLists instance method. You also need a concurrent DispatchQueue. I create a global one for this example, but you can use an existing one. Don't use DispatchQueue.main for this, if you want your app to be responsive while processing.
Here's the code:
import Foundation
let dispatchQueue =
DispatchQueue(label: "PathFinder-\(UUID())",attributes: .concurrent)
struct PathFinderVersion4
{
private let graph: Graph
private var pathList = [Path]()
private var currentPath = Path()
private init(for graph: Graph)
{
self.graph = graph
self.pathList.reserveCapacity(graph.count)
self.currentPath.reserveCapacity(graph.count)
}
public static func pathList(for graph: Graph) -> [Path]
{
let concurrency = min(4, graph.count)
let pointGroups = split(.init(graph.keys), numberOfGroups: concurrency)
var pathLists = [[Path]](repeating: [], count: concurrency)
let waitSems = Array(
repeating: DispatchSemaphore(value: 0),
count: concurrency
)
for groupIndex in pointGroups.indices
{
dispatchQueue.async
{
defer { waitSems[groupIndex].signal() }
var pathFinder = Self(for: graph)
pathLists[groupIndex] =
pathFinder.makePathLists(for: pointGroups[groupIndex])
}
}
// Need to signal each semaphore after waiting or will crash on return.
// See Apple documentation for DispatchSemaphore
waitSems.forEach { $0.wait(); $0.signal() }
var result = [Path]()
result.reserveCapacity(pathLists.reduce(0) { $0 + $1.count })
pathLists.forEach { result.append(contentsOf: $0) }
return result
}
private static func split<Value>(
_ values: [Value],
numberOfGroups: Int) -> [[Value]]
{
var groups = [[Value]]()
groups.reserveCapacity(numberOfGroups)
let groupSize = values.count / numberOfGroups
+ (values.count % numberOfGroups == 0 ? 0 : 1)
var valueIndex = values.startIndex
while valueIndex < values.endIndex
{
var group = [Value]()
group.reserveCapacity(groupSize)
let valueEnd = min(valueIndex + groupSize, values.endIndex)
while valueIndex < valueEnd
{
group.append(values[valueIndex])
valueIndex += 1
}
groups.append(group)
}
return groups
}
private mutating func makePathLists(for points: [Point]) -> [Path]
{
for src in points
{
for edge in graph[src]!
{
assert(edge.0 == src, "sanity check failed")
currentPath.append(edge)
appendAllPaths()
currentPath.removeLast()
}
}
return pathList
}
private mutating func appendAllPaths()
{
assert(currentPath.count > 0, "currentPath must not be empty on entry")
guard let src = currentPath.last?.1 else { return }
guard let edges = graph[src] else
{
if currentPath.count > 1 {
pathList.append(currentPath)
}
return
}
for edge in edges
{
assert(edge.0 == src, "sanity check failed")
currentPath.append(edge)
appendAllPaths()
currentPath.removeLast()
}
}
}
Upvotes: 1
Related Questions
- Python - create tree from dictionary
- Swift : How to create a dictionary dynamically from a json?
- Create a tree from a given dictionary
- How to create nested dictionary elements in Swift?
- More efficient way for converting structure properties into dictionary
- Most efficient way to flatten an array of dictionaries containing arrays
- More appropriate solution than a nested dictionary?
- How to quickly populate a dictionary in Swift
- Build tree data from dictionary
- Approaches to create a nested tree structure of NSDictionaries?