※ Swiftバージョン
Apple Swift version 4.0.2 (swiftlang-900.0.69.2 clang-900.0.38)
Target: x86_64-apple-macosx10.9
書いたこと
swiftは命令型プログラミングと関数型プログラミングの両方のパラダイムを持ち合わせるマルチパラダイム言語です。
上記はそれぞれクラス(or 構造体）と代数的データ型(enumのこと）を用いて各種のデータ構造を表すことが出来ることで見出すことも出来ます。
そこで単方向リストでそれぞれを実装し、そのメリット、デメリットを比較してみました。
命令型プログラミングと関数型プログラミングの違い
関数型プログラミングの基礎 JavaScriptを使って学ぶ (amazon)」から
- 土台となっている数学モデルが異なる
- 命令型プログラミング = チューリング・マシン
- 関数型プログラミング = ラムダ計算
- それぞれにおける計算の意味が異なる
- 命令型プログラミング = 命令(状態の変更）を実行すること
- 関数型プログラミング = 関数を呼び出して値を得ること
classとenumによる単方向リストの定義
※ Swiftのstructは再帰的な型の宣言が出来ないため、命令型プログラミングでの例としてclassを用いています。
class
class List<T> {
var head: Node<T>?
var last: Node<T>?
class Node<T> {
let value: T
var next: Node<T>? = nil
init(_ value: T) {
self.value = value
}
}
}
enum
enum List<T> {
case empty
indirect case node(T, List<T>)
}
classによる実装
[gist] (https://gist.github.com/ysn551/b02d8568191cbb6de001490aebc9e4ea#file-class_list-swift)
extension List {
func append(_ newValue: T) {
let newNode = Node(newValue)
if self.head == nil {
self.head = newNode
self.last = self.head
} else {
self.last!.next = newNode
self.last = self.last!.next
}
}
func insert(_ newValue: T, at index: Int) {
let newNode = Node(newValue)
if index == 0 {
let oldHead = self.head
self.head = newNode
newNode.next = oldHead
if self.last == nil {
self.last = self.head
}
} else {
var node = self.head
for _ in 1..<index {
node = node?.next
if node == nil {
break
}
}
let temp = node?.next
node?.next = newNode
newNode.next = temp
if self.last === node {
self.last = newNode
}
}
}
func remove(at idx: Int) {
if self.head == nil {
return
} else if idx == 0 {
let prevHead = self.head
let next = self.head!.next
self.head = next
if self.last === prevHead {
self.last = self.head
}
} else {
var prev = self.head
var node = self.head?.next
for _ in stride(from: 1, to: idx, by: 1) {
if node == nil || node?.next == nil {
prev = nil
node = nil
break
}
prev = node!
node = node!.next
}
// delete node
prev?.next = node?.next
if self.last === node {
self.last = node?.next
}
}
}
}
enumによる実装
extension List {
func appending(_ newElement: T) -> List<T> {
switch self {
case .empty:
return .node(newElement, .empty)
case .node(let value, let tail):
return .node(value, tail.appending(newElement))
}
}
func inserting(_ newElement: T, at index: Int) -> List<T> {
switch self {
case .empty:
return .node(newElement, .empty)
case .node(let value, let tail):
if index == 0 {
return .node(newElement, .node(value, tail))
} else {
return .node(value, tail.inserting(newElement, at: index-1))
}
}
}
func removing(at idx: Int) -> List<T> {
switch self {
case .empty:
return .empty
case .node(let value, let tail):
if idx == 0 {
return tail
} else {
return .node(value, tail.removing(at: idx-1))
}
}
}
}
それぞれのメリットとデメリット
コード
- enumの方がシンプル
- classは状態の管理が大変だった(headとlast)
実行速度
- classの方が圧倒的に速い
まとめ
classによる実装は、状態の管理(とくにlastを追随させること)が大変でしたが、実行速度は圧倒的にclassの方が早くなります。
また実装もメモリの状態をステップバイステップで変更していく感じで実装できるため、イメージしながら実装できました。
しかしながらenumによる実装は、状態を変更させていくのではなく、関数を呼び出していく感じになるため、状態の変更がイメージし辛く、そこが難しいと思いました。
また実行速度も大変遅くなるため、メモ化も合わせて行う必要があると思われます。
参考書籍 & サイト
命令型プログラミングと関数型プログラミングの違いについて:
関数型プログラミングの基礎 JavaScriptを使って学ぶ amazon
学術的な支点からも解説されているので、とても勉教になりました。
単方向リストの実装について:
swift-algorithm-club/LinkedList
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Linked%20List