J'ai un dictionnaire avec la structure suivante: [Point:[Line]], où:

  • Point - structure de données personnalisée contenant deux coordonnées (X, Y)
  • Ligne - tuple (Point, Point) qui contient les premier et dernier points de la ligne.
  • Clé - premier point de la ligne.

Il s'agit donc d'un dictionnaire de lignes regroupées par leur premier point, comme suit:

[a: [(a,b),(a,c)], b: [(b,c), (b,d)], c: [(c,d)] ]

Le but est de convertir ce dictionnaire en une liste de structures de données comme suit:

  1. (a, b) -> (b, c) -> (c, d)
  2. (a, b) -> (b, d)
  3. (a, c) -> (c, d)

Donc, fondamentalement, un arbre avec la racine au premier point.

J'ai essayé d'utiliser le modèle et la pile de générateur pour effectuer cette opération, j'ai donc créé un générateur en utilisant le premier point et mis dans la pile, puis j'ai commencé une boucle while jusqu'à ce que la pile soit vide, puis dans la boucle, je supprimais le générateur actuel et en créais de nouveaux basés sur les derniers et premiers points, le code ressemblait à ceci:

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)
                }
            }
        }
        
    }
    
}

Cette solution est très simple. Cela fonctionne, mais j'ai une très grande quantité de données dans le dictionnaire, et le nombre de combinaisons est encore plus grand, donc cet algorithme est extrêmement lent et peu efficace en mémoire.

La principale lenteur est causée par l'ajout et la récupération de données vers / depuis la pile qui a l'implémentation suivante:

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

Et un autre goulot d'étranglement est lié à la copie des données et à la méthode deinit.

J'essayais de trouver une meilleure solution, mais je n'ai encore rien trouvé. Serait reconnaissant pour toutes suggestions. Merci.

0
Sergii Sopin 12 mars 2021 à 02:41

1 réponse

Meilleure réponse

Bien que le modèle de constructeur soit utile, je pense que dans ce cas, cela complique simplement la solution simple, bien que, comme vous le verrez, je vais en présenter quelques-uns qui sont plus compliqués, mais ceux-ci sont basés sur des optimisations de performances accrues sur le premier. solution simple.

Comme vous l'avez noté, l'initialisation et la désinitialisation des classes est un peu lente. En fait, le pire est l'allocation de mémoire dynamique. Les classes sont puissantes et ont certainement leur utilité, mais elles ne sont pas l'outil le plus rapide de la boîte à outils Swift. À moins que vous ne fassiez des méthodes final, leur appel peut nécessiter une répartition virtuelle. Cela peut également arriver avec les protocoles en fonction des détails de leur déclaration, bien que dans ce cas, cela s'appelle «thunking table témoin». Mais le pire dans les classes est que leurs instances peuvent être jonchées à peu près n'importe où dans la mémoire. C'est l'enfer sur le cache sur puce du processeur. Donc, pour les performances, essayez d'éviter la répartition dynamique et les types de référence (par exemple, les classes), et lorsque vous avez besoin d'allouer de la mémoire (comme Array ou Dictionary), essayez d'allouer tout ce dont vous avez besoin à la fois et réutilisez-le autant que possible. Dans Swift, cela nécessite une réflexion en raison de la copie sur écriture. Vous pouvez facilement finir par allouer de la mémoire lorsque vous n'en aviez pas l'intention.

Je présente trois solutions. Chacun est plus compliqué, mais aussi (espérons-le) plus rapide que le précédent. Je vais vous expliquer pourquoi et ce qu'il faut rechercher. Je dois mentionner que je n’inclus pas la solution la plus simple. C'est un peu comme ma première solution mais avec des tableaux de variables locales. Les performances ne seraient pas particulièrement bonnes, et votre question indique clairement que les performances sont un problème.

Il y a d'abord une plaque chauffante. Pour le coder et le tester, j'avais besoin de définir vos types Point et Line, ainsi que quelques autres que j'utilise pour plus de commodité, ainsi que certaines extensions uniquement pour générer une sortie. Ce code est commun aux trois solutions. Remplacez Point et Line par vos propres définitions.

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: "->"))
    }
}

