最も簡単に fib を高速化する方法 - ドレッシングのような二つ値を返せば良いんですよ。メモ化なんてしなくていい。
計算量とBig-O記法 - 素人がプログラミングを勉強していたブログ
プログラマであればアルゴリズムに関する話で、O(n)だとかO(log n)だとか、O(n2)だとか、そういった記号を目にすることはよくあると思う。 なんとなく、log n < n < n2の順に計算量が増加していくとかそういうことも知っていると思うが、計算量の増加とは何か説明しろと言われると、なかなか難しいと思う。この記事では高校数学レベルでわかるように考えていきたい。 まず、計算にかかる時間を、nを入力のサイズとしてf(n)を計算にかかる最大時間を返す関数とすると、計算量一般を、O(f(n))という、入力に対する計算時間の増加率として定義することができる（より厳密には、f:R+ -> R+ where R+=[0,∞)で、a>bであればf(a) >= f(b)であるとき）。 g(n) = n ^ 2 はn = 1に対して1を返す一方、より増加率の低い h(n) = n + 100 は、n
ウェーブレット行列とFM-indexで全文検索を書いてみた - くじらにっき++
www.youtube.com 去年のはじめに高速文字列本を買ったのですが、アルゴリズムを眺めるだけで実装はしていませんでした。特にウェーブレット行列は実装が大変そうにしか見えなくて敬遠していたのですが、ICPCの夏合宿で @hirokazu1020 さんに「あれはアイデアさえ理解していれば実装するのは簡単だよ」という旨のことを言われたので、学校のプログラミングの演習の自由課題としてウェーブレット行列とFM-indexを実装してみました。 制作物はブラウザ上で動く青空文庫のインクリメンタル検索です。C++で書いたFM-indexをboost-pythonを使ってPythonから呼び出せるようにし、Flaskを使ってブラウザからのリクエストに応答するような仕組みにしてみました。アルゴリズムの本質的なところは全て自分で書こう！というモチベーションで始めたのですが、SA-ISが難しくてsais.
これはヒドイ「初中級エンジニアが【アルゴリズムを優しく学べる】本とサイト16選」 - カレーなる辛口Javaな加齢日記
http://paiza.hatenablog.com/entry/20141014algorithm うーん，これはヒドイ．これ書いてる人は，おそらくプログラマーじゃない． 「アルゴリズムとデータ構造」の参考書／学習書ではなく読み物の比率が高い．ソフトウエアエンジニア／プログラマーでない人が，なんちゃってアルゴリズムを囓るのにはこれでもいいけど，プログラマの勉強用じゃねーな． 今出てるアルゴリズム本だと，だいたいこの辺だと思う． アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一出版社/メーカー: 近代科学社発売日: 2012/08/02メディア: 単行本購入: 1人 クリック: 16回この商品を含むブログ (21
作って覚える転置インデックス、「検索エンジン自作入門」 - プログラマでありたい
先行発売で、検索エンジン自作入門を購入しました。まだペラペラと眺めている状況ですが、これが非常に面白いです。 「検索エンジン自作入門」は、集めた文章をいかに整理するかをテーマとして扱っている本です。整理するという意味は、検索エンジンを利用するというライフハック的な意味ではありません。整理する為の検索エンジン自体を自分で作ることで理解するという、極めて硬派な本です。 「検索エンジン自作入門」とは？ 「検索エンジン自作入門」は、未踏IT人材発掘・育成事業にスーパークリエータに認定された山田浩之氏と、Senna/groongaの開発者の末永匡氏の共著です。検索エンジンについて語らせたら、日本でこれ以上の人たちはいないだろうという組み合わせです。ということで、内容は非常に濃いのですが、難しい内容を解りやすく解説されています。 一方で、扱っている内容は非常にマニアックです。下に目次付けておくので見て
人工知能を実現する学習アルゴリズムに必要な能力 - 人工知能に関する断創録
今年は、Deep Learningを研究する予定（2014/1/4）だったのだけれど、多層パーセプトロンまで到達した（2014/2/5）ところで少々（？）足踏みしている。Deep Learningの構成要素であるボルツマンマシンを理解するのに手間取っているためだ。ボルツマンマシンの理解には、マルコフ確率場やMCMCの理解が必要なことがわかったので少し廻り道してモンテカルロ法を先に勉強（2014/6/20）していたというわけ。 ただ、そればかりでは少々退屈になってきたので少し先回りして Deep Learning の先駆者のBengioさんが書いた論文 Learning Deep Architectures for AI を勉強している。示唆に富む見解が多いのであとで振り返られるように記録しておきたい。 まずは、1.1節のDesiderate for Learning AIの部分。人工知能を
Visualizing Garbage Collection Algorithms
Most developers take automatic garbage collection for granted. It’s just another amazing feature provided by our language run-times to make our jobs easier. But if you try to peek inside a modern garbage collector, it’s very difficult to see how they actually work. There are thousands of implementation details that will confuse you unless you already have a good understanding of what it’s trying t
検索エンジン自作入門 | 技術評論社
概要 まいにち使っている検索エンジンがどうやって動いているか、知っていますか？ 本書では、小さな検索エンジンを作りながら、ソースコードレベルで検索エンジンのしくみを解説。 Yahoo!Japanの検索エンジン開発チームを経て2008年度上期未踏IT人材発掘・育成事業において高性能分散型検索エンジンの開発によりスーパークリエータに認定された山田浩之氏と、全文検索エンジンSenna／Groongaの開発に携わってきた末永匡氏による、オンリーワンの1冊です。 目次 第1章 検索エンジンはいかにして動くのか 1-1 検索エンジンの構成を理解する 検索エンジンとは 検索エンジンを構成するコンポーネント 検索エンジンに関連するコンポーネント 1-2 高速な全文検索を実現するインデックスの仕組み 全文検索の2つの方法 転置インデックスの仕組み 転置インデックスの作り方 転置インデックスで用いられる用語
Java8 で java.lang.Object#hashCode() の生成アルゴリズムが変更されていました。 - 地平線に行く
java.lang.Object#hashCode()の性質という記事で書いたのですが、Java の Object#hashCode() の値はただの乱数となっています。 この乱数のアルゴリズムが、Java SE 8 で「線形合同法」から「XORシフト方式」に変更になっていました。 といっても、変更されたのはたった1文字。 VMオプションのデフォルト設定が -XX:hashCode=0 から -XX:hashCode=5 に変わっただけでした。 hotspot-rt Udiff hotspot/src/share/vm/runtime/globals.hpp どういうこと？ もともと、Java の以前の実装*1 *2から、Object#hashCode() のアルゴリズムはVMオプション -XX:hashCode=? で選べるようになっていました。 ですが、デフォルトは長いこと 0(=線形
機械学習アルゴリズムへの招待 | POSTD
機械学習の問題 については以前に紹介したので、次はどんなデータを収集し、どんな機械学習アルゴリズムを使うことができるのかを見ていきましょう。本投稿では、現在よく使用されている代表的なアルゴリズムを紹介します。代表的なアルゴリズムを知ることで、どんな技法が使えるかという全体的なイメージもきっとつかめてくるはずですよ。 アルゴリズムには多くの種類があります。難しいのは、技法にも分類があり拡張性があるため、規範的なアルゴリズムを構成するものが何なのか判別するのが難しいということですね。ここでは、実際の現場でも目にする機会の多いアルゴリズムを例にとって、それらを検討して分類する2つの方法をご紹介したいと思います。 まず1つ目は、学習のスタイルによってアルゴリズムを分ける方法。そして2つ目は、形態や機能の類似性によって（例えば似た動物をまとめるように）分ける方法です。どちらのアプローチも非常に実用的
プログラマのための文書推薦入門 (社内勉強会の発表資料) - y_uti のブログ
勤務先の社内勉強会で、機械学習を用いた文書推薦*1に関する基本的なことがらについて説明しました。その資料を公開します。 プログラマのための文書推薦入門 from y-uti 数学やコンピュータサイエンスを専門的に学んでいないエンジニアでも理解しやすいように、できるだけ数式を使わずに説明したつもりです。厳密性にはこだわっていないので、専門家からはあちこちツッコミを受ける内容かもしれません。 プログラマ向けということで、実際にコンピュータ上で動作を確認できるように、Wikipedia のデータを対象にして類似文書検索を行うスクリプトを作成しました。GitHub に置いてあります。 y-uti/document-recommendation · GitHub *1:推薦というより情報検索、類似文書検索という方が適切だったかもしれません。
もし女子大生プログラマに『アルゴリズム』を図解で教えるとしたら -
2014年4月16日より2014年5月14日まで開催していたpaizaオンラインハッカソン（略してPOH![ポー！]）Vol.2「女子大生とペアプロするだけの簡単なお仕事です！」で提出された最速コードはどのような高速化のアプローチでで生み出されたのでしょうか？ POH Vol.2に登場した女子大生インターンプログラマの木野ちゃん（左のイラスト）にアルゴリズムを図解で教えるとしたら、どう教えるだろうか、という事で、今回は図解してみました。 今回は前回の最速コード発表レポート（【結果発表】女子大生プログラマの心を鷲掴みにした最強のコード8選）に引き続き、最速コードの裏側に迫ります。 ■高速化のアプローチ方法について 今回もPOH Vol.1 と同様に、POH Vol.2では計算量の改善による高速化を柱とするアプローチを想定して出題されました。基本は定数倍高速化によって想定解法よりも悪い計算量の
【読書感想】世界でもっとも強力な9のアルゴリズム ☆☆☆ - 琥珀色の戯言
世界でもっとも強力な9のアルゴリズム 作者: ジョン・マコーミック,長尾高弘出版社/メーカー: 日経BP社発売日: 2012/07/19メディア: 単行本購入: 15人 クリック: 437回この商品を含むブログ (21件) を見る Kindle版もあります。こちらのほうが低価格。 世界でもっとも強力な9のアルゴリズム 作者: ジョンマコーミック出版社/メーカー: 日経BP社発売日: 2013/10/10メディア: Kindle版この商品を含むブログ (6件) を見る 内容紹介 コンピュータを使い物にするアルゴリズムにはどういうものがあるか、今日的な視点から選んだ実際に役立っている9のアルゴリズムのアイデアを、章ごとに掲げてわかりやすく説明した読み物です。 図を多用し、その仕組みをたとえを使いながら見せることに重点を置いています。著者が選んだ基準は、 (1)インターネットでメールやブラウザを
平方数かどうかを高速に判定する方法 - 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関数として利用できます）。本稿ではこの実装
幅優先探索 | アルゴリズム[Ruby/Python][AOJ 0129]
『幅優先探索』をRuby/Pythonで解いてみました。AIZU Online Judgeで対応している問題は『Seven Puzzle』です。 🏀 概要深さ優先探査の説明は『通勤・通学中に理解する深さ優先探索と幅優先探索』、 『アルゴリズム図鑑：iOS & Androidアプリ』が分かりやすかったです。 要点は次のとおり。 根ノードで始まり隣接した全てのノードを探索。階層(根ノードからの距離が近い順)にルートを調べる 🐯 サンプル問題(AOJ)Seven Puzzle Aizu Online Judge。1-7までの数字と、1つ空白のあるパズルをとく問題。 😀 Rubyコード 01234567がそろった状態(ゴール)からスタートして、0を移動させる 幅優先探索で過去に到達していない状態になったら、手数(移動数)を記録 すでに到達済の状態であれば、スキップ(幅優先探索なら手数が同等か
![幅優先探索 | アルゴリズム[Ruby/Python][AOJ 0129]](https://cdn-ak-scissors.b.st-hatena.com/image/square/c2ea7e72d0d7f3ba6c237909f321e67ffbdaa24e/height=288;version=1;width=512/https%3A%2F%2Fmorizyun.github.io%2Fimg%2Fog_image.png)
Non-blocking Transactional Atomicity | Peter Bailis
Peter Bailis :: Highly Available, Seldom Consistent Data management, distributed systems, and beyond Non-blocking Transactional Atomicity 28 May 2013 tl;dr: You can perform non-blocking multi-object atomic reads and writes across arbitrary data partitions via some simple multi-versioning and by storing metadata regarding related items. N.B. This is a long post, but it’s comprehensive. Reading the
WebSocketを再接続するアルゴリズムの工夫 - ワザノバ | wazanova
http://blog.johnryding.com/post/78544969349/how-to-reconnect-web-sockets-in-a-realtime-web-app 1 comment | 0 points | by WazanovaNews ■ comment by Jshiike | 約2時間前 John RydingのブログでWebSocketの再接続のアルゴリズムの工夫について紹介しています。 リアルタイムウェブアプリにおいて、何らかの理由でバックエンドとの接続が切れた場合、クライアントは一定間隔で再試行するというロジックを設定（参考コード）していたとします。その場合、大量のクライアントがいて、もし長い時間接続が不能であれば、再開時にバックエンドには大量のリクエストが集中することになります。 そこでJohnがお薦めするExponential Backoff
グラフの自動レイアウトに挑戦 #1 グラフ構造をSVGで表示
2022-08-12 13:50:22 作成したアプリケーションとソースコード アプリケーション： https://refd6y.csb.app/ （ブラウザで実行します） ソースコード： https://codesandbox.io/s/graph-layout1-refd6y はじめに 連載記事のトップのところに書いた図はこのようなものだ。 これをコンピュータに自動配置させたい。 Eadesのばねモデル このような、つながった複数の物体をコンピュータに自動配置させるのは「グラフ描画」または「グラフレイアウト」と呼ばれる分野であり、さまざまなアルゴリズムが研究されている。この連載記事では比較的単純な「Eadesのばねモデル」というアルゴリズムを採用する。 Eadesのばねモデルとは、次のようなモデルをつくって物理シミュレーションすることで、物体を配置するアルゴリズムだ。 各ノード(頂点)
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－
1000万件の高評価がたった1件だけの評価に負けないスコアランキングアルゴリズム（ライブラリ）
