社内でElasticsearch勉強会を開いた

同僚からのリクエストで社内Elasticsearch勉強会を開いた。

全文検索の基礎始まりElasticsearchの基礎的なことの話

直前まで資料作ってたので、発表しながらまとまりないな〜と思ったけど思いの外好評っぽくてよかった。

speakerdeck.com

sidekiq の scheduled jobの性能

sidekiq と scheduled job

ruby でよく使われるジョブキューにsidekiqというものがあります。 Rails などでは Active Job のバックエンドとして使うこともできます。

sidekiq は即時的に処理を行うだけではなく、Scheduled Jobという機能があり、例えば以下のようにすると1時間後にjobを実行することができます。

MyJob.perform_in(1.hour)

# active job
MyJob.set(wait: 1.hour).perform_later

また、即時で実行したい場合には以下のようにします

MyJob.perform_async

# active job 
MyJob.perform_later

sidekiq の queue の実装

sidekiqでは、queueにredisを使用しており、即時実行用の queue と scheduled job 用のqueueは異なった実装になっています。 それぞれについて、どのようにjobを溜めているのか、どのようにjobを取り出しているのかをみていきます。

即時実行

即時実行の場合、 redisのリストに

"queue:#{queue_name}"

というkeyでjobがpushされていきます。コードはこの辺です。

キューから取り出すときも単純で、単にリストからpopしているだけです。

scheduled job

scheduled job はソート済みセット型を使用しています。 n時間後に実行の場合、以下のようにtimeオブジェクトを浮動小数点数への変換を行い、変換した値をソート済みセット型のスコアとして使用しています。

# https://github.com/mperham/sidekiq/blob/2ed92600fa71a9c275189d01df369ad4f8b9ca32/lib/sidekiq/worker.rb#L55-L66

def perform_in(interval, *args)
  int = interval.to_f
    now = Time.now.to_f
    ts = (int < 1_000_000_000 ? now + int : int)

    payload = @opts.merge('class' => @klass, 'args' => args, 'at' => ts)
    # Optimization to enqueue something now that is scheduled to go out now or in the past
    payload.delete('at') if ts <= now
    @klass.client_push(payload)
  end
  alias_method :perform_at, :perform_in
end
# https://github.com/mperham/sidekiq/blob/2ed92600fa71a9c275189d01df369ad4f8b9ca32/lib/sidekiq/worker.rb#L136-L144
def client_push(item) # :nodoc:
  pool = Thread.current[:sidekiq_via_pool] || get_sidekiq_options['pool'] || Sidekiq.redis_pool
  # stringify
  item.keys.each do |key|
    item[key.to_s] = item.delete(key)
  end

  Sidekiq::Client.new(pool).push(item)
end
# https://github.com/mperham/sidekiq/blob/2ed92600fa71a9c275189d01df369ad4f8b9ca32/lib/sidekiq/client.rb#L69-L77
def push(item)
  normed = normalize_item(item)
  payload = process_single(item['class'], normed)

  if payload
    raw_push([payload])
    payload['jid']
  end
end
# https://github.com/mperham/sidekiq/blob/2ed92600fa71a9c275189d01df369ad4f8b9ca32/lib/sidekiq/client.rb#L181-L206
def raw_push(payloads)
  @redis_pool.with do |conn|
    conn.multi do
      atomic_push(conn, payloads)
    end
  end
  true
end

def atomic_push(conn, payloads)
  if payloads.first['at']
    conn.zadd('schedule', payloads.map do |hash|
      at = hash.delete('at').to_s
      [at, Sidekiq.dump_json(hash)]
    end)
  else
    q = payloads.first['queue']
    now = Time.now.to_f
    to_push = payloads.map do |entry|
      entry['enqueued_at'] = now
      Sidekiq.dump_json(entry)
    end
    conn.sadd('queues', q)
    conn.lpush("queue:#{q}", to_push)
  end
end

続いて、queueからjobを取り出す処理を見ていきます。

  • ソート時みセット型から、Time.now.to_f.to_s 以下のスコアのjobを取得
  • 取得したjobをソート済みセット型から削除を試みる
  • 削除が成功すると、取得したjobを即時実行のqueueにpushする

