[Swift] Swiftでポインタを使って処理を高速化してみる
前書き
Swiftのような高級言語(高水準言語)を書いている人にとって、普段はポインタを意識することはないでしょう。
今回はそんな世界へと一歩踏み入れてみましょう！
ポインタを使った高速化
簡単な例を使って見ていきましょう。
Example1
1. コード例
0~1000の数字を合計するだけの処理を考えた時、以下のようになります。
func runLoopNumbers() {
var sum = 0
for i in (0...1000) {
sum += i
}
}
これをポインタを用いた場合は、以下のように書けます。
func runLoopPointerNumbers() {
var sum = 0
let sumPointer = UnsafeMutablePointer<Int>(&sum)
for i in (0...1000) {
sumPointer.pointee += i
}
}
このUnsafeMutablePointerというのを用いることでポインタを表しています。
（表すための方法がいくつかあり、参考文献の方に詳しく載せているのでそちらをご覧ください）
2. 比較結果
それぞれ１０回ずつ実行した結果とその平均時間を取ると
| 回数 | ポインタなし | ポインタあり |
|---|---|---|
| 1回目 | 2.10E-02 | 7.37E-04 |
| 2回目 | 9.09E-03 | 7.12E-04 |
| 3回目 | 9.41E-03 | 7.10E-04 |
| 4回目 | 9.87E-03 | 7.16E-04 |
| 5回目 | 9.72E-03 | 7.19E-04 |
| 6回目 | 9.12E-03 | 7.25E-04 |
| 7回目 | 1.01E-02 | 7.26E-04 |
| 8回目 | 9.05E-03 | 7.28E-04 |
| 9回目 | 9.14E-03 | 7.30E-04 |
| 10回目 | 8.93E-03 | 7.15E-04 |
| Average | 1.05E-02 | 7.22E-04 |
| = 0.010539 | = 0.000722 |
実行時間が１秒にも満たないので、一見たいしたことはないかもしれませんが...
実行速度に15倍程の差がついていることがわかります。
※ DateのtimeIntervalSinceで計測
※ E-01 = 10^-1 = 1/10
Example2
海外の競技プログラミングでお馴染みLeetCodeの「1. Two Sum」という問題を例にとってみましょう。
0. 前提
問題は以下のようになっています。
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
つまり
「与えられた配列（nums）から２つを選択し、指定した値(target)を作れるかどうか」
ということになります。
その最初の例として、以下が与えられます。
Given nums = [2, 7, 1, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
1. コード例
愚直にforやwhileを使って解けば、このようになるでしょう。（あくまで一例として）
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
for i in 0 ..< nums.count {
var j = i+1
while j < nums.count {
if nums[i] + nums[j] == target {
return [i, j]
}
j += 1
}
}
return []
}
シンプルに配列を２回調査する線形探索をしています。
これをポインタを用いた場合は、以下のように書けます。
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var newNums = nums
let pointer = UnsafeMutablePointer<Int>(&newNums)
for i in 0 ..< nums.count {
var j = i+1
while j < nums.count {
if pointer[i] + pointer[j] == target {
return [i, j]
}
j += 1
}
}
return []
}
var newNums = numsとしているのが冗長ですが、ポインタを使うために仕方なく置く必要があります。
2. 比較結果
| ポインタなし | ポインタあり |
|---|---|
| 24ms | 8ms |
実行速度が3倍早くなっていることがわかります。
処理が重たいものであればもっと顕著な差が出せるでしょう。
3. 余談
ちなみにポインタを使わなくても、この問題は高速にできるので載せておきます。（あくまで一例として）
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var keyValue = [Int: Int]()
for (i, num) in nums.enumerated() {
if let index = keyValue[target-num] {
return [i, index]
}
keyValue[num] = i
}
return []
}
数字をkeyとして値をキャッシュしておき検索する（ハッシュテーブルを使う）方法です。
これであれば、O(n)で済むのでかなり高速です。
実行時間は8msでポインタを使った時と同じ速度を出すことができました。
終わりに
実務で使うというのはなかなか難しいかもしれません。
競技プログラミングのようなロジックだけを考える、といった部分的な使い方であればとても入りやすいでしょう。
ただ、余談でも紹介しましたが...
ポインタを使う前にアルゴリズムをちゃんと用いることで高速化できることが多いです。
とはいえ、触ってみてるのは楽しいので、是非みなさんも使ってみてください！
参考文献
Swiftのポインタ関連
ポインタ関連
Author And Source
この問題について([Swift] Swiftでポインタを使って処理を高速化してみる), 我々は、より多くの情報をここで見つけました https://qiita.com/hcrane/items/3adaa811733db2d323d9著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .