MySQLのfilesortは何ソートで行われているのか - $shibayu36->blog;
最近、CourseraのArgorithms, Part1という講義を受けている。そこでソートの講義を受けて、そういえばMySQLのORDER BYでfilesortになったときってどのソートが使われているのだろうと気になってきたので調べてみた。 調べてみると非常に難解で、結局いまいち分からなかったが、今の段階の調べた内容をひとまず書いておく。MySQLのコードを読んだのも初めてで、しかもちゃんと読み解くことができなかったので、情報が間違っている可能性も非常に高い。間違ってたら指摘してもらえるとうれしいです。 調査結果 最初に調査結果を書いておく。たぶんこれは非常に単純化したもので、詳しく見るともっといろいろチューニングされてそう。 sort_buffer_size以内のメモリ量でソートが可能な場合、メモリ内でのみソートされる ソートにsort_buffer_size以上のメモリが必要な場
Realm Objective-C & Swift 2.2: スレッド間のオブジェクトを受け渡し、関連による並べ替えなどをサポート
Realm Objective-C & Swift 2.2: スレッド間のオブジェクトを受け渡し、関連による並べ替えなどをサポート これまでのRealmの設計が目指していたもののひとつに、一貫性があり、わかりやすいスレッドモデルを提供するということがありました。このたび、 Realm Objective‑C および Realm Swift 2.2より、安全にスレッド間をまたいでオブジェクトを受け渡すことができる仕組みを用意しました。また関連のプロパティを並べ替えに使用することがこのバージョンからできるようになりました。その他、同期に関する改善と不具合の修正が含まれます。 スレッドに従う 本日より、Realmでは複数のスレッド間でオブジェクトを扱うことがさらに簡単になりました。これまでのマルチスレッドの対応は何年もの間の絶え間ない議論の果てに下された決断で、意図的なものです（なぜなら、 マル
ダンスで覚えるソートアルゴリズム - 強火で進め
こんな動画が有るって事はハンガリーでは「踊って覚えるアルゴリズム」って感じの本が出てそうな感じですねw インサーションソート 挿入ソート - Wikipedia http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88 バブルソート バブルソート - Wikipedia http://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88 セレクションソート 選択ソート - Wikipedia http://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88 シェルソート シェルソート - Wikipedia http:
sort と uniq でさくっとランキングを出力する - blog.nomadscafe.jp
知っている人多いと思うけど、よく使うイディオム $ .. | sort | uniq -c | sort -nr 「sort | uniq -c」で重複行をカウントでき、さらに「sort -n」で行を数字と見なしてソートすることで重複行のカウントで並べなおすことができます 例えば、Webサーバのaccess_logからよくアクセスしてくるIPアドレスを集計してランキングを表示するには以下のよう書けます $ tail -10000 access_log |cut -f 1 -d ' ' | sort |uniq -c|sort -nr|head -10 209 207.46.204.192 203 59.106.108.114 202 66.249.69.108 171 199.59.149.168 137 78.46.45.35 129 66.249.69.65 120 66.249.69
Big Sky :: コードリーディング2日目。sort
« 最近の GNU CoreUtils を使っている限り rm -rf / は --no-preserve-root 付けないと / は消せない | Main | Learn Vim Progressively » 昨日は rm を読みました。今日は、ずいぶん前に「GNU textutilsに入ってるsort(1)にはコア数によって動的にスレッドを生成してソートする処理が入ってるのでそういうの興味ある人はコード読むといいと思います。」と言ってた部分を読もうと思います。 ソースは昨日と同様に CoreUtils の src/sort.c です。 ソートのメイン処理は main の一番下の方にあって if (mergeonly) { struct sortfile *sortfiles = xcalloc (nfiles, sizeof *sortfiles); size_t i; for (
algorithm - bucket sort - 比較しなければソートは相当速い : 404 Blog Not Found
2012年01月11日07:00 カテゴリアルゴリズム百選Math algorithm - bucket sort - 比較しなければソートは相当速い 珠玉のプログラミング Jon Bentley / 小林健一郎訳 絶賛風邪こじらせ中につきコードと戯れることに。 新ソートアルゴリズム「配列挿入ソート」だ! - hp12c その名も「配列挿入ソート」! すでに突っ込み入ってるけど、それ、もしかしたら人類最古のアルゴリズムだから。 最古にして最速? おそらくプログラムを組んだことがない人でも「誰にも教えられずに」知った「天然の」アルゴリズムの筆頭に来るのがこのバケットソートではないでしょうか。 ソートしたいものに適当に番号を振っておく 番号がついたバケツを用意する ソートしたいものの番号がついたバケツにそれを放り込む 必要があればバケツの中身を同じやり方でソートする 番号順にバケツの中身をぶち
オトコのソートテクニック2008
今日は仕事納めだったので、一年の締めくくりとしてMySQLにおけるソートの話でもしようと思う。 インデックスを利用しないクエリで最もよく見かけるもののひとつは、ORDER BYを用いたソート処理だろう。もし、ソート処理においてインデックスを用いることが出来れば、MySQLは結果を抽出してから結果行をソートするのではなく、インデックス順に行を取り出せば良いので高速にソート処理することが可能になる。特に、LIMIT句やWHERE句を用いて行の絞り込みを行う場合は効果が絶大である。しかし、ひとたびインデックスを利用できない状況に直面すると、たちまちテーブルスキャンが発生して性能が劣化してしまう。 例えば、100万行のレコードを格納したt1というテーブルがあるとする。そのテーブルに対して以下のようなクエリを実行した場合を考えよう。 mysql> SELECT col1, col2 ... colx
Using filesort
去年ソートに関する記事を書いたが、今日はその続きである。 MySQLでEXPLAIN SELECT...を実行するとExtraフィールドでよく見かける「Using filesort」という文字列。Filesortって一体なんだろう？と思ったことはないだろうか。単刀直入に言ってFilesortの正体はクイックソートである。 クエリにORDER BYが含まれる場合、MySQLはある程度の大きさまでは全てメモリ内でクイックソートを処理する。ある程度の大きさとはsort_buffer_sizeであり、これはセッションごとに変更可能である。ソートに必要なメモリがsort_buffer_sizeより大きくなると、テンポラリファイル（テンポラリテーブルではない）が作成され、メモリとファイルを併用してクイックソートが実行される。 Filesortは全てのソート処理において実行されるわけではない。前回の記事
Java は Collections.sort があるのに .NET は List 自身が Sort メソッドを持っているのはなぜ？ - Insider .NET会議室
.NETではデータ構造アルゴリズムに合わせた効率的なソートアルゴリズム/実装を選択しやすいことを重視したのでは？(インタフェース上の話です。実装は知りません) 例えば、配列を利用したListでは(不安定で構わないならば)クイックソートが向いているでしょうし、連結リストを利用したListではマージソートが向くはずです。また、Javaの場合はCollections.sort()でリストの中身を配列に変換してからソートして書き戻すので無駄が多いです。 あしゅさん .NETではデータ構造アルゴリズムに合わせた効率的なソートアルゴリズム/実装を選択しやすいことを重視したのでは？(インタフェース上の話です。実装は知りません) なるほど、効率の面からということですね。リストの内部構造を良く知っている List 自身に Sort を任せるのは、たしかに一理あると思います。ただし、私はつぎの2つの点から、そ
Java 7 の Fork/Join で 並列マージソート ＆ クイックソート - 映画は中劇
Java 6 までの Concurrency Framework の主役は、 Executor です。Executor を使うと、 非同期処理や複数セッション処理の並列化を、効率的に実装することができます。 Java 7 では、 Fork/Join という新しい仕組みが登場します。これは、 Executor とは異なった種類の計算、 CPU が律速となるような重い計算をターゲットにしています。重い計算を小さなタスクに分割して、小分けになったタスクを複数のスレッド (プロセッサ) が並列実行することで、高速に処理する、という実行モデルです。OpenMP に似ているはずです。使ったことないけど。 Fork/Join の仕組みについて、詳しくは、下記桜庭さんの記事をお読みください。スレッドごとの実行待ち行列の取り回しの仕方など、面白いです。 Java SE 7徹底理解 第2回 細粒度の並行処理
いろいろなソートアルゴリズム
<body> <p>このページにはフレームが使用されていますが、お使いのブラウザではサポートされていません。</p> </body>
quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
![quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream](https://cdn-ak-scissors.b.st-hatena.com/image/square/f9103c273a45047a455a47c2322a4ec545cd77ee/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127143682567%2F17680117127143702106%2F1558185862)
Java 7のArrays.sort(Object[]): 柴田 芳樹 (Yoshiki Shibata)
Java 7のEarly Access版をダウンロードしました。昨日、Joshua Bloch氏にProject Coinへ彼が提案している言語仕様の変更はすでに実装されているのかと聞いたところ、まだプロトタイプされていないということでした。で、その話のついでに、ソートの話になり、Java 7にはTimSortが入っているということで、調べてみました。 従来、コレクションフレームワークのArraysクラスのsort(Object[])は、今まではマージソートで実装されていました。しかし、Java 7にはパッケージプライベート宣言されているTimSortクラス（TimSort.java）が追加されており、Arrays.sort(Object[])（と関連する他のsortメソッド）はデフォルトでTimSortクラスのsortメソッドを使用するように書き換えられています。 TimSort.jav
![Java 7のArrays.sort(Object[]): 柴田 芳樹 (Yoshiki Shibata)](https://cdn-ak-scissors.b.st-hatena.com/image/square/91294c5e7d5927632be882106d59f6c861902287/height=288;version=1;width=512/https%3A%2F%2Fblog.ss-blog.jp%2F_common%2Fimg%2Fsonet_logo_l.png){kind=logo}
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Home
Rerun Me - Dynamic programming Java for online casinos
MySQLチューニング虎の巻／ソートに関連するトピックとクエリの書き換え
December 2011