という処理を行なっています

# https://github.com/mperham/sidekiq/blob/2ed92600fa71a9c275189d01df369ad4f8b9ca32/lib/sidekiq/scheduled.rb#L11-L33

def enqueue_jobs(now=Time.now.to_f.to_s, sorted_sets=SETS)
  # A job's "score" in Redis is the time at which it should be processed.
  # Just check Redis for the set of jobs with a timestamp before now.
  Sidekiq.redis do |conn|
    sorted_sets.each do |sorted_set|
      # Get the next item in the queue if it's score (time to execute) is <= now.
      # We need to go through the list one at a time to reduce the risk of something
      # going wrong between the time jobs are popped from the scheduled queue and when
      # they are pushed onto a work queue and losing the jobs.
      while job = conn.zrangebyscore(sorted_set, '-inf', now, :limit => [0, 1]).first do

        # Pop item off the queue and add it to the work queue. If the job can't be popped from
        # the queue, it's because another process already popped it so we can move on to the
        # next one.
        if conn.zrem(sorted_set, job)
          Sidekiq::Client.push(Sidekiq.load_json(job))
          Sidekiq::Logging.logger.debug { "enqueued #{sorted_set}: #{job}" }
        end
      end
    end
  end
end

queueの実装のまとめ

sidekiqでは、即時実行のqueueからjobをpopし、実行するやつはworker、scheduled job のqueue からjobを取得し即時実行のqueueにpushするやつはpooler と呼ばれておりそれぞれ別のスレッドで動いています。

ごちゃごちゃ書きましたが、文章だけだとわかりづらいので図にするとこんな感じです。

f:id:ogidow:20180625103131p:plain

scheduled job のパフォーマンス

ようやく本題です。 ある時点に多くの job を schedule すると、scheduled job の性能が悪くなります。 ここでいう性能が悪いというのは「n分後にscheduleしたが、実際に実行されるまでに時間がかかる」ということを意味しています。

処理量が増えるので、1つの poller あたりの処理量が頭打ちになり性能が悪くなるのは当たり前と思うかもしれません。 しかし、この問題は poller を増やしてもあまり改善しません。 「なぜpoller を増やしても改善しないのか、また即時実行の場合はworker を増やせば大量の処理を捌けるのか」ということを簡単な実験をしながら検証していきます。

即時実行の場合

上で説明した通り、即時実行の場合はredisのリスト型の queue にobが積まれており、worker が queue に積まれているjobを取り出し実行します。

簡易的に queue に 10万件の job が積まれていることを以下のように表現します。

require 'redis'
redis = Redis.new(host: '127.0.0.1', port: '6379')

100000.times do |i|
  redis.rpush('hoge', i)
end

そして、次のように 並列数(worker の数)を増やしつつ、job を 全て queue から取り出す速度を計測します。

require 'benchmark'
require 'redis'
require 'connection_pool'

number_of_worker = 5

Benchmark.realtime do
  Parallel.each((1..number_of_worker).to_a, in_processes: number_of_worker) do |i|
    redis_pool.with do |conn|
      while job = conn.rpop('hoge') do
      end
    end
  end
end

結果は以下のようになりました。

並列数 実行時間
1 21.21864500000038
3 19.56006800000023
5 15.638484000000062
7 13.080714000000171
10 11.504145999999764

並列数が増えるにしたがって、実行時間が短くなっていることがわかります。 このことから、即時実行でパフォーマンスに問題がある場合に、worker の数を増やすことは一定の効果があると考えられます。

scheduled job の場合

scheduled job の場合はソート済みセット型をqueueとして利用しているので、以下のように10万件の job が積まれていることを表現します。

require 'redis'
redis = Redis.new(host: '127.0.0.1', port: '6379')

100000.times do |i|
  redis.zadd('hoge', rand, i)
end

そして、同じように 並列数を増やしつつ、job を 全て queue から取り出す速度を計測します。

require 'benchmark'
require 'redis'
require 'connection_pool'

number_of_worker = 5

Benchmark.realtime do
  Parallel.each((1..number_of_worker).to_a, in_processes: number_of_worker) do |i|
    redis_pool.with do |conn|
      while job = conn.zrangebyscore('hoge', 0, 1, :limit => [0, 1]).first do
        conn.zrem('hoge', job)
      end
    end
  end
end

ポイントは即時実行の場合はqueueから job を取得する処理とqueueから削除する処理が同時にできるのに対し、 scheduled job では取得と削除を別々にやってます。

計測結果は以下のようになりました。

並列数 実行時間
1 46.90739100000064
3 82.63857199999984
5 125.35556799999995
7 111.53749299999981
10 150.0042739999999

並列数が増えるに連れて実行時間は長くなる傾向にあるようです。

scheduled job では並列で、queue から job の取得・削除を行うので以下のずのように競合が発生します。 競合が発生すると、片方の poller の処理が無駄になり効率が悪くなってしまいます。 並列数が増えると競合する確率が高くなり、処理の効率が落ち結果的に実行時間が長くなってしまうのかもしれません。

f:id:ogidow:20180626134443p:plain

実際にどのくらいの回数競合しているかを調べて見ます。

redis.del 'conflict'

Parallel.each((1..number_of_worker).to_a, in_processes: number_of_worker) do |i|
    redis_pool.with do |conn|
      while job = conn.zrangebyscore('hoge', 0, 1, :limit => [0, 1]).first do
        unless conn.zrem('hoge', job)
          conn.rpush('conflict', rand)
        end
      end
    end
  end

redis.llen 'conflict'
並列数 競合数
1 0
3 90490
5 164632
7 219304
10 308126

並列数が増えるに連れて、競合数も増えていることがわかります。 今回の実験では job数が10万件だったので、単純に10万回処理すれば良いはずですが、並列数10の場合は 308126回も処理が無駄になっています。

もちろん、実際は各poller が queue をポーリングするタイミングはもう少しばらけますが、poller が増えれば競合する確率も高くなるということには変わりありません。

同じ時間帯に大量の job を scheduling していて、実際に実行される時間までラグがあるという場合には、処理を1つのjobにできるだけまとめて、jobの数自体を減らすなどの工夫が必要かもしれません*1

*1:処理をまとめるかつ冪等なjobを書かないといけないという難しさはありますが...

Elasticsearchでtoo_many_clauseに遭遇した時のメモ

Elasticsearchで特定の条件で検索を行うときに too_many_clause に遭遇したときに調べた時のメモ。

indexの定義とデータは以下の感じとする

$ curl "localhost:9200/tests?pretty"
{
  "tests" : {
    "aliases" : { },
    "mappings" : {
      "test" : {
        "properties" : {
          "title" : {
            "type" : "text"
          }
        }
      }
    },
    "settings" : {
      "index" : {
        "number_of_shards" : "5",
        "provided_name" : "tests",
        "creation_date" : "1508801834006",
        "analysis" : {
          "filter" : {
            "ngram" : {
              "type" : "nGram",
              "min_gram" : "3",
              "max_gram" : "25"
            }
          },
          "analyzer" : {
            "default" : {
              "filter" : [
                "ngram"
              ],
              "type" : "custom",
              "tokenizer" : "keyword"
            }
          }
        },
        "number_of_replicas" : "1",
        "uuid" : "Fsi43Wx2S8uyyf8wtn59Xg",
        "version" : {
          "created" : "5060199"
        }
      }
    }
  }
}
$ curl "localhost:9200/tests/_search?pretty"
{
  "took" : 1,
  "timed_out" : false,
  "_shards" : {
    "total" : 5,
    "successful" : 5,
    "skipped" : 0,
    "failed" : 0
  },
  "hits" : {
    "total" : 3,
    "max_score" : 1.0,
    "hits" : [
      {
        "_index" : "tests",
        "_type" : "test",
        "_id" : "2",
        "_score" : 1.0,
        "_source" : {
          "title" : "fugafuga"
        }
      },
      {
        "_index" : "tests",
        "_type" : "test",
        "_id" : "1",
        "_score" : 1.0,
        "_source" : {
          "title" : "hogehoge"
        }
      },
      {
        "_index" : "tests",
        "_type" : "test",
        "_id" : "3",
        "_score" : 1.0,
        "_source" : {
          "title" : "foobar"
        }
      }
    ]
  }
}

