tutorial - nsoperationqueue swift 3 example

Una solución más rápida para caminar de una palabra a otra

Question

Tengo una tarea de tarea donde el objetivo es hacer que una palabra se convierta en otra, cambiando solo un personaje a la vez. Elijo hacerlo en Swift y usar el diccionario BSD estándar ( /usr/share/dict/words ) para mi fuente de palabras.

El siguiente código funciona como se esperaba. Sin embargo, para algunas combinaciones, funciona bastante despacio. Por ejemplo, define -> system

¿Puedo usar Grand Central Dispatch y procesamiento paralelo para hacerlo más rápido? ¡Muchas gracias!

import Foundation
typealias CString = [CChar]
// Get list of words from the standard BSD dictionary
let wordList = try! String(contentsOfFile: "/usr/share/dict/words")
.componentsSeparatedByString("/n")
.map { $0.lowercaseString.cStringUsingEncoding(NSUTF8StringEncoding)! }
func distance(fromCString: CString, toCString: CString) -> Int {
guard fromCString.count == toCString.count else {
fatalError("The two strings must have the same number of characters")
}
var distance = 0
for i in 0..<fromCString.count {
if fromCString[i] != toCString[i] {
distance++
}
}
return distance
}
func find(start: String, _ end: String) -> [String]? {
guard start.characters.count == end.characters.count else {
fatalError("''/(start)'' and ''/(end)'' must have the same number of characters")
}
// String is slow. Switch to bytes array for speed
let startCString = start.cStringUsingEncoding(NSUTF8StringEncoding)!
let endCString = end.cStringUsingEncoding(NSUTF8StringEncoding)!
// Get list of words with same length
var candidates = wordList.filter { $0.count == startCString.count }
// If either start or end is not in the dictionary, fail
guard (candidates.contains { $0 == startCString }) else {
fatalError("''/(start)'' is not in the dictionary")
}
guard (candidates.contains { $0 == endCString }) else {
fatalError("''/(end)'' is not in the dictionary")
}
// Do the search
var i = 0
var iterations = 0
var queue = [[CString]]()
queue.append([startCString])
while queue.count > 0, let lastWord = queue[0].last where lastWord != endCString {
iterations++
i = 0
while i < candidates.count {
if candidates[i] == lastWord {
candidates.removeAtIndex(i)
} else if distance(lastWord, toCString: candidates[i]) == 1 {
queue.append(queue[0] + [candidates[i]])
candidates.removeAtIndex(i)
} else {
i++
}
}
queue.removeAtIndex(0)
}
if queue.isEmpty {
print("Cannot go from ''/(start)'' to ''/(end)''")
return nil
} else {
return queue[0].map { String(CString: $0, encoding: NSUTF8StringEncoding)! }
}
}

Ejemplos:

find("bat", "man") // bat -> ban -> man. 190 iterations, fast.
find("many", "shop")) // many -> mand -> main -> said -> saip -> ship -> shop. 4322 iterations, medium
find("define", "system") // impossible
find("defend", "oppose") // impossible

Answer 1

Pequeño problema muy interesante. Usar la indexación nativa en los diccionarios te permitirá hacer que esto vaya mucho más rápido. Además, puede reducir considerablemente el número de iteraciones buscando una cadena de palabras de ambos extremos al mismo tiempo.

Hice un ejemplo que tiene un tiempo de configuración más largo pero, una vez que se hace la indexación de palabras, los resultados de la cadena de palabras son prácticamente instantáneos.

