Text による整列を効率化する

[s-yata]

概要

現在の実装では， Text の整列に文字列同士の比較にもとづくクイックソートを使っています． 文字列同士の比較では効率が悪いため，マルチキークイックソートか Radix sort に変更することを検討しています． いくつかデータを用意してから，それぞれを試して速いものを選択しようと思います．

[s-yata]

マルチキークイックソート

N/A が邪魔になるので，最初に N/A を後ろに移動する必要があります． それが終われば，バイト単位のマルチキークイックソートで対処できます． 整列対象が少なくなれば挿入ソートへと切り替えるのは現在の実装と同じです．

前方一致が長くなると不利になるものと予想されます．

[s-yata]

Radix sort

基本的な考え方はマルチキークイックソートと同じになると思います． N/A が邪魔になること，バイト単位で整列を進めること，仕上げは挿入ソートを使うこと，そして前方一致が長くなると不利になることです．

[s-yata]

データの種類

Text では入力できるデータが何でもありになるので，ベンチマークに使用するデータの生成方法が重要になります． たとえば，擬似乱数を使って単純に生成すると， Radix sort が有利になるはずです．

そういうわけで，現在は以下のようなデータを考えています．

• 一様な擬似乱数
  • 擬似乱数を使って数字列やアルファベット列を生成します．
• 偏りのある擬似乱数
  • 文字の出現頻度に偏りを持たせます．
• Word をつなげたもの
  • 擬似乱数を使って Word を生成します．
  • いくつかの Word をつなげて Text にします．

URL などは用意できるので，そういうのも試しておこうと思います．