curl だけで色々やるの面倒臭いので Elasticsearchのclientとして elasticsearch-ruby を使う。

まず、上記のindexの定義で普通に検索できることを確認

[29] pry(main)> client.search index: "tests",
[29] pry(main)* body: {
[29] pry(main)*   query: {
[29] pry(main)*     match: { title: "hoge" }
[29] pry(main)*   }
[29] pry(main)* }
=> {"took"=>2,
 "timed_out"=>false,
 "_shards"=>{"total"=>5, "successful"=>5, "skipped"=>0, "failed"=>0},
 "hits"=>{"total"=>1, "max_score"=>0.59868973, "hits"=>[{"_index"=>"tests", "_type"=>"test", "_id"=>"1", "_score"=>0.59868973, "_source"=>{"title"=>"hogehoge"}}]}}

ところが、極端に長い文字列で検索をかけると too_many_clause エラーが発生する

[30] pry(main)> client.search index: "tests",
[30] pry(main)* body: {
[30] pry(main)*   query: {
[30] pry(main)*     match: { title: "hoge" * 20 }
[30] pry(main)*   }
[30] pry(main)* }
Elasticsearch::Transport::Transport::Errors::BadRequest: [400] {"error":{"root_cause":[{"type":"query_shard_exception","reason":"failed to create query: {\n  \"match\" : {\n    \"title\" : {\n      \"query\" : \"hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge\",\n      \"operator\" : \"OR\",\n      \"prefix_length\" : 0,\n      \"max_expansions\" : 50,\n      \"fuzzy_transpositions\" : true,\n      \"lenient\" : false,\n      \"zero_terms_query\" : \"NONE\",\n      \"boost\" : 1.0\n    }\n  }\n}","index_uuid":"Fsi43Wx2S8uyyf8wtn59Xg","index":"tests"}],"type":"search_phase_execution_exception","reason":"all shards failed","phase":"query","grouped":true,"failed_shards":[{"shard":0,"index":"tests","node":"8ggISAxpTti1T1y_YxqBIQ","reason":{"type":"query_shard_exception","reason":"failed to create query: {\n  \"match\" : {\n    \"title\" : {\n      \"query\" : \"hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge\",\n      \"operator\" : \"OR\",\n      \"prefix_length\" : 0,\n      \"max_expansions\" : 50,\n      \"fuzzy_transpositions\" : true,\n      \"lenient\" : false,\n      \"zero_terms_query\" : \"NONE\",\n      \"boost\" : 1.0\n    }\n  }\n}","index_uuid":"Fsi43Wx2S8uyyf8wtn59Xg","index":"tests","caused_by":{"type":"too_many_clauses","reason":"maxClauseCount is set to 1024"}}}]},"status":400}
from /Users/syuta.ogido/works/minne/minne-app/vendor/bundle/ruby/2.4.0/gems/elasticsearch-transport-5.0.4/lib/elasticsearch/transport/transport/base.rb:202:in `__raise_transport_error'

まずは エラーメッセージがどういう意味なのか調べる

Elasticsearch の基盤である lucene のページでエラーメッセージの意味を見つけた https://lucene.apache.org/core/6_0_0/core/org/apache/lucene/search/BooleanQuery.TooManyClauses.html

Thrown when an attempt is made to add more than BooleanQuery.getMaxClauseCount() clauses. This typically happens if a PrefixQuery, FuzzyQuery, WildcardQuery, or TermRangeQuery is expanded to many terms during search.

BooleanQuery.getMaxClauseCount() 以上のboolean query を組み立てたときに投げられる例外らしい。

今回、自分で組み立てたqueryには明示的にboolean queryを使ってないので、match query で内部的にboolean query が生成されているのだろう。 エラーメッセージにmaxClauseCount is set to 1024 と書かれているのでmatch query が内部的に組み立てたboolean query が1024 個を超えたっぽい。

次にmatch queryがどんな動作をするのか調べる。 match queryの説明を読んでみると以下のことがか書かれている。 https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-match-query.html#query-dsl-match-query-boolean

The match query is of type boolean. It means that the text provided is analyzed and the analysis process constructs a boolean query from the provided text

match query は検索ワードをアナライザにかけて、その結果を元にboolean query を組み立ててるよという感じ。

token filterに nGram を設定しているのでそれで、検索ワードが大量に分割されていそう。 どのくらいのワードに分割されているのか調べてみる

[37] pry(main)> client.indices.analyze(index: 'tests', text: "hoge" * 20)["tokens"].count
=> 1541

エラーになった時の検索ワードだと1541ワードに分割されている

じゃあ、どのくらいの長さの検索ワードなら大丈夫なの?というのを調べる

[56] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 100)["tokens"].count
=> 2001
[57] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 900)["tokens"].count
=> 20401
[58] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 100)["tokens"].count
=> 2001
[59] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 90)["tokens"].count
=> 1771
[60] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 80)["tokens"].count
=> 1541
[61] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 70)["tokens"].count
=> 1311
[62] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 60)["tokens"].count
=> 1081
[63] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 59)["tokens"].count
=> 1058
[64] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 58)["tokens"].count
=> 1035
[65] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 57)["tokens"].count
=> 1012

予想が正しければ、57 文字まで大丈夫で58文字からエラーになるはずなので試してみる

[67] pry(main)> client.search index: "tests",
[67] pry(main)* body: {
[67] pry(main)*   query: {
[67] pry(main)*     match: { title: "a" * 57 }
[67] pry(main)*   }
[67] pry(main)* }
=> {"took"=>55, "timed_out"=>false, "_shards"=>{"total"=>5, "successful"=>5, "skipped"=>0, "failed"=>0}, "hits"=>{"total"=>0, "max_score"=>nil, "hits"=>[]}}
[68] pry(main)> client.search index: "tests",
[68] pry(main)* body: {
[68] pry(main)*   query: {
[68] pry(main)*     match: { title: "a" * 58 }
[68] pry(main)*   }
[68] pry(main)* }
Elasticsearch::Transport::Transport::Errors::BadRequest: [400] {"error":{"root_cause":[{"type":"query_shard_exception","reason":"failed to create query: {\n  \"match\" : {\n    \"title\" : {\n      \"query\" : \"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\",\n      \"operator\" : \"OR\",\n      \"prefix_length\" : 0,\n      \"max_expansions\" : 50,\n      \"fuzzy_transpositions\" : true,\n      \"lenient\" : false,\n      \"zero_terms_query\" : \"NONE\",\n      \"boost\" : 1.0\n    }\n  }\n}","index_uuid":"Fsi43Wx2S8uyyf8wtn59Xg","index":"tests"}],"type":"search_phase_execution_exception","reason":"all shards failed","phase":"query","grouped":true,"failed_shards":[{"shard":0,"index":"tests","node":"8ggISAxpTti1T1y_YxqBIQ","reason":{"type":"query_shard_exception","reason":"failed to create query: {\n  \"match\" : {\n    \"title\" : {\n      \"query\" : \"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\",\n      \"operator\" : \"OR\",\n      \"prefix_length\" : 0,\n      \"max_expansions\" : 50,\n      \"fuzzy_transpositions\" : true,\n      \"lenient\" : false,\n      \"zero_terms_query\" : \"NONE\",\n      \"boost\" : 1.0\n    }\n  }\n}","index_uuid":"Fsi43Wx2S8uyyf8wtn59Xg","index":"tests","caused_by":{"type":"too_many_clauses","reason":"maxClauseCount is set to 1024"}}}]},"status":400}
from /Users/syuta.ogido/works/minne/minne-app/vendor/bundle/ruby/2.4.0/gems/elasticsearch-transport-5.0.4/lib/elasticsearch/transport/transport/base.rb:202:in `__raise_transport_error'

