julia の DataFrames.jl で重複のある文字列の列は、文字列毎に整数を与えると検索が高速化できる
julia の DataFrames.jl で重複のある文字列の列は、文字列毎に整数を与えると選択が高速化できるという話しです。
まとめて言ってしまうと下記の速度比較のように、文字列と文字列を比べるよりも、整数と整数を比べる方が早いという話しです。
julia> using BenchmarkTools
julia> @benchmark 1234567890 == 123456790
BenchmarkTools.Trial:
memory estimate: 0 bytes
allocs estimate: 0
--------------
minimum time: 0.027 ns (0.00% GC)
median time: 0.033 ns (0.00% GC)
mean time: 0.032 ns (0.00% GC)
maximum time: 0.035 ns (0.00% GC)
--------------
samples: 10000
evals/sample: 1000
julia> @benchmark "a" == "a"
BenchmarkTools.Trial:
memory estimate: 0 bytes
allocs estimate: 0
--------------
minimum time: 3.963 ns (0.00% GC)
median time: 3.965 ns (0.00% GC)
mean time: 4.106 ns (0.00% GC)
maximum time: 16.982 ns (0.00% GC)
--------------
samples: 10000
evals/sample: 1000
上記の速度差については、10^4 行程度の DataFrame だと気にしていませんでした。 しかし、データが大きくなってくると高速化が必要性を感じるようになってきたので、具体的に調べてみることにしました。 自然言語解析でも token 化として単語に数字を当ててから解析が始まるようなので、ぼんやりとは感じていました。 実際に測定してみると上記の差ほどではありませんが、重要な問題のようです。
さて、サンプルの DataFrame 作製から行いたい処理の説明をします。
サンプルは、1列目が名前 (string)、2列目が整数 (Int64)、3列目が小数 (Float64) の DataFrame を組みます。 1列目の名前には重複があり、名前毎に2列目や3列目の集計をしたいというような処理を考えます。 任意の名前が含まれる行がどこかを、調べるということが必要になります。 任意の名前が行に含まれるかを調べる時に、(1) 名前、つまり string で調べていくか、 (2) 名前毎に重複のない整数 Int64 を Dict で当てて、整数どおしでの比較をしていくかの2つの方法でどのくらいの差があるかを調べてみます。今回は1列目しか使いませんでしたが、恐らく、具体例がある方が判りやすいと考えます。
まず、サンプルの DataFrame を乱数で作製していきます。A1 に乱数の文字列を10^4通り格納して、乱数で 5 × 10^5 個を取り出し A2 に格納しています。これでほどほどに重複のある1列目が作れます。2列目と3列目は単純に乱数を並べます。
julia> using Random, StatsBase, DataFrames, BenchmarkTools
julia> A1 = [randstring(12) for i in 1:10^4];
julia> A2 = rand(A1, 5*10^5);
julia> A3 = rand([1:100;], 5*10^5);
julia> A4 = rand( 5*10^5);
julia> df1 = DataFrame(name= A2, valueInt = A3, valueFloat = A4)
500000×3 DataFrame
│ Row │ name │ valueInt │ valueFloat │
│ │ String │ Int64 │ Float64 │
├────────┼──────────────┼──────────┼────────────┤
│ 1 │ f9O1ekfJ8lSy │ 68 │ 0.559995 │
│ 2 │ fwxl1ucdTtF9 │ 13 │ 0.919493 │
│ 3 │ DGFdpi1pwBFk │ 61 │ 0.86851 │
│ 4 │ sIQxfS3idIwW │ 82 │ 0.916269 │
│ 5 │ 2aVfbh5Q7Ssp │ 91 │ 0.159836 │
│ 6 │ O9ZsYFjQlkSQ │ 28 │ 0.23163 │
│ 7 │ 5xzRpz98NrNj │ 7 │ 0.639465 │
│ 8 │ dMVJDa3K7hm8 │ 6 │ 0.0226518 │
--- 以下略 --
まず、1列目の df1.name の重複具合を調べてみましょう。
julia> countMap = countmap(df1.name);
julia> describe(collect(values(countMap)))
Summary Stats:
Length: 10000
Missing Count: 0
Mean: 50.000000
Minimum: 24.000000
1st Quartile: 45.000000
Median: 50.000000
3rd Quartile: 55.000000
Maximum: 80.000000
Type: Int64
平均で50回、最小24回から、最大80回の重複があるデータが出来ました。
重複の無い df1.name の文字列は unique() で得ることが出きます。
julia> arrayUniqueName = unique(df1.name)
10000-element Array{String,1}:
"f9O1ekfJ8lSy"
"fwxl1ucdTtF9"
"DGFdpi1pwBFk"
"sIQxfS3idIwW"
"2aVfbh5Q7Ssp"
"O9ZsYFjQlkSQ" ...以下略
文字列のまま、unique にした文字列が df1 のどの行で出てくるかを調べて、array で組んで取り出す関数を作ります。 `unique(df1.name)`の順番に string のまま、df1 を調べて行きます。 この処理は意外と時間がかかります。
julia> function selectRowNumByName(arrayString::Array{String,1})
arrayStringUnique = unique(arrayString)
arrayNum = map(x -> findall(arrayString.== x ), arrayStringUnique)
return hcat(arrayStringUnique, arrayNum)
end
selectRowNumByName (generic function with 1 methods)
julia> @time selectRowNumByName(df1.name[1:10^4]);
0.410448 seconds (25.41 k allocations: 35.484 MiB)
上記では10^4行しか調べていませんが、10^6個くらいの行数だととかなり辛く感じます。 ちなみに、MacBook Pro (Retina, 13-inch, Early 2015) で調べています。 5年程違うと 10倍くらい早いコンピューターが手に入るのかもしれませんが、100倍の速度は手に入らないでしょう。
次に、`unique(df1.name)`にひとつずつ、整数を1対1で対応させていく Dict を組んむ関数を定義してから df1.name を調べる関数を作ります。
julia> function tokenDictizer(arrayString::Array)
arrayStringUnique = unique(arrayString);
tokenDict = Dict(arrayStringUnique .=> [1:length(arrayStringUnique);])
return tokenDict
end
tokenDictizer (generic function with 1 methods)
julia> function selectRowNumByToken(arrayString::Array)
arrayStringUnique = unique(arrayString);
dictToken = tokenDictizer(arrayStringUnique)
arrayTokenized = map(x -> dictToken[x] , arrayString)
rowNums = map(x -> findall(arrayTokenized .== dictToken[x]), arrayStringUnique)
return hcat(arrayStringUnique, rowNums)
end
selectRowNumByToken (generic function with 1 methods)
julia> @time selectRowNumByToken(df1.name[1:10^4]); # 準備体操
0.235432 seconds (320.77 k allocations: 50.845 MiB)
julia> @time selectRowNumByToken(df1.name[1:10^4]);
0.039964 seconds (25.48 k allocations: 36.377 MiB)
10倍ほど早い結果が出ました。
せっかくですので、BenchmarkTools を使って調べてみましょう。
julia> @benchmark selectRowNumByName(df1.name[1:10^4])
BenchmarkTools.Trial:
memory estimate: 35.20 MiB
allocs estimate: 25202
--------------
minimum time: 352.008 ms (0.00% GC)
median time: 359.839 ms (0.00% GC)
mean time: 364.644 ms (0.80% GC)
maximum time: 401.222 ms (10.16% GC)
--------------
samples: 14
evals/sample: 1
julia> @benchmark selectRowNumByToken(df1.name[1:10^4])
BenchmarkTools.Trial:
memory estimate: 36.09 MiB
allocs estimate: 25267
--------------
minimum time: 38.345 ms (0.00% GC)
median time: 39.327 ms (0.00% GC)
mean time: 45.629 ms (13.13% GC)
maximum time: 107.267 ms (51.82% GC)
--------------
samples: 111
evals/sample: 1
文字列のデータ数 (length) が、10^6を越えて来たり、頻回に計算する際には、整数などに1回置き換える処理が良いように考えます。
オマケで、DataFrames.jl の groupby と combine を使ってみます。尚、10^4個で準備体操をした後の速度測定です。
julia> @time gdf = DataFrames.groupby(df1[1:10^5,:], :name)
0.006376 seconds (52 allocations: 4.818 MiB) # 以下略
julia> @time combine(gdf, :valueInt => mean)
0.001045 seconds (172 allocations: 324.516 KiB)
10000×2 DataFrame
│ Row │ name │ valueInt_mean │
│ │ String │ Float64 │
├───────┼──────────────┼───────────────┤
│ 1 │ f9O1ekfJ8lSy │ 39.7 │
│ 2 │ fwxl1ucdTtF9 │ 45.7 │
│ 3 │ DGFdpi1pwBFk │ 46.0714 │
│ 4 │ sIQxfS3idIwW │ 52.1538 │
│ 5 │ 2aVfbh5Q7Ssp │ 48.7778 │
...以下略
さすがに、DataFrames.jl の groupby と combine は、上手に使ったら早そうですね。
