タグ

algorithmとJavaScriptに関するodzのブックマーク (2)

  • Javascriptでdiffる ( with 形態素解析 ) (nakatani @ cybozu labs)

    Javascript で diff というのはいくつか試された例はあるようですが、まだこれといった決定打は出ていない様子です。 実は diff は見た目ほど軽い処理ではないので、Javascript にやらせるのはこれが結構大変…… diff の計算量は、おおざっぱに言うと比較対象の要素数の二乗に比例し(実際にはそれより小さくすることができるのですが、まあ話のイメージとして)、かつメモリを大量に消費するので、バッチ的な処理に最適化されていない Javascript にはどうしても荷が重いものとなってしまいます。 比較対象の要素数を減らせば当然計算量は減りますが、行単位で比較してもあまり嬉しくない(わざわざ Javascript で処理するということは自然文が対象と思って良いでしょう)。最小の文字単位だとギブアップ。 ということは形態素解析で分かち書きして、単語単位で diff するのが J

  • Algorithm - O(n log(n))より速いsort : 404 Blog Not Found

    2006年12月03日01:45 カテゴリMath Algorithm - O(n log(n))より速いsort 404 Blog Not Found:javascript - Array#sortがオレquicksortより遅い!?はちょっとした驚きですが、実はデータの種類さえ限定できれば、builtin sortを出し抜くことはJavaScriptでなくてもそれほど難しくありません。 例えば、ソートしたい対象が密集した整数値で、メモリーがふんだんにある場合には、bucket sortがあります。これを使えば、Perlにおいてすらbuilt-inを簡単に出し抜けます。 % perl bucket.pl 10000 Benchmark: running bucket, builtin, quick for at least 3 CPU seconds... bucket: 3 wallc

    Algorithm - O(n log(n))より速いsort : 404 Blog Not Found
    odz
    odz 2006/12/03
    あとで
  • 1