57文字のやつはエラーにならず58文字のやつは too_many_clauses になった。 今回は nGramでanalyzeしていて、min_gram が 3 max_gram が25 だから、57文字まで大丈夫だけど、許容できる文字数はanalyzerの設定によって変わってくる。

analyzerの設定とqueryによってはこの辺も気をつけないといけなさそう。

searchkickのコードリーディング

普段、ElasticsearchとDBの関連付け兼Elasticsearchのクライアントとして searchkickをよく使っている。

searchkickは便利で、

Model.search('term', options).results

のようにメソッドを呼ぶだけで、Elasticsearchに検索をかけて、取得したドキュメントの_idフィールドを元にDBに検索をかける。その結果をModel オブジェクトの配列として受け取ることができる。

searchkickはoptionに並び並び順を指定することができる。 例えば

Model.search('term', order: { hoge: :desc }).results

といった感じに指定すれば、最終的に得られるModelオブジェクトの配列は hoge の降順に整列されている。

そこで少し疑問に思ったことがあった。searchkickが発行するsqlにはorder byなどは指定されていなかった。

Elasticsearchに検索でパフォーマンスを出すために非正規化されたデータが入っているので order by column はできないにせよ、 order by field(id, ids)のようなsqlが発行されるのだろうと思っていた。

