https://twitter.com/kinaba のログ (twilog の方が便利です。)
| http://www.amazon.co.jp/s/?rh=k%3A%22%22%2Cn%3A52033011&sort=-price Amazonの価格順ソート、大抵のカテゴリで1677215円が並ぶので24bit上限が設定されてるのかと思ったら、http://www.amazon.co.jp/dp/4822216020 超えてるものもあるな。 | |
| @gusmachine Flash10のときもOpera10のときも問題になっていた記憶があります。http://d.hatena.ne.jp/edvakf/20090527/1243449333 このせいで今でも見るのが面倒なFlashがいくつか… | |
| @sinya8282 あ、Sは完全にわかってるとしてよいです。動機は https://t.co/ZQCo8DWf で、書いたコード(≒S)と、正しい実装はよくわからんがせいぜいこの程度の複雑さだろという見積もり(≒n) から、必要なテストケースの個数を出したい感じです。 | |
| @sinya8282 最大でもn文字未満全部試せば足りるような気はするんですが、regularであるというのを使うともっと減らせるという事実はないかなー等考えてます（もしかするとちょっと考えると明らかに無理かもしれないですけど | |
| S=空集合だと全探索が必要。もっと複雑な言語の方が楽。まずは言語に落とした方が簡単かと思ったけど逆に情報量足りない気がしてきた。いきなり関数を考えた方がいいのか。（寝る） | |
| Pessimal Algorithms and Simplexity Analysis 読んでる http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.9158 これ最遅ソートの話ではないか！"Sorting can be solved in Ω(n^{log(n)/(2+ε)}) time"！ | |
| 最遅ソートとは http://www.kmonos.net/wlog/122.html#_2142110912 明かな無駄をするというズルをせずにソートの遅さを極めるとどうなるか考える遊びである。「明かな無駄」とは一体何かの適切な定義を見つけられるかがポイントで、自分の考えた基準ではΩ(n^2)の遅さが限界でしたが多項式超えてる凄い | |
| "simplexity" という単語で検索することを思いつかなかったのは敗北するしかない。あと Slowsort という項目は何故ドイツ語版Wikipediaにだけあるのか http://de.wikipedia.org/wiki/Slowsort | |
| ちなみにさっきの論文は Funny TCS-related papers etc? http://cstheory.stackexchange.com/questions/3111/funny-tcs-related-papers-etc というスレが上がってたのを見て知りました。 | |
| Knuthのトイレットペーパー問題とかいいですね。「世の中には二種類の人間がいる。トイレットペーパー置きが２巻きあるトイレ個室に入った時に、残りが多い方から使う人間と、少ない方から使う人間とだ…！」という記事 http://cstheory.stackexchange.com/questions/3111/funny-tcs-related-papers-etc | |
| そして Simplexity の論文は定義は別にフォーマルに詰めてなかった。残念。 |