Hatena::ブログ(Diary)

やねうらお−ノーゲーム・ノーライフ このページをアンテナに追加 RSSフィード

GT-Rの買取ならここですわ。どこよりも高く買取ってもらえるはず。お勧め!GT-R 買取
電王戦出場記念! 書籍化されたで! 監修したで!(`ω´) 絶版なってしもた Kindle版で復活!! 記事書いたで!
解析魔法少女美咲ちゃん マジカル・オープン!

YaneuLabs / やねうら王公式 / やねうらおにメール / twitter / プロフィール

 | 

2009-11-27 降順insertion sortについて

[] 降順insertion sortについて  降順insertion sortについてを含むブックマーク  降順insertion sortについてのブックマークコメント


昨日の記事で、世間で広く知られているinsertion sortのコードがいかにひどいかについて書いた。

私の提案したコードWikipediaにも掲載(注記としてだろう)したほうがいいのではという意見をいくつか頂戴した。


Yuichirou 2009/11/26 02:03

私はyaneuraoさんのコードの方が可読性にも優れていると思います。むしろ日本語Wikipediaコードは脱出条件が複雑な内側のループを無理にfor文で書いているため、可読性が落ちています。

yaneuraoさん、ぜひその最後のコードWikipediaに掲載すべきだと思いますがいかがでしょうか。

上のYuichirouさんの意見は好意からだろうが、はてブでは、次のような否定的な意見も見られる。

shuji_w6e 「馬鹿すぎる」とか「駄目すぎる」とか何様なんだろ?調べて回ったついでに全部書き換えてくればいいのに。

それに対して私はコメント欄で次のように返した。

アホか。「調べて回ったついでに全部書き換え」るなんてこと、なんで調べた人間がいちいちしなきゃならんのだ。お前こそ何様のつもりだ。


まあ、それはそれとしても(私は常に大人げないのだ!)、仮に、私の書いたinsertion sortのコードがよく知られているコードに比べてすごくわかりやすくて、かつ、よく知られているコードより数割速いとしよう。「わかりやすくて」や「数割速い」については異論もあるだろうが、話の便宜上、そうだとしよう。


仮に、わかりやすくて、数割速くとも、insertion sortは、いまさら私のコードを普及させるわけにはいかない理由がある。


それは、例えば、降順に並べ替えるinsertion sortを見てもらうとわかる。普通は、ソートというとたいていは昇順(小さい数字から大きい数字)に並び変える。しかし、降順で並び変えたいときだってある。降順のinsertion sortはどう書くか。


  psortv[n] = INT_MIN; // 末尾に番兵を置く
  for ( i = n-2; i >= 0; i-- )
  {
    // このsortv,moveがtmp変数だとみなせば、
    // ふつうの挿入ソート。ループ変数が逆方向に動くだけ。
    sortv = psortv[i];  move = pmove[i];
    for ( j = i+1; psortv[j] > sortv; j++ )
    {
      // 降順なので前にひとつずらしていく。
      psortv[j-1] = psortv[j];  pmove[j-1] = pmove[j];
    }
    psortv[j-1] = sortv;  pmove[j-1] = move;
  }

Bonanzaで使われているinsertion sortとは何か?

http://d.hatena.ne.jp/LS3600/20091126


上の降順insertion sortのコードは、あの将棋プログラムBonanzaで実際に使われているのだそうだ。


先頭でINT_MINを代入しているのが番兵で、psortv[i]の値が降順になるように、pmove[i]もソートする。要するにソートするレコード1つは、{psortv[i] , pmove[i] }で、計8バイトソートkeyはpsortv[i]。


あとは、普通のinsertion sortのコードを思い浮かべれば、psort[0]..psort[n-1]の範囲に対して降順並び変えしているんだなというのはわかる。ただ、このプログラムを見せられてそれがパッとわかる人は少ないかも知れない。


このように、番兵つき降順insertion sortは実際のプログラムのなかでは慣用句的に使われる。しかし、普通のinsertion sortのコードが頭のなかに入っていないとこれを見てすぐに理解することは不可能だろう。


つまり、insertion sortのコード慣用句であって、「for(int i=0 ; i < N ; ++i)」と同じように理解せねばならない。このプログラムを見ていちいち「ここでn-2から始まって…」なんて考えるものではない。そんなことをしていたら日が暮れてしまう。


初心者プログラマでない限り、「for( int i=0 ; i < N ; ++i)」を見た瞬間、ループのなかでiの取り得る値は {0 , … , N-1 } で、このループはN回まわると頭に思い浮かぶだろう。上の降順insertion sortについても同様だ。


このループ先頭のpsortv[n] = INT_MINを見た瞬間、「番兵をセットしたな」と思い浮かび、for(i = n-2 の2を見た瞬間、「これは降順insertion sortだな」とピンと来なければならない。内側のforでsortvと比較してあるから、keyはpsortv[i]だと確定して、内側のforが抜けたところで、書き戻しているから、「ああ確かに典型的なinsertion sortだ」と理解できなければならない。


このように、降順insertion sortはいたるところに現実的に使われており、これらを使ってあるソースを素早く理解しようと思えば、典型的なinsertion sortのコードを覚えておく必要がある。これはShell sortや、ダイクストラ法などについても同様で、ある程度熟練したプログラマなら見ただけで「アレだな」と理解出来て然りなのである。


そのような理由から、いまさらよく知られたコードを、いくらそれより速くてわかりやすいとしても「こちらのほうがいい書き方だよ」だなんて単純に置き換えることは出来ないのである。ましてほとんどのアルゴリズム教科書のinsertion sortのコードが昨日の記事のような具合で、長年その教科書を使って勉強してきた人がたくさんいるわけである。


ちなみに、Shell sortは、よく知られているようにinsertion sortを用いるsortアルゴリズムであるが、Shell sortをDonald L.Shellが提案したのが1959年である。すなわちinsertion sortなんてものは、それ以前からあったことは間違いない。そう考えると半世紀以上の歴史がある。


こんな古典的なアルゴリズムの改良コードを提案するには、かなりの教育的な配慮のもとに、「こちらのほうがこういう理由で、こういう状況において速くなるんだよ」と示さねばならないのである。単に無責任Wikipediaを書き換えて回ればいいという問題では決してない。


おまけに、ターゲットアーキテクチャが定まらないと、「こちらのほうが速い」というのを示すのはとても難しい。


例えば、Knuthは、その著書TAOCP(The Art Of Computer Programming)のなかで、MIXというRISC型の仮想マシンを提案した。(最近Knuthの本ではMMIXという新しいバージョンのものが使われている) MIXマシンで最短で書けることやMIXマシンで何stepで実行できるのかというのをアルゴリズム研究の礎にした。


私が思うに、その方針は正しい。しかし、現実的には世のなかのパソコンはほとんどがいまやx86/x64マシンであり、それらのマシンには、分岐予測という仕組みが備わっている。分岐予測が外れたときにはもの凄く大きなペナルティを食らうのが普通である。この部分をある程度考慮した上でアルゴリズムを検討しないと、現実に即したものにならない。その意味ではTAOCPで使われているMIXマシン現実的なマシンとの溝を埋め合わせるための教育的な試みが必要だと思う。


ターゲットアーキテクチャが定まらないと、「こちらのほうが速い」というのを示すのはとても難しい』と書いたが実際は、ターゲットx86/x64,Corei7限定だとしても「こちらのほうが速い」を示すのにはとても労力が必要だ。コンパイラコンパイルさせてみて明らかに実行時間に差があるならともかく、普通アセンブリコードを見せて、こっちのほうが分岐予測が当たりやすく、かつこの命令とこの命令のlatencyがこちらより少なくそして、使用するレジスタが何本で済むだとか、そういう話になる。


しかし特定の命令のlatencyについては公開されていないものもある。または、「worst caseでこれだけのlatency」だとかその程度の情報しかわからないものもある。実測すると言っても前後コンテキストの影響を結構受けたり、そのときのレジスタの値でlatencyが変わったりしえるので測定自体が難しい。


結局、本気で1サイクルでも短いプログラムを書こうと思うとIntelプロセッサの開発チームに問い合わせなければならないが、私は、いまだかつてIntelプロセッサの開発チームに問い合わせて教えてもらえたというプログラマは知り合いに一人しか居ない。彼は、「(当時はPrescottの時代だったから)イスラエルFAXしてこことここを教えてもらった」と言っていたが、ある程度名のある会社で名のある製品を作っていないと門前払いだろう。


さて、長々と書いたが、

・insertion sortは高速化のために特化されたソートアルゴリズムであり高速でなければその存在価値がない。

・世間でよく知られているinsertion sortのコードは決して質の良いコードではなく、改良の余地がある。

・しかし、世間でよく知られているinserion sortのコードぐらい覚えておかないと他人の書いたソースを読めませんよ。

という3つが私の言いたかったことで、こうやってたくさんの人の目に触れたことで私としてはとても満足している。

nn 2009/11/27 11:51 >単に無責任にWikipediaを書き換えて回ればいいという問題では決してない。
Wikipediaに"無駄なwritebackを消すとこんな形になる"と書けば良いだけです。
番兵のパターンも書くといいでしょう。
wikipediaのアルゴリズムのページは英語版ですら評判良くない状態なので、協力お願いします。

yaneuraoyaneurao 2009/11/27 12:01 > Wikipediaに"無駄なwritebackを消すとこんな形になる"と書けば良いだけです。

ええ、そう書くと「その無駄なwritebackを消すと本当に速いのか?」「どのアーキテクチャで本当に速いのか?」「どのコンパイラで本当に速いのか?」「そのソースは本当にわかりやすいのか?」「似たサンプルコードを2種類掲載する意味はあるのか?」「伝統的な教科書のサンプルコードとは違うようだが、これはお前が考えたのか?」「出典を示せ」「番兵のパターンは広く使われているのか?」「要出典」「サンプルにそこまで必要ないだろう」「要出典」「要出典」「要出典」etc..(´Д`)

