文字列検索アルゴリズムの覚え書き - 我らねぶた馬鹿
マイコミジャーナルの連載記事で、「StringSearch」という文字列検索のためのJavaライブラリを紹介しました。 攻略! ツール・ド・プログラミング (44) 高速な文字列検索を実現するJavaライブラリ「StringSearch」 | マイナビニュース その補足も兼ねて、記事中に出てくる文字列検索アルゴリズムについて少しまとめてみました。細部を省略した大雑把な説明なので厳密な解説ではありませんが、参考までに。 naiveアルゴリズム 対象の文字列とパターン文字列を先頭から順番に比べていき、マッチしなかったら1文字進めてまた最初から比べるという手法です。 java.lang.StringのindexOf()メソッドなどはこの実装だそうです。 Knuth Morris Pattアルゴリズム（KMPアルゴリズム） マッチに失敗した場合に、比較するスタート位置を1文字ずつ進めるではなく、何
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
特集！知らないと損をする計算量の話 - Qiita
1. はじめに 今回は実務プログラミングにおいて知らず知らずのうちに遅いコードになっていそうな例をいくつか挙げて、それを計算量の観点から高速化してみたいと思います。 2. 計算量を意識することにどんな意味があるか 身近な例として、Qiita Contribution ランキングの作成を考えてみましょう。ランキングを作成するためには、各ユーザーの Contribution 数を大きい順に並び替える処理、すなわちソートが必要になります。 Qiita ユーザー数は現在およそ $30$ 万人です。標準ライブラリの sort を用いれば、それほどの計算時間はかからないと思います。しかし仮にこれを愚直な sort アルゴリズム (例えば、挿入ソートやバブルソートなど) で実行したら恐ろしいことになります。 愚直なソートは、並び替える要素の個数の 2 乗に比例した時間がかかります。すなわち $n$ を並
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ - Qiita
はじめに --- DP は役に立つ はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 巷ではよく「DP なんて実務では使わない」といった言説が定期的に流れますが、そんなことはないです。僕自身この 2 年間で DP が使える実務案件に 3 件くらい関わりました！ それはともかくとして、DP を学び立ての方がよく抱く悩みとして「バリエーションが多すぎて混乱するし、統一的なフレームワークがほしい」というのがあります。確かに DP のバリエーションは非常に多岐にわたるのですが、そのほとんどが以下の 3 つのフレームワークで説明できると思います: ナップサック DP 区間 DP bit DP 今回はこのうちのナップサック DP について、とにかく
アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～ - Qiita
今の場合は A さんが 31 歳の場合のストーリーでしたが、A さんが 20 歳～ 35 歳のうちのどの年齢であったとしても、似たようなストーリーで必ず 4 回の質問で当てることができます！(他の例も是非考えてみてください。) ちなみに、このような「真ん中で切ってどちらかに絞って行く」タイプのアルゴリズムには二分探索法という名前がついています。応用情報技術者試験でも頻出のテーマですので馴染みのある方も多いと思います。 1-2. つまり、アルゴリズムとは 上の年齢当てゲームという問題では、相手の年齢を当てる「方法・手順」を二分探索法に基づいて導きました。このようにアルゴリズムとは、 問題を解くための方法・手順 のことです。さて、アルゴリズムと聞くと「コンピュータ上で実装されたプログラム」のことを思い浮かべる方も多いと思いますが、必ずしもコンピュータと関係がある必要はなく、日常生活でも多々登場
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
NVIDIAが｢この画像をあの画像っぽく｣できる高速で高品質なAIアルゴリズム｢FastPhotoStyle｣を公開
NVIDIAが｢この画像をあの画像っぽく｣できる高速で高品質なAIアルゴリズム｢FastPhotoStyle｣を公開2018.03.28 12:4531,133 たもり 本物かと見間違うクオリティ。 以前取り上げた雪原を草原に変えるAdobeのアルゴリズムなど、画風変換のアルゴリズムは何も真新しいものではありません。しかし、NVIDIAが発表したAIアルゴリズム｢FastPhotoStyle｣は、既存のアルゴリズムより各段に速い処理スピードを誇り、出来上がった画像のクオリティも高いのです。 FastPhotoStyleを開発したのは、 NVIDIAとカリフォルニア・マーセッド大学の科学者チーム。先月、｢A Closed-form Solution to Photorealistic Image Stylization｣という論文を発表しました。 PetaPixelによれば、従来のこういった
df-pnアルゴリズムを用いた詰将棋Solverによる最善解・余詰の導出 - すぎゃーんメモ
以前書いた、詰将棋問題生成の続き。 memo.sugyan.com 逆算による詰将棋の問題生成の方法自体は悪くないとして (バグによって有り得ない局面が出来上がったりしてしまったりもしたけど)、正しく詰将棋問題として成立するものが出来上がっているかどうかを検証するためのSolverが必要不可欠であり、これのパフォーマンスが生成のパフォーマンスにも影響してくる、というようなことを書いた。 実際、前回の記事のときに実装したSolverでは 総当たり的に探索するのは3〜5手が限界 詰将棋のルールに則る動きに限定しても、有り得る局面は指数関数的に増加する 合駒が絡む問題に対して正しく解が導けないことがある 先の展開まで読まないと無駄な合駒かどうかの判定ができない といった問題があった。 df-pnアルゴリズムによる探索 2002年の論文「df-pn アルゴリズムの詰将棋を解くプログラムへの応用」が
縦横比を無視したリサイズをしても違和感のない画像に仕上げることができる画像リサイズ用ライブラリ「Caire」
画像ファイルのリサイズはすべてのピクセルに対して均等に伸縮させるものです。このため、人物や建物が写っている画像に縦横比を無視したリサイズを行うと、被写体のバランスも崩れてしまい、違和感のある画像になってしまいます。画像リサイズ用ライブラリ「Caire」は画像内にある人物や建物などの比率を維持したままリサイズでき、違和感のない画像を作り出せます。 GitHub - esimov/caire: Content aware image resize library https://github.com/esimov/caire 「Caire」はSeam carvingアルゴリズムを使った画像リサイズ用ライブラリです。Seam carvingアルゴリズムはレスポンシブウェブデザインを採用したウェブページのように、画面サイズに応じて画像のリサイズを行うようなコンテンツにおいて、縦横比を無視したリサイ
一から学ぶベジェ曲線 | POSTD
(編注：SVGアニメーションを元記事にならい追加しました。リクエストありがとうございました。) 皆さんは線分のことをどう表現しますか？ 線分は、端点によって考えられるかもしれません。その端点を P0 、 P1 と呼ぶことにしましょう。 線分を厳密に定義するならば、「 P0 と P1 を結ぶ直線において、 P0 と P1 の間にある全ての点の集合」と言えるかもしれません。これは以下のように表せるでしょう。 便利なことに、上記の定義から、その線分上のどこにある点の座標でも簡単に求めることができます。例えば、中点は L(0.5) にあります。 実は、2点間のどんな値でも、任意の精度で 線形補間する ことが可能です。そのため、時間関数 L(t) の t で線をたどるといった、より複雑なことができるのです。 ここまで来ると、「それが曲線と何の関係があるのか？」と不思議に思うかもしれません。2つの点だ
モールス符号の「地図」 - roombaの日記
謎の遺跡 ある遺跡を考えます。唯一の入口からその遺跡の中に入ると2つの扉があり、扉にはそれぞれ「・」「ー」という2種類の文字が書いてあります。 試しに「・」と書かれた扉を開き、隣の部屋に移動すると、またもや「・」「ー」と書かれた2つの扉があります。先ほどの部屋と違うのは、扉と扉の間に「E」と書かれていることです。 今度は「ー」と書かれた扉を開き、隣の部屋に移動すると、やっぱり「・」「ー」と書かれた2つの扉があって、その間には「A」という文字が書かれていました。 ……この遺跡を探検すると、どのような間取りになっているのでしょうか？ 遺跡の「地図」 ある人がこの遺跡を調査した結果、以下の地図のように部屋がつながっていることが判明しました。一番上が入口の中の部屋で、下に行くほど遺跡の奥に対応します。 この地図を使えば、好きな部屋に迷わず行くことが可能になります。 たとえば、「A」と書かれた部屋に
組合せ最適化を使おう - Qiita
野菜の選び方はナップサック問題、乗り換え駅探索は、最短路問題といいます。典型問題は、よく研究もされているので、多くの場合、効率的な解法があります。あるいは、定式化がされているので、すぐ解くことができます。あとで、やってみましょう。ここで、あげている全ての典型問題の実行例は、典型問題と実行方法をご覧ください。 汎用問題 最近、私がやっているコンテナの仕事のお話しをします。 世界中の人たちが、いろいろなものを安く買えるのはコンテナ輸送のおかげです。中国などで生産したものを日本やアメリカやヨーロッパに、大量に安く運べるからです。でも、空のコンテナが、どんどんたまります。また中国に戻さないといけません。いつ、どこからどこに戻すかを決めるのが、最小費用流問題になります。ところが、最小費用流問題で表せない制約条件もあります。1 つが、カボタージュとよばれるものです。カボタージュというのは、国内のみの輸
CodeIQについてのお知らせ
2018年4月25日をもちまして、 『CodeIQ』のプログラミング腕試しサービス、年収確約スカウトサービスは、 ITエンジニアのための年収確約スカウトサービス『moffers by CodeIQ』https://moffers.jp/ へ一本化いたしました。 これまで多くのITエンジニアの方に『CodeIQ』をご利用いただきまして、 改めて心より深く御礼申し上げます。 また、エンジニアのためのWebマガジン「CodeIQ MAGAZINE」は、 リクナビNEXTジャーナル( https://next.rikunabi.com/journal/ )に一部の記事の移行を予定しております。 今後は『moffers by CodeIQ』にて、 ITエンジニアの皆様のより良い転職をサポートするために、より一層努めてまいりますので、 引き続きご愛顧のほど何卒よろしくお願い申し上げます。 また、Cod
ランダムフォレストのつくりかた（C++の実装例つき） - じじいのプログラミング
この記事は24日目の記事のつづきです。前日の関連記事「ランダムフォレストのつかいかた」もありますので、こちらもよろしくお願いします。 ランダムフォレストのつかいかた - じじいのプログラミング ランダムフォレストは、機械学習の中でも、確率統計の知識がほぼ無しで実装できる簡単なアルゴリズムで、しかも性能もなかなかのものです。TopCoder機械学習マッチのいくつかは、コードを提出してTopCoderサーバで実行するルールなので、実装しやすいランダムフォレストは有力な選択肢です。実際にランダムフォレストが１位をとったコンテストもかなりあります。 決定木の作り方さえ理解すれば、ランダムフォレストは実装できたも同然ですので、この記事では、決定木を作る部分をメインに取り上げます。 アドバイスをいただけると、とてもうれしいです。間違いのご指摘は大歓迎です。 実装は、TopCoderの他の競技者（Psy
大規模グラフ解析のための乱択スケッチ技法
1. The document discusses probabilistic modeling and variational inference. It introduces concepts like Bayes' rule, marginalization, and conditioning. 2. An equation for the evidence lower bound is derived, which decomposes the log likelihood of data into the Kullback-Leibler divergence between an approximate and true posterior plus an expected log likelihood term. 3. Variational autoencoders are
クリスマスの歌
今年もクリスマスが近付いた. 最近の私にそういう機会はないが, 以前はクリスマスキャロルに誘われて聞きにいったりした. そこで歌われる歌の中に, On the first day of Christmas,... で始まる歌がある. 出典によって文句や順番が多少違ったりするが, 大体はこうだ. On the 1st day of Christmas, my true love sent to me: a Partridge in a Pear Tree. On the 2nd day of Christmas, my true love sent to me: 2 Turtle Doves and a Partridge in a Pear Tree. クリスマスの1日目, 私の恋人は ナシの木の1羽のヤマウズラをくれた. クリスマスの2日目, 私の恋人は 2羽のヤマバトと ナシの木の1羽
［CEDEC 2014］「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」 - 4Gamer.net
［CEDEC 2014］ナムコ作品で見る乱数の歴史。「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」レポート ライター：箭本進一 神奈川のパシフィコ横浜で行われた，ゲーム開発者向けイベントCEDEC 2014の最終日である2014年9月4日，「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」という講演が行われた。 登壇したバンダイナムコスタジオ HE技術部 加来量一氏 この講演のユニークな点は，旧ナムコの作品を「乱数」という視点から振り返るということだ。バンダイナムコスタジオ HE技術部のプログラマーである加来量一氏は，旧ナムコの初期作品50本を解析し，それぞれの時代でどのような乱数が使われていたかを特定した。そこから見えてくる乱数技術改良の歴史を見ていくというのが，講義の主旨なのである。 1980年代のナムコアーケ
実践・最強最速のアルゴリズム勉強会 第三回講義資料(ワークスアプリケーションズ & AtCoder)
書籍『問題解決力を鍛える！アルゴリズムとデータ構造』 の出版を記念した講演会を 2020/10/29 に実施しました。 そのときに「動的計画法についてもっと聞きたい」という声を多数いただきました。それを受けて、 「動的計画法に学ぶ数理科学の精神」 と題しまして、2021/1/22 に第二弾の講演会を行いました。そのときの講演資料です。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.graco.c.u-tokyo.ac.jp/icpc-challenge/wp-content/uploads/2014/12/2014.pdf
実践・最強最速のアルゴリズム勉強会 第二回講義資料(ワークスアプリケーションズ & AtCoder)