Vous mentionnez que Point a un X et un Y, mais pour ce problème, cela n'a pas d'importance. Vous avez juste besoin de "choses" uniques pour servir de points de terminaison pour vos instances Line.

Ensuite, j'ai déclaré les entrées de votre exemple:

let (a, b, c, d) = (Point(), Point(), Point(), Point())
let input = [ a: [(a,b),(a,c)], b: [(b,c), (b,d)], c: [(c,d)] ]

Avec le code commun à l'écart, voici les solutions réelles:

Solution 1

Bien que la récursion introduit une surcharge en elle-même, le principal problème de la solution la plus simple est qu'elle nécessite des tableaux locaux qui sont alloués et désalloués de haut en bas dans la pile d'appels. Les allocations de mémoire dynamique et les désallocations pour eux sont en fait le principal problème de performances avec la solution récursive simple.

La solution consiste à tenter de pré-allouer le stockage de travail et de le réutiliser tout au long de la récursivité, ou du moins de rendre les réallocations rares.

Une façon serait d'allouer les tableaux de travail au niveau supérieur et de les transmettre en tant que paramètres inout. Une autre est de leur rendre les propriétés mutables d'un struct (en fait, un class ne serait pas si mal dans ce cas, car vous n'allouez qu'une seule instance). J'ai choisi cette dernière approche.

Comme je l'ai mentionné dans mon commentaire, je considère ce problème comme un problème de théorie des graphes .. Point = node. Line = bord. Bien que ce ne soit pas explicitement indiqué, je suppose qu'il n'y a pas de cycles. Mettre du code pour détecter les cycles n'est pas si difficile, mais compliquerait légèrement la solution. Je suppose également que la sortie ne doit pas contenir d'entrées avec un seul Line, car votre exemple n'inclut aucun exemple de cela.

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()
        }
    }
}

Hormis la fonction wrapper init et static, pathList(for:), l'algorithme n'est en réalité que deux fonctions. L'initialiseur est l'endroit où je pré-alloue le stockage de travail. En supposant qu'il y ait une entrée dans le graph Dictionary pour chaque Point, aucun chemin ne peut être plus long que les entrées des clés dans le graph ... du moins pas sans cycles , donc currentPath est initialisé avec autant de capacité. Une réflexion similaire s'applique aux autres tableaux de travail. Le pathList est probablement plus grand que graph.count, mais à moins qu'il y ait beaucoup de Line non connectés, il devra être au moins aussi grand que graph. .

makePathLists() est la partie qui lance les choses, en extrayant le Point et le tableau de Line pour chacune de ses entrées. Il initialise la première entrée d'un currentPath, puis appelle appendAllPaths() pour ajouter récursivement de nouvelles instances Line à currentPath en descendant. Lorsqu'il atteint la fin, il a trouvé un chemin complet, il ajoute donc le currentPath au pathList. Sur le chemin du retour, il supprime l'entrée qu'il a ajoutée de currentPath afin qu'il soit dans un état qu'il puisse être réutilisé à nouveau pour emprunter un autre chemin dans le graphique.

Une fois que makePathLists() a itéré sur toutes ses clés et que appendAllPaths() a récidivé pour chacune d'elles, pathList contient le résultat. Je ne suis pas sûr à 100% que ce soit dans le format que vous souhaitez. C'est essentiellement une liste plate de tous les chemins qu'il a trouvés. C'est donc en quelque sorte une structure de données unique. Mais tous les chemins seront regroupés en fonction du point de départ de la ligne, il est donc assez facile de le diviser en listes plus petites, si c'est ce que vous voulez réellement.

Dans tous les cas, la réutilisation du stockage existant est l'endroit où cette version tire l'essentiel de ses performances.

Vous pouvez l'appeler comme ceci:

print("Version 1")
for path in PathFinderVersion1.pathList(for: input) {
    print("\(path)")
}

Et voici la sortie pour les données que j'ai configurées comme entrée:

Version 1
(b,c)->(c,d)
(a,b)->(b,c)->(c,d)
(a,b)->(b,d)
(a,c)->(c,d)

