読者です 読者をやめる 読者になる 読者になる

once upon a time,

Iris Tradをビール片手に聞くのが好きなエンジニアが、機械学習やRubyにまつわる話を書きます

Juliaでword countして気づいたこと #JuliaAC

advent calender Julia

この記事は、Julia Advent Calendar 24日目の記事です。 昨日は@nezuqさんのJuliaで楽しくWebスクレイピング!でした。

悲しいお知らせですが、このブログを通じてわかったのは、Python > Ingress >>> Juliaという人気度だということでした。Ingressの話は今回しません。

当初は、Cで書かれたライブラリをバインディングする方法について書こうと思っていたのですが、r9y9さんによるポインタ周りの解説が出ていたので、必要なくなったかなと思い、Juliaならではの型の話をしたいと思います。

このお話は、自分がjulia-usersで質問したことの回答をまとめたものです。

気軽にコミッターから斧が飛んでくるのがいいですね。さすが、Karpinskiさん*1

Ruby脳のWord count

僕は自然言語処理が好きなので、word countをちょくちょくやります。MapReduce時代以降Word countはHello worldの代わりに急成長していると言えましょう。 Rubyでword countをするなら、Hashを使ってこう書きます

hash = Hash.new{|h, k| h[k] = 0 }
words.each do |word|
  hash[word] += 1
end

もし、閾値以下の単語を除去したいならもう一回ループを回して、判定しますが、頻度top N個の単語を取り出したいときはどうしますか?

top10個の単語を取り出したいときはこう書きます。

hash.sort_by{|_,v| -v}.take(10)

簡単ですね。

Juliaの世界でのWord count

では、Juliaでも同様のことをやりたくなった場合どう書きますか? Dictをsortしたいですよね?

できないんです

julia> sort(
sort(r::UnitRange{T<:Real}) at range.jl:531             sort(v::AbstractArray{T,1}) at sort.jl:346
sort(r::Range{T}) at range.jl:534                       sort(A::AbstractArray{T,N},dim::Integer) at sort.jl:364

あれれ?調べていると、過去にはsort_byが出来た時期もあったようなのですが、今は出来ないようです。

そこで考えだしたのは、DataFrameを使えばいいんじゃない!って方法

dict = Dict{String, Int64}("apple" => 100, "town" => 250, "space" => 24)
df = DataFrame(word = collect(keys(dict)), count = collect(values(dict)))
sort(df, cols = [:count], rev = true)

でも、このDataFrameの作り方、convert(DataFrame, dict)で単純にできる形式と全然違うので不安ですよね。 なので、有識者に聞いてみました

julia-usersで聞いてみた回答

閾値処理をしたいなら、Dict()作って二回ループ回せばいいし、Top N個の単語を取ってきたいのなら、PriorityQueue()を使うのがいいよ、との回答でした。

後からsortするとo(NlogN)かかるじゃん。それだったら、最適なデータ構造を使えばいいんじゃないの、ということでした。確かに。

こんなコードになります。 書き方も処理速度もほとんど代わりませんね。Collection.dequeue!(pq)して、必要な回数だけ取り出しましょう。

julia> f = open("input.txt")
IOStream(<file input.txt>)

julia> text = readall(f);

julia> function count_word(text::UTF8String)
         mecab = Mecab("-O wakati")
         counts = Dict{UTF8String, Int}()
         for word in split(sparse_tostr(mecab, text))
             counts[word] = get(counts, word, 0) + 1
           end
         counts
       end
count_word (generic function with 1 method)

julia> @time count_word(text)
elapsed time: 0.953731616 seconds (29676144 bytes allocated, 24.68% gc time)
Dict{UTF8String,Int64} with 13583 entries:
  "ウィキ"    => 1
  "TAKE"      => 2
  "null"      => 4
  "変革"      => 5
  "クソ"      => 1
  "228"       => 3
  "迫っ"      => 1
  "村山"      => 1
  "寺嶋"      => 1
  "リビング"  => 1
  "国籍"      => 1
  "ベーコン"  => 1
  "出す"      => 13
  "Core"      => 5
  "当選"      => 2
  "moguno"    => 1
  "Brainfuck" => 1
  "積ん"      => 4
  "backup"    => 2
  "stress"    => 1
  "Qw"        => 1
  "細かい"    => 3
  "従って"    => 1
  "括弧"      => 1
  "ある程度"  => 1
  "法"        => 14
  ⋮           => ⋮

julia> function count_word2(text::UTF8String)
         mecab = Mecab("-O wakati")
         counts = Collections.PriorityQueue()
         for word in split(sparse_tostr(mecab, text))
             counts[word] = get(counts, word, 0) - 1
           end
         counts
       end
count_word2 (generic function with 1 method)

julia> @time count_word2(text)
elapsed time: 0.891081099 seconds (24265472 bytes allocated, 20.83% gc time)
PriorityQueue{Any,Any,ForwardOrdering} with 13583 entries:
  "ウィキ"    => -1
  "TAKE"      => -2
  "null"      => -4
  "変革"      => -5
  "クソ"      => -1
  "228"       => -3
  "迫っ"      => -1
  "村山"      => -1
  "寺嶋"      => -1
  "リビング"  => -1
  "国籍"      => -1
  "ベーコン"  => -1
  "出す"      => -13
  "Core"      => -5
  "当選"      => -2
  "moguno"    => -1
  "Brainfuck" => -1
  "積ん"      => -4
  "backup"    => -2
  "stress"    => -1
  "Qw"        => -1
  "細かい"    => -3
  "従って"    => -1
  "括弧"      => -1
  "ある程度"  => -1
  "法"        => -14
  ⋮           => ⋮

型と多重dispatchがある分、なんでも同じようにできるわけではないこと、そしてそれをやるのが本当に最適手なのかを考えることができました。 なお、julia-usersは気軽に質問できてどんどん斧が飛んできて楽しいので、みなさんも読むことをおすすめします!

明日はkimrinさんによるJuliaで楽器を作ろう!です。楽しみですね。

*1:本人のアイコン、バイキングの帽子をかぶっているのが有名ですよね