LC_ALL=Cでsortを高速に

bashのsortがLC_ALL=Cにすると速くなるという記事を見つけました（割と有名なようで）。

ちょっとbashで試してみます。一応sortのversionも晒しておきます。

$ sort --version
sort (GNU coreutils) 5.93
Copyright (C) 2005 Free Software Foundation, Inc.
This is free software.  You may redistribute copies of it under the terms of
the GNU General Public License <http://www.gnu.org/licenses/gpl.html>.
There is NO WARRANTY, to the extent permitted by law.

Written by Mike Haertel and Paul Eggert.

それでは、10桁の英数字列を100万個生成し、それをソートして比較します。

$ cat /dev/urandom | LC_ALL=C tr -dc '[:alnum:]' | fold -w 10 | head -n 1000000 > words.txt
$ time LC_ALL=C sort words.txt > /dev/null

real    0m0.751s
user    0m0.712s
sys     0m0.039s
$ time LC_ALL=ja_JP.UTF-8 sort words.txt > /dev/null

real    0m16.918s
user    0m16.820s
sys     0m0.076s
$ time LC_ALL=en_US.UTF-8 sort words.txt > /dev/null

real    0m17.057s
user    0m16.915s
sys     0m0.093s

なぜLC_ALL=Cにすると速くなるかというと、バイト列でソートしてくれるからだそうです。でもそのせいで並び順も変わってしまう点には注意が必要です。

Rで試した

Rのsort関数も同じような挙動をするのでしょうか。気になります。

dat <- read.table("words.txt")[[1]]
bench <- function(lc_all) {
  Sys.setlocale(locale = lc_all)
  time <- proc.time()
  assign(lc_all, sort(dat), pos = globalenv())
  proc.time() - time
}

bench("C")
##    user  system elapsed 
##   5.850   0.042   7.430 
bench("ja_JP.UTF-8")
##    user  system elapsed 
##  19.240   0.085  20.647 
bench("en_US.UTF-8")
##    user  system elapsed 
##  19.081   0.076  20.366

しっかり差がついています。

all(get("C") == get("ja_JP.UTF-8"))
## [1] FALSE
all(get("C") == get("en_US.UTF-8"))
## [1] FALSE
all(get("ja_JP.UTF-8") == get("en_US.UTF-8"))
## [1] TRUE

ただutf-8かどうかで並び順は変わってしまうようですね。

ちなみにこちらはdplyrのarrange関数を使って比較した場合です。

bench2 <- function(lc_all) {
  Sys.setlocale(locale = lc_all)
  time <- proc.time()
  assign(lc_all, arrange(as.data.frame(dat), dat)[[1]], pos = globalenv())
  proc.time() - time
}

bench2("C")
##    user  system elapsed 
##   2.406   0.013   2.722
bench2("ja_JP.UTF-8")
##    user  system elapsed 
##   2.877   0.020   3.294 
bench2("en_US.UTF-8")
##    user  system elapsed 
##   2.325   0.012   2.602

as.data.frameをはさんでもこの速さ。さすがの羽鳥氏です。

all(get("C") == get("ja_JP.UTF-8"))
## [1] TRUE
all(get("C") == get("en_US.UTF-8"))
## [1] TRUE
all(get("ja_JP.UTF-8") == get("en_US.UTF-8"))
## [1] TRUE

速度がほとんど変わらないように、結果も変わらない。安心です。

J's blog

趣味で統計•データ解析をしています

LC_ALL=Cでsortを高速に

Rで試した