nn 2009/11/27 12:04 併記すれば良いって話です。別に早い必要はありません。
[citation needed]が付くかもしれませんが、特に問題は無いかと。

yaneuraoyaneurao 2009/11/27 12:47 > 別に早い必要はありません。

速いコードである必要がないなら、併記すること自体の価値が問われるのでは。「writebackを消して速くなると思うのか」「writebackを消せれば何が嬉しいのだ」「writebackを消したコードがどこに使われているのだ」「writebackを消したコードはどの本に載っているんだ」「要出典」「writebackを消して速くなる例を」「サンプルコードとして掲載する価値があるのか」「要出典」「要出典」「要出典」…心が一瞬で折れそうです(´ω`)

nn 2009/11/27 13:30 load/storeを減らしたってだけで書く価値はあるでしょう。特に要素が大きい場合に効果はでかいですし(まぁその場合はポインタ使うことが多いですが)。

yaneuraoyaneurao 2009/11/27 13:47 > load/storeを減らしたってだけで書く価値はあるでしょう。

そう言っていただけると大変嬉しいです。また、その価値を正しく理解していただけているというのにも本当に今回の記事を書いて良かったなぁと思います。

まあ、それはそれとしてですね、私はWikipediaを編集する他の人を説得したり編集合戦をしたりするぐらいなら、もっと他のアルゴリズムについてもその改善に取り組んだり、もっと未解決のソフトウェア上の問題に取り組んでいるほうが自分の性にあってるんですよね。まあ、ひとことで言うとヒッキーなんです。そんなわけで、お許しを(´ω`)人

mgymgy 2009/11/27 20:17 やねさんが本に書いてそれを出典にすればおk

ねむねむねむねむ 2009/11/28 01:53 出典厨は日本に特に多いようなので、英語版を主に使えばよいかと思います。

http://slashdot.jp/it/comments.pl?sid=472446&cid=1661387

ねむねむねむねむ 2009/11/28 14:32 英語ろくに分かっていないけど、英語版のノートに投げておきました。日本語版は労力をかけて記載する魅力を感じないのでパスします。

http://en.wikipedia.org/w/index.php?title=Talk:Insertion_sort

yaneuraoyaneurao 2009/11/29 02:47 ↑おお、ありがとさんです。

しかし、その降順insertion sortは私のソースコードではないので
> // yaneurao's descending order insertion sort
は間違いです。

その部分は、Bonanzaのソースコードで、かつ、その降順insertion sortは改良されたものではなく、典型的なinsertion sortを逆順で書くとどうなるかというものなので、それは高速なコードとしては適切な例ではありません。

典型的なinsertion sortを降順insertion sortにして番兵(delimiter)をつけてある実際に有名なソースコードで使われている例としての意味はあります。

ねむねむねむねむ 2009/11/29 17:46 すみません、寝ぼけていました。Bonanzaのコードに関しては削除しました。

板子一枚下板子一枚下 2009/11/29 18:25 高水準言語などチューリングマシンという計算の化け物が被った薄皮にすぎないから
人間にとっての理解しやすい書き方の議論などよりも
高い実行効率(時間および空間)をもたらすアルゴリズムを提案する方が有意義なのは当然なのだが
このようなエントリが立つと前者の方向に引っ張られる引力のようなものがさかんに働く罠、

