Swift 数列の重複チェック（計算量）比較

paizaレベルアップ問題集のクエリメニューより
[指定要素の検索 (query) Swift編](https://paiza.jp/works/mondai/query_primer/query_primer__multi_search)をやりました。

# 対象読者
Swift初学者、競プロ初心者


# テストケース4の実行時間を比べます
入力値1行目
与えられる数字：98765
チェックする数字：100000
[入力値全DL](https://paiza.jp/works/mondai/downloads/test_case?id=5687)
ブラウザ完結のこちらが楽です[指定要素の検索 (query) Swift編](https://paiza.jp/works/mondai/query_primer/query_primer__multi_search)

# 6パターン

1. Array→Set変換してIntの組合せ(0.10秒)
1. Array→Set変換してStringの組合せ(0.11秒)
1. Set型とIntの組合せ(0.11秒)
1. Set型とStringの組合せ(0.13秒)
1. Array型とIntの組合せ(3.00秒以上)
1. Array型とStringの組合せ(3.00秒以上)


## 1. Array→Set変換してIntの組合せ(0.10秒)


```swift:0.10～0.11
let ak=readLine()!.split(separator: " ").map {Int($0)!}
let a=ak[0]
let k=ak[1]
var arr=[Int]() 
for _ in 0..<a{
    let an=Int(readLine()!)!
    arr+=[an]
}

let setArr=Set(arr)

for _ in 0..<k{
    let kn=Int(readLine()!)!
    if setArr.contains(kn){
        print("YES")
    } else {
        print("NO")
    }
}
```

## 2. Array→Set変換してStringの組合せ(0.11秒)

```swift:0.11
let ak=readLine()!.split(separator: " ").map {Int($0)!}
let a=ak[0]
let k=ak[1]
var arr=[String]() 
for _ in 0..<a{
    let an=readLine()!
    arr+=[an]
}
let setArr=Set(arr)

for _ in 0..<k{
    let kn=readLine()!
    if setArr.contains(kn){
        print("YES")
    } else {
        print("NO")
    }
}
```


## 3. Set型とIntの組合せ(0.11秒)
```swift:0.11秒
import Foundation
let ak=readLine()!.split(separator: " ").map {Int($0)!}
let a=ak[0]
let k=ak[1]
var arr=Set<Int>() 
for _ in 0..<a{
    let an=Int(readLine()!)!
    arr.insert(an)
}

for _ in 0..<k{
    let kn=Int(readLine()!)!
    if arr.contains(kn){
        print("YES")
    } else {
        print("NO")
    }
}
```

## 4. Set型とStringの組合せ(0.13秒)
```swift:0.12秒～0.13秒
import Foundation
let ak=readLine()!.split(separator: " ").map {Int($0)!}
let a=ak[0]
let k=ak[1]
var arr=Set<String>() 
for _ in 0..<a{
    let an=readLine()!
    arr.insert(an)
}

for _ in 0..<k{
    let kn=readLine()!
    if arr.contains(kn){
        print("YES")
    } else {
        print("NO")
    }
}
```
## 5. Array型とIntの組合せ(3.00秒以上)
```swift:タイムアウト
let ak=readLine()!.split(separator: " ").map {Int($0)!}
let a=ak[0]
let k=ak[1]
var arr=[Int]() 
for _ in 0..<a{
    let an=Int(readLine()!)!
    arr+=[an]
}

for _ in 0..<k{
    let kn=Int(readLine()!)!
    if arr.contains(kn){
        print("YES")
    } else {
        print("NO")
    }
}
```
## 6. Array型とStringの組合せ(3.00秒以上)
```swift:タイムアウト
let ak=readLine()!.split(separator: " ").map {Int($0)!}
let a=ak[0]
let k=ak[1]
var arr=[String]() 
for _ in 0..<a{
    let an=readLine()!
    arr+=[an]
}

for _ in 0..<k{
    let kn=readLine()!
    if arr.contains(kn){
        print("YES")
    } else {
        print("NO")
    }
}
```

# contains()が遅い？
計算量はO(n)

# ArrayよりSetが早い？
追加はArrayが早い
比較はSetが早い

公式SetのOverviewより

:::note 
You use a set instead of an array when you need to test efficiently for membership and you aren’t concerned with the order of the elements in the collection, or when you need to ensure that each element appears only once in a collection.

配列の代わりにセットを使用するのは、メンバーシップのテストを効率的に行う必要があり、コレクション内の要素の順序を気にしない場合、または各要素がコレクション内に一度だけ現れることを確認する必要がある場合です。
:::

# おわりに
SetはArrayよりも効率的に比較できそうな記述
Setではキーを使った参照は、O(1) で実行されるように実装されているらしい
ソースのどの部分かわからなかった
比較は結構面白い
この調子で公式に入り浸れるように続けていきたい

# 参考
[contains(_:)](https://developer.apple.com/documentation/swift/array/contains(_:))
[Set](https://developer.apple.com/documentation/swift/set/)
[Array](https://developer.apple.com/documentation/swift/array)
[Setは遅いのか](https://qiita.com/KyoheiG3/items/0bf9887a55fe7ad05811)