昔Array#include?の多用でボトルネックになりかけた失敗

Ruby Rails 失敗談 tips

カテゴリーを4つつけたら
[Ruby][Rails][失敗談][tips] 記事タイトル
と非常に読みづらくなったので、初期設定のカテゴリーは分ける2行表示に戻した。

==========================================

それっぽい例で例えます。
完全そのものを言ってるわけではございませんｗ


ショッピングカートシステムがあったとして、
Cartオブジェクトのインスタンスに、商品の種類･個数を持っていたとする。
種類はcodeとかproduct_nameとかそういう感じで、
個数はquantityかな。

で、大体のEC系サイトだと
「注文する」とか「カートに入れる」とかそんなボタンで、
カートに注文確定前の予定の品として、保持されますよね。


そこで、
一度入っている商品が、もう一度追加された場合にどうするか。
パターンとしては
・同じ商品の2商品目として追加する(エラーチェックをかけない)
・何もしない(システム依存。多分上記と同じ)
・既に入っているとエラーを出す(カート内をチェックして同一商品存在時にエラー)
・既に入っている商品の個数quantityに+1する(カート内をチェックして同一商品存在時に+1)
とかが考えられます。


これをする際に、
Cartインスタンスが商品種類を配列でもたせていて、それは間違いではないと思います。

が、追加する際に、
(@cart.productsでカート内部商品を識別するコードとか商品オブジェクトが配列で入ってて取れるとする)

@cart.追加("入れたい商品オブジェクト") unless @cart.products.include?("入れたい商品オブジェクト")

とした。

これはつまり、
1000個の商品をカートに入れるような人が居た場合に、
新しい商品をカートに入れるたびに、前チェックが走るので、
結構ボトルネックの元なります。

ただ、どうやればこの実装がより速くなるかは結構難しいですね。
割と上のはシンプルな発想なので、間違ってはいないはずだし、
それ以上に適切なコードってのもさほど存在しない気もします。
例なので、こうした方が速い・正しいって言及はしていきませんけどねｗ


まぁこの例だと、若干感じにくいかもしれません。


では、下記例だとどうでしょうか。


アクセスログとかから、
アクセス総数はログ行数でわかるとして、
ユーザー数がとりたい場合。
サンプルなので、必ずログの行にユーザーIDがついているものとして、
ユーザーIDが含まれて居るかどうかの判定は入れないコードの例を書きます。

  access_log = File.open("アクセスログファイル")
  
  #ログ行数カウント用
  total_access = 0 

  #ユーザー数のためにユーザーIDを格納する配列。
  #ユーザーIDを正規表現で取り出して追加していく
  user_ids = [] 
  access_log.each do |log_line|
    total_access += 1
    user_id = log_line[/user_id=(\d+)/,1].to_i #正規表現でユーザーIDを抜き取る

    #user_ids配列に、user_idが存在しなければ配列にID追加
    user_ids << user_id unless user_ids.include?(user_id)
  end

  puts "アクセス数 #=> #{total_access}"
  puts "アクセス人数 #=> #{user_ids.size}"

こんな例。
これはログがGB単位になったらそもそもFile.ipenしてeachするようなRubyスクリプトで集計してちゃダメだし例として適切なの？
って突っ込まれるかもしれません。突っ込まないでくださいｗ


で、これはめっちゃボトルネックなコードになります。
アクセスごとに、
「このユーザーってもうアクセスした人としてカウントしてたっけ？
してなかったら追加しなきゃだよねー　キャハハ」
な事をしてるから、凄い遅い。

それも、
配列がでかくなって格納されるユーザーIDが1万人とか超えて、
ログの行数が100万行以上あるなら・・・

毎回各行のたびに、最終的には1万個のIDが入った入った配列の要素に、
追加したい要素が含まれるかinclude?でチェックする。

ご想像がつきますでしょうか。
半端なく重い。


結構私は、Array#include?は好きで多用していたので、
こんな例に近い事になったことがあります。
今も使いますが、配列のサイズ・評価される回数が少ない場合かどうか考えて入れるとかしています。