さらに言うと人間にとっての理解しやすには一意性などないから強硬な主張は宗教的教条に近い
例えばif (data[i] > tmp)部分をcontinueに置き換えることは誰しも考えることだろうけども(漏れも考えたけども)
そう書かれたら書かれたで、for文内におけるcontinueのふるまい(けっこう微妙なものがある)を
思い出して眼前のコードに当てはめねばならないから解釈のコストが下がったとは言い難い
(個人的にそういう作業を避けたいと言っているのではなくて、コストの定量的大小が不定の意味)

foooofoooo 2009/12/01 23:23 http://www001.upp.so-net.ne.jp/isaku/build.html
に約4年前から似たようなコードがあるよ

いもいも 2009/12/02 00:09 一応wikipedia版の方を擁護しておくと、アルゴリズムの記述としてこちらの方が美しいというのがあります。

コードの部品をそれぞれ
A: tmp = data[i];, B: j = i, C: j > 0, D: data[j-1] > tmp, E: data[j] = data[j-1];, F: j--, G: data[j] = tmp;
とすると、wikipedia版は
A、B、C0、D0、E0、F0、C1、D1、E1、F1、C2、D2、E2、F2、...、En、Fn、(CまたはD)、G
と、0回目も1回目以降も同じ処理が繰り返されます。
一方、やねうらおさんの方だと、
A、D0、B、E0、F0、C1、D1、E1、F1、C2、D2、E2、F2、...、En、Fn、(CまたはD)、G
という風に、0回目と1回目以降の処理が異なっている汚さがあります。(Dという処理が2箇所に書かれていて、対称性がないせいです。)
(そして、実はループに入った場合、省略されているのは最初のC0だけという罠・・・)

もし、ループに入らなかった場合には、wikipedia版は
A、B、C0、D0、G
やねうらおさん版だと、
A、D0
となり、確かに差は見られます。(特に、Gがないのは大きい)

ただ、全コードのp(0<=p<=1)が既にソート済みであるような状態だとすれば、元のコードの計算量がO((1-p)n^2)+O(pn)で、改めたコードの計算量がO((1-p)n^2)+O(αpn) (αは改善度)であり、ほんの微々たるものであると言わざるをえません。
(まぁ、その微々たるものを求めて、挿入ソートとか使うのでしょうが。)

「学術的な立場だと」どちらにしろ挿入ソートはO(n^2)のソートであり、上のようなO(n)の最適化は、あまり意味がありません。(※あくまで、学術的視点。実用面からは別問題。)
ならば、対称性を持ったきれいなアルゴリズムの記述の方がいい、となります。
(ソートの正当性の証明をするのに、最初の「もし〜なら」のクッションが一段抜けるので、証明のスピードは速くなりますw)

yaneuraoyaneurao 2009/12/02 06:43 > p(0<=p<=1)が既にソート済みであるような状態だとすれば、元のコードの計算量がO((1-p)n^2)+O(pn)で、改めたコードの計算量がO((1-p)n^2)+O(αpn) (αは改善度)であり、ほんの微々たるものであると言わざるをえません。

・insertion sortではソートする要素数自体は少ないと仮定できるので O(n^2)よりO(αn)のほうが現実的には利いてくる。この意味において、オーダーで評価すること自体がinsertion sortの計算量の評価方法として適切ではない。

・また評価の仕方が、x86/x64アーキテクチャには即してない。例えばソートされている配列に、ソートされていない配列をappendした配列に対して(こういう配列をinsertion sortでソートしたいというのは現実的によく起こりえます)、元のコードだといかに分岐予測が外れるかという観点で考えるべき。元のコードだと分岐予測が外れまくるので、改善後のコードとは雲泥の差。

yaneuraoyaneurao 2009/12/02 06:46 > http://www001.upp.so-net.ne.jp/isaku/build.html
> に約4年前から似たようなコードがあるよ

それを言えば私は約25年以上前から、insertion sortをこの形で書き続けています。私の書いたinsertion sortのコードもいたるところに散らばっています。

しかし、それが広く知られているわけでも教科書に載っているわけでも何でもなく、これを機に周知する必要があると思ったのでブログに書いてみました。

いもいも 2009/12/02 07:49 ソートされた配列に要素を追加してソートし直すような場合、そもそも追加してからソートするのが間違いで、ソートしてからマージするのが正解です。
前者の場合、O((n+m)m)かかりますが、後者ならO(n+m+mlogm)で済みます。(n: 元の配列のサイズ、m: 追加する要素数)
細かい改善に目を奪われて、根本的な改善を見失ってしまっては本末転倒です。

yaneuraoyaneurao 2009/12/02 07:55 > ソートされた配列に要素を追加してソートし直すような場合、そもそも追加してからソートするのが間違いで、ソートしてからマージするのが正解です。

ええ、それはもちろんそうです。元のコードで典型的に分岐予測が外れまくるケースがそれだったのでそう書きました。

実際には対象とする配列が「ソートされた配列」であることは仮定できないので、「ほぼソートされた配列」にソートされていない配列をappendした配列をinsertion sortでソートすると読み替えてください。

yaneuraoyaneurao 2009/12/02 08:08 自己レスすみません。

> 元のコードで典型的に分岐予測が外れまくるケースがそれだったのでそう書きました。

