歩いたら休め

なんでこんな模様をしているのですか？

【アルゴリズム】検索エンジンで重要なトップnソートについてまとめておく

アルゴリズム

検索エンジンやレコメンドエンジンを昔実装していた先輩から、飲み会で

という話を聞きました。

ところが、私は低レイヤーの言語（CやC++）から逃げてPythonを始めたような人間なので、残念ながら「アルゴリズムとデータ構造」と呼ばれるような分野は全く詳しくありません。

しかし、社内には既に数学や機械学習・数理計画法の知識では敵わない人がいるため、私は生き延びるためには実装やアーキテクチャ（要するに数理モデルを「検索エンジン」として使えるようにする技術）を勉強しなければいけないと思っています。

という話はさておき、今後これらの分野を勉強するときのために、「トップnソート」関連の記事についてポインタを残しておこうと思います。

まずはこちらの記事。"top n sort"ではなく"top k-selection"と呼んでいますが、同じアルゴリズムだと思います。

qiita.com

プログラムを書くお仕事をしていると、いろんな場面で top-k selection をしなきゃいけない状況にちょくちょく出くわすことがあるかと思います。もちろん RDBMS を使っていれば、ORDER BY sort_column LIMIT k とすることでさくっと top-k selection が実現できるわけですが、RDBMS の外で top-k selection をしなきゃいけない状況だって (年に 2〜3 回もあるかは個人差がありますが)、人生の中で 1〜2 回は遭遇するんじゃないかと思います。

非常にわかります。私の場合、今のところ運良く「nが小さく、全部ソートしてしまっても遅くなかったケース」「一番大きなものだけ選ぶケース」にしか当たっていないので実装せずに済んでいるのですが。

こちらの記事のコメントで、言われている「mikioさんのページ」は、

本当は、mikioさんがかなり色々と実験をされていたので、そこにリンクが張れるとよかったんですが、ページが消えてるみたいで、見つかりませんでした……。

別の記事でも言及があったため、そのURLをインターネットアーカイブを探ると見つかりました。

開発メモ: トップNソートの検討

データベースに対して、ある順序でソートした時の最初の何件かが欲しいというクエリを投げることはよくあるだろう。SNSで言えば、誰かのコンテンツの最新10件を表示するとかいう場合だ。SQLだと　"ORDER BY timestamp DESC LIMIT 10" とかいう感じ。同じような操作は全文検索システムのスコアリングでも定番である。俺もよく自分で実装するわけだが、その度に適当な試行錯誤をして時間がもったいないので、今回は入念に調べて決定版を出そうじゃないか。

こちらの記事では、実際にC++でヒープソート、クイックソートを改造して実装しています。

なお、「レコメンドエンジンって、要するに検索エンジンの特殊なもの」ということは、以下の本の「Solrをレコメンドエンジンとして使う」という章でも書かれていました。検索エンジンの性能評価についても書かれていたのできちんとやればかなり勉強になりそうです。

[改訂第3版]Apache Solr入門――オープンソース全文検索エンジン (Software Design plus)

[改訂第3版]Apache Solr入門――オープンソース全文検索エンジン (Software Design plus)

本当は、業務でElastic Searchを使うような案件ができれば良いのですが、今のところそんな機会は無さそうです。仕方ないのでプライベートでAWS Lambdaを使ってクローラーを作り、まずは検索サービスを作るためのデータを集めようと画策しています。

【Python3.6】AWS Lambdaでツイッターを検索して自動リツイートする

AWS Lambda Python python-twitter

先程の記事に引き続き、AWS LambdaでPython3.6が使えるようになったので、過去にPython2.7で書いたバッチ処理のレガシーコードをLambdaに移行しています。

まずは、下の記事で書いた「ツイッターを検索した結果を自動リツイートする」コードを移行します。今見るとけっこうコード酷いですね。

kiito.hatenablog.com

Pythonのコードを書き直す

AWS Lambdaの流儀に従ってコードを書いていきます。

ここではlambda_function.pyにlambda_handlerという関数を用意して、実行するように設定することとします。

後述しますが、アクセストークン等は環境変数で渡しています。

import os
import time
from datetime import datetime
import twitter


TARGET_TERMS = ['ファンタジスタドール', '鵜野うずめ']
API_ENV_KEY = ['CONSUMER_KEY', 'CONSUMER_SECRET', 'ACCESS_TOKEN_KEY', 'ACCESS_TOKEN_SECRET']
COUNT = 100

