計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell - Qiita
皆さん、ソートは好きですか？ 僕はHaskellerのクセにボゴソートが好きです。 ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる — やんぎん (@4116You) July 28, 2019 なにやらTLでスターリンソートなるものが流行っていました。 まずO(n)とは何かという事なんですが、これはビッグ・オー記法と言ってアルゴリズムの性能の指標を表すものです。 O(n)の他にO(1)とかO(log(n))とかO(nlog(n))とかO(n^2)とかがありますが、詳しくは割愛します。この辺を参考にするとよく分かると思います。ともかく、O(n)はむっちゃ速い、というかソートアルゴリズムではまず有り得ないです。 にも関わらず、スターリンソートはその壁を打ち破って、O(n)で並べ替えを実現しちゃうんですよね。 というわけでHaskellで
手を動かして読む技術書のススメ なっとく！アルゴリズム｜まりーな／エンジニア
実際手を動かしてみて思ったのだが、３章で使った内容を４章でも発展して使い、そして５章でさらに発展させるという形で段階的にわかるようになっている構成であることに気がついた。手を動かしてみないとわからないものである・・。 ●練習問題がある 章の終わりに練習問題がある。コレの良いところは、一つに付き2~5分くらいで終わること。たくさん時間がかかると本章だけで、挫折しそうになるのに、問題がいい感じに軽いというところが乗り越えられるポイントだった ●気になっていたアルゴリズムが紹介されていた。 ナップザック問題や巡回セールスマン問題。名前は聞いたことあるけど、具体的にどうやって解くのか知らないという問題を絵付きで解き方が紹介されていてよかった。 ●メモリの仕組みビックオー記法と配列とリンクリストの紹介 どうしたら早くなるかという話だけじゃなくて、そもそもどうして遅くなるのか、どうやって値が保存されて
岡田を切る技術 - Qiita
これはとある回顧録 何度も諦めかけましたが、数年の歳月を経て遂に岡田を切る技術が一旦の完成へと至りました。その技術を巡る奮闘の歴史と成果について、ここに記録を残していきたいと思います。 画像時代 まずは「切る」という動作が何を指すかを明確にしておきます。 厳密な定義というよりは、切った感を得るために必要そうなふるまいとして定義します。 平面上のある領域が、任意の直線を境界として分割されること 分割された領域は物理法則に準じてふるまうこと 要するに気持ちよく岡田を切ることができれば目標は無事達成です。 物理エンジン 切った感を高めるためにはやはり「物理法則」に準じたふるまいが欲しくなります。つまりブラウザ上で動く物理エンジンが必要です。 世の中にはフルスクラッチで物理エンジンを作れる人間と作れない人間が居ると思われますが、残念ながら私は後者でした。勝ち目の薄い勝負は避け、素直に巨人の方にすが
競技プログラミングで使う有名グラフアルゴリズムまとめ
0. はじめに AtCoderなどでは、グラフを扱った問題が多く出るが、その度に一から実装していると時間が掛かりすぎてしまうため、有名なものをあらかじめ持っておく必要がありそう。そこで、Pythonを用いて、ダイクストラ法、ベルマンフォード法、プリム法、クラスカル法、ワーシャルフロイド法を実装した。 コメント、意見等ある方は是非! お待ちしてます! 1. ダイクストラ法 1.1. ダイクストラ法(defaultdictで実装) defaultdictで実装すると、リストで実装するよりも、ノード数$N$が大きい際には高速に動作する。ただし、経路復元の関数は、うまく書けなかった......。 (2019/7/6 追記)結局できました。1.1.1. を参照してください。 import collections import heapq class Dijkstra: def __init__(se
Sorting algorithm reference, for coding interviews and computer science classes | Interview Cake
Which Sorting Algorithm Should I Use? It depends. Each algorithm comes with its own set of pros and cons. Quicksort is a good default choice. It tends to be fast in practice, and with some small tweaks its dreaded worst-case time complexity becomes very unlikely. A tried and true favorite. Heapsort is a good choice if you can't tolerate a worst-case time complexity of or need low space costs. The
とても強い計算量クラスのコンピュータとその実現方法 - Qiita
この記事は武蔵野アドベントカレンダー19日目の記事です。 物理のステートメントはだいぶ雑ですが、計算のステートメントには一応正確さに気を使って書いているつもりです。何か誤りがあった場合は、@iKodackまでご連絡いただけると幸いです。 (2018/12/22に「宇宙破壊コンピュータはセールスマン巡回問題の最適化問題を解けるか？ 」「時間遡行コンピュータで無限ループすると何が起きるか？」を記事末尾に追加しました。) (2018/12/28に「宇宙破壊コンピュータは答えが無い場合に全ての宇宙を破壊する？」について記事末尾に追加しました。) 前書き より速い計算機が欲しい、という欲求は全ソフトウェアエンジニア共通であることが知られています。 最近、業務において500GBのSSDや16GBのメモリを最低水準にするべきではないか、という議論がネットで活発になされていますが、生産性を限界まで高める限
【決定版】コンピュータ将棋のHASHの概念について詳しく | やねうら王 公式サイト
いまどきの将棋ソフトを使っていると、「HASH 50%」などと表示されている。これはHASH利用率と呼ばれる。この数字が大きくなってくると探索の効率が悪くなる。要するに潤沢にメモリがある場合に比べると弱くなる。これは、どれくらいの値までであるなら適切なのか？HASH利用率が99%にならない限りHASHには余裕があるものなのか？HASHはどういう仕組みになっているのか？HASH利用率が50%の状況で、ハッシュ衝突はしているのか？など、わりとソフトを長年使っていても知らない人が多いのでここに原理から詳しく説明した決定版的な記事を書く。 ShogiGUIや将棋神やねうら王に表示されている「HASH」とは何ですか？ 一度探索した局面を保存しておく表です。 この表に登録するときにハッシュ(hash)という値を使って登録するため、ハッシュテーブル(hash table)と呼ばれます。これを略して(値と
簡潔ビットベクトルでRubyをlog N倍速くした - クックパッド開発者ブログ
技術部のフルタイムRubyコミッタの遠藤（@mametter）です。昨日の Hackarade #04 の開催報告に続き、2日連続で記事を投稿します。 今回は、ある条件下でのRubyの実行速度を高速化した話を紹介します。この改善はすでにMRIの先端にコミットされていて*1、年末リリース予定のRuby 2.6に含まれる予定です。 ひとことで言うと、「簡潔ビットベクトルを索引に使うことで、プログラムカウンタから行番号を計算するアルゴリズムをO(log N)からO(1)に改善した。これにより、TracePoint有効時やコードカバレッジ測定下で、長さ N のメソッドの実行が O(N log N) から O(N) に高速化される」ということです。順に説明します。 背景：Rubyのバイトコードの構造 この最適化を理解するにはまず、Rubyのバイトコードのある特徴を知る必要があります。 たとえば x
OpenDataStructures.jp
オープンソース版 Open Data Structures 日本語訳の PDF ファイルを以下で公開しています。最新のソースコードは GitHub のリポジトリ https://github.com/spinute にあり、適宜こちらの PDF ファイルに反映しています。 以下のものは C++ 版です（Java 版はこちら、疑似コード版はこちらにあります）。 目次 訳者まえがき 本書の読み方 訳者謝辞 なぜこの本を書いたのか 謝辞 第1章 イントロダクション 効率の必要性 インターフェース 数学的背景 計算モデル 正しさ、時間計算量、空間計算量 コードサンプル データ構造の一覧 ディスカッションと練習問題 第2章 配列を使ったリスト ArrayStack：配列を使った高速なスタック操作 FastArrayStack：最適化された ArrayStack ArrayQueue：配列を使ったキュ
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
df-pnアルゴリズムを用いた詰将棋Solverによる最善解・余詰の導出 - すぎゃーんメモ
以前書いた、詰将棋問題生成の続き。 memo.sugyan.com 逆算による詰将棋の問題生成の方法自体は悪くないとして (バグによって有り得ない局面が出来上がったりしてしまったりもしたけど)、正しく詰将棋問題として成立するものが出来上がっているかどうかを検証するためのSolverが必要不可欠であり、これのパフォーマンスが生成のパフォーマンスにも影響してくる、というようなことを書いた。 実際、前回の記事のときに実装したSolverでは 総当たり的に探索するのは3〜5手が限界 詰将棋のルールに則る動きに限定しても、有り得る局面は指数関数的に増加する 合駒が絡む問題に対して正しく解が導けないことがある 先の展開まで読まないと無駄な合駒かどうかの判定ができない といった問題があった。 df-pnアルゴリズムによる探索 2002年の論文「df-pn アルゴリズムの詰将棋を解くプログラムへの応用」が
直感で理解する量子コンピュータ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 本記事はWACUL Advent Calendar 2017の12/25の記事になります。 こんにちは、株式会社WACULで、データ分析の仕事をしている@onhrsです。 現在、機械学習エンジニアをしておりますが、数学や物理などが好きなので（できるとは言ってません）、今でも重力波を解析したり、量子アニーリングのイジングモデルを計算したりしております。 今回は、徐々に浸透してきた量子コンピュータについて、最近の動向を含め個人的に勉強しまとめてみました。とりあえず量子コンピュータは何か、量子アルゴリズムとは何かっていうのがわかってもらえたら
Hayato.io
Hayato.io This Page Is Under Construction - Coming Soon! Why am I seeing this 'Under Construction' page? Related Searches: All Inclusive Vacation Packages fashion trends Top 10 Luxury Cars Best Penny Stocks find a tutor Trademark Free Notice Review our Privacy Policy Service Agreement Legal Notice Privacy Policy|Do Not Sell or Share My Personal Information
Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
Classes
デジタルメディア処理2, 前期木3, 豊洲地区教室棟03S22 303教室 本講義は，デジタルメディア処理１、デジタルメディア処理２という対となる科目の後半にあたるものです． 2017年度は，井尻の芝浦工大赴任に伴い，例外的に「デジタルメディア処理２」から井尻が担当することとなりました． そのため講義の前半部分には，本来デジタルメディア処理１にて扱うべき初歩的な内容も含まれています． また，2018年度のデジタルメディア処理２では，画像認識，パターン認識や深層学習などの高度な内容も盛り込む予定です． 2017年度デジタルメディア処理のページ 受講生へ． すべての講義は学内システムにて視聴可能です．興味があれば参照してください．（現在は履修生のみ対象なのですが将来的はもっとアクセスしやすくしたいと思っています．） 感想． 今年度は後半部分（デジタルメディア処理２）から担当ということで，基礎も
「プログラミングの常識」を時々見直す必要性について｜Rui Ueyama
自分の中のプログラミングの常識というものは、ときどき現実のハードウェアに合わせて調節しないといけない。ハードウェアが進歩し続けているので、コンピュータで簡単にできることと相対的に難しいことのバランスが変化し続けているからだ。ここでは特にストレージにフォーカスして書こうと思う。 昔はメモリが相対的にとても貴重な資源だったので多くのプログラマがメモリを節約することに血道を上げていた。例えばWindowsの初期の頃に設計されたデータ構造には、メモリをバイト単位ででもいいから節約したいという意図の痕跡がいまでも多く見受けられる。DRAMの次に速い記憶装置はHDDだったので、メモリが足りなくなればHDDにデータを保存せざるを得ないのだが、DRAMとHDDのランダムアクセスの速度差は、机の上の本の開いているページを見るのと、その本をAmazonで注文して到着するのを待つのと同じくらいのスケールで違うの
Ideone.com
Ly8gYm9vbCBxdWVyeShpbnQgeCkgeyByZXR1cm4gWCA8PSB4OyB9IOOBruWgtOWQiOOAggppbnQgc29sdmUoKQp7CglpbnQgYj0xPDwzMDsKCWludCBhbnM9Yi0xOwoJd2hpbGUoYil7CgkJaWYocXVlcnkoYW5zLWIpKWFucy09YjsKCQliLz0yOwoJfQoJcmV0dXJuIGFuczsKfQoKLy8gYm9vbCBxdWVyeShpbnQgeCl7cmV0dXJuIHg8PVg7IH0g44Gu5aC05ZCI44CCCmludCBzb2x2ZSgpCnsKCWludCBiPTE8PDMwOwoJaW50IGFucz0wOwoJd2hpbGUoYil7CgkJaWYocXVlcnkoYW5zK2IpKWFucys9YjsKCQliLz0yOwoJfQoJcmV0
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - sazameki/maze-algorithms: 迷路生成の各種アルゴリズムのC++実装 (Win/Mac両対応)
Z80における「手抜き」回転行列のさらなる改良 | yasuokaの日記 | スラド
TheAlgorithms/Python: All Algorithms implemented in Python
