GoogleがJPEGエンコーダー「Guetzli」をオープンソースで公開
by greyloch Google製のJPEGエンコーダー「Guetzli」がGitHubで公開されています。生成されるJPEGファイルはlibjpegと比較したとき、同等の品質でファイルサイズが20～30％ほど小さくなるとのことです。 GitHub - google/guetzli https://github.com/google/guetzli 特にニュースリリースなどは発表されていないようなのですが、2016年10月にEncode.ruというフォーラムにJyrki Alakuijala氏が投稿した内容(Googleキャッシュ)によると、このGuetzliはGoogleが新たな圧縮アルゴリズムとして2013年に発表した「Zopfli」ライクな、非常に遅いJPEGエンコーダーだとのこと。 画像の品質とファイルサイズについて、butteraugliを用いてlibjpegと結果を比較した
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
定番アルゴリズム本リスト - カレーなる辛口Javaな加齢日記
どうせ何度も使い回ししそうなので，独立した項目に切り離した． アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一出版社/メーカー: 近代科学社発売日: 2012/08/02メディア: 単行本購入: 1人 クリック: 16回この商品を含むブログ (21件) を見るアルゴリズムイントロダクション 第3版 第2巻: 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一出版社/メーカー: 近代科学社発売日: 2012/12/26メディア: 単行本購入: 1人 クリック: 4回
世界でもっとも強力な9のアルゴリズム - しっきーのブログ
米国の大学教授によるコンピュータ・サイエンスのガイド。大方の人はアルゴリズムと聞くとソートプログラムを思い浮かべるだろうが、本書は普段私達がよく使うようなシステムに関わるアルゴリズムを取り上げる。これはアルゴリズムなのか？というトピックもあるが、重要な考え方を扱っていることに変わりはない。 世界でもっとも強力な9のアルゴリズム 作者: ジョン・マコーミック,長尾高弘出版社/メーカー: 日経BP社発売日: 2012/07/19メディア: 単行本購入: 15人 クリック: 437回この商品を含むブログ (21件) を見る 平易な言葉で説明できていて、数学的な手法を抜きにすれば、コンピューターの基本的な考え方がわりとシンプルにできていることがわかる。「この本の著者として私がとても驚いたのは、これら大きなアイデアは、どれもコンピュータープログラミングやコンピューター科学の予備知識を一切必要とせずに
深さ優先探索による塗りつぶし
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
色々なダイクストラ高速化
KMCの例会講座で用いたスライドを一部編集したものです。 ビット演算を組み合わせたトリッキーな方法で様々な操作を高速に行う方法を紹介します。
Optimizing A* for grid maps
► 2024 ( 1 ) ► March 2024 ( 1 ) ► 2023 ( 14 ) ► December 2023 ( 1 ) ► November 2023 ( 1 ) ► October 2023 ( 1 ) ► September 2023 ( 1 ) ► August 2023 ( 1 ) ► July 2023 ( 1 ) ► April 2023 ( 4 ) ► March 2023 ( 1 ) ► February 2023 ( 1 ) ► January 2023 ( 2 ) ► 2022 ( 13 ) ► December 2022 ( 2 ) ► November 2022 ( 2 ) ► October 2022 ( 2 ) ► September 2022 ( 1 ) ► June 2022 ( 1 ) ► May 2022 ( 1 ) ► April 20
Open Data Structures
Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues, unordered dictionaries, ordered dictionaries, and graphs. Data structures presented in the book include stacks, queues, deques, and lists implemented as arrays and linked-lists; space-efficient implementations of lists; skip lists; hash tables and hash codes; binary search
Parsing Expression Grammar - Wikipedia
Parsing Expression Grammar（PEG）は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。 PEGにおける構文（文法）の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「｜」（縦棒、バーティカルバー）で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」（「/」であらわす）という意味を使う。 このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析
プログラミングコンテストで、C++を使って全ての問題を解くのに必要なアルゴリズムは何ですか？ | POSTD
これが私の提案するリストです。必要とされるアルゴリズムや概念のほとんどが挙げられています。いくつかの要素はアルゴリズムではなかったり（フェイクや状態、関心事など）、重複していたりもします。 最後に1つ、アドバイスを。 知識を蓄える前に、まずは思考能力を鍛えることを重要視しましょう。これはコンテストのみならず、あなた自身の将来にも役立ちます。思考能力を鍛えるには、アルゴリズムではなく純粋な思考を必要とする、アドホックを使いこなせるようになりましょう。 topcoderのDiv2とCodeforcesのDiv2の2つに集中することも効果的だと思います。どちらも、低いレベルから問題に取り組んでいきましょう。例えば、Div2-250をマスターしてからDiv2-500に取り組む、などです。
std::string::findより速くなるかもしれない。boost::algorithmのboyer_moore_searchとかknuth_morris_pratt_searchとか - Qiita
std::string::findより速くなるかもしれない。boost::algorithmのboyer_moore_searchとかknuth_morris_pratt_searchとかC++文字列 この記事は、C++ Advent Calendar 2014の2014年12月7日ぶんです。（1時間弱遅刻してしまいました） これは何ですか C++標準の文字列クラスstd::stringには、その中に指定されたキーワード（文字列）が含まれているか&含まれている場合には何文字目から出現するかを返すメソッドとして、std::string::findが用意されている。 多くの場合これがあれば事足りるのだが、あまり長い文字列を検索キーワードに指定するような場合には、（少なくとも理論的には）大幅に遅くなることが知られている。 これを改善した（少なくとも理論的には）アルゴリズムとして、Boyer-Mo
アルゴリズムとプログラミングをビジュアルで一挙に理解できる「VisuAlgo」
アルゴリズムを理解するのにビジュアル化することは非常に有効で、プログラムをビジュアル化することで理解が進むのもまた同じ。そこで、アルゴリズム・プログラミングの理解が進むようにと、アルゴリズムを記述したプログラムコードを一挙にビジュアル化することで、アルゴリズム＆プログラミングを同時に学習できる一挙両得なサービス「VisuAlgo」が公開されています。 VisuAlgo - visualising data structures and algorithms through animation https://visualgo.net/en 上記のVisuAlgoサイトで試しにソートアルゴリズムの基本プログラム「バブルソート」をビジュアル化してみます。「Sorting」の「bubble」をクリック。 検索窓の下に「bubble」と表示されたのを確認したら「Sorting」の画像をクリック。
平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
日本の競技プログラミングを世界水準に引き上げる レッドコーダー 秋葉拓哉 | 三年予測 | dodaエンジニア IT
レッドコーダー 秋葉拓哉 1988年生まれ。25歳。高校2年生のときにプログラミングコンテスト「SuperCon」で準優勝、 「日本情報オリンピック」にて優勝を達成。それ以降プログラミングコンテストに精力的に参加し、 2012年に「ACM-ICPC」世界大会にて銅メダルを獲得。 プログラミングコンテスト向けアルゴリズム書『プログラミングコンテストチャレンジブック(第二版)』(マイナビ)が発売中。 秋葉拓哉は、最初は自分がレッドコーダーになれるとは思っていなかったそうだ。 レッドコーダーとは、約60万人がオンラインで参加するプログラミングコンテスト「TopCoder」での成績を示す数字「レーティング」が2200以上の挑戦者のことだ。プログラマの中でも一目置かれる存在である。 2007年に秋葉が大学に入りTopCoderの存在を知った頃、レッドコーダーは日本で4人しかいなかった。レッドコーダー
コンピュータを進化させてきた偉大なるアルゴリズムまとめ
By Kai Schreiber IT技術の進化のスピードには目を見張るものがありますが、それを支えているのはアルゴリズムと呼ばれる処理方法(技術的アイデア)です。さまざまなアルゴリズムの中でも、コンピュータの進化に革命的な影響をもたらしたとされる偉大なアルゴリズムは以下の通りです。 Great Algorithms that Revolutionized Computing http://en.docsity.com/news/interesting-facts/great-algorithms-revolutionized-computing/ ◆ハフマン符号(圧縮アルゴリズム) Huffman coding(ハフマン符号)は、1951年にデービッド・ハフマン氏によって開発されたアルゴリズム。頻出頻度の大小によって対戦するトーナメントツリーを考えて、ブロックごとに0と1の符号をもたせる
最近点対問題の線形時間乱択アルゴリズム - うどん記
これは Competitive Programming Advent Calendar Div2013 の 20 日目の記事です．最近点対問題の話をします． 最近点対問題は，空間上に点の集合が与えられた時に，その中で最も距離が近いペアを探す問題です． 応用としては，何らかのオブジェクトを特徴ベクトルに写した後で，最も類似したペアを探したいときなどに役に立つのではないかと思います．競技プログラミング界では，今年のICPC会津大会で3次元上の最近点対問題が出題されました． 空間が平面のときは分割統治による $O(n\log{n})$ 時間アルゴリズムが有名かと思います．今回は一般の次元で，(ハッシュマップを用いて)線形時間で動く実装が楽そうな乱択アルゴリズムの紹介をします．参考にした文献は以下のサーベイです． Smid, Michiel. Closest point problems in c
message threading
message threading. © 1997-2002 Jamie Zawinski <jwz@jwz.org> In this document, I describe what is, in my humble but correct opinion, the best known algorithm for threading messages (that is, grouping messages together in parent/child relationships based on which messages are replies to which others.) This is the threading algorithm that was used in Netscape Mail and News 2.0 and 3.0, and in Grendel
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://metodosestadisticos.unizar.es/asignaturas/62801/DiferentialEvolution.pdf
warterlogueのアルゴリズム分析
VisuAlgo moves to https://visualgo.net/en