唐突な競プロ要素。

開発環境

> xcodebuild -version
Xcode 12.3
Build version 12C33

imos法

いもす法とは,累積和のアルゴリズムを多次元,多次数に拡張したものです.
いもす法 - いもす研 (imos laboratory)

具体例を追って imos法 を理解していく。


あなたは旅館を経営しています。
  
旅館では[ルール]の内容に従って、一週間の各曜日の客の総数を管理しています。  
どうすれば客の管理を効率化できますか?  
[客の入退場予定]を使って、効率化の例を示してください。  
  
[ルール]
・ 1×7 の表を使用(1つのセルが各曜日に対応)
  
[客の入退場予定]
1. 入場: 0曜日 | 退場: 2曜日
2. 入場: 3曜日 | 退場: 6曜日
3. 入場: 1曜日 | 退場: 4曜日

愚直な解法

  • 方針:「入場する曜日」 から 「退場する前日の曜日」までの間のすべてのセルの値を +1
  • 計算量:Nを曜日数, Mを客の入退場数とした場合 O(NM)

 

初期状態

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |  # 曜日 
-----------------------------
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |  # 各曜日の客の総数 

 

1. 入場: 0曜日 | 退場: 2曜日

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |  
-----------------------------
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |  

 

2. 入場: 3曜日 | 退場: 6曜日

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |  
-----------------------------
| 1 | 1 | 0 | 1 | 1 | 1 | 0 |  

 

3. 入場: 1曜日 | 退場: 4曜日

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |  
-----------------------------
| 1 | 2 | 1 | 2 | 1 | 1 | 0 |  

 

効率が悪い。
7日泊まる客が10000人いる場合、 7 * 10000 回 セルを更新する必要がある。

imos法を使った解法

  • 方針:「入場する曜日」 のセルの値を +1、「退場する曜日」のセルの値を -1 して、最後に累積和を取る
  • 計算量:Nを曜日数, Mを客の入退場数とした場合 O(N+M)

 

初期状態

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |  # 曜日 
-----------------------------
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |  # 各曜日の客の総数 

 

1. 入場: 0曜日 | 退場: 2曜日

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |  
-----------------------------
| 1 | 0 | -1| 0 | 0 | 0 | 0 |  

 

2. 入場: 3曜日 | 退場: 6曜日

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |  
-----------------------------
| 1 | 0 | -1| 1 | 0 | 0 | -1|  

 

3. 入場: 1曜日 | 退場: 4曜日

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |  
-----------------------------
| 1 | 1 | -1| 1 | -1| 0 | -1|  

 

最後に前から後ろに足していく(累積和)

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |  # 曜日 
-----------------------------
| 1 | 1 | -1| 1 | -1| 0 | -1|  # 各曜日の客の総数 
-----------------------------
| 1 | 2 | 1 | 2 | 1 | 1 | 0 |  # 累積和

 

愚直な解法の O(NM) と比較して、 O(N+M) に収まり効率化された。

imos法(一次元)の練習問題

練習問題を解くと理解が深まるのでおすすめ。

imos法でセルの管理をする

本題。
iOSアプリ内でcollectionViewの状態管理を imos法 で行った。

コード

gif

参考