def lambda_handler(event, context):
    client = TwitterClient()
    client.run(TARGET_TERMS)
    return True


class TwitterClient(object):
    def __init__(self):
        self.client = twitter.Api(*[os.environ[k] for k in API_ENV_KEY])
        self.nowtime = int(time.mktime(datetime.now().timetuple()))
        self.begin_time = self.nowtime - 60 * 60
    
    def run(self, terms):
        for term in terms:
            for tweet in self._search_tweet(term):
                if tweet.created_at_in_seconds in range(self.begin_time, self.nowtime):
                    self._post_retweet(tweet.id)

    def _search_tweet(self, term):
        return self.client.GetSearch(term=term, count=COUNT, result_type='recent')

    def _post_retweet(self, tweet_id):
        try:
            self.client.PostRetweet(tweet_id)
        except:
            print(f'{tweet_id}は既にリツイートされています')

ちなみにpython-twitterというライブラリを使っています。

github.com

zipで固めてアップロードする

先程の記事で用意したDockerイメージを使って、依存ライブラリも含めたzipファイルを用意しました。

kiito.hatenablog.com

requirements.txtには以下を記述しています。

python-twitter

環境変数でアクセストークン他を設定する

AWS Lambdaでは環境変数が設定できるので、アクセストークンなどはこちらから渡すことにします。

dev.classmethod.jp

こんな感じです。

f:id:takeshi0406:20170506170833p:plain

本来は「暗号化ヘルパーを有効にする」を選択すべきだと思うのですが、「どうせ自分以外見ないだろう」という甘い考えでやっていません。

本当はDockerで環境変数や依存ライブラリまで再現した開発環境を用意すればかっこよかったのですが、今回は小規模なコードなので特に用意しませんでした。

その他の設定

あとは以下の設定を行いました。特に難しいことはないと思います。

  • 「トリガー」で定期的に実行する
  • タイムアウト時間を3秒から3分まで長く設定しなおす（3秒ではさすがに打ち切られてしまう）

【Python3.6】AWS Lambdaを再現するDocker Imageのdocker-lambdaを使ってみた

docker AWS AWS Lambda

この間AWS LambdaでPython 3.6がサポートされたので、レンタルサーバーで動かしているTwitterの自動投稿やクローラーを移行しようと画策しています。

AWS LambdaがPython3.6に対応したので使ってみた ｜ Developers.IO

外部ライブラリ（twitterライブラリやBeautifulSoupなど）を利用使いたいので、zipで固めてデプロイする方法でいきたいのですが、いろいろ面倒そうなのでまずはその辺の煩雑な作業を自動化する手段でやってみました。

いろいろ調べていくうちに、以下の記事に紹介されている、「手元の環境で擬似的にLambdaを実行する」というDockerイメージが良さそうだったので使ってみます。

AWS Lambdaの開発環境を構築～docker-lambdaの紹介～ – クリエイティブ - ブログ - 株式会社テレビ朝日メディアプレックス

今回は Lambdaのデバッグ効率を上げるdocker-lambdaの設定手順を紹介します。

名前からイメージ出来る通り、Dockerで疑似的にLambdaを実行するという物になります。

github.com

ただし、Docker Imageが2GB弱ほどあるので、多少ハードディスクの容量は食ってしまうので、もしローカル環境で使うならば注意が必要かもしれません。

私はMac OS Xを利用しているので、公式サイトの"Docker for Mac"からダウンロードしました。

実は未だにちゃんとDockerを使ったことが無かったのですが、次のサイトを参考に簡単に勉強すれば、問題なく使うことができました。

www.atmarkit.co.jp

docker-lambdaを試しに実行する

lambda_function.pyという名前で現在のこのようなファイルを用意します。

def lambda_handler(event, context):   
    print("value1 = " + event['key1'])
    return event['key1']

公式のExampleにもある通り、引数にeventの値となるjsonを渡して実行します。

$ ls
lambda_function.py
$ docker run -v "$PWD":/var/task lambci/lambda:python3.6 lambda_function.lambda_handler '{"key1": "key2"}'
START RequestId: bcc19516-283b-485d-b728-69497756be19 Version: $LATEST
value1 = key2
END RequestId: bcc19516-283b-485d-b728-69497756be19
REPORT RequestId: bcc19516-283b-485d-b728-69497756be19 Duration: 32 ms Billed Duration: 132.0 ms Memory Size: 1536 MB Max Memory Used: 18 MB
"key2"