さっきの1万ID、100万行なアクセスログなら、
メモリ膨らむのでメモリ的な余裕あればですけれども、

  access_log = File.open("アクセスログファイル")
  
  #ログ行数カウント用
  total_access = 0 

  #ユーザー数のためにユーザーIDを格納する配列。
  #ユーザーIDを正規表現で取り出して追加していく
  user_ids = [] 
  access_log.each do |log_line|
    total_access += 1
    user_id = log_line[/user_id=(\d+)/,1].to_i #正規表現でユーザーIDを抜き取る

    #user_ids配列に、user_idの存在に関わらずuser_idをぶちこむ
    user_ids << user_id
  end

  puts "アクセス数 #=> #{total_access}"
  puts "アクセス人数 #=> #{user_ids.uniq.size}" #最後にArray#uniqをかけて人数を得る


配列が行数分になるので、
バイト数的に結構場合によってはメモリ食いますので、メモリ問題は出ます。

ただ、毎行ごとに配列にinclude?かけて要素チェックした上で追加なんて判定が減った事で、
段違いに早くなります。
Array#uniqは大きい配列にも、そこまで遅くないので、こっちの方が正解。
メモリを考えると不正解かな。


each_with_indexか、カウントしてるのでtotal_accessによって、
定期的に3000回に1回くらいuniq!で破壊的に配列縮めれば少しは良いのかも？
ガベージコレクションがどのタイミングで動いて、破壊的に減らした分をうまいこと綺麗にして軽くしてくれるかはわかりませんが・・・。
仮にGC.startを明示的に書いても、each途中で軽くなるかは…やったことないのでわかりません。


まとめ

eachとかイテレータ、ループの中で、
include?する時は気をつけよう、出来たら使うのはやめよう。

どうしても使うときは、
if文とかでinclude?に行く回数を下げるとか(でも毎度if評価は入るね)、
イテレータ・ループ回数が少ない保証がある場合くらいのほうが幸せ。

===========================================

余談。
最近ArrayやHashの変数宣言を、シンタックスシュガーな
array = []
hash = {}
で書かなくなってきた。

変数宣言時に、
初期値とかある程度、上手く動いてくれたら幸せな事が分かるようになってきたので、
array = Array.new(いろいろ)
hash = Hash.new(いろいろ)
と書く事が増えた。

何も無くても、後から後ろに付けて変えやすいから、
array = Array.new
hash = Hash.new
で長いと言われてもちゃんと書いてる。



個人的には、特に
hash = Hash.new(0)
で、キーに対する初期値を0にしとくのがよくやります。

さっきのアクセスログで、ユーザーIDごとのアクセス数も出して！とか言われた場合に便利。
(その要求なら別のアーキテクチャ使おう！ってのがパフォーマンスとして正解かと思いますが例ですので)

  access_log = File.open("アクセスログファイル")
  
  #ログ行数カウント用
  total_access = 0 

  #ユーザーIDごとのアクセス用Hash {ユーザーID(Fixnum) => アクセス回数(カウント)}
  user_id_with_access = Hash.new(0)

  access_log.each do |log_line|
    total_access += 1
    user_id = log_line[/user_id=(\d+)/,1].to_i #正規表現でユーザーIDを抜き取る

    #HashのユーザーIDのキーに、アクセス回数追加
    user_id_with_access[user_id] += 1
  end

  puts "アクセス数 #=> #{total_access}"
  puts "アクセス人数 #=> #{user_id_with_access.keys.size}" #Hashのkeyがユーザー人数になりますね

  #これならアクセス回数ごとの人数分布とかも出そうと思えば出せるね！


user_id_with_access = {}
だと、
user_id_with_access[user_id] += 1
部分で最初に
nil + 1と解釈されて、
NoMethodError: undefined method `+' for nil
って怒られてしまう。

それをしない方法の力技tipsとしては、

test_hash = {}
test_hash[:test_key] += 1 rescue test_hash[:test_key] = 1

みたいな事も出来るけど、スマートじゃない。

何かと、
色んな数をカウントアップしていくHashを持ちたい場合なんかは、
Hash.new(0)と書くほうが非常に便利と。