この部分、間違いですね(´ω`) よく考えてませんでした。

私が言うべきだったことは、
・ある程度ソートされた配列に対してinsertion sortを行なった場合について考える。
・これなら分岐予測がどの程度はずれるのかを評価しやすい。
・その場合、元のコードでは分岐予測が外れる回数が多いことがわかる。
ということです。

ほぼソートされた配列にソートされていない配列をappendした配列をinsertion sortしたときどうなるかという話は、insertion sortするときに、配列の前からではなく後ろから辿ったときに分岐予測が外れる回数が増えるという話で、それはいまの話の流れとは全然関係がないです。後者の話をちょうど検討していた直後だったので間違えて書いてしまいました。すみません。

yaneuraoyaneurao 2009/12/23 10:24 自己レスすみません。メールでご指摘をいただいたので訂正。「番兵(delimiter)」 → 番兵はふつう「sentinel」ですね。

トラックバック - http://d.hatena.ne.jp/yaneurao/20091127

2009-11-26 広く知られているinsertion sortのコードは駄目すぎる

[] 広く知られているinsertion sortのコードは駄目すぎる  広く知られているinsertion sortのコードは駄目すぎるを含むブックマーク  広く知られているinsertion sortのコードは駄目すぎるのブックマークコメント


insertion sortは「挿入ソート」と訳される。(Wikipediahttp://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88 )


■ 日本語


Wikipedia日本語のページのコード引用すると次のようになっている。

for (i = 1; i < n; i++) {
    tmp = data[i];
    for (j = i; j > 0 && data[j-1] > tmp; j--) {
        data[j] = data[j-1];
    }
    data[j] = tmp;
}

上のコードでは、内側のループでinsertの必要がなかった場合でも最後にdata[j] = tmpでtmp変数をwrite backしており、しかも、insertの必要のなかった場合でもj=iが1回実行される。それらの意味において(速度的な観点からすれば)とても無駄コードである。


write backすることの弊害は、このコードでは読み出したばかりのところに書き出すだけなので、そのメモリは(いまどきのアーキテクチャなら)L1 cacheに載っているだろうから、大きな損だとは言えないが、例えば、t[X].Order に従って t[X] 自体を昇順ソートしたいような場合、write backのコスト馬鹿にならない。(sizeof(T[X])==12ぐらいだとして)


どこの馬鹿アルゴリズム教科書から引用してきたのかは知らないが、こんなものをサンプルとして掲載しないでもらいたい。


■ 英語版・イタリア語


次いでWikipediaのinsertion sortの英語で書かれたページのコードも見ておこう。

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i - 1;
        while j >= 0 and A[j] > value do
        begin
            A[j + 1] := A[j];
            j := j - 1;
        end;
        A[j + 1] := value;
    end;
end;

こちらはPascalで書かれている。さきほどのコードの変形だが、さきほどのコードよりさらに悪い。jにi-1を入れているが、これが無駄で、j にはiを入れて、"j + 1 "を"j"に、" j "を "j - 1"にしたほうがコンパイラはいいコードを生成するだろう。


j >= 0の判定も初回は不要なわけで、insertの必要がない場合でも1回無駄な j >= 0の判定が必要になる。これもダメダメコードと言える。


■ フランス語


同じく、フランス語のほうも見てみよう。

#define MAX 100
 
void insertion(int t[MAX]) 
{
    /* Tri du tableau t par insertion sequentielle */
    int i,p,j;
    int x;
 
    for (i = 1; i < MAX; i++) 
    {
        /* Stockage de la valeur en i */
        x = t[i]; 
 
        /* Recherche du plus grand indice p inferieur a i tel que t[p] <= t[i] */
        p = i-1;
        while (t[p] > x && p-- > 0) {}
 
        /* Il faut inserer t[i] juste apres cette case */
        p++;
 
        /* Decalage avant des valeurs de t entre p et i */         
        for (j = i-1; j >= p; j--) {
            t[j+1] = t[j]; 
        }   
 
        t[p] = x; /* Insertion de la valeur stockee a la place vacante */
    }
}

こちらは、英語版のページに書かれていたコードをCで書き直したものだ。ループカウンタのj以外に、無駄なpという変数が導入されている。insertする地点pを求めて、そこ以降の要素をひとつ前にずらすコードなのだが、無駄変数pが必要になる上に、そのあとのループではループカウンタをダウンカウントして、配列の後ろから前に向かってアクセスしている。


せっかくinsertする地点が求まっているのにわざわざreverse memory copyで書いて、コンパイラ最適化を阻害し、かつメモリハザードを起こす意味がわからない。こんなことは馬鹿のすることだ。


■ ドイツ語


INSERTIONSORT(A)
1 for j = 2 to length(A)
2     do key = A[j]
          //Fuge A[j] ein in die sortierte Folge A[1 .. j - 1]
3         i = j - 1
4         while i > 0 and A[i] > key
5             do A[i + 1] = A[i]
6                 i = i - 1
7         A[i + 1] = key

Fortranで書かれた疑似コードなのでjのindexが2から始まるが、アルゴリズムとしては英語版と同じだ。これも話にならない。


■ 中文

void insertion_sort(char array[], unsigned int first, unsigned int last)
 {
 	int i,j;
 	int temp;
 	for (i = first+1; i<=last;i++)
 	{
 		temp = array[i];
 		j=i-1;
 
 		//与已排序的数逐一比?,大于temp?,?数移后
 		while((j>=first) && (array[j] > temp))
 		{
 			array[j+1] = array[j];	
 			j--;
 		}
 
 		array[j+1] = temp;	
 	}
 }
這個更好:
 void InsertSort(char array[],unsigned int n)
 {
    int i,j;
    int temp;
    for(i=1;i<n;i++)
    {
      temp = array[i];//store the original sorted array in temp
      for(j=i ; j>0 && temp < array[j-1] ; j--)//compare the new array with temp
      {
          array[j]=array[j-1];//all larger elements are moved one pot to the right
      }
     array[j]=temp;
    }
 }

中段に書いてある「這個更好」は、「以下のように書いたほうがいいよ」の意味だと思う。


前者は英語版のコード後者日本語版のコードとほぼ同じだ。さきほど私が解説したように後者のほうがいいコードが生成されるだろう。しかし、ループの最後でwrite backしているのはいただけない。


■ 誰がこんな駄目なコードを広めたのか


以上で見てきたようにWikipediaのinsertion sortのサンプルはひどすぎる。おそらく書籍か何かの丸写しで、これがinsertion sortとして広く信じられているコードなんだろうけど、だとしたらとても悪いコードが広まっていると言わざるを得ない。


insertion sortは配列の要素が少ないときや、ある程度整順されていることがわかっているときにはとても有用なアルゴリズムであり、この関数高速化はとても重要なのだ。(高速化が不要ならそもそも何も考えずに最初から言語ライブラリにあるqsort関数でも呼び出しておけばいいわけだし)


ひょっとしてinsertion sortを提案した奴(誰かは知らん)が、こんなひどいコードを広めたのかも知れない。だとしたらそいつはかなり罪深いと思う。


例えば、Introduction to Algorithms, Second Editionを見てみると(第3版は最近出たようだが私は持っていない)、次のコードが掲載されている。

INSERTION-SORT(A)
1 for j ← 2 to length[A]
2 do key ← A[j]
3 	> Insert A[j] into the sorted sequence A[1 .. j - 1].
4 	i ← j - 1
5 	while i > 0 and A[i] > key
6 		do A[i + 1] ← A[i]
7 			i ← i - 1
8 	A[i + 1] ← key

Wikipedia英語版のコードと同じアルゴリズムだ。一連の劣悪なコードはこいつが犯人かも知れない。


また、アルゴリズム本で有名なROBERT SEDGEWICKの著書の何冊かには次のコードが掲載されている。

procedure insertion;
    var i, j, v: integer;
    begin
    for i:=2 to N do
        begin
        v:=a[i]; j:=i;
            while a[j-1]>v do
                begin a[j] :=a[j-1]; j:=j-1 end;
            a[j] :=v
        end ;
    end ;

こちらはWikipedia日本語版のコードとほぼ同じだ。こちらのコードはまだ救いはあるが、お世辞にも高速とは言い難い。ついでに言えば、このコードだけ見ればwhileのところの条件式に「j > 1 &&」が忘れてあるように思えるが、a[0]には番兵を置くと本文中にある。


■ まとめ


結局、insertion sortは最初に発案した奴が、きっとこんな駄目なコードを書いたんじゃないかと思う。(よく知らん) そしてそれがほとんどすべてのアルゴリズム教科書採用されている。Wikipediaのinsertion sortは言わずもがなである。


私ならinsertion sortは次のように書く。これは、上で見てきたinsertionコードより典型的には3割程度速い。何より無駄なwrite backや"j = i - 1"などをしていないのでコードがわかりやすい。

  // yaneurao's insertion sort
  for (int i = 1; i < MAX; i++) 
  {
    int tmp = t[i];
    if (t[i-1] > tmp)
    {
      int j = i;
      do {
        t[j] = t[j-1];
        --j;
      } while ( j > 0 && t[j-1] > tmp);
      t[j] = tmp;
    }
  }

※ whileの条件を (t[j] > tmp && j > 0) と 書き間違えてました。コメント欄でご指摘をいただいたので修正しました。

また、昇順ではなく降順ならば、配列の要素をひとつ多く確保して、先頭にINT_MAXか、その末尾の要素にINT_MINを番兵(sentinel)として入れておき、jの終端チェックを省略することでさらに数割速くなるだろう。


昇順ソートの場合もt[0]は事前に空けておき、t[0] = INT_MINなどを番兵として代入しておき、j > 0 を省略することで同じく数割速くなるだろう。

hogehoge 2009/11/26 00:36 速くなるのは分かるけど、とても分かりやすくなったとは思えない。
例ってのはエッセンスを伝えるものだから、
遅くても分かりやすいものを載せるのは正解だと思う。
そもそも後置 while はどの言語にもあるわけじゃないし、
無限ループ+if-break に置き換えるとますます読み辛くなる。
「こういう高速化法がありますよ」ってのは載せてもいいとは思うけど。

yaneuraoyaneurao 2009/11/26 00:55 > とても分かりやすくなったとは思えない。

元のコードのように挿入しないときも値をwrite backするコードのほうが非直観的で、このinsertion sortの形を見慣れていないと何をしているのか理解しにくいです。対して私のコードは、t[i - 1] <= t [ i ] である限りは、ifが成立せず tに対して何も影響を与えませんから、すなわちすべての i に対して t[ i - 1 ] <= t[ i ] になるようにしようとしていることは明白です。

> 例ってのはエッセンスを伝えるものだから

insertion sortに限って言えばそれは間違いです。これは、要素数が少ないときのために特化されたソートであって、もともとの狙いが高速化にあります。insertion sortで書いて高速化しないなら何の利用価値もないのです。

この速度的に見て駄目駄目なコードがあまねく広く知られていて、コピペしていたるところに使われているのです。それはとても大きな実害を招いているのです。

> そもそも後置 while はどの言語にもあるわけじゃないし、

後置whileが無い言語ならばgotoで良いのです。そもそも疑似コードで示しているだけなのですから、後置whileであろうが何であろうが使って良いのです

YuichirouYuichirou 2009/11/26 02:03 私はyaneuraoさんのコードの方が可読性にも優れていると思います。むしろ日本語版Wikipediaのコードは脱出条件が複雑な内側のループを無理にfor文で書いているため、可読性が落ちています。
yaneuraoさん、ぜひその最後のコードをWikipediaに掲載すべきだと思いますがいかがでしょうか。

kilreykilrey 2009/11/26 02:10 - } while (t[j] > tmp && j > 0);
+ } while (t[j-1] > tmp && j > 0);
ですよね。

ingktingkt 2009/11/26 02:15 j = iである初回のdo whileループの終了条件チェックが、ループに入るかどうかを判定するif文と重複しています。そこをif文にするなら、その分ループ展開もするべきではありませんか?

yaneuraoyaneurao 2009/11/26 02:32 > kilreyさん

> + } while (t[j-1] > tmp && j > 0);

あっ、ingktさんの指摘と同じ意味ですね。まずingktさんの指摘は正しいです。私は、番兵を置くコードを普段書いているので、このチェックは今回の記事のために追加したものでそのときに書き間違えたようです。

それで、その場合 j > 0ではなく j > 1にしないと[j - 1]が j==0のときアクセス違反になります。よって、この部分は、
while (j > 0 && t[j-1] > tmp);
が正しいのではないかと思うのですが、どうでしょう?

yaneuraoyaneurao 2009/11/26 02:44 ブクマのコメントで気になるのがあったので返信しておきます。

> kilrey 技術, ネタ Atom/gcc -O3だと、Wikipedia版は最内ループをj=i-1から始まるように変えてNが大きければ5%くらいやね版より速くなった。これはコンパイラの最適化傾向に由来する誤差のような気がする。

ひとつ上のコメントにあるように私のコードが間違えていたためかも知れません(汗) ご迷惑おかけします。

実験されたコードを是非私にメールしてください。私のほうでも追試したいです。

仮にそれで本当に私のコードより速くなるとしたら、それはgccが、do〜while + ループ内メモリコピー に対する最適化が甘いのかも知れませんね。

また、アセンブラで書けば確実に私のコードのほうが高速なのは明白なのですから、これは決して「コンパイラの最適化傾向に由来する誤差」ではありません。ゆえにアルゴリズム的には(高速化できる伸びしろの大きさとしては)、私のコードのほうが断然優れていると思います。

実際Visual C++2008コンパイルした場合、N == 1000ぐらいでも私の書いたコードのほうが圧倒的に速いです。(配列の中身がある程度まばらな数字であるなら)

ingktingkt 2009/11/26 03:00 >while (j > 0 && t[j-1] > tmp);
これが正しいと思います。展開する必要はありませんでしたね。

yaneuraoyaneurao 2009/11/26 03:04 ↑了解です。コメントありがとうございます。

yaneuraoyaneurao 2009/11/26 03:15 Yuichirouさん
> yaneuraoさん、ぜひその最後のコードをWikipediaに掲載すべきだと思いますがいかがでしょうか。

Wikipediaよりは、まずはアルゴリズム本関係の著者に連絡すべきかも知れません…が、うまく伝える自信がないので私はパスで(´ω`)人

