Swift Language
Algoritmi con Swift
Ricerca…
introduzione
Gli algoritmi sono una spina dorsale per il calcolo. Fare una scelta di quale algoritmo utilizzare in quale situazione distingue una media da un buon programmatore. Con questo in mente, ecco le definizioni e gli esempi di codice di alcuni degli algoritmi di base là fuori.
Inserimento Ordina
Insertion sort è uno degli algoritmi più basilari in informatica. L'ordinamento di inserimento classifica gli elementi iterando attraverso una raccolta e posiziona gli elementi in base al loro valore. Il set è diviso in metà ordinate e non ordinate e si ripete fino a quando tutti gli elementi sono ordinati. L'ordinamento di inserzione ha la complessità di O (n2). Puoi inserirlo in un'estensione, come nell'esempio seguente, oppure puoi creare un metodo per questo.
extension Array where Element: Comparable {
func insertionSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
let key = output[primaryindex]
var secondaryindex = primaryindex
while secondaryindex > -1 {
if key < output[secondaryindex] {
//move to correct position
output.remove(at: secondaryindex + 1)
output.insert(key, at: secondaryindex)
}
secondaryindex -= 1
}
}
return output
}
}
Ordinamento
Bubble Sort
Questo è un semplice algoritmo di ordinamento che passa ripetutamente nell'elenco per essere ordinato, confronta ogni coppia di elementi adiacenti e li scambia se sono nell'ordine sbagliato. Il passaggio attraverso la lista viene ripetuto fino a quando non sono necessari swap. Sebbene l'algoritmo sia semplice, è troppo lento e poco pratico per la maggior parte dei problemi. Ha complessità di O (n2), ma è considerato più lento dell'ordinamento di inserzione.
extension Array where Element: Comparable {
func bubbleSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryIndex in 0..<self.count {
let passes = (output.count - 1) - primaryIndex
//"half-open" range operator
for secondaryIndex in 0..<passes {
let key = output[secondaryIndex]
//compare / swap positions
if (key > output[secondaryIndex + 1]) {
swap(&output[secondaryIndex], &output[secondaryIndex + 1])
}
}
}
return output
}
}
Inserimento sort
Insertion sort è uno degli algoritmi più basilari in informatica. L'ordinamento di inserimento classifica gli elementi iterando attraverso una raccolta e posiziona gli elementi in base al loro valore. Il set è diviso in metà ordinate e non ordinate e si ripete fino a quando tutti gli elementi sono ordinati. L'ordinamento di inserzione ha la complessità di O (n2). Puoi inserirlo in un'estensione, come nell'esempio seguente, oppure puoi creare un metodo per questo.
extension Array where Element: Comparable {
func insertionSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
let key = output[primaryindex]
var secondaryindex = primaryindex
while secondaryindex > -1 {
if key < output[secondaryindex] {
//move to correct position
output.remove(at: secondaryindex + 1)
output.insert(key, at: secondaryindex)
}
secondaryindex -= 1
}
}
return output
}
}
Selezione sort
L'ordinamento della selezione è noto per la sua semplicità. Inizia con il primo elemento dell'array, salvandone il valore come valore minimo (o massimo, a seconda dell'ordine di ordinamento). Quindi ittera attraverso la matrice e sostituisce il valore minimo con qualsiasi altro valore inferiore a quello minimo che trova sulla strada. Questo valore minimo viene quindi posizionato nella parte più a sinistra della matrice e il processo viene ripetuto dall'indice successivo fino alla fine dell'array. L'ordinamento della selezione ha la complessità di O (n2) ma è considerato più lento della sua controparte: Selezione.
func selectionSort () -> Array {// controlla la guardia del caso triviale self.count> 1 else {return self}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
var minimum = primaryindex
var secondaryindex = primaryindex + 1
while secondaryindex < output.count {
//store lowest value as minimum
if output[minimum] > output[secondaryindex] {
minimum = secondaryindex
}
secondaryindex += 1
}
//swap minimum value with array iteration
if primaryindex != minimum {
swap(&output[primaryindex], &output[minimum])
}
}
return output
}
Ordinamento rapido: tempo di complessità O (n log n)
Quicksort è uno degli algoritmi avanzati. Presenta una complessità temporale di O (n log n) e applica una strategia di divisione e conquista. Questa combinazione si traduce in prestazioni algoritmiche avanzate. Quicksort divide prima un grande array in due sotto-array più piccoli: gli elementi bassi e gli elementi alti. Quicksort può quindi ordinare in modo ricorsivo i sotto-array.
I passaggi sono:
Scegli un elemento, chiamato pivot, dall'array.
Riordinare la matrice in modo che tutti gli elementi con valori inferiori al pivot vengano prima del pivot, mentre tutti gli elementi con valori maggiori del pivot vengono dopo di essa (valori uguali possono andare in entrambi i modi). Dopo questo partizionamento, il perno si trova nella sua posizione finale. Questo è chiamato operazione di partizione.
Applicare ricorsivamente i passaggi precedenti al sotto-array di elementi con valori più piccoli e separatamente al sotto-array di elementi con valori maggiori.
funzione di muting quickSort () -> Array {
func qSort(start startIndex: Int, _ pivot: Int) {
if (startIndex < pivot) {
let iPivot = qPartition(start: startIndex, pivot)
qSort(start: startIndex, iPivot - 1)
qSort(start: iPivot + 1, pivot)
}
}
qSort(start: 0, self.endIndex - 1)
return self
}
mutating func qPartition(start startIndex: Int, _ pivot: Int) -> Int {
var wallIndex: Int = startIndex
//compare range with pivot
for currentIndex in wallIndex..<pivot {
if self[currentIndex] <= self[pivot] {
if wallIndex != currentIndex {
swap(&self[currentIndex], &self[wallIndex])
}
//advance wall
wallIndex += 1
}
}
//move pivot to final position
if wallIndex != pivot {
swap(&self[wallIndex], &self[pivot])
}
return wallIndex
}
Selezione sort
L'ordinamento della selezione è noto per la sua semplicità. Inizia con il primo elemento dell'array, salvandone il valore come valore minimo (o massimo, a seconda dell'ordine di ordinamento). Quindi ittera attraverso la matrice e sostituisce il valore minimo con qualsiasi altro valore inferiore a quello minimo che trova sulla strada. Questo valore minimo viene quindi posizionato nella parte più a sinistra della matrice e il processo viene ripetuto dall'indice successivo fino alla fine dell'array. L'ordinamento della selezione ha la complessità di O (n2) ma è considerato più lento della sua controparte: Selezione.
func selectionSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
var minimum = primaryindex
var secondaryindex = primaryindex + 1
while secondaryindex < output.count {
//store lowest value as minimum
if output[minimum] > output[secondaryindex] {
minimum = secondaryindex
}
secondaryindex += 1
}
//swap minimum value with array iteration
if primaryindex != minimum {
swap(&output[primaryindex], &output[minimum])
}
}
return output
}
Analisi asintotica
Dal momento che abbiamo diversi algoritmi tra cui scegliere, quando vogliamo ordinare un array, dobbiamo sapere quale farà il suo lavoro. Quindi abbiamo bisogno di un metodo per misurare la velocità e l'affidabilità di algoritm. È qui che entra in gioco l'analisi asintotica. L'analisi asintotica è il processo di descrizione dell'efficienza degli algoritmi al crescere della loro dimensione di input (n). Nell'informatica, i asintotici sono solitamente espressi in un formato comune noto come Notazione Big O.
- Tempo lineare O (n) : quando ogni elemento nell'array deve essere valutato affinché una funzione possa raggiungere il suo obiettivo, ciò significa che la funzione diventa meno efficace con l'aumentare del numero di elementi. Si dice che una funzione come questa funzioni in tempo lineare perché la sua velocità dipende dalla sua dimensione di input.
- Tempo polinomico O (n2) : se la complessità di una funzione cresce esponenzialmente (ovvero che per n elementi di una complessità dell'array di una funzione è n al quadrato) quella funzione opera in tempo polinomico. Di solito sono funzioni con cicli annidati. Due loop nidificati determinano la complessità di O (n2), tre cicli nidificati determinano la complessità di O (n3), e così via ...
- Tempo logaritmico O (log n): la complessità delle funzioni temporali logaritmiche viene ridotta al minimo quando aumenta la dimensione dei suoi input (n). Questi sono il tipo di funzioni che ogni programmatore cerca.
Ordinamento rapido: tempo di complessità O (n log n)
Quicksort è uno degli algoritmi avanzati. Presenta una complessità temporale di O (n log n) e applica una strategia di divisione e conquista. Questa combinazione si traduce in prestazioni algoritmiche avanzate. Quicksort divide prima un grande array in due sotto-array più piccoli: gli elementi bassi e gli elementi alti. Quicksort può quindi ordinare in modo ricorsivo i sotto-array.
I passaggi sono:
Scegli un elemento, chiamato pivot, dall'array.
Riordinare la matrice in modo che tutti gli elementi con valori inferiori al pivot vengano prima del pivot, mentre tutti gli elementi con valori maggiori del pivot vengono dopo di essa (valori uguali possono andare in entrambi i modi). Dopo questo partizionamento, il perno si trova nella sua posizione finale. Questo è chiamato operazione di partizione.
Applicare ricorsivamente i passaggi precedenti al sotto-array di elementi con valori più piccoli e separatamente al sotto-array di elementi con valori maggiori.
mutating func quickSort() -> Array<Element> { func qSort(start startIndex: Int, _ pivot: Int) { if (startIndex < pivot) { let iPivot = qPartition(start: startIndex, pivot) qSort(start: startIndex, iPivot - 1) qSort(start: iPivot + 1, pivot) } } qSort(start: 0, self.endIndex - 1) return self}
func mutating qPartition (start startIndex: Int, _ pivot: Int) -> Int {
var wallIndex: Int = startIndex //compare range with pivot for currentIndex in wallIndex..<pivot { if self[currentIndex] <= self[pivot] { if wallIndex != currentIndex { swap(&self[currentIndex], &self[wallIndex]) } //advance wall wallIndex += 1 } }
//move pivot to final position
if wallIndex != pivot {
swap(&self[wallIndex], &self[pivot])
}
return wallIndex
}
Grafico, Trie, Stack
Grafico
In informatica, un grafico è un tipo di dati astratti che intende implementare il grafico non orientato e i concetti di grafico diretto dalla matematica. Una struttura di dati del grafico consiste in un insieme finito (e possibilmente mutevole) di vertici o nodi o punti, insieme a un insieme di coppie non ordinate di questi vertici per un grafo non orientato o un insieme di coppie ordinate per un grafico diretto. Queste coppie sono note come bordi, archi o linee per un grafico non orientato e come frecce, bordi diretti, archi diretti o linee dirette per un grafico diretto. I vertici possono far parte della struttura del grafico o possono essere entità esterne rappresentate da indici o riferimenti interi. Una struttura dati del grafico può anche associare a ciascun bordo un valore di bordo, come un'etichetta simbolica o un attributo numerico (costo, capacità, lunghezza, ecc.). (Wikipedia, fonte )
//
// GraphFactory.swift
// SwiftStructures
//
// Created by Wayne Bishop on 6/7/14.
// Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation
public class SwiftGraph {
//declare a default directed graph canvas
private var canvas: Array<Vertex>
public var isDirected: Bool
init() {
canvas = Array<Vertex>()
isDirected = true
}
//create a new vertex
func addVertex(key: String) -> Vertex {
//set the key
let childVertex: Vertex = Vertex()
childVertex.key = key
//add the vertex to the graph canvas
canvas.append(childVertex)
return childVertex
}
//add edge to source vertex
func addEdge(source: Vertex, neighbor: Vertex, weight: Int) {
//create a new edge
let newEdge = Edge()
//establish the default properties
newEdge.neighbor = neighbor
newEdge.weight = weight
source.neighbors.append(newEdge)
print("The neighbor of vertex: \(source.key as String!) is \(neighbor.key as String!)..")
//check condition for an undirected graph
if isDirected == false {
//create a new reversed edge
let reverseEdge = Edge()
//establish the reversed properties
reverseEdge.neighbor = source
reverseEdge.weight = weight
neighbor.neighbors.append(reverseEdge)
print("The neighbor of vertex: \(neighbor.key as String!) is \(source.key as String!)..")
}
}
/* reverse the sequence of paths given the shortest path.
process analagous to reversing a linked list. */
func reversePath(_ head: Path!, source: Vertex) -> Path! {
guard head != nil else {
return head
}
//mutated copy
var output = head
var current: Path! = output
var prev: Path!
var next: Path!
while(current != nil) {
next = current.previous
current.previous = prev
prev = current
current = next
}
//append the source path to the sequence
let sourcePath: Path = Path()
sourcePath.destination = source
sourcePath.previous = prev
sourcePath.total = nil
output = sourcePath
return output
}
//process Dijkstra's shortest path algorthim
func processDijkstra(_ source: Vertex, destination: Vertex) -> Path? {
var frontier: Array<Path> = Array<Path>()
var finalPaths: Array<Path> = Array<Path>()
//use source edges to create the frontier
for e in source.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = nil
newPath.total = e.weight
//add the new path to the frontier
frontier.append(newPath)
}
//construct the best path
var bestPath: Path = Path()
while frontier.count != 0 {
//support path changes using the greedy approach
bestPath = Path()
var pathIndex: Int = 0
for x in 0..<frontier.count {
let itemPath: Path = frontier[x]
if (bestPath.total == nil) || (itemPath.total < bestPath.total) {
bestPath = itemPath
pathIndex = x
}
}
//enumerate the bestPath edges
for e in bestPath.destination.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = bestPath
newPath.total = bestPath.total + e.weight
//add the new path to the frontier
frontier.append(newPath)
}
//preserve the bestPath
finalPaths.append(bestPath)
//remove the bestPath from the frontier
//frontier.removeAtIndex(pathIndex) - Swift2
frontier.remove(at: pathIndex)
} //end while
//establish the shortest path as an optional
var shortestPath: Path! = Path()
for itemPath in finalPaths {
if (itemPath.destination.key == destination.key) {
if (shortestPath.total == nil) || (itemPath.total < shortestPath.total) {
shortestPath = itemPath
}
}
}
return shortestPath
}
///an optimized version of Dijkstra's shortest path algorthim
func processDijkstraWithHeap(_ source: Vertex, destination: Vertex) -> Path! {
let frontier: PathHeap = PathHeap()
let finalPaths: PathHeap = PathHeap()
//use source edges to create the frontier
for e in source.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = nil
newPath.total = e.weight
//add the new path to the frontier
frontier.enQueue(newPath)
}
//construct the best path
var bestPath: Path = Path()
while frontier.count != 0 {
//use the greedy approach to obtain the best path
bestPath = Path()
bestPath = frontier.peek()
//enumerate the bestPath edges
for e in bestPath.destination.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = bestPath
newPath.total = bestPath.total + e.weight
//add the new path to the frontier
frontier.enQueue(newPath)
}
//preserve the bestPaths that match destination
if (bestPath.destination.key == destination.key) {
finalPaths.enQueue(bestPath)
}
//remove the bestPath from the frontier
frontier.deQueue()
} //end while
//obtain the shortest path from the heap
var shortestPath: Path! = Path()
shortestPath = finalPaths.peek()
return shortestPath
}
//MARK: traversal algorithms
//bfs traversal with inout closure function
func traverse(_ startingv: Vertex, formula: (_ node: inout Vertex) -> ()) {
//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()
//queue a starting vertex
graphQueue.enQueue(startingv)
while !graphQueue.isEmpty() {
//traverse the next queued vertex
var vitem: Vertex = graphQueue.deQueue() as Vertex!
//add unvisited vertices to the queue
for e in vitem.neighbors {
if e.neighbor.visited == false {
print("adding vertex: \(e.neighbor.key!) to queue..")
graphQueue.enQueue(e.neighbor)
}
}
/*
notes: this demonstrates how to invoke a closure with an inout parameter.
By passing by reference no return value is required.
*/
//invoke formula
formula(&vitem)
} //end while
print("graph traversal complete..")
}
//breadth first search
func traverse(_ startingv: Vertex) {
//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()
//queue a starting vertex
graphQueue.enQueue(startingv)
while !graphQueue.isEmpty() {
//traverse the next queued vertex
let vitem = graphQueue.deQueue() as Vertex!
guard vitem != nil else {
return
}
//add unvisited vertices to the queue
for e in vitem!.neighbors {
if e.neighbor.visited == false {
print("adding vertex: \(e.neighbor.key!) to queue..")
graphQueue.enQueue(e.neighbor)
}
}
vitem!.visited = true
print("traversed vertex: \(vitem!.key!)..")
} //end while
print("graph traversal complete..")
} //end function
//use bfs with trailing closure to update all values
func update(startingv: Vertex, formula:((Vertex) -> Bool)) {
//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()
//queue a starting vertex
graphQueue.enQueue(startingv)
while !graphQueue.isEmpty() {
//traverse the next queued vertex
let vitem = graphQueue.deQueue() as Vertex!
guard vitem != nil else {
return
}
//add unvisited vertices to the queue
for e in vitem!.neighbors {
if e.neighbor.visited == false {
print("adding vertex: \(e.neighbor.key!) to queue..")
graphQueue.enQueue(e.neighbor)
}
}
//apply formula..
if formula(vitem!) == false {
print("formula unable to update: \(vitem!.key)")
}
else {
print("traversed vertex: \(vitem!.key!)..")
}
vitem!.visited = true
} //end while
print("graph traversal complete..")
}
}
prova
Nell'informatica, un trie, chiamato anche albero digitale e talvolta albero radiale o albero prefisso (come possono essere ricercati dai prefissi), è un tipo di albero di ricerca: una struttura dati dell'albero ordinata che viene utilizzata per memorizzare un insieme dinamico o associativo array in cui le chiavi sono solitamente stringhe. (Wikipedia, fonte )
//
// Trie.swift
// SwiftStructures
//
// Created by Wayne Bishop on 10/14/14.
// Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation
public class Trie {
private var root: TrieNode!
init(){
root = TrieNode()
}
//builds a tree hierarchy of dictionary content
func append(word keyword: String) {
//trivial case
guard keyword.length > 0 else {
return
}
var current: TrieNode = root
while keyword.length != current.level {
var childToUse: TrieNode!
let searchKey = keyword.substring(to: current.level + 1)
//print("current has \(current.children.count) children..")
//iterate through child nodes
for child in current.children {
if (child.key == searchKey) {
childToUse = child
break
}
}
//new node
if childToUse == nil {
childToUse = TrieNode()
childToUse.key = searchKey
childToUse.level = current.level + 1
current.children.append(childToUse)
}
current = childToUse
} //end while
//final end of word check
if (keyword.length == current.level) {
current.isFinal = true
print("end of word reached!")
return
}
} //end function
//find words based on the prefix
func search(forWord keyword: String) -> Array<String>! {
//trivial case
guard keyword.length > 0 else {
return nil
}
var current: TrieNode = root
var wordList = Array<String>()
while keyword.length != current.level {
var childToUse: TrieNode!
let searchKey = keyword.substring(to: current.level + 1)
//print("looking for prefix: \(searchKey)..")
//iterate through any child nodes
for child in current.children {
if (child.key == searchKey) {
childToUse = child
current = childToUse
break
}
}
if childToUse == nil {
return nil
}
} //end while
//retrieve the keyword and any descendants
if ((current.key == keyword) && (current.isFinal)) {
wordList.append(current.key)
}
//include only children that are words
for child in current.children {
if (child.isFinal == true) {
wordList.append(child.key)
}
}
return wordList
} //end function
}
(GitHub, fonte )
Pila
In informatica, uno stack è un tipo di dati astratto che funge da raccolta di elementi, con due operazioni principali: push, che aggiunge un elemento alla raccolta e pop, che rimuove l'ultimo elemento aggiunto che non è stato ancora rimosso. L'ordine in cui gli elementi escono da una pila dà origine al suo nome alternativo, LIFO (per ultimo dentro, prima uscita). Inoltre, un'operazione di sbirciata può dare accesso alla parte superiore senza modificare lo stack. (Wikipedia, fonte )
Vedi le informazioni sulla licenza qui sotto e la fonte del codice originale su ( github )
//
// Stack.swift
// SwiftStructures
//
// Created by Wayne Bishop on 8/1/14.
// Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation
class Stack<T> {
private var top: Node<T>
init() {
top = Node<T>()
}
//the number of items - O(n)
var count: Int {
//return trivial case
guard top.key != nil else {
return 0
}
var current = top
var x: Int = 1
//cycle through list
while current.next != nil {
current = current.next!
x += 1
}
return x
}
//add item to the stack
func push(withKey key: T) {
//return trivial case
guard top.key != nil else {
top.key = key
return
}
//create new item
let childToUse = Node<T>()
childToUse.key = key
//set new created item at top
childToUse.next = top
top = childToUse
}
//remove item from the stack
func pop() {
if self.count > 1 {
top = top.next
}
else {
top.key = nil
}
}
//retrieve the top most item
func peek() -> T! {
//determine instance
if let topitem = top.key {
return topitem
}
else {
return nil
}
}
//check for value
func isEmpty() -> Bool {
if self.count == 0 {
return true
}
else {
return false
}
}
}
La licenza MIT (MIT)
Copyright (c) 2015, Wayne Bishop & Arbutus Software Inc.
L'autorizzazione è concessa, a titolo gratuito, a chiunque ottenga una copia di questo software e dei relativi file di documentazione (il "Software"), per trattare il Software senza restrizioni, inclusi senza limitazione i diritti di utilizzo, copia, modifica, fusione , pubblicare, distribuire, concedere in licenza e / o vendere copie del Software e consentire alle persone a cui è fornito il Software di farlo, fatte salve le seguenti condizioni:
La suddetta nota sul copyright e questa nota di autorizzazione devono essere incluse in tutte le copie o parti sostanziali del Software.
IL SOFTWARE VIENE FORNITO "COSÌ COM'È", SENZA GARANZIE DI ALCUN TIPO, ESPLICITE O IMPLICITE, INCLUSE, A TITOLO ESEMPLIFICATIVO, LE GARANZIE DI COMMERCIABILITÀ, IDONEITÀ PER UN PARTICOLARE SCOPO E NON VIOLAZIONE. IN NESSUN CASO GLI AUTORI OI DETENTORI DEL COPYRIGHT SARANNO RITENUTI RESPONSABILI PER QUALSIASI RECLAMO, DANNO O ALTRO RESPONSABILITÀ, SIA IN UN ATTO DI CONTRATTO, TORT O ALTRO, DERIVANTE DA, FUORI O IN RELAZIONE AL SOFTWARE O ALL'UTILIZZO O ALTRI CONTRATTI NELL'AMBITO DEL SOFTWARE.