Get theory, practice coding, and move beyond programming challenges to building your own working projects. Join over 700 000 learners at Hyperskill.
Hyperskill — Learn programming, create apps
Get theory, practice coding, and move beyond programming challenges to building your own working projects. Join over 700 000 learners at Hyperskill.
GitHub - scandum/quadsort: Quadsort is a branchless stable adaptive mergesort faster than quicksort.
半順序でソートするためのアルゴリズムとは？ - Qiita
はじめに ソートのアルゴリズムは通常、実数における通常の順序関係のように全順序である順序関係に対して行うものですが、本記事では半順序に対するソートのアルゴリズムについて解説します。 半順序とは 集合X上の二項関係 ≦ が半順序であるとは、以下の性質を満たすものとして定義されます。 反射律 任意のx $\in$ Xに対し、x ≦ x を満たす。 反対称律 任意のx, y $\in$ Xに対し、x ≦ y かつ y ≦ x ならば x = yを満たす。 推移律 任意のx, y, z $\in$ Xに対し、x ≦ y かつ y ≦ z ならば x ≦ zを満たす。 ここに全順序律 任意のx, y $\in$ Xに対し、x ≦ y または y ≦ x を満たすこと追加したものを全順序と言います。 通常、ソートを行うアルゴリズムはこの全順序関係を仮定した上で成り立つアルゴリズムです。しかし以下のよう
WEB+DB PRESS連載記事「Rubyのウラガワ」を期間限定で無償公開（公開終了）
新型コロナウイルスの影響で多くの学校が休校する状況を受け，『WEB+DB PRESS』で笹田耕一氏が執筆しており，現在も連載中の「Rubyのウラガワ」の第1回から第5回までの記事のPDFを，学習用に期間限定で無償公開します。 記事の概要やダウンロード先などは以下のとおりです。 記事名 Rubyのウラガワ ── Rubyインタプリタに学ぶデータ構造とアルゴリズム 記事概要 本連載では，Rubyインタプリタという，実際に多くの人が利用しているアプリケーションを題材にしてデータ構造とアルゴリズムを学ぼうという趣旨で，その実装を紹介します。単なる実装の紹介だけではなく，なぜそのような選択をしているか，その背景を紹介できればと思っています。（Vol.110「連載のはじめに」より） 公開範囲 Vol.110（第1回）～Vol.114（第5回） 公開期限 2020年4月5日まで ※期限が過ぎまし
二分木 - Rustではじめるデータ構造とアルゴリズム（第1回）
Rustの特徴のひとつは、所有権(ownership)・移動(move)・借用(borrow)の概念です。これらがコンパイル時に厳格にチェックされることにより、古くから未定義挙動でプログラマを悩ませてきたダングリングポインタなどの問題がなくなり、メモリ安全性がもたらされます。 しかし一方で、自分で多少複雑なデータ構造を定義しようとする場合にはコンパイルを通すだけでもかなりの知識・力量が要求されます。 この（不定期）連載では、 Rustではじめるデータ構造とアルゴリズム と題し、プログラミングコンテストなどでよく見かける基礎的なデータ構造とアルゴリズムを、できるだけシンプルにRustで実装していきます。 &, &mut, Box, Rc, Cell, RefCell などの使い分けや、なぜそれを使う必要があるかの解説を、実例を通して行います。 第1回は、最もシンプルな木構造である 二分木 を
木の数え上げ - Haskell-Misc
これはHaskell Advent Calendar 2019 24日目の記事として書いたものです． code:Tree.hs {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE LambdaCase #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE NPlusKPatterns #-} module Tree where import Data.Bool (bool) import Data.List (genericIndex, genericTake, findIndex, scanl') import Data.List.NonEmpty (NonEmpty(..)) import Numeric.Natural import Control.Comonad.Cofree (Cofree(.
Knuth-Morris-PrattアルゴリズムのHaskellでの実装の解説 - Qiita
はじめにのまえに この記事はHaskell Advent Calendar 2019の19日目の記事の補足です。よくばってネタを増やしすぎたので、一部の話題をこちらにわけました。もとの記事でも、かんたんに説明していますが、こちらのほうがより、ていねいな説明になっています。 はじめに 文字列のなかから「特定の並びの文字列の位置」を抽出するアルゴリズムで、有名なものにBoyer-MooreアルゴリズムとKnuth-Morris-Prattアルゴリズム(以下、KMPアルゴリズムと表記)とがある。後者のHaskellによる実装について解説する。実装は「関数プログラミング 珠玉のプログラミングデザイン(以下PFADと表記する)」のものを紹介する。 サンプルコード サンプルコードは、つぎのリポジトリに置いてある。参考にしてほしい。 GitHub: YoshikuniJujo/test_haskell/
Haskellのscan系関数を使いこなす | 雑記帳
Haskellはリストを操作する関数を多数提供しています。map, filter, foldあたりが代表的で、これらは他の言語でもおなじみかと思います。 一方で、scan系関数（scanl, scanr）は他の言語ではあまり見かけない気がします。同じ関数型言語のSMLやOCamlにも標準では入っていないようです。 この記事では、scan系関数がどういう場合に利用できるかを紹介します。 scan系関数とは 定義と図解 scan系関数は、リストを元にして新しいリストを構築する関数です。新しいリストの要素は、与えられた初期値と関数を使って元のリストを途中まで畳み込んだものになります。「foldの途中経過を残す版」とでも言えば良いでしょうか。 型はそれぞれ次のようになります： scanl :: (b -> a -> b) -> b -> [a] -> [b] scanr :: (a -> b ->
スターリンソートよりも速いO(1)のソート - Qiita
はじめに みなさん、スターリンソートはご存じですね？ 以下のツイートが有名でしょう。 ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる — やんぎん (@4116You) July 28, 2019 Qiitaの記事では 計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell https://qiita.com/Tatsuki-I/items/380d6bd06515b872b2b2 や 計算量O(n)で噂のスターリンソートを実装してみた https://qiita.com/MeilCli/items/721526d716851e92192a などが有名ですね。 しかし、これでもまだO(n)にしかなっていません。我々が目指すべきはO(1)のアルゴリズムです。 そこで、次のような
解析不能！30年以上前のレトロゲームから謎の「自動生成アルゴリズム」が見つかる - ナゾロジー
Point ■レトロゲームには容量不足や技術的制約を解決するため、現代の我々から見ても解析できない謎の技術が使われていることがある ■今回、ATARI2600から82年に発売されたゲーム『Entombed』に、全くロジックが不明の迷路自動生成プログラムのコードが発見された ■迷路の壁を完全ランダムに配置すればクリア不能になってしまうが、このプログラムがなぜ通行可能なパターンで迷路を生成しているかは、まったくの謎だという ほんの数十年前、コンピュータ関連の技術が飛躍的に向上しました。 特にデータ容量の向上はめざましく、現代の若い人たちにとって容量の単位は「ギガ」が標準になっています。 しかし初代のスーパーマリオの全ゲーム容量は40KB、初代ドラゴンクエストの全容量は64KBでした。 これはこの記事のトップに貼られている画像の容量よりも遥かに小さい容量です。 レトロゲームの開発は、そんな小さな
バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート - Line 1: Error: Invalid Blog('by Esehara' )
はじめに 恐らく、プログラマの中で配列内の要素を整列させたりするソートにお世話にならなかった人、というのは余り考えられないのではないでしょうか。しかし、とはいえ、大抵はソートを自前で実装せず、組み込み関数であったり、あるいは何らかのライブラリで済ませることが殆どだと思う。 車輪の再発明というよりも、バグとか、自分が考慮していなかった挙動などを避けるために、自前でソートを組むことは余りないのですが、とはいえ、自分なりにソートを実装して見ると、それがどういう特徴を持ったソートであるか、というのがわかりますし、また、ソートというのはいったいどういう操作で実現されるのかという洞察が深まってくるなあ、という実感があったりする。 なので、今回はあるソート二つについての話を書くのが趣旨です。 最高のアルゴリズムはある、だが最悪のアルゴリズムは何か 一口にソートといったところで、ソート自体にも銀の弾丸があ
遅いソート - 鍋あり谷あり
http://bugrammer.hateblo.jp/entry/2014/08/16/014212 ( バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート ) を読んで。 ちゃんと終わるけどもっと遅いソートがあるので書いてみた。 たぶん名前がついていると思うんだけど、調べてないので名称不明。 こういう奴。 def try_all_sort(s) s.permutation(s.size){ |x| return x if x.each_cons(2).all?{ |a,b| a<=b } } end typical case では bogo sort と同じオーダー。 bogo sort と違って、worst case は有限。O((N+1)!)だと思う。 で。ベンチマーク。 100要素を1000回なんて宇宙が消滅するまでに終わらないので、試した
やさしいスターリンソート入門【実用的】 - Qiita
概要 最近、巷ではスターリンソートというソートが流行っています。 ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる — やんぎん (@4116You) July 28, 2019 スターリンといえば粛清、というような考え方によるソートです。 しかし、ちょっと待ってください。スターリンには粛清以外の選択肢もありました。 すなわち、シベリア送りです。 この記事では、粛清ではなくシベリア送りによる「やさしいスターリンソート」を実装し、データの量を減らすことなく、計算量を減らします。 それによって、銀河に平和をもたらします。 ※このソートは、「スターリンソート」とは異なるのでご注意ください。 「やさしいスターリンソート」とは スターリンソートでは、ソート順に反する要素を粛清することによりソートをしていました。 やさしいスターリンソートでは、粛清
スキップリスト - Wikipedia
スキップリスト（英: skip list）は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log n)である。1989年にウィリアム・ピューが発表した[1][2][3][4]。 スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され（高さ1が確率50%、高さ2が25%、高さ3が12.5%など）、リスト上の探索において連結リストの一部を高速に飛ばすことができる。 スキップリストの例。1〜10を追加し、ソートされた状態で保持されている。 説明[編集] スキップリストはリストの階層になっている。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - google/farmhash: Automatically exported from code.google.com/p/farmhash
GitHub - jtobin/mighty-metropolis: The classic Metropolis sampling algorithm.
アルゴリズムビジュアル大事典
Haskellで二分探索木, AVL木を書いた - Qiita
手続き型脳で型推論を実装してみた | κeenのHappy Hacκing Blog
A Free Ebook on Greedy Algorithms, Divide & Conquer, and Dynamic Programming