WebGLで暴力的な並列ソートに挑戦する
日照時間足りてますか？やまだです。 KLab Advent Calender 11日目の記事です。 最近WebGLで実装できるちょっと強そうなソートアルゴリズムを知ったので書いてみました。 WebGLよくわかんないやーって人も雰囲気だけでも伝われば幸いです。 強さの秘訣 WebGLは3Dを描くAPIとして著名ですが、2Dはもちろん、工夫次第で汎用計算（GPGPU）にも応用できます。 WebGLでの演算は通常のJavaScript演算とは違い、GPUを使った並列な浮動小数点演算を可能とします。 そして、ソートアルゴリズムの中には計算量こそ地味なものの、並列処理が可能なものがあります。 そのうちの一つがバイトニックソートです。 GPUを使い、物量で計算する暴力的な並列ソートをやっていきましょう。 バイトニックソートとは 前述のとおり、並列処理が可能なソートアルゴリズムです。 配列を小さい領域に
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
MySQLのfilesortは何ソートで行われているのか - $shibayu36->blog;
最近、CourseraのArgorithms, Part1という講義を受けている。そこでソートの講義を受けて、そういえばMySQLのORDER BYでfilesortになったときってどのソートが使われているのだろうと気になってきたので調べてみた。 調べてみると非常に難解で、結局いまいち分からなかったが、今の段階の調べた内容をひとまず書いておく。MySQLのコードを読んだのも初めてで、しかもちゃんと読み解くことができなかったので、情報が間違っている可能性も非常に高い。間違ってたら指摘してもらえるとうれしいです。 調査結果 最初に調査結果を書いておく。たぶんこれは非常に単純化したもので、詳しく見るともっといろいろチューニングされてそう。 sort_buffer_size以内のメモリ量でソートが可能な場合、メモリ内でのみソートされる ソートにsort_buffer_size以上のメモリが必要な場
二分探索サンプルコード集（コピペ用） - まめめも
二分探索は、感覚的なわかりやすさに反してバグが入りやすいことで有名なアルゴリズムです。20 の教科書のうち 15 でバグっていたという報告もあるそうです。 実際、自分も書くたびにバグに苦しんできました。変な値を返すだけでなく、out of bounds アクセスや無限ループもよく起きます。一旦動いたと思っても、後になってバグが発症することも多く、たちが悪いです。 そこで、きちんとテストした二分探索のサンプルコードを自分のコピペ用に作ってみました。 動作仕様 (境界探索版) ソートした配列 a に対して、「値が c 以上になる範囲のうちの一番左のインデックス」を返す関数 bsearch_min を書きます。 a = [0, 1, 1, 1, 2, 2, 2, 3] p bsearch_min(a, 2) #=> 4 値が c 以上になる値がない場合は a.size を返します。空配列の場合は
Haskellで無限個の無限リストをソートされた形で結合する - プログラムモグモグ
CodeforcesやProject Eulerの問題には、無限リストをうまく使うと綺麗に解くことができる問題がたくさんあります。 数列の性質から探索範囲の上界を決めて解を探索することが多いのですが、きちんとした根拠を持って上界を決めることができることは少なく、余裕を持って十分に広い範囲で計算して解を求める解法がよく取られます。 Haskellの特徴である遅延評価とその洗練された糖衣構文を用いると、無限リストを簡単に扱うことができます。 上界を適当に定める解法よりも、より宣言的で美しく、時に効率的なコードで同じ解を得ることができます。 しかし、無限リストをきちんと、それも無限個の無限リストをきちんと扱うとなると、意外と苦労します。 この記事では、無限個の無限リストをソートされた形で結合する方法について説明します。 一般的な無限リストではなく、条件はかなり絞っていてます (そうでないと原理的
ソート済の整数列を圧縮する件
圧縮されたソート済の整数列ってのは汎用的なデータ構造で、たとえば検索エンジンの転置インデックスとか、いろんなところで使うわけです。で、検索エンジンの場合は速度重要なので、PForDeltaとか様々なデータ構造が研究されてる。 一方、H2O には、ブラウザキャッシュに載ってない js や css をサーバプッシュする仕組み「cache-aware server push」があって、何がキャッシュされているか判定するためにブルームフィルタを全ての HTTP リクエストに含める必要がある。 で、ブルームフィルタを圧縮しようと思うと、ブルームフィルタってのはソート済の整数列として表現できるので、これを圧縮しようって話になる。 検索エンジン等で使う場合は速度重要だけど、HTTPリクエストに載せる場合は空間効率のほうが重要になる。ってことで、空間効率が理論限界に近いゴロム符号（の特殊系であるライス符号
ekmett先生のdiscriminationというライブラリの動画を見たので雑に要約してみた - xuwei-k's blog
本当に雑に(前半部分だけを)まとめただけなので、ちゃんと知りたい人は、元動画やライブラリのコードや、元論文読むとよいです http://hackage.haskell.org/package/discrimination https://www.youtube.com/watch?v=cB8DapKQz-I https://github.com/ekmett/contravariant/blob/v1.3.2/src/Data/Functor/Contravariant/Divisible.hs やる気がでたら、もう少し真面目な解説を後で別に書くかも知れませんし、書かないかもしれません。 先に簡単に自分の感想的なものを書いておきます。 ソートの話なはず、の動画を見ていたら、なぜか前半は「圏論」や「Hask」や「Contravariantなんちゃら」の話してて 「あれ、見る動画間違ったのかな
JavaのTimSortがバグってる件について | さにあらず
Python で実装され、その後 Java にも移植されたソートアルゴリズムである TimSort が盛大にバグっていることが発見されました。 このバグがどのようにして発生するのかについては、以下のドキュメントを精査して下さい。 TimSort fails with ArrayIndexOutOfBoundsException on worst case long arraysOpenJDK’s java.utils.Collection.sort() is broken: The good, the bad and the worst caseどんなことが起こるのか#通常の利用では想定しえない場所でArrayIndexOutOfBoundsExceptionが発生します。 例えば、以下のようなスタックトレースになります。 Exception in thread "main" java.l
データ集計コマンドを極めてシステム処理と業務速度を爆速化するお話 - Y's note
Index データ集計コマンド 爆速で検索したいぜ！ lookを使う LC_ALL=Cを設定する データのランダムサンプリングがしたいぜ！ sedを使う awkを使う sortの--random-sortを使う Script言語を使う shufを使う ランダムサンプリング速度比較 合計と平均値を集計したいぜ！ 列データ取得 重複行のカウント 合計値出力 平均値出力 複数ファイルのデータ結合がしたいぜ！ 共通項目での結合 同じ行数での結合 まとめ データ集計コマンド joinコマンドが便利過ぎて生きるのが辛い - Yuta.Kikuchiの日記 lookコマンドによる二分探索が速すぎて見えない - Yuta.Kikuchiの日記 今日はデータ集計を行う上で絶対に覚えておいた方が良いコマンドと知識を紹介したいと思います。これを身につければシステム処理と業務効率化に大きく繋がると思います。この記
しばらくフリーエンジニアとして生きようと思う JavaでBeanを簡単ソート
今度の仕事で使いそうなのでメモ ComparatorChainとBeanComparatorでbeanのソートが簡単にできる。 ソートキーが複数ある場合は、条件を追加できる。 これ便利だな～ 【利用したjarファイル】 commons-beanutils-1.8.3.jar commons-logging-1.1.1.jar commons-collections-3.2.jar ダウンロードページ 【ソースコード】 Test.java package jp.co.haman.main; import java.util.ArrayList; import java.util.Collections; import java.util.List; import org.apache.commons.beanutils.BeanComparator; import org.apache.co
GNU ls の -v オプションのようにソートするComparator - らくさん
GNU ls の -v オプション -v バージョン名とバージョン番号でソートする。 (訳注: バージョンの一番低いものが最初にくる。デフォルトのソートのように動作するが、 10 進の数字のシーケンスは、インデックス番号またはバージョン番号として数値的に扱われる。 ゼロを前にもつ数値部分は小数として扱われる。 ls -1 ls -1v bar-1.gz bar-1.gz bar-100.gz bar-2.gz bar-12.gz bar-12.gz bar-2.gz bar-100.gz foo-1.007.gz foo-1.007.gz foo-1.012b.gz foo-1.01a.gz foo-1.01a.gz foo-1.012b.gz ) http://www.linux.or.jp/JM/html/GNU_fileutils/man1/ls.1.html のようにソートするCo
RE: sort を使うときは，LC_ALL=C を忘れずに - ny23の日記
Twitter ID も livedoor ID もないので直接コメントできないが，sort (GNU coreutils) の名誉のために，ここにメモしておく． 404 Blog Not Found:algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な まず第一印象として，この程度のサイズのファイルのソートで sort (GNU coreutils) がいまどきこんなに遅いはずはない．LC_ALL=C で追試すると，やはり bucketsort との差は無くなった．上の記事（に対するツイート）は Twitter 上でもそれなりにリツイートされているように見えるのだけど，この実行時間に違和感を感じる人が全くいないのはどういうことなのだろうか．sort を実際に使う人がほとんど見ていないのか，それとも計算量が違うから速くて当然という思い込みか．
東京を走る路線のデータを使って、最短経路問題をダイクストラ法で解く - imHo
ダイクストラ法が小さなサンプルデータで動いたら、実際のデータを使ってみたくなるのが人情。東京を走る地下鉄のデータでやってみたいと思った。 JavaScriptとPrototype.jsとGoogleMapsAPIとすったもんだしたあげく、なんとか動くものができた。 502 Bad Gateway テストアプリはこちら JavaScriptのソースはここのhtmlに 駅や路線のデータは駅データ．ｊｐのものを使わせてもらいました。 使ったのは東京メトロ＋都営＋山手線 駅（ノード）の数は、同じ駅でも路線ごとで別にカウントして 322 駅同士をつなぐ線路（エッジ）の数は、徒歩や乗換えを含め 912 体感もっさり感じるけど、経路の検索以外のところがかなりかかってる Tips Prototype.js Array.without は超重い、使うな！ Hash.keys で返ってくるキーはすべて文字列に
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)
jQueryのSortableとem-websocketを組み合わせてみた - nkmrshn’s diary
jQueryのSortableとem-websocketを組み合わせ、同じページをブラウザで閲覧中のユーザが、共同してリストの順番などを変更できないかRuby on Railsで試してみました。 また誰かが操作中は、警告アイコンを表示するようにしました。 ソース http://github.com/nkmrshn/share_sortable 用意 Gemfileにem-websocketを追加し、「bundle install」でインストールします。 gem 'em-websocket' gem 'jquery-rails'また、今回はprototype.jsではなくjQueryなので、jquery-railsも追加し、アプリの作成は「rails new APP_NAME -J」とprototype.jsを作らず、インストール後に rails generate jquery:instal
開発メモ: トップNソートの検討
上位N件をソートした状態で取り出すという、いわゆる「トップNソート」の効率的な実装について検討してみた。 背景 データベースに対して、ある順序でソートした時の最初の何件かが欲しいというクエリを投げることはよくあるだろう。SNSで言えば、誰かのコンテンツの最新10件を表示するとかいう場合だ。SQLだと "ORDER BY xxx LIMIT yyy" とかいう感じ。同じような操作は全文検索システムのスコアリングでも定番である。俺もよく自分で実装するわけだが、その度に適当な試行錯誤をして時間がもったいないので、今回は入念に調べて決定版を出そうじゃないか。 全体をソートして上位を取り出せば目的は満たせるのだが、それだと無駄な計算が多い。100万件の中から上位10件だけ欲しい場合に、残りの99万9990件まで律儀にソートする必要はない。ということで、上位N件をソートして取り出すという「トップNソー
マルチキークイックソート - sileのブログ
「Sorting and Searching Strings」で説明されているマルチキークイックソートの実装。 詳細はリンク先を参照。 マルチキークイックソート 文字列の配列のソートが高速に行える URL("http://...")の配列のような接頭部分の重複率が高い文字列配列の場合でも性能が低下しにくい クイックソート + 基数ソート、のような感じ？ ソート方法 基本的には通常のクイックソートと似ていて「ピボット要素*1を選んで、配列を分割する」といったことを繰り返す。 ただし、クイックソートは各段階で配列を二分割(ピボット要素よりも大きいか小さいか*2 )し、そのための比較には要素(文字列)全体を用いるのに対して、マルチキークイックソートでは、配列は三分割(ピボット要素よりも大きいか小さいか、それとも等しいか)され、そのための比較には文字列全体ではなく(各段階で)一文字のみ、が用いられ
corte.si
Hilbert Curve + Sorting Algorithms + Procrastination = ? 2010-01-26 I like the Hilbert curve. I like sorting algorithm visualisations. I occasionally procrastinate when I should be doing more important things. When all these factors converge, the result is a post like this. In a previous post, I drew a picture of a Hilbert curve by projecting a Hilbert curve traversal of the RGB colour cube onto a
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Sorting numbers in string format with Python
Information Technology Laboratory