// --- wordPath.swift ---
// create a list of link patterns for a word
// ------------------------------------------
// A link pattern is an ordered list of letters in a word where one letter is missing
//
// This corresponds to a combination of letters that can from the word
// by adding a single letter and, conversely to combinations of letters that
// are possible by removing a letter from the word
//
// Letters are sorted alphabetically in order to ignore permutations
//
// for example:
//
// "corner" has 6 link patterns (one of which is a duplicate)
//
// the sorted letters are : "cenorr"
//
// the links are the 6 combinations of 5 out of 6 letters of "cenorr"
// with letters kept in alphabetical order.
//
// because letters are sorted, the combinations can be obtained by
// removing one letter at each position.
//
// removing position 1 : enorr
// removing position 2 : cnorr
// removing position 3 : ceorr
// removing position 4 : cenrr
// removing position 5 : cenor
// removing position 6 : cenor (this is the duplicate)
//
public func linksOfWord(_ word:String)->[String]
{
var result:[String] = []
// sort letters
let sortedLetters = word.characters.sorted()
// return one string for each combination of N-1 letters
// exclude duplicates (which will always be consecutive)
var wordLink = ""
for skipChar in sortedLetters.indices
{
let nextLink = String(sortedLetters[0..<skipChar])
+ String(sortedLetters[skipChar+1..<sortedLetters.count])
if nextLink == wordLink { continue }
wordLink = nextLink
result.append(wordLink)
}
return result
}
// Create an index of wordlinks to the words that can be fromed from them
// ----------------------------------------------------------------------
// - The wordLinks dictionary contains a list of all the words that can be formed
// by adding one letter to a given link pattern
// - This is essentially the reverse of linksOfWord for all words in the dictionary
// - note: Swift will use lazy initialization for this global variable, only executing the closure once.
//
public var wordsOfLink:[String:[String]] =
{
var result:[String:[String]] = [:]
// get all words
let wordList = try! String(contentsOfFile: "/usr/share/dict/words")
.lowercased()
.components(separatedBy:"/n")
// add each word to the index of its wordLinks
for word in wordList
{
for wordLink in linksOfWord(word)
{
result[wordLink] = (result[wordLink] ?? []) + [word]
}
}
return result
}()
// Iteration counted, for comparison with OP
public var iterations = 0
// word path seeking algorithm
// ---------------------------
// - Go through word paths using linksOfWord and wordsOfLink as a virtual tree structure
// linksOfWord("word") -> 1:N array of links -> wordsOfLink("Link") -> 1:N array of words
// - Performs a breadth-first tree search by exausting shorter path lengths before moving on to longer ones
// - Simultaneously search forward and backward to minimize the exponential nature of path expansions
//
public func findWordPath(from fromWord:String, to toWord:String, shortestPath:Bool=false) -> [String]?
{
iterations = 0
// both words must be same length
guard fromWord.characters.count == toWord.characters.count
else { return nil }
// processing in lowercase only
let startWord = fromWord.lowercased()
let endWord = toWord.lowercased()
// keep track of links already processed (avoid infinite loops)
var seenLinks = Set<String>()
var seenWords = Set<String>()
// path expansion from starting word forward to ending word
var forwardLinks:[String:[String]] = [:] // links that have a forward path connecting to the starting word
var forwardPaths = [[startWord]] // partial forward paths to examine
var forwardIndex = 0 // currently examined forwardPath (index)
// path expansion from ending word backward to starting word
var backwardLinks:[String:[String]] = [:] // links that have a backward path connecting to the ending word
var backwardPaths = [[endWord]] // partial backward paths to examine
var backwardIndex = 0 // currently examined backwardPath (index)
// establish initial links to start and end words
// - allows logic to only check path to path connections
// (and not path to word in addition to it)
linksOfWord(startWord).forEach{forwardLinks[$0] = [startWord]}
linksOfWord(endWord).forEach{backwardLinks[$0] = [endWord]}
// Explore shorter paths in each direction before moving on to longer ones
// This improves performance but does not guarantee the shortest word path
// will be selected when a connection is found
// e.g. forward(4)->backward(3) could be found before backward(4)->forward(2)
// resulting in a 7 word path when a 6 word path exists.
// Finding the shortest possible word path requires that we explore forward only
// (which is what the shortestPath parameter controls)
var currentLength = 1
// Examine partial word paths in multiple passes with an increasing path length (currentLength)
// - For each path length, check if forward and backward paths can connect to one another.
// - For each length, forwardIndex and backwardIndex advance through the paths
// of the current length thus exhausting both forward and backward paths of that length
// before moving on to the next length.
// - As paths of the current length are examined, the partial path arrays receive new (longer) word paths
// to examine.
// - The added paths have 1 additional word which creates a new group of paths for the next pass
// at currentLength + 1
// - When none of the partial word paths can be extended by adding a word that was not seen before
// the forward or backward path array will stop growing and the index will reach the end of the array
// indicating that no word path exists between start and end words
while forwardIndex < forwardPaths.count
&& ( backwardIndex < backwardPaths.count || shortestPath )
{
// Examine forward path links (of current length) for connection
// to the end word or to a backward path that connects to it
while forwardIndex < forwardPaths.count
&& forwardPaths[forwardIndex].count == currentLength
{
let forwardPath = forwardPaths[forwardIndex]
forwardIndex += 1
iterations += 1
// expand links for last word of "forward" path
for wordLink in linksOfWord(forwardPath.last!)
{
// link connects to a backward path, return the combined forward and backward paths
if let backwardPath = backwardLinks[wordLink]
{ return forwardPath + backwardPath }
// don''t explore links that have already been examined
if !seenLinks.insert(wordLink).inserted
{ continue }
// record forward path to allow linking from backward paths
// i.e. this link is known to lead to the starting word (through forwardPath)
if !shortestPath
{ forwardLinks[wordLink] = forwardPath }
// for all words that can be created by adding one letter to the word link
// add new forward paths to examine on the next length pass
for word in wordsOfLink[wordLink] ?? []
{
if seenWords.insert(word).inserted
{
forwardPaths.append(forwardPath + [word])
}
}
}
}
// Examine backward path links (of current length) for connection
// to the start word or to a forward path that connects to it
// allowing one length backward path to support unknown end words
while !shortestPath
&& backwardIndex < backwardPaths.count
&& backwardPaths[backwardIndex].count == currentLength
{
let backwardPath = backwardPaths[backwardIndex]
backwardIndex += 1
iterations += 1
// expand links for first word of "backward" path
for wordLink in linksOfWord(backwardPath.first!)
{
// link connects to starting path, combine and return result
if let forwardPath = forwardLinks[wordLink]
{ return forwardPath + backwardPath }
// don''t explore links that have already been examined
if !seenLinks.insert(wordLink).inserted
{ continue }
// record backward path to allow linking from forward paths
// i.e. this link is known to lead to the ending word (through backwardPath)
backwardLinks[wordLink] = backwardPath
// for all words that can be created by adding one letter to the word link
// add new backward paths to examine on the next length pass
for word in wordsOfLink[wordLink] ?? []
{
if seenWords.insert(word).inserted
{
backwardPaths.append( [word] + backwardPath )
}
}
}
}
// all forward and backward paths of currentLength have been examined
// move on to next length
currentLength += 1
}
// when either path list is exausted, there are no possible paths.
return nil
}