shiroshiro 2009/11/26 05:11 おもしろいです。TAOCPを見てみたら、やっぱり書き戻ししてました (Second Edition, Volume 3 p.80)。ただし、こちらの議論でのj>0チェックはループ最後になってるのと(同書ではiとjが入れ替わってるのでi>0チェック) 、実行時間の検討ではレコードサイズは1ワードと仮定してます。Knuthはこの時点ではMIXインストラクションでのステップ数最小を強調していて、メモリアクセスのペナルティは考えてないみたいなんで、ステップ数優先でこうしたのかもしれません。時代によってアルゴリズムのコンスタントファクターに影響を与える要素の重みが大きく変化したということなのでしょう。(あと、コンスタントファクタなのであまり重視されてこなかったという面もあるかも。)
Third Editionは持ってないですがどうなっているでしょうね。

yaneuraoyaneurao 2009/11/26 06:50 TAOCP(The Art Of Computer Programming)、2nd Ed.Vol.3の内容、いま確認しました。

> 実行時間の検討ではレコードサイズは1ワードと仮定してます

そうですね。実際はレコードサイズが3ワードとか4ワードでinsertion sortしたいケースも多々あるので、そういったケースについてもきちんと検討して欲しいところですね。

このKnuthのコードは、MIXインストラクションとして最小だとは思うのですが、最速かというと集合がworst case(すなわちソートしたい逆の順番で値が並んでいるとき)ではそうかも知れませんが、そうではない場合は、i←j-1を実行している時間が丸々無駄になるので、最速じゃないような気がします。(MIXインストラクションは、私はよくわからないので、もう少し注意深く読まないといけませんが)

