中央値の中央値 - Wikipedia
中央値の中央値（ちゅうおうちのちゅうおうち、英: median of medians）とは、クイックセレクトに基づく選択アルゴリズムのことである。k番目に大きい要素を選択するための最悪計算時間が線形になることが特徴である。 このアルゴリズムでは、最初におおよその中央値を線形時間で探索し、その値をクイックセレクトでのピボット値とする。つまり、（漸近的な）おおよその中央値選択アルゴリズムを使って、（漸近的な）一般値選択アルゴリズムを構築したものである。 このアルゴリズムは、マヌエル・ブラムら[1]によって開発されたもので、著者の名字の頭文字を取ってBFPRTとも呼ばれる。この原著では中央値の中央値アルゴリズムをPICKと呼び、クイックセレクトをFINDと呼んでいた。 概要[編集] クイックセレクトは分割統治法であり、計算の各段階で、残っている探索対象の要素が個の場合にの計算時間を必要とする。そ
PHPとPythonとRubyの連想配列のデータ構造が同時期に同じ方針で性能改善されてた話 - hnwの日記
PHPとPythonとRubyの連想配列のデータ構造がそれぞれ4〜5年ほど前に見直され、ベンチマークテストによっては倍以上速くなったということがありました。具体的には以下のバージョンで実装の大変更がありました。 PHP 7.0.0 HashTable高速化 (2015/11) Python 3.6.0 dictobject高速化 (2016/12) Ruby 2.4.0 st_table高速化 (2016/12) これらのデータ構造はユーザーの利用する連想配列だけでなく言語のコアでも利用されているので、言語全体の性能改善に貢献しています1。 スクリプト言語3つが同時期に同じデータ構造の改善に取り組んだだけでも面白い現象ですが、さらに面白いことに各実装の方針は非常に似ています。独立に改善に取り組んだのに同じ結論に至ったとすれば興味深い偶然と言えるでしょう2。 本稿では3言語の連想配列の従来実
flint blog: 「選択アルゴリズム」と「中央値の中央値」
ある小説の登場人物、あるいは、あるアーティストの曲といった集合について考えるとき、「それらの中で最も好きなものはどれですか?」という問いに答えることは (甲乙付け難くて悩むケースもあるかも知れませんが) 比較的簡単です。 しかし、「2番目に好きなものは?」「3番目に好きなものは?」...といった具合に質問を続けていくと、どんどん回答が困難になっていくはず。 最も嫌い (好きでない) ものについては、好きでないものと同じように簡単に答えられるので、最も特定が困難なのは、好きな (あるいは嫌いな) 順に並べたとき、そのシーケンスの中央に位置する要素だと言えるでしょう。 私はこれまで、プログラミングにおいてもこれと同様の問題が存在する、即ち、ある配列 (要素数n )について特定の指標に沿っての並べ替え (ソート) を行ったときに中央あるいはその付近に配置される要素を特定するには、ソートそのものと
foreach
ここでは詳細には触れませんが、 当サイト上にある「C++ STL」や「アルゴリズムとデータ構造」でもコレクションについて簡単な説明がありますので、興味のある方はそちらをご覧ください。 また、コレクションについてより詳しく知りたい方は検索エンジンで「データ構造 アルゴリズム」などをキーワードにして検索してみてください。 ここでは例として連結リストを示します。 あくまで例として示すだけなので、単純な実装方法を取っています。 (本来はもう少しちゃんとした実装の仕方をしないとだめ。) using System; using System.IO; /// <summary> /// リストのノード /// </summary> class Node { public int elem; public Node next; public Node() : this(0, null){} public
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
すごく簡単なアルゴリズムがphpで書けなくてつらい - Qiita
ある条件でソートされているIDのリストを与えられて、なんとなく近い範囲でマッチングさせたいという要件があった。配列からの任意の要素の取り出しは O(n) だけど、末尾や末尾から固定した範囲の要素に限って言えば O(1) なので、後ろの方からマッチングさせながら要素を取り出していけば O(n) でマッチングできるはず。 なんにも難しいことは無い話で、 Python で書けばこうなる。 list.pop() が末尾からのインデックス (-1 が最後の要素を表す) を許すのが地味に便利だ。 # coding: utf-8 def match(seq, r=100): from random import randint # 奇数個の時に先頭周辺の要素がボッチになるのが嫌なら、先に後ろの方の # 要素を取り除いて偶数にしておくこと. while len(seq) >= 2: # 引数を省略すると末
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
stdClassを連想配列に変換する程度の関数