L'ordre exact change légèrement d'une exécution à l'autre car Dictionary ne distribue pas nécessairement ses keys dans un ordre cohérent d'une exécution à l'autre, même si elles sont insérées exactement de la même manière temps. J'ai testé chaque version pour vérifier qu'elles émettent toutes la même sortie (et vous devriez donc), mais je n'inclurai pas à nouveau la sortie pour les autres versions.

Solution 2

Cette version est basée sur la solution 1, donc tout s'applique également à cette version. Ce qui est différent, c'est l'ajout de la technique de programmation dynamique de la mise en cache des valeurs intermédiaires. Fondamentalement, je cache les chemins en cours de route, de sorte que lorsque je les rencontre à nouveau, je n'ai pas à faire toute cette récursivité. Je peux simplement utiliser le chemin mis en cache à la place.

Il y a un hic avec cette mise en cache, elle nécessite l'allocation de certains caches locaux, ce qui introduit à nouveau l'allocation de mémoire dynamique. Cependant, l'espoir n'est pas perdu. Pour commencer, en supposant que de nombreux nœuds dans le graphe aient plusieurs arêtes d'entrée (c'est-à-dire que de nombreuses lignes différentes se connectent à la même ligne), le résultat devrait être globalement gagnant en évitant une grande quantité de récursivité. De plus, je réutilise les caches locaux, de sorte que je n'ai à en allouer un nouveau que lorsque je rentre plus profondément que la profondeur maximale précédente atteinte. Ainsi, même si une certaine allocation se produit, elle est minimisée.

Toute cette gestion du cache rend le code plus long, mais plus rapide.

Pour rendre le code plus lisible, j'ai mis la mise en cache locale dans une structure imbriquée. Voici le code de la 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

Les solutions 1 et 2 utilisent toujours la récursivité. La récursivité est élégante et agréable à penser, car vous pouvez exprimer un problème comme un problème un peu plus simple et un peu. Mais à moins qu'il ne soit récursif à la queue, les compilateurs ne peuvent pas l'optimiser particulièrement bien. La solution à ce problème est donc d'utiliser l'itération au lieu de la récursivité.

Transformer un algorithme récursif en un algorithme itératif n'est pas toujours aussi facile et peut entraîner un code laid. C'est certainement le cas ici. Il existe peut-être un algorithme itératif plus simple, mais je ne le sais pas. J'ai donc essentiellement remplacé la récursivité par une machine à états + pile. J'ai déjà utilisé cette technique pour le code récursif dont il avait désespérément besoin pour être plus rapide, et cela fonctionne. Le code est une douleur totale pour un humain à lire et à maintenir, mais les compilateurs peuvent en optimiser l'enfer.

Cette version utilise toujours les solutions intermédiaires mises en cache de la 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 ... ouais, il est là dans toute sa vilaine gloire. Ça marche. C'est rapide. Bonne chance pour le maintenir.

La question est de savoir si la vitesse en vaut la peine si on la compare aux problèmes de lisibilité et aux maux de tête liés à la maintenance, et tout dépend des exigences de l'application. À mon avis, la vitesse devrait être très importante pour supporter le maintien de cette version, et je suis normalement d'accord pour supporter une certaine laideur pour obtenir de la vitesse dans un code critique. D'une manière ou d'une autre, cette version, écrite dans un langage qui n'a même pas d'instruction goto, est néanmoins un enfant-affiche pour la raison pour laquelle goto est considéré comme mauvais en premier lieu.

Solution 4 (Bonus)

À l'origine, je viens de mentionner que vous pouviez le paralléliser, mais je ne l'ai pas mis en œuvre. J'ai décidé que pour être complet, un exemple de parallélisation devrait vraiment être inclus.

J'ai choisi de paralléliser la solution 1, mais les trois solutions précédentes peuvent être parallélisées exactement de la même manière. Les modifications à apporter consistent à ajouter la méthode split et à modifier la méthode static pathList(for:) ainsi que la méthode d'instance private makePathLists. Vous avez également besoin d'un DispatchQueue simultané. J'en crée un global pour cet exemple, mais vous pouvez en utiliser un existant. N'utilisez pas DispatchQueue.main pour cela, si vous voulez que votre application soit réactive pendant le traitement.

Voici le 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()
        }
    }
}
1
Chip Jarred 13 mars 2021 à 01:09