あと、同書、演習問題33の解答では、番兵を置くアルゴリズムのMIXコードが掲載されていますね。

あと、insertion sortの発案者が誰なのかはこの本には書かれてないですね。

ff 2009/11/26 11:12 ソート済みのデータ列に対して追加するアルゴリズム。
挿入ソートってのは「配列」じゃなくて「Linked List」に対してもっとも効率的に動くものじゃないかな。
配列に対して挿入ソートを使う場面が思い浮かばない…。

名無し名無し 2009/11/26 14:17 日本語版の元ネタは珠玉のプログラミングかな、と思います。
確認したところ、変数名dataがxなだけで載ってる擬似コードそのままなので。

yaneuraoyaneurao 2009/11/26 18:19 > 配列に対して挿入ソートを使う場面が思い浮かばない…。

5個程度しかデータが無いことがわかっている配列を高速にソートしたいときにはいつでも使えると思いますよ。

> 日本語版の元ネタは珠玉のプログラミングかな、と思います。

確認しようと思ったら、その本、友達にあげたのでした・・。

yaneuraoyaneurao 2009/11/26 18:22 はてブで気になるコメントがあったので、返信。

> nanakoso 高々数割の高速化のためにアルゴリズムの例示サンプルコードにけちをつける人々

何度でも言いますが、数割遅くてもどうでもいいという程度の処理ならそもそもinsertion sortを使う必要はないのです。それくらい高速化が要求されるところにinsertion sortは使うのです。

ボトルネックになっているところが数割違えば、XeonとCorei7ぐらい違ってくるのです。お金に換算すれば、それこそ何十万とか何百万とか変わってくるのです。そういうシビアなところに使うのです。そういうシビアなプログラムを書いたことがないか、もしくは書くつもりがなら、しょーもないコメントをつけずに黙ってお引き取りください。

反復何とか反復何とか 2009/11/26 21:18 挿入ソートの使いどころは、もし昇順でない要素を見つけたらスゲー得するのでラッキー、という類の問題の一部な場面ですね

yaneuraoyaneurao 2009/11/26 21:30 はてブに対する返答。

> shuji_w6e 「馬鹿すぎる」とか「駄目すぎる」とか何様なんだろ?調べて回ったついでに全部書き換えてくればいいのに。

アホか。「調べて回ったついでに全部書き換え」るなんてこと、なんで調べた人間がいちいちしなきゃならんのだ。お前こそ何様のつもりだ。

yaneuraoyaneurao 2009/11/26 22:05 はてブに対する返答。

> akimotokenichi Wikipediaは事典なので効率を要求するのはちょっと…。物事の仕組みを知ったり考え方のヒントを得るためのものだと思うので、理解しやすいコードの方がよいと思う。パフォーマンスについては注記してあれば十分では。

何度でも言いますが、insertion sortはsortの効率を追求するための手法であって、高速でないなら何の意味もないのです。

また理解しやすさで言えば(見ようによっては)私のコードのほうが理解しやすいでしょう。bellbindさんがはてブで指摘しているように(私のコードで)「ソート済みのときはメモリをいじらない特徴を主張するのであれば、内側ループの直前に "if (data[i - 1] <= tmp) continue;"を入れるだけにしとくのがわかりやすいと思う」は確かにそうで、そう書き直せば、さらに私のコードのほうが元のコードよりさらにわかりやすいでしょう。

「パフォーマンスについては注記してあれば十分」かも知れませんが、insertion sortについては、Wikipediaに書かれているコードがすでに広くコピペされて使われています。あるいはアルゴリズム本のコードがすでにコピペされて広く使われています。Wikipediaの問題ではなく世間に氾濫しているアルゴリズム本のほうにそもそもの問題があります。それがコンピュータサイエンスの授業で使われて、悪いコードを覚えて、いまだにそのコードを使っている人がたくさんいます。また、Wikipediaのinsertion sortのサンプルコードは何も考えずに広くコピペして使われています。そういう意味では、これは、かなり根の深い問題なのです。どこに"注記"すれば、そういった人たちまでに伝わるでしょうか?

また、shuji_w6eさんのように「調べて回ったついでに全部書き換えてくればいいのに」などと無責任に言う人がいますが、Wikipediaのすべての言語のものを書き換えるのは一個人では不可能で、また、速度的に良いコードかどうかを判断するには、ターゲットとするコンピュータアーキテクチャが存在して、かつそのアーキテクチャについて精通していないと判断できません。要するに、他の人とコンセンサスを確立するのが非常に難しく、Wikipediaを編集する他の人たちを説得するには並々ならぬ労力が必要です。

反復何とか 反復何とか 2009/11/26 22:37 批判ついでにWikipediaを書き換えればいいと言う人はWikipediaの編集方針を理解していないと言わざるおえない
・ウィキペディアの掲載基準は、「真実であるかどうか」ではなく、「検証可能かどうか」です。
・独自研究を書いてはいけません
・書く事柄には検証可能な出典(刊行物等)が必要です

というわけで、yaneurao氏がまた本を書いて技術書売り上げのクリーンヒットを放てばすぐ解決する問題

yaneuraoyaneurao 2009/11/26 23:01 > yaneurao氏がまた本を書いて技術書売り上げのクリーンヒットを放てばすぐ解決する問題

