はじめに
先日Qiitaに投稿された金は愛よりも重いという記事、単純なコードで世の真実を暴き出す興味深いものでした。
私も触発されて「希望」と「絶望」はどちらが大きいのか比較したりしてたのですが、ある時ふと自分の名字と私のチームのメンバーの名字を比較してみました。
こんな感じで。
"#{私の名字}" > "#{相手の名字}"
結果はなんと全てfalse。
つまり私の名字はチームで最弱だったわけです。
まあ、私が最弱なのは別にどうでもいいのですが、逆に最強の名字はなんなのかが気になったので、最近気になってるエリちゃん(Elixirのこと)の勉強も兼ねてそれを調べてみました。
完成品
ソースはgithubに上げてます。
大会規定
- 名字の一覧は実在名字（名字）の五十音順通覧から取得する
- 勝敗は文字列の比較して大きい方を勝者とする
- ただし、そのまま比較するとやる前からだいたい勝敗がわかるので、あえてSHA256で取得したハッシュ値を用いる
- 名字の一覧を2.に基づいてソートし、先頭に来たものを優勝者とする
実装の解説
1. 名字の一覧の取得 まずは一つのページから
まずは実在名字（名字）の五十音順通覧に載ってる名字を片っ端から取得します。
サンプルなどを見つつ、Webサイトをスクレイピングして名字を抽出するモジュールを作成します。
defmodule ScrapeWebPage do
@moduledoc """
http://myoujijiten.web.fc2.com/50ontuuran.htmlから名字一覧を取得する
"""
@doc """
urlからHTMLを取得
名字のリストに変換して返す
## param
- url: 取得先URL
"""
def getHTML(url) do
IO.puts "Search to #{url}"
case HTTPoison.get(url) do
{:ok, %HTTPoison.Response{status_code: 200, body: body}} ->
IO.puts "Get from #{url}"
findFamilyNameList(body)
{:ok, %HTTPoison.Response{status_code: 404}} ->
IO.puts "Not found :("
list = []
list
{:error, %HTTPoison.Error{reason: reason}} ->
IO.inspect reason
list = []
list
end
end
@doc """
HTMLから名字のリストを作成
## param
- body: HTTPoisonで取得したHTML
"""
defp findFamilyNameList(body) do
Floki.find(body, "table[width=1000] tbody tr")
|> Enum.map(&(findName(&1)))
|> Enum.filter(&(String.length(&1) > 0))
|> Enum.map(fn name ->
[name: name, hash: cryptoString(name)]
end)
end
@doc """
tr要素から目当てのテキストを力技で掘り出す
## param
- tr: tr要素
"""
defp findName(tr) do
elem(tr, 2)
|> Enum.at(1)
|> elem(2)
|> Enum.at(0)
|> addToList
end
@doc """
各名字をリストに追加
ただし、文字列でないと判定されれば空文字列にする
空文字列は後の工程でフィルタリングされる
## param
- text: tr要素から抽出したテキスト(名字)
"""
defp addToList(text) do
case is_binary(text) do
true -> text
_ -> ""
end
end
@doc """
文字列をSHA256でハッシュ化する
## param
- string: 入力文字列
"""
defp cryptoString(string) do
:crypto.hash(:sha256, string)
|> Base.encode16(case: :lower)
end
end
実際にWebサイトを見に行ってもらうとわかるのですが、すごく古き良きインターネッツなページであまり要素にクラスとかつけてないのでスクレイピングは力技です。
それではひとまず「あ~」のページで試して見ましょう。
まだまだ序の口ですが、すでに2000件以上のエントリーです。
2. 全てのページから名字を取ってくる
まだ「あ」で始まる名字の半分ほどを取っただけですので、この調子でどんどん取っていきましょう。
まずは取得先となる全てのURLを列挙します。
本当はこれもトップページからスクレイピングすべきかもしれませんが、力技スクレイピングがあまりにも辛かったので...
defmodule UrlList do
@moduledoc false
@doc """
取得先URLの一覧
"""
def get do
[
"http://myoujijiten.web.fc2.com/a1.html",
"http://myoujijiten.web.fc2.com/a2.html",
# (中略) 実際は50件ほど
"http://myoujijiten.web.fc2.com/yuyo.html",
"http://myoujijiten.web.fc2.com/rawagyou.html"
]
end
end
めちゃくちゃ長いので、これはこれでモジュールにしてます。
ではメインになるモジュールから呼び出して見ましょう。
defmodule FamilyNameChampionship do
@moduledoc """
Decide the STRONGEST family name in Japan.
"""
def main() do
IO.puts "Start"
urls = UrlList.get() # URLの一覧取得
# 取得したURLごとにスクレイピング
list = Enum.map(urls, &(ScrapeWebPage.getHTML(&1)))
|> Enum.reduce(fn(x, acc) -> Enum.concat(x, acc) end)
IO.puts "Get All Lists"
IO.puts "#{length(list)} Names Entry"
champion = Enum.sort(list, fn (x, y) -> x[:hash] > y[:hash] end)
|> Enum.at(0)
IO.inspect champion
end
end
という感じのソースを書きそうになりましたが、これではエリちゃん(Elixirのことだってば!)の力を全く発揮できません。
実行してみればわかりますが、かなり時間がかかります。
1件ずつ順番にアクセスして行ってるからです。
エリちゃんは並列処理で力を発揮するので、スクレイピングのあたりを並列化して処理を速めましょう。
3. 名字取得を並列化する
それでは処理を並列化していきましょう。
Elixirで並列処理を行う際はTaskモジュールを使います。
全ての処理が終わるのを待って結果を受け取るので、Task.async/1とTask.await/2を使うようにメインモジュールを編集します。
urls = UrlList.get()
tasks = Enum.map(urls, fn url ->
Task.async(fn ->
ScrapeWebPage.getHTML(url)
end)
end)
list = Enum.map(tasks, &Task.await(&1, 10000))
|> Enum.reduce(fn(x, acc) -> Enum.concat(x, acc) end)
これで勝つる!
地獄への道は善意で舗装されている
と思ってたらここで問題発生。
テストのためにURL5件とかでやってたうちは大丈夫だったのですが、10件超えたあたりで突然エラーが発生するようになりました。
そこには
503 Service Temporarily Unavailable
の文字が!
確認してみたところ、特定のURLを踏んだら発動するわけでなく、単純に並列で投げるリクエストの数が一定以上になると発動する503のエラーなので、短時間でリクエスト投げすぎてサーバの処理能力を超えたと考えるのが妥当かと思います。
冷静に考えると、同一のIPアドレスから一つのサーバに対して1秒以内に何十件もHTTPリクエストが飛ばすとか
完全にDDos攻撃です。絶対に真似しないでください。
私がサーバ管理者ならそっとファイアウォールのブラックリストに追記すると思います。
皆さんもうっかりやってしまわないように気をつけましょう。
ちなみに一般的な語意とは違って、法的には「善意」というのは「そんなつもりじゃなかった」って感じの意味です。例えば偽ブランド品を偽物だと知らずに本物として販売した場合、販売者は法的には善意です。
本当に反省してます...
分割して統治せよ
まとめて並列処理するとDDos攻撃になってしまいますが、かと言って1つずつアクセスしていくのはあまりにもだるい。
そこで折衷案としてURLを5件ずつのグループに分けて処理していくことにします。ちょうどいいことにエリちゃんにはEnum.chunkという関数があるので、こいつを使ってURLのリストを5件ずつに分けます。
こうすればいい感じにインターバルを挟むのでDDos攻撃してしまうことは避けられます。
ただし、一度リストをネストさせてから、また戻すので若干処理がややこしくなります。
defmodule FamilyNameChampionship do
@moduledoc """
Decide the STRONGEST family name in Japan.
"""
def main() do
IO.puts "Start"
urlGroups = UrlList.get()
|> Enum.chunk(5, 5, []) # 5件ずつグループ化 Enum.chunk/2だと余った要素が無視されるのでEnum.chunk/4を使う
list = Enum.map(urlGroups, &(getByUrlGroup(&1)))
|> Enum.reduce(fn(x, acc) -> Enum.concat(x, acc) end)
IO.puts "Get All Lists"
IO.puts "#{length(list)} Names Entry"
champion = Enum.sort(list, fn (x, y) -> x[:hash] > y[:hash] end)
|> Enum.at(0)
IO.inspect champion
end
@doc """
url5件ごとに並列で取得する
"""
defp getByUrlGroup(urlGroup) do
Enum.map(urlGroup, fn url ->
Task.async(fn ->
ScrapeWebPage.getHTML(url)
end)
end)
|> Enum.map(&Task.await(&1, 10000)) # この時点で待ち受ける
|> Enum.reduce(fn(x, acc) -> x ++ acc end) # ネストされたリストを戻す
end
end
今度こそ勝つる!
補足 Enum.flattenを使わない理由
多分上記のコードを見て、「ネストされたリストをフラットにしたいならEnum.flatten使えばいいじゃん。バカなの?死ぬの?」と思った方もいるかと思うので補足しておきます。
キモになるのはScrapeWebPage.findFamilyNameListの返り値です。
defp findFamilyNameList(body) do
Floki.find(body, "table[width=1000] tbody tr")
|> Enum.map(&(findName(&1)))
|> Enum.filter(&(String.length(&1) > 0))
|> Enum.map(fn name ->
[name: name, hash: cryptoString(name)]
end)
end
はい、キーワードリストにしちゃったんですよねぇ...
欲しいのはキーワードリストのリストなわけなんです。
なのでEnum.flattenしちゃうと
[name: "hoge", hash: "aaaaaaaaaa", name: "fuga", hash: "bbbbbbbbbbb"]
みたいなカオスなリストになっちゃいます。
なので、Enum.reduceで要素を連結していくという方式を取ってます。
最強の名字は誰か?
それでは実行してみましょう
ちゃんと5件ずつ順番に取得してます。
全名字を取得しました。
なんとその数124,307名。
これは大規模な大会ですねぇ...
さて、結果は...!?
「茶園」...?
あまり馴染みのない名字だったので名字由来net軽く調べてみると
近年、鹿児島県に多く、特に枕崎市に多数みられる。
とのこと。
近年多いってどういうことだ...?
何はともあれ、最強の名字決定戦 SHA256級のチャンピオンは茶園さんに決定しました。
おめでとうございます。
アルゴリズムを変えると当然違う結果になると思いますが、わざわざ記事にするほどのものにはならないと思いますので、あとはひっそりと個人的に楽しみます。