[B! sort] gfxのブックマーク

ソートアルゴリズムを極める！〜なぜソートを学ぶのか〜 - Qiita

NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回はソートについて記します。 0. はじめにデータ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。特にソートは、計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法ヒープ、バケットなどのデータ構造乱択アルゴリズムの思想といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や

gfx 2018/04/05

リンク

汎用ソート殺し - d.y.d.

00:26 12/12/18 BookLive! 7月に出会ってからずっと電子書籍ストアとして BookLive! をひいきにしているのですが、一体どこが好きなのか語りたくなりました。 ITMedia のこれでもう迷わない、電子書店完全ガイドという一連の記事の、電子書籍の端末の話よりストアの話をしましょうよというコンセプトに思いっきり影響されています。といっても、第一印象が「普通のことが普通にできるので感激した！！」というもので、つまり今年の前半に使っていた幾つかの電子書籍ストア/専用アプリが残念だっただけかもしれません。買った本がどこをクリックすれば読めるのか理解するのに10分かかった、とか、 6冊以上買うと本棚アプリから画面外に本がはみ出るので手でいちいち棚を変えて整理しないと読めない、とか。本当に普通に使えるという以上に特筆することもないんですが、あ、でも、今年になる

gfx 2012/12/02

リンク

algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な : 404 Blog Not Found

2012年01月13日08:00 カテゴリアルゴリズム百選Lightweight Languages algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な The C Programmming Lanugage K&R 言い出しっぺの法則。 404 Blog Not Found:algorithm - bucket sort - 比較しなければソートは相当速いこれほど素晴らしいアルゴリズムなのに、なぜlibcやLL言語の組み込みとして用意されていないのでしょう? https://plus.google.com/103748274114027132441/posts/VmpVES1hFds - Shiro Kawai さんのコメント他のソートアルゴリズムのような汎用のライブラリになってないのは、目的によってチューニングポイントが違って、それらに

gfx 2012/01/13

sort

リンク

algorithm - bucket sort - 比較しなければソートは相当速い : 404 Blog Not Found

2012年01月11日07:00 カテゴリアルゴリズム百選Math algorithm - bucket sort - 比較しなければソートは相当速い珠玉のプログラミング Jon Bentley / 小林健一郎訳絶賛風邪こじらせ中につきコードと戯れることに。新ソートアルゴリズム「配列挿入ソート」だ! - hp12c その名も「配列挿入ソート」! すでに突っ込み入ってるけど、それ、もしかしたら人類最古のアルゴリズムだから。最古にして最速? おそらくプログラムを組んだことがない人でも「誰にも教えられずに」知った「天然の」アルゴリズムの筆頭に来るのがこのバケットソートではないでしょうか。ソートしたいものに適当に番号を振っておく番号がついたバケツを用意するソートしたいものの番号がついたバケツにそれを放り込む必要があればバケツの中身を同じやり方でソートする番号順にバケツの中身をぶち

gfx 2012/01/11

sort

リンク

高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development

先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解

gfx 2011/10/26

たしかにオリジナルのコードは複雑で、移植したのにぜんぜん何やってるかわかりませんでした

リンク

DRMacIver/understanding-timsort - GitHub

This is the repo corresponding to a series of blog posts I'm writing on understanding the details of timsort. It will make more sense more sense read in context with the articles. One thing important to note: The code as it currently is is not timsort. It's an adaptive mergesort that more or less resem bles the core of timsort. As time goes on it will asymptotically converge to something that looks

gfx 2011/10/19

リンク

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

gfx 2011/10/19

blogged

リンク

Timsort - Wikipedia

Timsort is a hybrid, stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the rem ainder more efficiently. This is done by merging runs until

gfx 2011/09/20

timsort
sort

リンク

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

gfx 2011/09/20

sort
timsort

リンク

初めて学ぶソートアルゴリズムは何がいい？ | スラド Slashdotに聞け

ソートについて学ぶといえばまずストレートインサーションあたりから入り、バブルソートが出てくるのはソートの章の中頃、というのが昔の定番だったように思います。ところが最近では、定番としてバブルソートを出してくる解説WEBページや、ソートの章の最初の事例がバブルソート（単純交換ソート）を出してくるアルゴリズムとデータ構造の書籍があるのを発見し、びっくりしました。はたしてソートについて学び始めるときに、最初に取り組むアルゴリズムはどれが適切なのでしょうか。バブルソートははたして適任でしょうか？

gfx 2011/05/20

スパゲティソートってこれか

リンク

4chan BBS - Genius sorting algorithm: Sleep sort

1 Name: Anonymous : 2011-01-20 12:22 Man, am I a genius. Check out this sorting algorithm I just invented. #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 Oh god, it works. But I don't like to wait 218382 seconds to sort '(0 218382)

gfx 2011/05/19

リンク

ランキングのつくりかた:Kenn's Clairvoyance

遅ればせながら、あけましておめでとうございます。先週には、ベイエリアの友人たちがやっているEchofonがPostUpに買収されるなど、幸先のよい新年のスタートとなりました。さて、最近ホットなマーケットといえばソーシャルゲームですが、ゲームといえばリーダーボード。ハイスコアのランキングで友人や見知らぬ人たちと競うのは、ビデオゲームが誕生した1970年代から欠かせない要素でした。ところが、インターネット経由で100万人規模のプレイヤーがつながるようになってきた現在、その全体をランキングづけするのは、技術的にも大きなチャレンジとなってきました。今回は、そのリーダーボードのつくりかたについて、ぼくらの作っているソーシャルゲーム・プラットフォームであるPankiaの運用で得られた知見を共有したいと思います。自分の順位を知る方法リーダーボードの基本的な考え方はシンプルで、それはつまり「ユ

gfx 2011/01/14

"現象に偏りがあるときには、そこに圧縮や最適化の可能性がある、と考えるのがコンピュータ・サイエンスの常道です。"

リンク

はてなブックマーク

タグ

関連タグで絞り込む (4)

sortに関するgfxのブックマーク (12)

お知らせ

今週のはてなブックマーク数ランキング（2024年4月第2週）

今週のはてなブックマーク数ランキング（2024年4月第1週）

月間はてなブックマーク数ランキング（2024年3月）

公式Twitter

キーボードショートカット一覧

はてなブックマーク

公式Twitter

はてなのサービス