自分で本に書いて、それを出典としてWikipediaの記事に追記したりするのは、すごく自作自演かつ捏造くさいですね…(´Д`)

すがーすがー 2009/11/27 00:46 >検証可能かどうか
無意味な処理でありバグってるのが自明なので、現在の記述は不適切であると検証可能です。

第一それは話の根拠の事であって、文章やソースコードの出展元を制約するものではありません。というか、既出のコードのみ掲載可能とか言い出すとライセンスで死にます。

あくまでWikipediaで許されている引用か、執筆者が定義に従って執筆したものであるべきです。
アルゴリズム全体の実装例は引用の範囲に収まるかは疑問ですし、執筆者がその定義から実装したコードを執筆する事には何の問題もありません。

yaneuraoyaneurao 2009/11/27 01:09 横からですが..
> 無意味な処理でありバグってるのが自明

?? 現在のWikipediaの挿入ソートのコードは別にバグってはいませんよ。パフォーマンス上の問題だけです。

通りすがり通りすがり 2009/11/27 16:52 yaneurao氏のコードが無駄なload/storeを減らした最適化されたコードであり、その差が挿入ソートを用いるべきとこでは無視できないコスト差が発生するという主張は分かります。

ただ『挿入ソートを知らない人』に示す最初のサンプルコードとしてはyaneuraoさんのは最適化のエッセンスも混ざってる分敷居が高いと思います。

かといって、各種本やウェブの記事、wikipediaのがそのままにしとくのが最良なのかというと
それをそのまま実践投入しちゃう人が量産されてしまうのも事実なので導入の後の発展として
実際に使えるコードを示すのがbetterなのではないかと思います。


shellやquickやheapなどにページ割いてる本はあれどinsertionにページ割いてる本ってあるんですかね?
学生の頃sedgewick先生の本を読みながら勉強してたんですけど、その本ではquickとかは分割がある程度進んだら
途中でinsertionに切り替えた方が速くなるよって教えてくれてるんだからinsertionにももうちょっとページ割いて
発展のコード例を示してくれてもいいのにとはコメントを書きながら思う今日この頃です(´Д`)