docker-lambdaでデプロイパッケージを作成する

次は、デプロイパッケージをdockerを使って作成します。

ローカルの環境（Mac OS X）でも同じことはできるのですが、特にPure Pythonでないライブラリを利用する際にエラーが出てしまうそうなので、できるだけ実際のAWSに近い環境でライブラリが用意できるので変なエラーに詰まることが少なくなることが期待されます。

docs.aws.amazon.com

Lambda 関数を作成するには、最初に Lambda 関数デプロイパッケージ (コードと依存関係で構成される .zip ファイル) を作成します。

以下の記事と、docker-lambdaリポジトリの「Create your own Docker image for finer control:」の項目を参考にして簡単にPython3.6をビルドできるdocker imageを作ります。

qiita.com

デプロイ用のDocker Imageを用意する

以下のようなDockerfileを用意します。

FROM lambci/lambda:build-python3.6

ENV AWS_DEFAULT_REGION us-east-1

ADD . .

CMD pip3 install -r requirements.txt -t /var/task && \
  zip -9 deploy_package.zip lambda_function.py && \
  zip -r9 deploy_package.zip *

mylambdaという名前でイメージを作ります。

docker build -t mylambda .

コードを用意する

作業ディレクトリで、lambda_function.pyとrequirements.txtを用意します（というか、この名前でファイルが存在していることを前提にDockerfileを書いています）。

$ ls
lambda_function.py requirements.txt

ひとまず、著名な外部ライブラリであるrequestsを使ったコードを書いてみます。

ひとまず、lambda_function.pyという名前で、こちらの記事で紹介されているグローバルIPを確認するAPIを呼び出しています。

import requests


def lambda_handler(event, context):
    res = requests.get('http://httpbin.org/ip')
    return res.json()

requirements.txtはこのような内容です。具体的なバージョンは特に指定していません。

requests

Dockerの環境内でzipで固める

次のコードを実行することで、Dockerfileの"RUN"の項目で指定されているシェルスクリプトが動き、deploy_package.zipが吐き出されます。

docker run -v "$PWD":/var/task mylambda

このdeploy_package.zipをアップロードすると、awscli等でアップロードすればLambda上で動かすことができます。

f:id:takeshi0406:20170506144610p:plain

まとめ

docker-lambdaを使ってAWS Lambdaの開発が便利になることを簡単に確認しました。

また、zipファイルとdevを同じディレクトリに保存しているので、何度も試行錯誤を行う際は微妙かもしれないので、適宜書き換えつつ利用しようと思います。

手軽に環境を捨てられるのもDockerの利点だと思うので。

【本】プログラマーは『ものづくりの数学のすすめ』を読んで、のんびり数学を勉強しよう

数学

『ものづくりの数学のすすめ 技術革新をリードする現代数学活用法』を読んでみたところ、とても面白かったのでおすすめしますという記事です。

そもそも私がこの本を読んだのは、

  • 著者の方のツイートを見かけて「面白い立場の方だな」と思ったこと
  • 最近私が関数型言語を勉強しており、集合論の言葉を学んだ後に、プログラミングの仕様を簡潔に理解することができるようになったこと

が主な理由です。

特に「ニュートンは議論は現代の物理学者でも難解だが、ライプニッツは運動という現象をシンプルに記述できる微分・積分記号を発明した。これによって後世の研究者が、明快に議論できるようになった。企業の研究者はライプニッツを目指そう」という提言が印象的でした。

さらに、「微分という記号や概念を使わずに、放物運動を記述するのはとても困難だ」とまで突っ込んで書かれていました。（私はプログラマーなので、ここでDDD（ドメイン駆動設計）を連想しました。）

また「数学者は論理だけで話を進めがちだが、グラフ化して問題のおおまかな傾向を知ることも大事。それぞれの軸が加算(+)される変数だった場合は線型軸を使うし、乗算(*)される変数だったときは対数軸を使うはずだ」というようなことが書かれていて、ハッとさせられました。今までなんとなく軸を使い分けていたのですが、代数学的な発想で考えると、「この変数にとって本質的な操作は何だ」というようなことまで掴めます。

『SOFT SKILLS』的な要素もあり、例えば他にも長いスパン・短いスパンの勉強の方法なども参考になりました。ITエンジニア向けの本だと、どうしても短いスパンの勉強が強調されてしまいがちなので。

