きまぐれ日記: Schwartzian Transform でランダムシャッフル
Schwartzian Transform を使って配列をシャッフルする話をみて、なるほどな～と思いつつも、よくよく考えてみるとこれは2つの意味で駄目です。 1. 計算量が O(n * log(n)) であること。 2. ランダムにシャッフルできない。 1. は説明するまでもないので、2の理由を考えてみます。 まず、rand() が 0..k-1 までの k種類の整数から 1 つ数値を返すものとします。配列のサイズが n の場合、 weightの並びの場合の数は k^n 通り存在します。ところが、配列の順列の場合の数は n! です。 ここで何か矛盾点があるように思えてきます。 実際に k = 2, n = 2 の場合を考えて見ましょう。この場合、サイズ2の配列をシャッフルするんですから、 要素を入れ替える場合と入れ替えない場合が 1/2 の確率で出現するのが正しいシャッフルです。 k =
Libicpc - nya3.jp
libicpc チーム kkntkr / Unknown による、ACM-ICPC 向けのアルゴリズムの実装をまとめたページです。 基礎 テンプレート マクロ 計算 ビット演算 実数比較 幾何 基礎 データ構造 内積・外積 回転方向関数 射影 面積・体積 円と円の共通部分 多角形の面積 交差 円と円の交点 円と直線の交差判定 円と直線の交点 凸多角形と線分の包含判定 多角形と点の包含判定 直線と直線の交差判定 直線と直線の交点 直線と線分の交差判定 線分と点の交差判定 線分と線分の交差判定 距離 最遠点対 直線と点の距離 直線と直線の距離 直線と線分の距離 線分と点の距離 線分と線分の距離 多角形 凸包 凸多角形のクリッピング その他 アレンジメント ダイス 三次元幾何 直線と直線の距離 グラフ 基礎 データ構造 最短路 Bellman-Ford Dijkstra Warshall-Flo
javascript - シャッフルシャッフル : 404 Blog Not Found
2006年08月30日18:30 カテゴリLightweight Languages javascript - シャッフルシャッフル なるほど。Schwartzian Transformの意外な利用法だなあ。 snippets from shinichitomita’s journal - JavaScriptの配列をsort関数でシャッフルする Array.prototype.shuffle = function() { return this.map(function(a){ return { weight: Math.random(), value: a } }) .sort(function(a, b){ return a.weight - b.weight }) .map(function(a){ return a.value }); } でも、実践ではどうだろう。調べてみた。
JavaScriptの配列をsort関数でシャッフルする - snippets from shinichitomita’s journal
あえてsort関数を使う方法でシャッフルしてみる。比較関数自体がランダムな値を返す場合と違って、これなら偏らない。 Array.prototype.shuffle = function() { return this.map(function(a){ return { weight: Math.random(), value: a } }) .sort(function(a, b){ return a.weight - b.weight }) .map(function(a){ return a.value }); }とりあえずFirefox1.5でOK。IEでもmap関数を自分で定義してやれば大丈夫のはず。 置換によるシャッフルと違って、weight値のところを適当に変化させれば、要素ごとに重みづけてのシャッフルもできると思う。たとえばよく聞く曲は優先的に前の方に持ってくるとか、その逆と
更新履歴兼雑記 - 音楽シャッフルクイズ
http://www.hyuki.com/d/200510.html#i20051020190000 しない。 以下 N=size。ありえる順列は N! 個。SWAPの全組み合わせは N^N 。よって N^N/N! 通りの組み合わせができれば正しくシャッフルされていると言える (コメントで指摘いただいた通り、「正しくシャッフルされていると言えるためには N^N/N! 通りの組みあわせができなければならない」が正しいです…) が、これは N>=3 で整数ではない。 なぜなら、 N^N/N! が整数になるには 1 から N の全ての n に対して N/n が割り切れなければならないが、 N/N-1 は偶奇の違いから N>=3 で常に割り切れない。 (翌朝追記。ここもひどい… N/N-1 が割り切れないのは偶奇は本質的じゃない。 N が 奇なら 2k+1/2k = 1+1/2k で割り切れない、
[結] 結城浩の日記「購入より購読・プログラムよりサポート・完成より進化」という傾向に対するネーミング
目次 2005年10月31日 - まだ名前のない実験ページ / 2005年10月30日 - 「再帰的な木を描くJavaのソースコード」を公開 / 「さまざまな方のための祈り」を更新 / 2005年10月29日 - 「ミルカさんとフィボナッチ数列」のLaTeXファイル公開 / 2005年10月28日 - わたっていく言葉 / ながれていく時間 / 仕事 / みなさんからのメッセージを読む / 『改訂第2版Java言語プログラミングレッスン』無料プレゼント抽選 / 2005年10月27日 - 夜 / 本 / 朝 / 2005年10月26日 - 夜 / 自分の理解を確かめて学習するということ / 朝 / 2005年10月25日 - 日記ダイジェストを更新 / 必要条件と十分条件 / 仕事 / おはようございます / 2005年10月24日 - コクヨのSlimB5ノートを使った感想 / 2005
Arrays#sort - てきとうなメモ
JavaにはArrays#sortというメソッドがあって配列をソートすることができる．ソートする対象がプリミティブ型だとquick sortで実装され，オブジェクトだとmerge sortで実装している．オブジェクトのソートはstableであるという仕様のためだと思われる． さらに，どちらの場合も配列のサイズが小さい場合はinsertion sortで実装されている．merge sortもquick sortも分割して再帰的に実行されるため，分割された配列の要素数が小さくなった時点で，insertion sortに切り替わっている．insertion sortはO(n^2)なんだけどもシンプルな実装なので短い配列の場合はそっちの方が効率がいいということだろう． その他いくつか面白いなと思った点． quick sortのpivot 配列を2等分(サイズが大きい場合は8等分)して，配列の両端と
グラフ理論ライブラリのJGraphTを使ってみた - kaisehのブログ
JGraphT JGraphTは、Javaのグラフライブラリです。グラフの描画ではなく、グラフ理論のモデルとアルゴリズムの方にフォーカスしています。とても使いやすかったので、紹介してみます。 無向グラフ UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>( DefaultEdge.class); g.addVertex("a"); g.addVertex("b"); g.addVertex("c"); g.addEdge("a", "b"); g.addEdge("b", "c"); System.out.println(g.vertexSet()); System.out.println(g.edgeSet()); System.out.println(g.edgesOf("c"));
キャッシュアルゴリズム - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "キャッシュアルゴリズム" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年8月) キャッシュアルゴリズム（英: cache algorithm）は、コンピュータ上で情報を格納するキャッシュを管理するプログラムまたはハードウェア構造を最適化するアルゴリズム群。キャッシュが一杯になったとき、このアルゴリズムで新たな情報を格納するための場所を選択し確保する。置換アルゴリズムあるいは置換ポリシーとも。 キャッシュのヒット率（hit rate）とは、探しているデータがキャッシュ上で見つかる率（頻度）である。キャッシュサイズを増やさずにヒ
いろいろなソートアルゴリズム
<body> <p>このページにはフレームが使用されていますが、お使いのブラウザではサポートされていません。</p> </body>
Binomial heap - Wikipedia
In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap), as it supports merging two heaps in logarithmic time. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps.[1] Binomial heaps were invented i
DBの基本を勉強したい人へオススメする本 - ｜ω・)ノ ＜黒猫の気まぐれ日記
最近，学部生に「DBについて勉強したいんですが何かオススメ参考書はありますか？」と聞かれた．私自身も，DBについて勉強したいなぁと感じていた．というのも，この頃院の授業で正規化の辺りを突っ込んでやったり，授業では習わない類のクエリを書いたり，数万件以上のデータを処理したり・・・とやっているうちにどうにも自分の知識不足を感じたからだ．学部の時は授業で理論の基本的なところを習って，あとはDBを利用したちょっとしたWebサービスを作ったくらいで，ちゃんと理解してこなかったから仕方ないといえばそうなんですが。。。まぁせっかくなので，DB関係の本で私がオススメかなーと思う本を挙げておきます(・ω・*) ●はじめの一歩DBについて勉強しようと思って一番最初に思い出したのは「マンガでわかるデータベース」という本．マンガでわかるデータベース作者: 高橋麻奈, あづま笙子, トレンドプロ出版社/メーカー:
Leo's Chronicle: ぜひ押さえておきたいデータベースの教科書
先日のエントリで少し話したのですが、僕が在学していたときの東大にはデータベースを学ぶためのコースというものがありませんでした（DB関係の授業は年に１つか２つある程度。現在はどうなんだろう？）。そんなときに役だったのは、やはり教科書。読みやすいものから順に紹介していきます。（とはいってもすべて英語の本です。あしからず） 一番のお薦めは、Raghu Ramakrishnan先生 (現在は、Yahoo! Research) の「Database Management Systems (3rd Edition)」。初学者から研究者まで幅広く使えます。データベース管理システム（DBMS）の基本概念から、問い合わせ最適化、トランザクション管理など、これらを実装・評価するために必要な、「DBの世界での常識」が、丁寧な語り口でふんだんに盛り込まれています。この1冊を読んでおけば、DBの世界で議論するための
はてなダイアリーのようにキーワードを自動でリンクするアルゴリズムを知りたいです。…
はてなダイアリーのようにキーワードを自動でリンクするアルゴリズムを知りたいです。単純に考えると、①キーワードのリストを持っておく。②対象となる文章に、あるキーワードが含まれているかを検索する。③「②」の検索をキーワードの数だけ繰り返す。ということになると思います。1万語のキーワードリストがある場合、1万回の検索を行うことになり、たとえば多数の投稿がある場合は効率も悪いですし負荷も掛かります。もっと効率のいいアルゴリズムがあるのでしょうか。
MA38SU - Hotels in Bangkok - best rates and availability of selected accommodations
wp.Vicuna Ext. The template VICUNA WordPress theme wp.Vicuna for CMS tools is available. Here, we have released the theme wp.Vicuna Ext. , Which makes customization easier . Vicuna Adaptor We have released Vicuna Adapter , an extension plug-in for wp.Vicuna Ext . Comments:10 rikuto 08-10-15 (Wed) 13:00 Nice to meet you, if you newly introduce WordPress 2.6.2, upload wp.Vicuna Ext. Ver.1.58 to them
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Computer Graphik UdS: Seminar
atso-net.jp
http://www.fumiononaka.com/TechNotes/Flash/FN0212002.html
Binomial Heap
きまぐれ日記: はてなキーワードを高速に付与