等価なコードに落とすだけの簡(ry等価なコードに落とすだけの簡(ry 2009/11/27 21:57 ループ実行時の統計を考慮しないコンパイラが教科書版挿入ソートからyaneurao版挿入ソートを導くことはほぼあり得ない
が、、
i=jや--jを挟んだt[j±定数]やt[i±定数]同士の同値性を見抜くぐらいには賢いコンパイラがyaneurao版挿入ソートを見たらば
クリティカルパス(if (t[i-1] > tmp) 非成立時のマシンサイクル)を短縮しようするあまり教科書版に変形してしまったりして、、

yaneuraoyaneurao 2009/11/29 02:40 > だからといって、最適化後「のみ」を掲載するのでは事典的意味が無いと思います。

もちろんそうです。そのことは↓で詳しく書いています。
http://d.hatena.ne.jp/yaneurao/20091127

hogeloghogelog 2009/12/06 04:35 > 挿入ソート
そこに書かれているコードは講義で挿入ソートを習った僕がWikipediaを見て「これ挿入ソートじゃないじゃん」と思い書き換えたものだったと思います。「Wikipediaに載せるコードはコピペとかじゃライセンスとかそういうのでダメなのでは?」と思ったので講義資料などのアルゴリズムの記述とかだけ参考にしつつ適当に。
http://ja.wikipedia.org/w/index.php?title=%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88&oldid=8899642
当時気づいていませんでしたが変数名間違ってました。で、修正がはいったわけですが
http://ja.wikipedia.org/w/index.php?title=%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88&oldid=10226327
挿入ソートじゃなくなってました、と。


で2007年頃に修正されてるけど間違ってることに気づきました。
http://d.hatena.ne.jp/hogelog/20070704/p1
その元になったコードが間違ってたのが恥ずかしかったので↑のことには言及しなかったんだったと思います。


で2008年頃にあらためてそれをWikipediaに書いた、と。
http://twitter.com/hogelog/status/755298012
http://ja.wikipedia.org/w/index.php?title=%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88&oldid=18212514


ここ見て「そういえば」とWikipediaの履歴見ながら辿ってわかりましたが、完全に僕の仕業ですね。

> Wikipediaに書かれているコードがすでに広くコピペされて使われています。
なかなか恐ろしい話です。

yaneuraoyaneurao 2009/12/06 07:37 ↑真相発覚(゜Д゜)!?

2009-11-04 日本語が亡びるとき

[] 日本語が亡びるとき  日本語が亡びるときを含むブックマーク  日本語が亡びるときのブックマークコメント


日々、新しい言葉が生まれ続けている。そのこと自体に私は異存はないのだが、現代において本当に言葉意味が変遷するようなことがあるのだろうか。


例えば、「役不足」の意味をいまだに間違えて使っているような人がいるのだろうか?インターネットだと掲示板などでさんざん「本来の意味は〜」なんて書かれており、私はインターネットを始めてから、もうすでに何十回もそういう書き込みを見た。インターネットならば国語辞典だって調べることが出来、どちらの意味が正しいのかぐらいすぐに確認することも出来る。


インターネットアクセスできない人たちならともかく、インターネットアクセスできる人たちが間違った意味で覚えたり、使い続けるなんてことはあり得ないんじゃないかと私は思うんだが。


私は、小学生のころ、「夫婦喧嘩は犬も食わぬ」という表現を友達に使って、友達はそんな言い回しは知らず、「そんな日本語ないよねぇ」と寄って集って馬鹿にされた。いまなら、携帯があって、簡単にインターネットアクセスできるから、そういう友達に対して辞書に載っていることぐらい簡単に証明できるだろうし、「そんな日本語ないよねぇ」と馬鹿にされるどころか、「え?辞書に載ってんじゃん?お前ら馬鹿じゃねーの?」と即座に言い返すことだって出来るだろう。


本当にそういう風に何らかの日本語データベースに即座にリーチできるという環境において、間違った言い回しが広まってしまい、社会全体としてコンセンサスが形成されるということなどあるのだろうか。どうも私にはそれが信じられないのである。


しかし、それとは別に、使われなくなって事実上消えていく言葉というのはあるのかも知れない。


広辞苑大辞林には、その言葉がどの程度知られているのかという度合いが表記されていない。年代別に何%の人が知っていたかというアンケート結果みたいなものが載っているとすこぶる良いと思うのだが。例えば、英語で文書を書いて、ネイティブな人におかしい表現がないか見てもらうと、「この言い回しは普通しないよ」とか「この単語よりはこっちが一般的に通用する語なので」とかそういうアドバイスをもらうことが多々あるが、それは結局辞書(or 言語データベース)にそういう情報が無いのがいけないのだと思う。


Google検索すれば何件ヒットするかというアバウトな情報はわかるが、件数が多いからと言って誰もが知っている表現とは限らないので、やはり辞書にその単語や熟語の知名度的なものが併記されるべきだと思う。


安定して使えるopen日本語用のparser(構文解析)の実装やAPIがあるともっといいんじゃないかと思うんだ。そのparserが、仮に「パース君」という名称だったとして、曖昧性があったりすればエラーもしくは警告が出るようになっているといいと思う。「主語が一意に確定しません」だとか「30代の人の50%以上が知らない表現です」だとか「一つの文の途中で主語が暗黙のうちにすり変わっています」だとか「くびき語法は公式文書で使うべきではありません」だとか、そういう警告が出る。


そうすれば、社内規定で、

メールで文書は「パース君」の警告レベル3で警告が出ないこと

議事録などの保管文書は「パース君」警告レベル4で警告が出ないこと。

なんて定められたりして、ずいぶんと意志の伝達がしやすくなると思うのだが。

名無し名無し 2009/11/04 23:37 リーチ→リサーチですかね。
データベースにリサーチ、という表現も妙なので、そういう言い回しがあるのかもしれませんが。
無意識にATOKから広辞苑ひいて調べた自分が記事内容とマッチしてて面白かったのでご報告。

yaneuraoyaneurao 2009/11/04 23:54 「リーチ」はreach(到達する)の意味のリーチでございます。情報インフラが整備されていて「(情報源に)reachできる」のニュアンスで使いました。

名無し名無し 2009/11/05 01:03 ああ、なるほど……。大変失礼しました。
英和辞典も入れてるんですが、道具があっても使うのは人間、という好例を示してしまったようです……w
結局のところ、データベースがあっても大多数の人間に調べる習慣がなければ、ということなんでしょうね。

名無し名無し 2009/11/05 01:45 パース君作ってください

ChiharuChiharu 2009/11/05 08:40 中学生のころ国語の先生から「情けは人のためならず」は歴史上、相反する意味が広まったことがあり、言い回しとして機能しなくなった、と聞いたことあります。「いずれ自分に返る」と「見返り求めちゃいけない。」本来は前者の意味で、後に後者が広まったとか。そんな言葉、多いんでしょうか。

青柳臣一青柳臣一 2009/11/05 10:08 私は詳しくありませんが、コーパスとか言うのが近いように思います。さすがに年代別コーパスとかはまだ無いみたいですが。
それにしても「パース君」欲しいですw

tackmantackman 2009/11/05 10:36 自然言語のパーサは難しい上に、常用しても本文よりワーニングの分量が多くなったりしそう。そうなると結局使う人は… フォーマルな文章には便利かもしれませんけどね。

インターネットが普及しようが辞書を携行する時代になろうが言葉の「誤用」は無くならないと思いますよ。普段の会話や文章で知ってる単語もかたっぱしから辞書引く人はいないか、いても少数派なわけで。
あと小学生が「そんな**ないわーww」とか言うのはそう言うこと自体が目的なので、ケータイで辞書引きなんかしようものならケータイそのものを壊される可能性の方が…

paellapaella 2009/11/05 11:36 情報は色々な側面で切り取れるn次元の構造を成していると思いますから、パース君には情報^nのサイズのデータベースが必要になりそうな。

通りすがり通りすがり 2009/11/05 17:07 パース君…興味あります…。

通りすがり 通りすがり 2009/11/05 18:56 パース君で卒論書きたいです・・・

871871 2009/11/05 19:54 tb打たせていただきました。
文字というか文書はソフトウェアが作る時代になるかもしれない。。と思って記事を書いたら…といった感じでw

パース君の場合「日常会話用」とか「論文用」とか必要になりそうですね。量としては前者が圧倒的だから機械的に処理すると前者が文句なしに「一般的な語彙」のようになるような気がします。

MinonMinon 2009/11/05 21:38 パース君、実現すると面白そうですね。厳密さを要する契約書関連の文書で力を発揮しそうですね。
会話などでは方言が混じったりすると認知率が低いと警告されたり、複数地域の方言が混じったりすると地域に一貫性がありませんとか警告されたりするのかなぁ。

通縋通縋 2009/11/05 23:38 若人ノ言葉ガ乱レユク様ニ意見ヲ求メラレタ金田一春彦氏ハ、「言葉ハ時代ニヨツテ変化シテユクモノナノデス。乱レテイルノデハナク変化シテイルノデス」ト曰ヒ、是ヲ笑止サレタトイフ。

いもいも 2009/11/06 01:18 (´・ω・`)

これは何語ですか?:P (<-これとか、どう発音するんだろう・・・)

神経質&神経質& 2009/11/06 19:56 もっと会社運営の話、業界の話が聞きたいです。

ねこねこ 2009/11/07 09:03 sexypsf-0.4.5-r1-psp.tar.bz2
こちらのソースのリンクが切れているのですが、
もう一度公開して頂けませんでしょうか?

yaneuraoyaneurao 2009/11/07 09:26 ↑そのファイル、すでに手元のHDDには見あたりません。バックアップ用のメディアのどこかにはあるはずなんですけど未整理でして..すみません。

形態素子形態素子 2009/11/07 14:30 動的計画法で解けるサイズを超える問題について
学習率αをいつ0にする(学習終了かつ失敗非許容)にするかはなかなか悩ましいところ

ねこねこ 2009/11/07 17:49 そうでしたか、残念です。

dsystemdsystem 2009/11/26 15:51 「課金」という言葉はもう取り返しがつかないくらい誤用が広まっていますが
(「課金した」「課金しました」などで検索すると大量にヒットします)
この誤用が広まったのは某ネトゲの課金がきっかけだったと記憶しています。
このように、インターネットによって誤用が修正される間もなく
爆発的に広まるケースも充分にあり得ると思います。

また、当時この誤用に対して指摘する人もいましたが、それに対して
「通じてるんだからいいだろ、細かいことをうるさく言うな」
という反応が多く見られたことも付け加えておきます。

yaneuraoyaneurao 2009/11/26 18:08 ↑ああ、なるほど。(お金を払う側が)「課金した」は確かに本来の意味からすると誤用ですね。

「インターネットによって誤用が修正される間もなく
爆発的に広まった」のは、「課金される」の意味の自動詞型の言葉が日本語に無いのがいけなかったんですかね…。

 | 

1900 | 01 |
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2014 | 01 | 02 | 03 | 04 | 06 | 08 | 10 | 11 | 12 |
2015 | 01 | 02 |


Microsoft MVP
Microsoft MVP Visual C# 2006.07-2011.06
Connection: close