中央値の中央値 - Wikipedia
中央値の中央値（ちゅうおうちのちゅうおうち、英: median of medians）とは、クイックセレクトに基づく選択アルゴリズムのことである。k番目に大きい要素を選択するための最悪計算時間が線形になることが特徴である。 このアルゴリズムでは、最初におおよその中央値を線形時間で探索し、その値をクイックセレクトでのピボット値とする。つまり、（漸近的な）おおよその中央値選択アルゴリズムを使って、（漸近的な）一般値選択アルゴリズムを構築したものである。 このアルゴリズムは、マヌエル・ブラムら[1]によって開発されたもので、著者の名字の頭文字を取ってBFPRTとも呼ばれる。この原著では中央値の中央値アルゴリズムをPICKと呼び、クイックセレクトをFINDと呼んでいた。 概要[編集] クイックセレクトは分割統治法であり、計算の各段階で、残っている探索対象の要素が個の場合にの計算時間を必要とする。そ
QuickSort Killer
We use your LinkedIn profile and activity data to personalize ads and to show you more relevant ads. You can change your ad preferences anytime.
IPアドレスをsortコマンドで並び替える | ex1-lab
IPアドレスをsortコマンドで昇順に並び替える「sort -V」 IPアドレスを記載されている下記のようなテキストファイルがある場合に、sortコマンドを利用してIPアドレス順に並べるには、「-V –version-sort」を使えば簡単にIPアドレスを昇順で並び替えできます $ cat ip.txt 192.168.0.1 202.145.12.1 192.168.30.1 34.23.10.1 221.111.49.1 168.192.0.1 12.132.12.1 20.1.2.1 30.1.11.1 230.2.1.1 「sort -V」を使って下記のように並び替えをおこなってみます。IPアドレスが昇順で並び替えができます。 「-V –version-sort」のオプションは、manコマンドで確認すると「自然な (バージョン) 数字順でソートする」となります。 自然なバージョンで
時間順にソート可能なUUIDv6, UUIDv7, UUIDv8の提案仕様 - ASnoKaze blog
IETFに「New UUID Formats」という提案仕様が提出されています。 これは、時系列順にソート可能なUUID version 6, UUID version 7, UUID version 8を新しく定義するものです。 詳しい背景は提案仕様にゆずりますが、ULIDを始めとして、時系列順にソート可能な一意な識別子を利用したいというユースケースがあります。例えば、データベースのキーとして使えば、ソートせずとも順番に並びますし、書き込む際も順々に書き込めるのでデータアクセスが局所的になります。 今回は簡単に、それぞれのUUIDのフォーマットを眺めていきます。なお、フォーマットは異なりますが、バージョンを示す値は同じ位置にあります。 UUIDv6 UUIDv6は128bit長で、UUIDv1と似てるフォーマットを取ります。 1582年10月15日(グレゴリオ暦)からの100ナノ秒単位で
sort コマンドで大容量テキストをソートする - Qiita
概要 テキストをソートする sort コマンド. 気軽に使えて優秀なコマンドだが, 大容量のデータに耐えられる 点も魅力の一つである. 本稿ではこのポイントを紹介したい. 確認環境 以下の sort コマンドの挙動を Mac OS X 上で確認した. 本稿のコマンド例はすべて GNU coreutils sort を用いたものである. GNU coreutils 8.31 2.3-Apple 大容量のテキストをソートしてみる sort コマンドは, かなり大容量のテキストを入力してもソートを完遂することができる. 完遂するという要件を満たすだけであれば, マシンスペックにほとんど依存しないことがポイントだ. 試しに大容量テキストをソートしてみよう. 以下に 10,000,000 レコードの乱雑なテキスト 1 をソートする例を示す. $ time (base64 /dev/urandom |
Smoothsort Demystified
Last Major Update: January 7, 2011 A few years ago I heard about an interesting sorting algorithm (invented by the legendary Edsger Dijkstra) called smoothsort with great memory and runtime guarantees. Although it is a comparison sort and thus on average cannot run faster than Ω(n lg n), smoothsort is an adaptive sort, meaning that if the input is somewhat sorted, smoothsort will run in time close
flint blog: 「選択アルゴリズム」と「中央値の中央値」
ある小説の登場人物、あるいは、あるアーティストの曲といった集合について考えるとき、「それらの中で最も好きなものはどれですか?」という問いに答えることは (甲乙付け難くて悩むケースもあるかも知れませんが) 比較的簡単です。 しかし、「2番目に好きなものは?」「3番目に好きなものは?」...といった具合に質問を続けていくと、どんどん回答が困難になっていくはず。 最も嫌い (好きでない) ものについては、好きでないものと同じように簡単に答えられるので、最も特定が困難なのは、好きな (あるいは嫌いな) 順に並べたとき、そのシーケンスの中央に位置する要素だと言えるでしょう。 私はこれまで、プログラミングにおいてもこれと同様の問題が存在する、即ち、ある配列 (要素数n )について特定の指標に沿っての並べ替え (ソート) を行ったときに中央あるいはその付近に配置される要素を特定するには、ソートそのものと
webdesign-dackel.com - このウェブサイトは販売用です！ - webdesign dackel リソースおよび情報
This webpage was generated by the domain owner using Sedo Domain Parking. Disclaimer: Sedo maintains no relationship with third party advertisers. Reference to any specific service or trade mark is not controlled by Sedo nor does it constitute or imply its association, endorsement or recommendation.
Linux/UNIXのsortコマンドでIPアドレスのソートを行う | 俺的備忘録 〜なんかいろいろ〜
2017/02/12 追記 以下の内容を記述していた時は知らなかったのだが、GNU sortを使っているのであれば普通に「-V(--version-sort)」で処理するほうがいい。 (Mac OS Xだとgsortが必要) sort -V blacknon@BS-PUB-DEVELOP:~$ cat test.txt 192.168.0.102 192.168.0.8 192.168.0.97 192.168.0.68 192.168.0.99 192.168.0.66 192.168.0.24 blacknon@BS-PUB-DEVELOP:~$ sort -V test.txt 192.168.0.8 192.168.0.24 192.168.0.66 192.168.0.68 192.168.0.97 192.168.0.99 192.168.0.102 その他、sortコマンドに
[Perl]連想配列のソート - ソースコードライブラリ
%nedan = ( "bag", 15000, "cup", 800, "watch", 6000, "tv", 38000, "camera", 25000 ); print "キー(商品名)で並べ替え\n"; foreach(sort keys %nedan){ printf "%6d = %s\n",$nedan{$_},$_; } print "\n値(値段)で並べ替え\n"; foreach(sort {$nedan{$a} <=> $nedan{$b}} keys %nedan){ printf "%+6s = %6d\n",$_,$nedan{$_}; } 連想配列のソートです。keys %nedanで連想配列のキーを配列として受け取ります。 あとはsort関数に渡してやります。キー名のソートの場合は単純にsort keys %nedanでソートされたキー名を得ることができ
MySQLで昇順ソートする時、NULL を最後に持ってくる - Web Tech Log by 1KB
Web開発、Webデザイン、SEO、携帯コンテンツなどWebにまつわるテクノロジーを追っかけるブログ。旧名「Web屋に復帰した人間のリハビリ日記」 はまったのでメモ。 某Webアプリを「スパゲッティPHPスクリプト+SQLite」から「CakePHP+MySQL」の環境に移植作業をしてました。ある情報を一覧表示したときの並び順が、移植元のアプリと違うのでorder句にあれこれ試してみてもうまくいきません。 しょうがないのでGoogle先生に聞いてみた。どうやら、DBMSによってNULLの値が上に来たり下に来たりするとのこと。昇順ソートの場合、SQLiteでは下に来て、MySQL上に来るらしい。こいつが原因だ（つーか常識？）。 MySQL で NULL を一番最後にして昇順にソートする 上記エントリーを参考にしました。いつもありがとうございます。 答えとしてはorder by 句に ‘IS
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
巨大なテキストファイルを高速に「シャッフル」するrubyワンライナ - 中野智文
巨大なテキストファイル（例えば500M、すみません、それほど巨大ではありません。）をランダムソート（例えばsort -R）しようとするとソートのアルゴリズムが走るためか、非常に時間がかかる。ところがランダムソートは厳密にはソートする必要がないはずである。そこでバケットソートのバケツをランダムに行うことを提案する。その方法は、複数の一時ファイルを作成し、それらのファイルにランダムに格納し、それを結合することで、トランプのような「シャッフル」を行うことにする。それが下記のrubyワンライナ。 ruby -r tempfile -ne 'BEGIN{R=1000;$ta=Array.new(R){|i|Tempfile.open(i)}}; $ta[rand(R)].print $_; END{$ta.each{|t|t.close;print open(t.path).read}}' R=10
漢数字が数字順にソートされない理由を調べてみた - give IT a try
はじめに：「なぜ漢数字は数字順に並ばない！？」 先日、こんなツイートをしたところ、結構たくさんの人にリツイートされました。（執筆時点で50件以上） 「漢数字はソートしても数字順に並ばない」という事実を生まれて初めて知った。まさかのサプライズ。 pic.twitter.com/Eqx3ltIfHs— Junichi Ito (伊藤淳一) (@jnchito) 2014年11月27日 「なぜ漢数字は数字順に並ばないのか」という問いに対して、表面的な回答をするなら「数字順に並ばないのは、数字の大きさではなく文字コード順でソートされているから」ということになります。 いや、もちろんそれはわかってるんです。 問題は「そもそもなんで数字順に文字コードを振らなかったの！？」ということです。 感覚的には「一郎、二郎、三郎」って並んでほしいじゃないですか。でも、プログラム上でソートすると「一郎、三郎、二郎」
【MySQL】ランダムにレコードを取り出す方法のひとつ at softelメモ
問題 MySQLで、ランダムに行を取り出したい。 order by rand() でいいの？ 答え よくあるのがこんな方法。 select * from t order by rand() limit 10; レコード数が少ない場合は問題ない。 レコード数が何万行とある場合は大問題。order by句にrand()を使うと、全レコード数分のrand()を算出して、全レコードでソートをかける。ものすごく大変そうなのは容易に想像できる。 そこでwhere句にrand()を使う方法。 10万レコードから100件欲しいときは、100/100000 = 0.001なので、こうすると理論上100件取れる。 select * from t where rand() <= 0.001; 理屈はそうだけど、実際はちょっと余裕を持たせて、こうするとよい。 select * from t where rand(
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
sort and uniq commands not running as expected when run though cron
ls gives me different sort orders during a cron job
Man page of SORT
Files in project not sorted alphabetically : IDEA-216003