テキストファイルを行単位でランダム順に並べ替える

概要

コマンド sort にオプション -R（--random-sort）を渡してやると，各行のハッシュ値をキーとする整列になります．でも，ハッシュ値の計算に時間がかかる上に，同じ行は必ず連続して配置されるという癖があるため，使い方には注意が必要です．

そこで，これらの欠点を補う方法が欲しくなります．そして，コマンド sort の機能（入力が大きいときは自動で外部整列になることなど）を有効利用できる方法に，各行の先頭にランダムデータを挿入してから sort により整列し，その後でランダムデータを削除するという方法があります．

例えば，ランダムデータを挿入するコマンドが ./insert-random-numbers，ランダムデータを削除するコマンドが ./delete-random-numbers のとき，以下のようにします．

$ ./insert-random-numbers < test-data | sort -n | ./delete-random-numbers

実験結果

100 万行のテキストファイルを入力として並べ替えにかかる時間を調べました．ランダムデータを挿入する方が，ずっと速く整列できています．

$ wc test-data
 1000000   963143 24454977 test-data

$ LC_ALL=C time -f 'real %E, user %U, sys %S' sort -R < test-data > /dev/null
real 0:19.52, user 19.31, sys 0.06

$ ./insert-random-numbers < test-data | \
  time -f 'real %E, user %U, sys %S' sort -n | \
  ./delete-random-numbers > /dev/null
real 0:03.68, user 2.79, sys 0.23

実験に使ったソースコードはこちら（http://sites.google.com/site/headdythehero/cabine/2010/0725/random-shuffle.tar.gz?attredirects=0&d=1）にあります．

追記（2010-08-03）：n-yo さんから time の場所について指摘があったので修正しました．

ランダムデータの挿入

#include <cstdio>
#include <cstdlib>
#include <ctime>

// 整数 Value の表現に必要なビット数を求めるための構造体です．
template <int Value> struct NumBits { enum { VALUE = NumBits<Value / 2>::VALUE + 1 }; };
template <> struct NumBits<0> { enum { VALUE = 0 }; };

// (2 ** NUM_BITS) より小さい疑似乱数を生成します．
unsigned long long generateRandomNumber()
{
  enum { NUM_BITS = 40 };
  unsigned long long random_number = 0;
  // ランダムデータの長さが NUM_BITS に達するまで std::rand() を呼び出します．
  for (int num_bits = 0; num_bits < NUM_BITS; num_bits += NumBits<RAND_MAX>::VALUE)
    random_number += static_cast<unsigned long long>(std::rand()) << num_bits;
  return random_number & (~0ULL >> (64 - NUM_BITS));
}

int main()
{
  std::srand(static_cast<unsigned>(std::time(NULL)));
  // 65,535 バイトより長い行があると困ったことになります．
  char buf[65536];
  while (std::fgets(buf, sizeof(buf), stdin) != NULL)
    std::printf("%llu %s", generateRandomNumber(), buf);
  return 0;
}

ランダムデータの削除

#include <cstdio>
#include <cstring>

int main()
{
  char buf[65536];
  // エラー処理は省略しています．
  while (std::fgets(buf, sizeof(buf), stdin) != NULL)
    std::printf("%s", std::strchr(buf, ' ') + 1);
  return 0;
}