高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
ごちうサーチ
2. 火星や月から宇宙人の顔を見つけた Nasa の画像をクラウドで処理 https://en.wikipedia.org/wiki /Face_on_Moon_South_Pole (Română தமிழ் 中文) http://target.lroc.asu.edu/qm3d/ o2w_3d_617653310_153_220_20 5_44_0/ 3. 飯テロ判定bot (Twitter @no_meshitero) 食事を判定する bot だが、それ以外の画像も判定 複数の画像認識クラウドサービスの結果を統合 ▪ Google, IBM, Microsoft, docomo “一蘭の飯テロ画像です”
ソートとリサイズが可能なペインコンポーネントreact-sortable-paneを作った - undefined
今作ってるtwitterクライントでソートとリサイズができるコンポーネントが欲しかったので作った。 作ったもの github.com デモ http://bokuweb.github.io/react-sortable-pane スクリーンショット 使い方 インストール npm i react-sortable-pane サンプル 以下のように使用する。 <SortablePane margin={10}> <Pane width={200} height={500} style={style}> A </Pane> <Pane width={300} height={400} style={style}> B </Pane> </SortablePane> このコンポーネントについて もともとは以下のコンポーネントを作ったときのデモだったんだけど、今回コンポーネント化しといた。 blog
とても長い配列の上位M件だけをクイックソートより高速に取り出す - Qiita
というわけで、10倍の差がでた。 当然、配列の長さやソートする長さ、また実装の方法によって性能差は変わってくるが 今回の方法は有効であるということは確認できた。 既存の記事(2015/11/09 20:22 追記) コメント欄でUnordered partial sorting にそれらしきことが書いてあると教えていただいた。 そちらでは、「上位k個を取り出す（ソートは不要）」という問題を考えている。 同様に分割統治法を用いてソートしていきながら、上位k個以内の小区間になったらその区間はソートせずに全て選択して良いとしている。 早い話が、QuickSelectによりk+1番目の要素を探してそれより上位の要素をごそっと抜き出している。 分割統治法で大雑把にソートしていきながら、不要なソートを行わないようにする という同様のアプローチである。 C++のSTLの場合(2015/11/09 22:
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
漢数字が数字順にソートされない理由を調べてみた - give IT a try
はじめに：「なぜ漢数字は数字順に並ばない！？」 先日、こんなツイートをしたところ、結構たくさんの人にリツイートされました。（執筆時点で50件以上） 「漢数字はソートしても数字順に並ばない」という事実を生まれて初めて知った。まさかのサプライズ。 pic.twitter.com/Eqx3ltIfHs— Junichi Ito (伊藤淳一) (@jnchito) 2014年11月27日 「なぜ漢数字は数字順に並ばないのか」という問いに対して、表面的な回答をするなら「数字順に並ばないのは、数字の大きさではなく文字コード順でソートされているから」ということになります。 いや、もちろんそれはわかってるんです。 問題は「そもそもなんで数字順に文字コードを振らなかったの！？」ということです。 感覚的には「一郎、二郎、三郎」って並んでほしいじゃないですか。でも、プログラム上でソートすると「一郎、三郎、二郎」
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
