トップ «前の日記(2009-12-20) 最新 次の日記(2009-12-23)» 編集

はじめてのにき

ここの位置付け

2004|11|
2005|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|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|

ToDo:


2009-12-21

_ splay tree

なんかこれよくわからんのは、 なんで一回でルートまで持っていっちゃうのかなーということ。 参照されるたびに splay を 1 step だけやるとかの方が 直感的に(本当に完全に直感だけど)平均的に速そうなイメージがあるのだけど。

ちゃんと調べたらどっかに書いてあるんだろうけど

(01:11)

_ .pro

http://yhara2.blogspot.com/2009/10/pro.html

golfer.pro とか取って Java で import pro.golfer.saru とかやりたいなーとか思ったけど 取られていた

(01:12)

本日のツッコミ(全4件) [ツッコミを入れる]
_ kinaba (2014-05-24 03:16)

償却時間計算量(最悪な操作列が来た時の平均計算量)を O(log(n)) にしたかったからじゃないかと思ってました。例えばsplayを1stepだけだと、木のバランスが一番とれてない状態で一番深いところにあった要素にn回連続アクセスされるとO(n^2 / n)=O(n)の償却計算量になってしまう。

途中適当なところでsplayを止めるのはsemi-splay treeとかいう名前でいくつかのバリエーションがあるみたいですが、僕もよくわかりません。

_ shinh (2014-05-24 03:16)

あーなるほど。えーとでもすぷれー木をバランスが一番とれてない状態にするのって大変そうな気がするんですが、えーとそうなることもあるんですかね…

_ kinaba (2014-05-24 03:16)

Wikipediaとかにありますが、小さい方から順番に1個1個アクセスしていくと一番崩れた状態になります。わりとよくある状況ではないかなーと

_ shinh (2014-05-24 03:16)

あーなるほど。 root まで持ってく splay を前提に小さい方から順番にアクセスしていくと悲惨な状態になるのはわかるのですが、例えば splay を 1step だけやる実装が前提ならそこまで悲惨な状態にならないような。 splay を 1step だけやる実装が前提なら、 0,1,2,3,4,... と入ってる tree に、 0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,... とアクセスしていくと崩壊する感じですかね。

お名前:
E-mail:
コメント:
人生、宇宙、すべての答え
本日のリンク元

2009年
12月
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
1.shinh(2014-05-24 03:16) 2.kinaba(2014-05-24 03:16) 3.shinh(2014-05-24 03:16)
search / home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h