揺動散逸日記

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としたときの誤差はどの程度あるのでしょう。

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

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

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

任意の自然数Nについて、これを

N = Πp_k^a_k (p_kは素数)

と素因数分解するとき、この自然数の約数の和Sは

S = Π((p_k^{a_k + 1} - 1) / (p_k - 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のコメントかな。
  • どこかにもっとofficialなリソースがあった記憶がありますが、今のところ見つかっていません。以下追記:
    • Must elements of a vector be contiguous?
    • 採択
    • via http://d.hatena.ne.jp/phoenix_hiro/20090114/1231949033, thanks!

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

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

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