どーも🙏 jollyjoesterです。
これはSwiftKotlin愛好会アドベントカレンダー 2020の1日目の記事です。
今日はすでに12/26ですがアドベントカレンダー終わってから1日目、諦めずに頑張っていきたいと思いますw
Swift.orgのブログで紹介されていたSwift Algorithmsが気になっていたのにスルーしていたので、あらためて見てみたいと思います。
Swift Algorithmsとは?
SequenceとCollectionに関するアルゴリズムをOpen Sourceとしてまとめたものです。下記のアルゴリズムが含まれているようです。
- Combinations / Permutations
- Product
- Chunked
- Chain
- Cycle
- Unique
- Random Sampling
- Indexed
- Partition
- Rotate
どんな動きをするかはGitHubのGuidesに記載ありますが、手元で動かした方が理解が捗ると思います。
よければGuidesの内容をほぼそのまま動かせるようにした次のPlaygroundを使ってみてください。
各アルゴリズムについて
Combinations
コレクションから組合せ(nCr)を計算するメソッドです。
便利ですね!
import Algorithms
let numbers = [10, 20, 30, 40]
for combo in numbers.combinations(ofCount: 2) {
print(combo)
}
//[10, 20]
//[10, 30]
//[10, 40]
//[20, 30]
//[20, 40]
//[30, 40]
Permutations
コレクションから順列(nPr)を計算するメソッドです。
import Algorithms
let numbers = [10, 20, 30]
for perm in numbers.permutations() {
print(perm)
}
//[10, 20, 30]
//[10, 30, 20]
//[20, 10, 30]
//[20, 30, 10]
//[30, 10, 20]
//[30, 20, 10]
Product
異なるコレクション同士の積(それぞれのコレクションの要素をかけあわせる)を作ります。
import Algorithms
let numbersInEnglish = ["one", "two", "three"]
for (number, numberInEnglish) in product(1...3, numbersInEnglish) {
print("\(number)\(numberInEnglish)")
}
//1one
//1two
//1three
//2one
//2two
//2three
//3one
//3two
//3three
こちらと同等の処理ですが、productが使えるとわかりやすいですね。
for number in 1...3 {
for numberInEnglish in numbersInEnglish {
print("\(number)\(numberInEnglish)")
}
}
Chunked
Chunkは「かたまり」のことです。
コレクションを複数のサブシーケンスに分割します。
forで回して詰め直すみたなことやらなくてすみますね。
import Algorithms
let numbers = [10, 20, 30, 10, 40, 40, 10, 20]
let chunks1 = numbers.chunked(by: { $0 <= $1 })
print(chunks1)
// [ArraySlice([10, 20, 30]), ArraySlice([10, 40, 40]), ArraySlice([10, 20])]
let names = ["David", "Kyle", "Karoy", "Nate"]
let chunks2 = names.chunked(on: \.first)
print(chunks2)
// [ArraySlice(["David"]), ArraySlice(["Kyle", "Karoy"]), ArraySlice(["Nate"])]
Chain
Chainは「鎖でつなぐ」という意味です。
要素の型が同じ2つのコレクションを連結します。
シンプル
import Algorithms
let numbers = chain([10, 20, 30], 1...5)
print(Array(numbers))
//[10, 20, 30, 1, 2, 3, 4, 5]
let letters = chain("abcde", "FGHIJ")
print(String(letters))
//abcdeFGHIJ
Cycle
Cycleは「循環する」という意味です。
コレクションを無限にor指定された回数繰り返します。
import Algorithms
for x in (1...3).cycled(times: 3) {
print(x)
}
//1
//2
//3
//1
//2
//3
//1
//2
//3
Unique
Uniqueは「一意の」という意味です。
コレクションから重複する要素を削除したコレクションを返します。
import Algorithms
let numbers = [1, 2, 3, 3, 2, 3, 3, 2, 2, 2, 1]
let unique = numbers.uniqued()
print(unique)
//[1, 2, 3]
Random Sampling
コレクションから指定した数の要素をランダムに抽出したコレクションを返します。
randomStableSampleの方を使うと抽出された要素の順番が維持されます。
import Algorithms
var source = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
let sample1 = source.randomSample(count: 4)
print(sample1)
// [70, 30, 10, 50]
let sample2 = source.randomStableSample(count: 4)
print(sample2)
//[20, 60, 80, 90]
Indexed
コレクションの各インデックスと要素をペアにします。
import Algorithms
let numbers = [10, 20, 30, 40, 50]
var matchingIndices: Set<Int> = []
for (i, n) in numbers.indexed() {
if n.isMultiple(of: 20) {
matchingIndices.insert(i)
}
}
print(matchingIndices)
//[3, 1]
Partition
特定の条件を元にコレクションを並べ替える処理です。
元のコレクションの順番を維持する、しないメソッドがそれぞれあります。
var numbers1 = [10, 20, 30, 40, 50, 60, 70, 80]
let p1 = numbers1.partition(by: { $0.isMultiple(of: 20) })
print(p1)
print(numbers1)
//4
//[10, 70, 30, 50, 40, 60, 20, 80]
numbers1 = [10, 20, 30, 40, 50, 60, 70, 80]
let p2 = numbers1.stablePartition(by: { $0.isMultiple(of: 20) })
print(p2)
print(numbers1)
// p2 == 4
// numbers == [10, 30, 50, 70, 20, 40, 60, 80]
PartitionされたIndexを利用することもできます。
let numbers2 = [10, 30, 50, 70, 20, 40, 60]
let p = numbers2.partitioningIndex(where: { $0.isMultiple(of: 20) })
print(numbers2[..<p])
print(numbers2[p...])
//[10, 30, 50, 70]
//[20, 40, 60]
Rotate
指定した要素を先頭に来るように並べ替える(回転?)処理です。
レンジを指定して並べ替えることもできます。
import Algorithms
var numbers1 = [10, 20, 30, 40, 50, 60]
let p = numbers1.rotate(toStartAt: 2)
print(p)
print(numbers1)
//4
//[30, 40, 50, 60, 10, 20]
var numbers2 = [10, 20, 30, 40, 50, 60]
numbers2.rotate(subrange: 0..<3, toStartAt: 1)
print(numbers2)
//[20, 30, 10, 40, 50, 60]
numbers2.rotate(subrange: 3..<6, toStartAt: 4)
print(numbers2)
//[20, 30, 10, 50, 60, 40]
まとめ
コレクションを処理する方法について、便利〜って処理から既存の方法で同じことができるけど表現力が上がったようなものまで様々ありましたね!
まだまだバージョンが0.0.2とできたばかりなので今後が楽しみです。
Refs
- Swift AlgorithmsのGitHubリポジトリ
- Swift.orgでのSwift Algorithmsのブログ
- https://swift.org/blog/swift-algorithms/
- Swift Algorithmsを解説したInfoQの記事
- https://www.infoq.com/jp/news/2020/11/swift-algorithms-open-sourced/
- 関連として様々なアルゴリズムをSwiftで実装が解説されているGitHubリポジトリ
- https://github.com/raywenderlich/swift-algorithm-club/