週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

http://twitter.com/kinaba/status/1210117338

かなり前の話ですが、母親にFIFOを教えたところ、野菜果物を取り出すときに「ファイフォー、ファイフォー」と歌いながら古いほうから取り出すようになりました。

配列をソートする際の各要素の平均移動距離が気になりました。N→∞でなら積分が使えて、全体の長さの1/3と求まります。 詳細はhttp://chasen.org/~taku/blog/archives/2007/02/post_822.htmlなど。

この値、正確にはN/3ではありません。たとえばN = 1ならソートする必要がないので移動距離は確実に0になります。N=2なら1/2になります。N/3としたときの誤差はどの程度あるのでしょう。

適当に計算したら正確な値が出ました。移動距離は(N2 - 1)/3N、全体の長さNで割ると 1/3 - 1/3N2になります。

予想より誤差が小さくて安心しました。ひょっとしてN/3 - 1とか、あるいはN/3 - √Nとかになるのではと心配していたので。

「素数はそれ以上分解できない」という意見がいくつかありました。

素数を素因数分解できない人は、例えば

任意の自然数Nについて、これを
N = Πpkak (pkは素数)
と素因数分解するとき、この自然数の約数の和Sは
S = Π((pkak + 1 - 1) / (pk - 1))
となる。
と簡単に言えなくて、Nが素数の場合とそれ以外の場合で場合分けをする必要があります。かわいそう。


追記@2/7/2009:二番目の式が激しく間違っていた(N = とか書いていた)ので修正。

コメントありがとうございます。

元々は(*v)[i]が非常に面倒という話を書きたかったはずなのですが、今読み返してみるとそこがすっかり抜け落ちていますね。

そもそもデリファレンスするときに(*a)と書くのが非常に面倒なのです。優秀な->オペレータはどこへ行ってしまったのでしょう。類似品に(*it)->hogeがあります。正直この表記はconst_iteratorよりもはるかに面倒です。const_iteratorは確かに長くて面倒ですが、使うときは補完するので問題はありません。一方で(*a)と書くのは割とキーボー ドに優しくないです。

そんなことを考えていたら、v->at(i)(*v)[i]と長さが大差なくて、むしろatの方が書きやすいことに気づいてしまったといったところです。そんな驚きを書きたかったのですが、原文ではまったくもってそこが抜け落ちていますね。反省。

コメントをくださった人へのまとめ。

  • atメソッドは範囲外アクセスに対して例外を投げます。operator[]はチェックをしません。
  • vector.dataはヘッダファイルから発見したので例として上げましたが、私の中では完全にstring.dataと混同していました。
  • atはいつ入ったのでしょうか。c++98?
  • atがどのくらい遅いのか書いたほうがいいかもしれませんがあいにく今は眠いです。
  • vectorはメモリ上に連続することが保証されています。More Exceptional C++のp. 47, Item 7の解説にあります。あるいはHerb Sutterのコメントかな。

vector<T>* v;を受け取ってインデックス参照をする場合、(*v)[i]v->at(i)のどちらがより望ましいのでしょう。私ならかなりの確率でvector<T>& ref = *v;としてrefをつかいますが。

さらにstlのvectorのページにはatやdataが載っていません。ここを参照するのに危険があるとは思いませんでし た。

stl-manualにも載っていません。c++/bits/stl_vector.hを見れば確実ですが。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。