- アルファベットの順序を並び替えた新しい辞書順でN個の文字列をソートする問題を、Common Lispで解いた。
- 効率的な解法は各文字を5ビットに詰めて1個の整数に圧縮し、整数比較でソートする「シュワルツ変換」を使うことで49msに短縮できる。
- 整数への圧縮は「文字数の上限が10、順位が26以内、左から上位ビットへ配置」という制約が揃って初めて辞書順と整数の大小が一致する。
1. 変則的な辞書順ソートの問題
AtCoderの問題「Neo-lexicographic Ordering」を題材に、Common Lispで2種類の解法を比較します。
26文字のアルファベットを並び替えた文字列 X が与えられます。
E – Neo-lexicographic Ordering
X の i 番目の文字が、新しい順序における i 番目に小さい文字です。
N 個の文字列をこの新しい辞書順でソートして出力します1。
たとえば X が bacdefg... なら、b が最も小さく、次が a、次が c という順になります。
1.1. 素直な解法：文字を変換してソートする（87ms）
アルファベット順が変わっているだけなので、各文字を「新しい順序での番号」に変換してしまえば、あとは普通の辞書順ソートです。
変換テーブルはエンコードとデコードの2方向を用意しました2。
エンコードは元の文字を新順序の文字に変換し、デコードはその逆です。
(defun encode (s rule-table)
(map 'string #'(lambda (ch)
(gethash ch rule-table))
s))
(defun make-rule-tables (str)
(loop for ch across str
for normal-code from (char-code #\a)
with encoder = (make-hash-table)
with decoder = (make-hash-table)
do (setf (gethash ch encoder) (code-char normal-code))
(setf (gethash (code-char normal-code) decoder) ch)
finally (return (list :encoder encoder :decoder decoder))))
(defun main ()
(let* ((X (read-line))
(N (read))
(Sn (loop repeat N collect (read-line)))
(rules (make-rule-tables X))
(enc (getf rules :encoder))
(dec (getf rules :decoder))
(encoded-Sn (loop for s in Sn
collect (encode s enc)))
(sorted (sort encoded-Sn #'string<=)))
(loop for s in sorted
do (princ (encode s dec))
(princ #\Newline))))
#-swank (main)Code language: Lisp (lisp)make-rule-tables は X を走査して、各文字に a から順の文字を割り当てます。bzz の b が新順序で1番目なら a に変換され、ソート後に元へ戻されます。
2. シュワルツ変換：文字列を整数に詰め込む（49ms）
より計算効率のよい解法を見ていたら、文字列長の上限が10であることを利用して1個の整数に圧縮してしまうアイデアがありました。
(defun make-order-table (x)
(declare (type string x))
(let ((table (make-array 26 :element-type '(unsigned-byte 8))))
(loop for ch across x
for k from 1
do (setf (aref table (- (char-code ch)
(char-code #\a))) k))
table))
(defun encode-string (s order-table)
(declare (type string s)
(type (simple-array (unsigned-byte 8) (26)) order-table))
(loop for ch across s
for j from 1
sum (ash (aref order-table (- (char-code ch)
(char-code #\a)))
(- 50 (* 5 j)))))Code language: Lisp (lisp)各文字を新順序での番号（1〜26）に変換し、その値を5ビットずつシフトして1個の int64 に埋め込みます3。
「エンコードした値でソートし、元の値はペアで保持する」このパターンを「シュワルツ変換」といい、カスタム比較が必要なソート全般で使えます4。
文字列長の上限が10なので、5ビット×10文字＝50ビットに収まります。
文字列 "bzz"
b=1, z=26, z=26
(1 << 45) | (26 << 40) | (26 << 35) で1個のint64になりますCode language: JavaScript (javascript)すると、ソートは整数の < 比較だけになります。
文字列の辞書順比較は最悪 O(文字列長) かかりますが、整数比較は O(1) です5。
N=50000 のケースでは差が出てきます。
復元はビット列から5ビットずつ取り出して X の添字とすれば元の文字に戻りますが、今回は元の文字列をペアとして保存しておくことでデコード処理自体が不要になります。
(defun main ()
(let* ((x (read-line))
(n (parse-integer (read-line)))
(order (make-order-table x))
(pairs (loop repeat n
for s = (read-line)
collect (cons (encode-string s order) s)))
(sorted (sort pairs #'< :key #'car)))
(loop for (_ . s) in sorted
do (write-line s))))
#-swank (main)Code language: Lisp (lisp)pairs は (整数 . 元の文字列) のコンスセルです6。
ソート後は cdr から元の文字列を取り出すだけなので、デコード処理が丸ごと消えています。
最終的なコードは
(defun make-order-table (x)
(declare (type string x))
(let ((table (make-array 26 :element-type '(unsigned-byte 8))))
(loop for ch across x
for k from 1
do (setf (aref table (- (char-code ch)
(char-code #\a))) k))
table))
(defun encode-string (s order-table)
(declare (type string s)
(type (simple-array (unsigned-byte 8) (26)) order-table))
(loop for ch across s
for j from 1
sum (ash (aref order-table
(- (char-code ch) (char-code #\a)))
(- 50 (* 5 j)))))
(defun main ()
(let* ((x (read-line))
(n (parse-integer (read-line)))
(order (make-order-table x))
(pairs (loop repeat n
for s = (read-line)
collect (cons (encode-string s order) s)))
(sorted (sort pairs #'< :key #'car)))
(loop for (_ . s) in sorted
do (write-line s))))
#-swank (main)
Code language: Lisp (lisp)
2.1. 2つの解法の違い
素直な解法はハッシュテーブルで変換して文字列をソートします。
効率的な解法は配列で変換して整数をソートします。
ハッシュテーブルと配列の差は、ルックアップのたびにハッシュ計算が走るかどうかです。(char-code ch) - (char-code #\a) で直接インデックスが出る配列アクセスは定数倍速くなります。
比較対象の差はより大きくなります。
文字列比較は文字が一致しなくなるまで走査しますが、整数比較は1回で終わります。
3. 整数への詰め込みが成立する条件
詰め込んだ整数の大小が元の辞書順と一致する場合にのみ、このアイデアは正しく動きます。
今回は左から順に上位ビットへ配置していて、1文字目の差が2文字目以降のどんな差よりも大きくなるよう設計されています。
5ビットで表せる最大値は31で、26文字の順位（1〜26）は収まります。
文字列長の上限が10なので50ビットに収まり、int64（63ビット符号付き）の範囲に余裕があります7。
これらの条件が崩れると整数の大小と辞書順が一致しなくなるので、制約を確認してから使うアイデアです。
4. まとめ
素直な解法は変換テーブルを往復させる発想で、コードの意図が追いやすいです。
効率的な解法は文字列を整数に圧縮して比較コストを下げ、元の文字列をペアで持つことでデコード処理を消しています。
- 辞書順（lexicographic order）は、文字列を1文字ずつ左から比較し、最初に異なる文字が現れた位置でどちらが小さいかを決める順序です。片方の文字列が尽きた場合は、短い方が小さいとみなされます
- Common Lispの
make-hash-tableはデフォルトの等価テストとしてeqlを使います。文字（character）はeqlで正しく比較できるので、このコードでは:testを明示する必要がありません。文字列をキーにする場合は:test #'equalが必要です。 – CLHS: Function MAKE-HASH-TABLE ashはCommon Lispの算術シフト関数です。(ash n k)はnをkビット左シフト（kが負なら右シフト）します。数学的にはfloor(n * 2^k)に相当します。 – CLHS: Function ASH- Schwartzian transform（またはdecorate-sort-undecorate）は、元の値にソートキーを付けてペアにし（decorate）、キーでソートし（sort）、元の値を取り出す（undecorate）という3段階で構成されます。キーの計算が高コストな場合に特に有効です。 – Schwartzian transform – Wikipedia
- 厳密には、Common Lispの整数は任意精度（bignum）のため、値が大きくなると O(1) にならない場合があります。ただし今回は50ビットに収まるためほとんどの処理系でfixnumとして扱われ、実質的に O(1) の比較になります。 – Common Lisp HyperSpec
- コンスセル（cons cell）はCommon Lispの基本データ構造で、2つの値を
carとcdrに格納します。(cons a b)または(a . b)と書きます。リストはコンスセルを連結して作られますが、ここでは対（ペア）として直接使っています。 – CLHS: Function CONS - 符号付き64ビット整数の最大値は 2^63 – 1 ≒ 9.2 × 10^18 です。今回の詰め込みに必要なのは最大50ビットなので、符号ビットを含めても問題なく収まります。 – Common Lisp HyperSpec