少し気になったのでどうやってソートしているのかsearchkickのコードを読んでみた。

searchkickがelasticsearchへの検索結果を元にDBにクエリを投げるのは resultsメソッドなのでそのあたり読んだ。 resultsメソッドが定義されているのはこの辺

まず

hits.group_by { |hit, _| hit["_type"] }.each do |type, grouped_hits|
  results[type] = results_query(type.camelize.constantize, grouped_hits).to_a.index_by { |r| r.id.to_s }
end

でDBに問い合わせを行い、その結果をresults変数に以下のような形式で格納している

{
  type: {
    id1: model_object1,
    id2: model_object2
  }
}

(id*は対になっているmodel_objectが保持しているrecordのidです。)

ここではまだソートは行っていない。コードを追っていくとModel.where(id: ids) を呼んでいるだけだ。

その下の方にご丁寧に sortとと書かれたコメントとともに以下のような処理が書かれている

hits.map do |hit|
  result = results[hit["_type"]][hit["_id"].to_s]
  if result && !(options[:load].is_a?(Hash) && options[:load][:dumpable])
    unless result.respond_to?(:search_hit)
      result.define_singleton_method(:search_hit) do
        hit
      end
     end

     if hit["highlight"] && !result.respond_to?(:search_highlights)
       highlights = Hash[hit["highlight"].map { |k, v| [(options[:json] ? k : k.sub(/\.#{@options[:match_suffix]}\z/, "")).to_sym, v.first] }]
         result.define_singleton_method(:search_highlights) do
           highlights
         end
     end
  end
  result
end.compact

なんか長々と書かれているが、大半はoptionによってmethodを定義するみたいなやつなので純粋にソートに関する部分を切り出したら以下のようになる

hits.map do |hit|
  results[hit["_type"]][hit["_id"].to_s]
end.compact

めちゃくちゃシンプルで、Elasticsearchへの検索の結果からどの順番でソートすれば良いかは分かっているので、DBへの問い合わせ結果をその順序で抜き出して配列にしているだけ。 下手にorder by field(id, ids) みたいなクエリでもindexでソートを解決できずにfilesortが発生することもあるが、この方法だとO(n)のコストでソートできるので、不特定多数の人に使われるgemと考えると、DBでソートせずrubyでソートするのが正しいのだろうと思った。

また、order by field(id, ids) をしているクエリでfilesortが発生したらsearchkickのようにruby側でソートするのも手だと思った。 gem のコードたまにしか読まないけど、読むと毎回何かしらの学びがある。

コンソールで動くインベーダーゲームっぽいやつ作った

何か急にゲームっぽいものを作りた衝動にかられて、インベーダーゲームくらいならシュッと作れるかなと思ってインベーダーゲームっぽい何かを作ってみた。

本物のインベーダーゲームはやったことありません。

 

f:id:ogidow:20170619082203p:plain

 

工夫したところというか、この手のものを作る時には当たり前だけど、画面がチラつかないように毎回、画面を全体を再描画という方法ではなく動きがある部分だけを描画するようにしています。

作るかと思って3時間くらいで動くもの作れたので満足(バグだらけだけど)。

微分について

微分をご存知でしょうか?

関数{f(x)}に対する微分は次の式で定義できますね
 {
\frac{df(x)}{dx}  =  \lim_{h \to 0}\frac{f(x+h)-f(x)}{h}
}

微分はでは関数{f(x)}の点{x}における接線の傾きを表します。
例えば、{f(x) = x^2}の関数を考えます。図で表すと以下のようになります。

f:id:ogidow:20170220084146p:plain

ここで{x=4}の点に接線を引きます。
f:id:ogidow:20170220085549p:plain

この緑の線の傾きが微分によって求めることができます。

では、任意の{x}の傾きを求めることができると何が嬉しいのでしょうか?

例えば、{f(x) = x^2}が体重とかコストとかを近似できると仮定します。体重もコスト小さいに越したことはないでしょう。
何らかのパラメータxが4の時、微分の値は{\frac{df(x)}{dx}  = 8 > 0}となりパラメータを小さくすれば、{f(x)}が最小になりそうだなと推測することができます。また、{f(x)}が最小の点で接線はx軸に水平になるので。{\frac{df(x)}{dx}  = 0}となり、{f(x)}は(厳密には違いますが)最小だと推測することができます。

何となく微分ができれば関数の最小値を求めることができて便利そうだなということがわかりました。
でもなぜ、微分で接線の傾きを求めることができるのでしょうか。直線の式といえば{y = ax + b}で表されます。
直線の傾きと呼ばれる部分は{a}です。中学校などで{(x1,y1),(x2, y2)}を通る直線の傾きは{a = \frac{yの増加量}{xの増加量} = \frac{y2 - y1}{x2 - x1}}と習ったと思います。
しかし、部分ではある1点における傾きを求めるので上記の方法は使うことができません。

ではどうするのでしょうか。{f(x) = x^2}として、
{(x1,y1),(x2, y2)}ではなく{(x,f(x)), (x + h, f(x + h)}と考えてみます。すると、2点を通る直線の傾きは{a =  \frac{f(x + h) - f(x)}{x + h - x} = \frac{f(x + h) - f(x)}{h}}と書けます。求めたいのは2点を通る直線の傾きではなく1点を通る直線の傾きです。{h}が限りなく0になれば2点ではなく1点を通る直線になりそうです。
{\lim_{h \to 0}\frac{f(x+h)-f(x)}{h}}としてhを限りなく0に近づけると、微分の定義戻りました。
微分によって、関数の最小値を求めることができると単回帰分析などでサンプルしたデータ群を元にデータを近似したモデルを作ることができるようになるのですがそれは別の記事で書きます。

若手エンジニアLT大会で登壇した

登壇してからかなり時間が経ちましたが書きます。

11月22日にドリコムさん主催の若手エンジニアLT大会で登壇させていただきました。

きっかけ

社内で@june29さんから声をかけていただき、登壇経験もなかったのでチャンスだと思い若手エンジニアLT大会に参加することを決めました。

内容

僕は、学生時代にコードレビューという文化が存在しなかったので、社会人になって初めてコードレビューというものを行いました。コードレビューをやってもらったり、やったりした中で感じたことを発表しました。

感想

各社の若手の皆さんはどうやって会社に技術貢献してきたかや入社して何をやってきたかなどを発表していました。 すべての発表においてレベルが高く、ポジティブな意味で自分ももっと頑張らないとなと思いました。

とても緊張しましたが参加してとてもよかったと思います。 あと、ドリコムさんのオフィスがめちゃくちゃお洒落でした。