...

// --- Playground ---
// compute word path and print result
func printWordPath(_ firstWord:String, _ lastWord:String)
{
print(" printWordPath(/"/(firstWord)/",/"/(lastWord)/")")
let startTime = ProcessInfo().systemUptime
if let foundPath = findWordPath(from:firstWord, to:lastWord, shortestPath:false)
{
let time = String(format:"%.5f",ProcessInfo().systemUptime-startTime)
print(" ///(foundPath.count) words : /(foundPath)/n // /(iterations) iterations, /(time) sec ")
}
else
{ print(" // No Path Found between /(firstWord) and /(lastWord)") }
print("")
}
printWordPath("bat","man")
// 3 words : ["bat", "amt", "man"]
// 16 iterations, 6.34718 sec <-- longer time here because of initializations
printWordPath("many","shop")
// 5 words : ["many", "hymn", "homy", "hypo", "shop"]
// 154 iterations, 0.00752 sec
printWordPath("many","star")
// 4 words : ["many", "maty", "mast", "star"]
// 101 iterations, 0.00622 sec
printWordPath("define","system")
// 6 words : ["define", "fenite", "entify", "feisty", "stymie", "system"]
// 574 iterations, 0.02374 sec
printWordPath("defend","oppose")
// 6 words : ["defend", "depend", "depone", "podeon", "pooped", "oppose"]
// 336 iterations, 0.01273 sec
printWordPath("alphabet","integers")
// 7 words : ["alphabet", "lapithae", "apterial", "epistlar", "splinter", "sterling", "integers"]
// 1057 iterations, 0.04454 sec
printWordPath("Elephant","Microbes")
// 8 words : ["elephant", "antelope", "lapstone", "parsonet", "somepart", "imposter", "comprise", "microbes"]
// 2536 iterations, 0.10133 sec
printWordPath("Microbes","Elephant")
// 8 words : ["microbes", "comprise", "persicot", "petrolic", "copalite", "pectinal", "planchet", "elephant"]
// 2232 iterations, 0.09649 sec
printWordPath("Work","Home")
// 4 words : ["work", "worm", "mohr", "home"]
// 52 iterations, 0.00278 sec
printWordPath("Head","Toes")
// 4 words : ["head", "ahet", "ates", "toes"]
// 146 iterations, 0.00684 sec
printWordPath("North","South")
// 3 words : ["north", "horst", "south"]
// 22 iterations, 0.00189 sec
printWordPath("Employee","Pesident")
// 7 words : ["employee", "employed", "redeploy", "leporide", "pedelion", "disponee", "pesident"]
// 390 iterations, 0.01810 sec
printWordPath("Yellow","Orange")
// 5 words : ["yellow", "lowery", "royale", "royena", "orange"]
// 225 iterations, 0.01025 sec
printWordPath("Whale","shark")
// 4 words : ["whale", "hawse", "asher", "shark"]
// 94 iterations, 0.00473 sec
printWordPath("Police","Fellon")
// 4 words : ["police", "pinole", "lionel", "fellon"]
// 56 iterations, 0.00336 sec
printWordPath("religion","insanity")
// 6 words : ["religion", "triolein", "reinstil", "senility", "salinity", "insanity"]
// 483 iterations, 0.02411 sec
printWordPath("ebony","ivory")
// 4 words : ["ebony", "eryon", "irony", "ivory"]
// 53 iterations, 0.00260 sec
printWordPath("electronic","mechanical")
// 7 words : ["electronic", "citronelle", "collineate", "tellinacea", "chatelaine", "atechnical", "mechanical"]
// 316 iterations, 0.01618 sec
printWordPath("detrimental","appropriate")
// 7 words : ["detrimental", "pentremital", "interpolate", "interportal", "prerational", "preparation", "appropriate"]
// 262 iterations, 0.01319 sec 

Tenga en cuenta que esto encuentra soluciones para sus dos últimos ejemplos y también noté que muchos -> mand -> main -> dijo -> ... estaba reemplazando dos letras que iban de "main" a "said", así que terminé con un camino diferente

Por cierto, puse las funciones en un archivo separado en el patio de juegos (en Fuentes) porque el recuento de ejecuciones de línea estaba ralentizando la ejecución hasta un rastreo.

[EDITAR] Las iteraciones modificadas cuentan para que sea más coherente con la forma en que contaba el código del OP. Se agregaron más ejemplos (se divirtieron demasiado con esto).

[EDIT] adaptado para Swift 3, agregó más explicación de la lógica, simplificó / optimizó aún más el código.