sortコマンドで複数のソート済みファイルを連結して１つのソート済みファイルを高速に作成する

2019-04-222022-01-28Bash

はじめに

巨大なソート済みファイルを連結して１つのソート済みファイルにしたかったが、巨大すぎて処理に時間がかかって困ってしまいました。

連結元のファイルはソート済みなので、うまいことマージすれば高速に処理できそうな気もします。

うまい方法が無いか調べてみました。

検証環境

$ uname -moi
x86_64 MacBookPro11,4 Darwin

$ bash -version
GNU bash, バージョン 5.0.3(1)-release (x86_64-apple-darwin18.2.0)

$ sort --version
sort (GNU coreutils) 8.31

検証準備

1〜1000000 までの数値が格納されている2つのファイル a.txt 、 b.txt を用意します。

これを連結し、全体としてソートされているファイルを作成したいと思います。

$ seq 1 1000000 > a.txt
$ seq 1 1000000 > b.txt

$ wc -l a.txt
1000000 a.txt
$ wc -l b.txt
1000000 b.txt

sortコマンドで普通にソート

sortコマンドに複数のファイル名を渡すことで、連結し全体としてソートすることができます。
timeコマンドと一緒に実行し実行速度や負荷を計測してみます。

3回計測します。

$ time sort -n a.txt b.txt > c
sort -n a.txt b.txt > c  1.31s user 0.25s system 269% cpu 0.579 total
$ time sort -n a.txt b.txt > c
sort -n a.txt b.txt > c  1.27s user 0.23s system 278% cpu 0.540 total
$ time sort -n a.txt b.txt > c
sort -n a.txt b.txt > c  1.26s user 0.22s system 287% cpu 0.512 total

CPUが複数格納されているPCですので、並列処理してくれたみたいですね。
頑張ってくれました。

sort -mコマンドでマージのみ行う

sortコマンドには-mオプションというものがあります。

ヘルプを引いてみます。

$ sort --help
Usage: sort [OPTION]... [FILE]...
  or:  sort [OPTION]... --files0-from=F
Write sorted concatenation of all FILE(s) to standard output.

With no FILE, or when FILE is -, read standard input.

...(省略)...

  -m, --merge               merge already sorted files; do not sort

...(省略)...

すでにソートされているファイル群をソートせずマージのみ行う、というオプションです。
ではこちらを使ってファイルを連結してみます。

ブレがあるかもしれませんので、3回試行してみます。

$ time sort -m -n a.txt b.txt > d
sort -m -n a.txt b.txt > d  0.23s user 0.03s system 90% cpu 0.288 total
$ time sort -m -n a.txt b.txt > d
sort -m -n a.txt b.txt > d  0.23s user 0.03s system 96% cpu 0.265 total
$ time sort -m -n a.txt b.txt > d
sort -m -n a.txt b.txt > d  0.23s user 0.03s system 96% cpu 0.268 total

処理時間は約1/2 、 CPU処理時間は約1/6 になりました。

両者が本当に同じ値になっているかを確認してみます。

# 両者の実行結果に差異がないことを確認
$ diff c d

どうやら問題がないようです。

ひとこと

連結対象のデータファイルがすでにソート済みの場合には、 -mオプションを使って効率化を図れますね。