素晴らしい本なのですが、人によって刺さる部分は違う気がします。本屋で見かけたときはちょっと立ち読みしてみてください。

ものづくりの数学のすすめ 技術革新をリードする現代数学活用法

ものづくりの数学のすすめ 技術革新をリードする現代数学活用法

余談ですが、最近は『集合・位相入門』を読んで集合論を勉強しています。今のところ「型や合成関数への感覚が深まって、コードがちょっときれいになった気がする」くらいの効果しか現れていませんが…。

また、このペースでいくと、線型代数まで学び直すのに2年くらいかかるんじゃないかと思ってます😩

集合・位相入門

集合・位相入門

以前も書いたとおり、こちらの記事に従って、少なくとも大学の学部生レベルまでは数学の能力を付けてみようと思います。

www.orecoli.com

また、『ものづくりの数学のすすめ 技術革新をリードする現代数学活用法』と同じ著者の前著も買ってみました。

線型代数学周遊―応用をめざして

線型代数学周遊―応用をめざして

まだ全然読めていませんが、第1章には「数学は言葉」であり、非数学な研究は「言葉にならないものを言葉にしてゆく科学の話」で、数学は「言葉になった後の科学の話」で、発想が全く異なるということが書かれていました。「ルールを守ってルール内のゲームを楽しむ」「定義を信じて進むうちにその定義の自然さを体感する」ということが書かれていました。

最近、ようやくそれが分かってきた気がします（が、数学を学んでも即座に役に立つ分野ではないので、目先で何を勉強すればいいのかということも同時に悩んでいます）。

【ニュース】「ブロックチェーン技術と不動産」について、有識者に質問してきてほしい

最近、「bitFlyerと積水ハウスがブロックチェーン技術を利用した不動産情報管理システムの構築を開始する」といったニュースが話題になっています。

jp.techcrunch.com

「ブロックチェーンを不動産に適用するとイケるんじゃないか」ということは以前から言われているようで、例えば以下のようなブログが見つかりました。

www.bankerfintech.com

冒頭の記事は、ブロックチェーン技術を用いれば、取引の透明性を高め、詐欺のリスクを減らし、売買に伴う煩雑なプロセスが簡素化され、取引のスピードがアップするというような内容が書かれています。

ちなみに、所有権の移転もブロックチェーン上に刻み込まれるようになるので、法務局も不要になるのかもしれません。

ついでに、こんなツイートも見つけました。「音楽ストリーミング」は確かに相性良さそうですね。

ところが、この話を上司としたところ、

「ノードを保有してるのって、企業なの？自治体なの？良からぬノードが過半数を超えてると改竄できちゃうはずだから、その辺がどう対応してるのか知りたい」

というコメントが返ってきました。しかし、私もブロックチェーン技術を「なんか分散してるもの」くらいしか理解していないため、答えられませんでした。

ブロックチェーン技術は、自社オリジナルのシステムに依存することなく、情報管理フォーマットが共通化し易いことが特性の一つであり、賃貸管理を行う不動産関連企業や自主管理の事業主が、当該プラットフォームへの相乗りが容易となる技術です。このたび構築を開始する業界初のブロックチェーン技術を 活用した不動産情報管理システムが、将来的には日本の不動産業界のネットワークを繋げる標準プラットフォームとなり、確立した不動産業界コンソーシアムとなるよう、住宅業界のリーディングカンパニーとして推進して参ります。

少なくとも、「他の会社が相乗りしやすい」ということまでしか書かれていません。

積水ハウスのIR情報も確認し、「ブロックチェーン技術を活用した不動産情報管理システムの構築を開始」という項目はあったのですが、その辺の定義がどうなっているのか分かりません。

ところで、こんなセミナーが無料で開催されるので気になる（特に上記の件を講師の方に質問してみたい）のですが、他に用事があって行けそうにありません。

peatix.com

もし興味ある知り合いがいたら、参加してどんな内容だったかを教えてほしいです。

【R】「20代のエンジニアの間で本当にPHPは廃れたのか？」を集計する

R dplyr ggplot2

前回の記事で、転職ドラフトのデータをスクレイピングし、簡単な分析を行いました。

kiito.hatenablog.com

ただし、こちらの記事の時点では、転職ドラフトは終わっておらず、中途半端なデータの状態のまま集計していました。 特に最終日に多くの指名が入っていたようで、そこで傾向が変わることは大いに考えられます。

