[JavaScript] 自然言語アルゴリズムで配列をソート

think49 @think49

JavaScript で自然順ソートを実装してみたい。自然順アルゴリズムの仕様がどこかに載ってないかな…。何となく、アルゴリズムは頭の中に出来ているのだけど、既に模範があるなら参考にしたい。

think49 @think49

@think49 JavaScript では 'abc' < 'efg' は true となり、'3' < '10'; は false となる。なるほど…。

Yuichirou Ogami @Yuichirou

@think49 これ? →http://sourcefrog.net/projects/natsort/

think49 @think49

@Yuichirou ありがとうございます。C言語を読めないといかんですね。(汗) でも、比較サンプルから形は見えてきました。

think49 @think49

1 < a === false だけど、'1'.charCodeAt(0) < 'a'.charCodeAt(0) === true となる。自然順ソートでは後者の挙動なので charCodeAt を使う必要がある。

think49 @think49

自然順アルゴリズムにおいて、01 === 1 なんだろうか？ a01 と a1 はどのようにソートするんだろう…。

think49 @think49

PHP の natsort で検証してみる。 http://docs.php.net/manual/ja/function.natsort.php

think49 @think49

$array = array("01", "1", "a1", "a01"); を natsort したところ、["01", "1", "a1", "a01"] を返してきた。同値と見なして良さそうだ。

think49 @think49

出来た。http://gist.github.com/660141 (natsort.js)

think49 @think49

natsort(['a1b', 'a1a', 'a', 'a2', 'a0', 'a20', 'a10', 'a1']); の結果が ["a", "a0", "a1", "a1b", "a1a", "a2", "a10", "a20"] となる。修正しなくては。

think49 @think49

修正した。 natsort(['a1b', 'a1a']); は ['a1a', 'a1b'] にソートされるようになった。

think49 @think49

今度は natsort(['rfc1.txt', 'rfc2086.txt', 'rfc822.txt']); が ["rfc822.txt", "rfc2086.txt", "rfc1.txt"] を返すようになってしまった…。 ちょっと時間をおいた方がいいかな。

think49 @think49

修正。natsort(['rfc1.txt', 'rfc2086.txt', 'rfc822.txt']); は ["rfc1.txt", "rfc822.txt", "rfc2086.txt"] を返すようになった。

think49 @think49

natsort(['x2-y7', 'x2-g8', 'x8-y8', 'x2-y08']); は ["x2-g8", "x2-y7", "x2-y08", "x8-y8"] を返す。/ これは期待通りの動作。

think49 @think49

natsort([ '1.3', '1.02', '1.002', '1.010', '1.1', '1.001']); は ["1.1", "1.001", "1.02", "1.002", "1.3", "1.010"] を返す。/ これは期待通りではない。

think49 @think49

natsort([3, 2, 1]); のように配列の要素にString型以外の値が存在するとき TypeError を返す不具合を修正した。

think49 @think49

修正。natsort([1.3, 1.02, 1.002, '1.010', 1.1, 1.001]); は [1.001, 1.002, "1.010", 1.02, 1.1, 1.3] を返すようになった。

think49 @think49

natsort(['pic 4 else', 'pic4']); は ["pic 4 else", "pic4"] を返す。/ これは期待通りではない。空白文字は読み飛ばさなければならない。

think49 @think49

修正。 natsort(['pic 4 else', 'pic4']); は ["pic4", "pic 4 else"] を返すようになった。

think49 @think49

natsort([-5, -1, -3, -7]); は [-1, -3, -5, -7] を返す。/ 「Natural Order String Comparison」では特に明記されていないが、自然順アルゴリズムは負の数を考慮しないと思われる。

think49 @think49

もし、負の数を考慮するのであれば http://goo.gl/Myx1N が 1-2, 1-02, 1-20 の配列となっているのはおかしい。 先頭の "1" は同値で -2, -02, -20 を比較するのだから、"1-20" が先頭に来なければならないはず。

think49 @think49

natsort.js を修正。空白文字を読み飛ばさなかったケアレスミスと string.length を得るタイミングをトリミングする前にするようにした。

think49 @think49

@think49 この修正によって、 http://goo.gl/Myx1N は期待通りにソートされるようになった。

think49 @think49

データ型がString型以外の時、string.length を正しく算出できなかった不具合を修正。

think49 @think49

http://goo.gl/JG6FV に natsort.js のサンプルを置いた。