tkherox blog

データサイエンスおよびソフトウェアについての話を書いています

データ分析でもアルゴリズム『いもす法』

はじめに

データサイエンスを日常的に行う中で大量のデータを扱うことが往々にしてあります.その際に頻繁に発生してくる問題が膨大な計算量による待ち時間発生や計算が有限時間内に終了しないといった問題です.

私は特にこの待ち時間を非常に厄介だと感じていてます. 何故かと言うと,待ち時間が発生すると当該処理が終わるまで別の作業をして効率的に物事を実施しようと思うのですが,逆にこのタスクの切り替えによってオーバヘッドがかかってしまい非効率になってしまうためです.

例えば,英語長文読解の勉強をしている途中で急に洗濯の依頼をされ,洗濯が終わった後に勉強を再開しようすると,途中まで読んでいた内容を思い出すために長文を読み直したりすることがあると思います.このようにタスクの切り替えにはオーバーヘッドが付き物であり,労力がかかることがしばしばあります.

そのため,データ分析に関しても可能な限り待ち時間を少なくして集中して取り組むことが良いと考えています.こういった経験から実行速度やメモリ効率に影響してくるアルゴリズムを理解することは重要であると思っており,時間があるときに私はアルゴリズムの学習をしています.
そこで,今回はその学習過程で出会った『いもす法』というアルゴリズムについてまとめていこうと思います.

『いもす法』ってなんぞや

いもす法は「ある連続する区間に、ある数 v を足す」という操作をK回繰り返した結果を、計算量 O(N+K) で高速に計算する方法です.
これだけ聞くとどういう事を意味しているのか分かりづらいと思うので,処理の具体的なプロセスを以下に記載します.

  1. 加算処理
    区間 [a, b]v を加算したいとき、a 番目の値に v を加算して b+1 番目の値に -v を加算する
  2. 累積和
    加算処理した結果を元に累積和を計算して結果を得る

要するに,いもす法では区間の入口で加算、区間の出口で減算をしたリストを作成して、リストの作成が終わったら前から順に累積和を計算していきます.この後ではPythonで実装した例を示していこうと思います.
また,いもす法の本家の解説は以下になります.より深い理解をしたい人は参照してください.

imoz.jp

Pythonでの実装例

さて,いもす法をPythonを用いて実装してみようと思います. 実行環境は以下となっています.

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.14.6
BuildVersion:   18G6042

$ python -V
Python 3.6.9

簡単のために長さがNの1次元配列を題材とします.
以下が今回扱う問題です.

長さが10のリストにおいて、
- 区間[1, 7]に2を加算
- 区間[4, 8]に3を加算
- 区間[0, 5]に5を加算
という3つの操作をしたときの最終結果はいくつか.

まず長さが10の配列を作成します.

N = 10
data = [0] * N

次に区間[1, 7] に2を加算する処理を適応します.
この場合はリストのインデックスが 1 の時に 2 を加算して,インデックスが 8 の時に 2 を減算します.

a, b = 1, 7
v = 2
data[a] += v
if b+1 != N:
    data[b+1] -= v

同様に区間 [4, 8][0, 5] に3と5をそれぞれ加算してリストを更新します.

a, b = 4, 8
v = 3
data[a] += v
if b+1 != N:
    data[b+1] -= v

a, b = 0, 5
v = 5
data[a] += v
if b+1 != N:
    data[b+1] -= v

そして最後にこのリストより累積和を計算します.

ans  = [0] * N
for i in range(0, N):
    if i == 0:
         ans[i] = data[i]
    else:
        ans[i] = ans[i-1] + data[i]

print(sum(ans))
#59

また,処理が冗長な部分を省いた場合のコードは以下となります.

# 要素のリスト作成
N = 10
data = [0] * N

# 要素のリスト更新
rlist = [(1, 7, 2), (4, 8, 3), (0, 5, 5)]
for a, b, c in rlist:
    data[a] += c
    if b+1 != N:
        data[b+1] -= c

# 累積和の計算
ans = [0] * N
for i in range(0, N):
    if i == 0:
         ans[i] = data[i]
    else:
        ans[i] = ans[i-1] + data[i]

print(sum(ans))

実際の実装例を踏まえて『いもす法』の一連な流れが理解できたと思います.
今回の例ではリストの長さが小さいため,『いもす法』を使わずとも各区間について2重ループを回すことで結果を求めることができます.しかし,このリストの長さが非常に長くなった場合には計算が立ちゆかなくなってくるので『いもす法』はそう言った場合に非常に効力を発揮ので覚えておいて損はないと思います.

まとめ

今回はデータ分析の下支えとなるアルゴリズムに関して知識整理を兼ねてまとめてみました.
データ分析のゴールは分析して終わりではなく,データ分析で得られた知見を顧客までデリバリして価値を提供する事になります.そのデリバリの方法の1つとしてソフトウェアによる提供が多くあると思います.そういった観点からも開発サイドでアルゴリズムに精通することは決して無駄にはならないのでデータ分析と合わせて学習していくと良いと思います.

ofuse.me