今回は、

  • 年齢と最高提示額の関係を集計する
  • 20代のエンジニアの間でPHPは本当に廃れたのか？

の2点に絞って調べてみようと思います。

なお、前回行った「年齢と最高提示額の関係を集計する」については、そもそも問題設定（「入札額が高いエンジニアに特有なスキルがある」という仮説自体）が的外れである可能性が高いように思うので、今回は実施しませんでした。

年齢と最高提示額の関係を集計する

前回同様の積み上げ棒グラフでのプロットを行いました。

f:id:takeshi0406:20170427225206p:plain

前回の記事のグラフがこちらです。比較すると、「ノーマル級」が一気に減っていることが目立ちますね。

f:id:takeshi0406:20170427224650p:plain

前回同様、上位層だけに注目したグラフをプロットしてみます。前回はここまで集計すると20代後半が減っていましたが、今では30代前半と同様まで残っていることが分かります。

f:id:takeshi0406:20170427230237p:plain

f:id:takeshi0406:20170427225641p:plain

20代のエンジニアの間でPHPは本当に廃れたのか？

こちらの記事の中で、「25〜27歳ぐらいになっている若手エンジニアにPHPの経験がない人が増えている」という記述がありました。

devblog.thebase.in

リブセンスさんが運営されている転職ドラフトという転職サイトで、全員のプロフィールを読んでいて薄々気がついていたことに改めて気がつかされたのですが、BASEの方でサーバサイドに使っているメインの技術はCakePHPというフレームワークでありPHPの技術なのですが、

新卒の就職先がRubyを使っていて、今、25〜27歳ぐらいになっている若手エンジニアにPHPの経験がない人が増えている！

しかし、われわれエンジニアはデータを見ずに判断してはなりません。

まず、30代のエンジニアの人数を調べてみましょう。次のようなコードで集計すると、

  • 30代エンジニアは145人
  • 20代エンジニアは122人

であることが分かりました。

# 年代の人数を調べるコード
df %>%
  dplyr::filter(readr::parse_number(age_name) == 30) %>% # 「20」に変更する
  dplyr::distinct(user_id) %>% 
  nrow()

次に、各年代の利用人数(count)と普及率(rate)の上位10件を取得してみます。

df %>%
  dplyr::filter(readr::parse_number(age_name) == 30) %>%
  dplyr::group_by(skills) %>%
  dplyr::summarise(count = n()) %>%
  dplyr::arrange(desc(count)) %>% 
  dplyr::mutate(rate = count/145) %>% 
  head(10)

30代の結果がこちら

skills count rate
MySQL 77 0.5310345
Java 68 0.4689655
JavaScript 67 0.4620690
PHP 53 0.3655172
AWS 43 0.2965517
Jenkins 43 0.2965517
Ruby 41 0.2827586
jQuery 41 0.2827586
Apache 36 0.2482759
Git 32 0.2206897

20代の結果がこちらです。

skills count rate
MySQL 55 0.4508197
JavaScript 54 0.4426230
AWS 44 0.3606557
PHP 39 0.3196721
Ruby 38 0.3114754
Java 35 0.2868852
jQuery 34 0.2786885
docker 29 0.2377049
Git 29 0.2377049
Jenkins 26 0.2131148

きちんとした技術の名寄せなどを行っていないラフな集計であるものの、たしかに、PHPの普及率が約37% => 約32%に減っており、Rubyの普及率は約28% => 約31%まで増えています。ただし、これが大きな問題になるほど「PHPの経験がない人が増えている」かどうかは分かりません。

もしかすると、企業側から参加者のプロフィールを見て「きちんとした(PHP|Ruby)のプロジェクトに参加したことある」と判断されるもので絞り込むと、この差はもっと広がってしまうのかもしれません。

また、今回は「一気に利用率が(上がった|下がった)技術」も集計すると面白いかもしれませんね。一時期「Smalltalk年収高いけど高齢化もすごい！」と話題になった、以下のツイートのグラフと同じ似た集計を行っても面白いかもしれません。

まとめ

以下のことは言えたと思います。

  • 転職ドラフトの終盤で、20代後半でも高額の指名が入っていた
    • 20代も安心して転職ドラフトに利用しよう！
  • PHPの経験のない人は増えているが、「そこまで極端に減ってなくない？」とも感じた