[ 目次, 前節, 次節, 索引 ] 2014-03-06 更新 [ 目次, 前節, 次節, 索引 ]
計算機プログラムの構造と解釈 第二版
[ 目次, 前節, 次節, 索引 ] 2014-03-06 更新 [ 目次, 前節, 次節, 索引 ]
jumbled pattern matchingというのを知った - EchizenBlog-Zwei
Binary Jumbled Pattern Matching via All-Pairs Shortest Paths(http://arxiv.org/pdf/1401.2065v1.pdf)という論文がLOUDS論文をreferしていて興味があったので読んでいた。jumbled pattern matchingという問題の時間計算量を改善したよ、という話だった。 不勉強ながらjumbled pattern matchingという言葉を知らなかった(もしくは忘れていた)。幸い、この論文にどういう問題であるか解説があったので容易に理解することが出来た。 なので忘れないうちにメモしておく。 jumbled pattern matchingというのはマッチさせる単語の文字の順番が入れ替わっていてもマッチさせるパターンマッチ。つまりabracadabraに対してabraだけでなくbaraもマッ
動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング
この記事は、Competitive Programming Advent Calendar Div2013（http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83）の8日目の記事です。 動的計画法(Dynamic Programming, DP)についての記事です。 12/9 前編にサンプルプログラム（http://ideone.com/2B7f4v）を追加しました 12/11 前編の図２つを差し替えました。 はじめに まずは、本やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。 プログラミングコンテストでの動的計画法 http://www.slideshare.net/iwiwi/ss-3578511 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メ
About - Project Euler
About Project Euler What is Project Euler? Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems. The motivation for starting Project Euler, and
疎行列の格納方式メモ - Negative/Positive Thinking
はじめに 巨大だけどほとんどの要素がゼロであるような疎行列は、そのまま保持するより、要素がゼロじゃないところだけをうまく保持する事でメモリや計算量を減らせたりする。 扱う行列のタイプによって、効率のよい形式がいくつかあるようなので代表的なものをメモしておく。 Coodinate(COO) Format 非ゼロ要素の(row indices, column indices, value)を要素数分持たせる形式 非ゼロ要素が散らばっている場合に有利 0 4 0 0 2 0 0 0 1 を row 0 1 2 column 1 1 2 value 4 2 1 のように保持する。 compressed sparse row(CSR) Format / compressed sparse column(CSC) Format Coodinate Formatにおいて、左から右、上から下へ順番に要素を
CodeIQで結城先生が出題されたCrossingが神がかっていた件 - やねうらおブログ(移転しました)
CodeIQで挑戦者数が400人超えという異例の事態になったCrossingとはどんな問題だったのか。twitterでも恐ろしい勢いで拡散され、最終日に100人を超えるチャレンジがあった、この問題。一体どこにそんな魅力があったのかについて考えてみる。 まず、このように注目されるためには満たすべき条件が二つある。 繁盛する飲食店を考えてもわかるように、まず美味しくなければならない。CodeIQで言うと、問題として良問でなければならない。解答後の達成感がなくてはならない。 次に、飲食店なら、その店に入ってみようという気にさせなければならない。入りにくそうなお店でも、料理さえ美味しければその後口コミで広がることもあるだろうが、それだと繁盛するまでに時間がかかりすぎる。だからCodeIQで言うと、まず問題を解いてみようという気にさせなければならない。 このどちらが欠けても駄目である。この問題はこの
非復元抽出の高速かつ実装が簡単な方法を考える - シリコンの谷のゾンビ
※ @tomerun さんに書いてもらったコードとその検証結果を記事の最後に追記しました．(2013-07-21 2:00) ふとしたきっかけで非復元抽出 (random sampling without replacement) を実装するときに気になったのでどんな実装がよいのか考えてみた．なお非復元抽出はビンゴのように，N個の要素の中からk個の異なる要素をランダムに選択するという意味である． 復元抽出については @unnonouno さんのブログなどに書いてあり，非復元抽出についてもリンクが張ってあったのだけれど，リンク先のブログ記事が読めない状態になっていていたのが残念． unnonouno: 高速な復元抽出の直感的な説明 はじめに std::vector
Googleの人のオークション理論論文でも読んでみる その1 - Fire and Motion
Goel, G., Mirrokni, V. and Leme, R. P., Polyhedral Clinching Auctions and the Adwords Polytope, 44th ACM Symposium on Theory of Computing (STOC 2012). Google の2012年excellent paperが挙げられていて，その中にオークション理論の論文があった．Machine Learningと異なり，オークション理論，メカニズムデザインは自分の専門分野の一つなので，かいつまんで紹介してみる．あまり厳密な数学的記述は行わず，わかりやすさ重視で説明してみたい． まず，オークションに関する多くの誤解を解いておきたい．オークションというとある品物（財）を高く売りつける方法，または（ヤフオクのように）いらないものを処分する方法と実用上，捉えられが
一般向けのDeep Learning
PFI 全体セミナーで発表した、専門家向けではなく一般向けのDeep Learning（深層学習）の解説です。どのような場面で活躍しているのか、今までの学習手法と何が違うのかを解説しています。
Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell
Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them. Over the last few years, I
wat-arrayでラクラク実装☆FM-Indexの作り方 - EchizenBlog-Zwei
というわけで大変便利なライブラリwat-arrayを使ってFM-Indexを簡単に実装してみるよ。本格的なライブラリは既にFM-Index++という良いものがあるので、本記事では仕組みの解説を目的とする。 参考資料: FM-index++を公開しました - tb_yasuの日記 An alphabet-friendly FM-index (P. Ferragina, G. Manzini, V. Makinen, G. Navarro, 2004) なお、本記事では前回の記事で実装した(ってほどでもないけど)text2bwt()とLF()を使っている。 話題のwat-arrayを使ってBurrows-Wheeler変換(BWT)してみた - EchizenBlog-Zwei 今回もテキストとしてmississippi#を使う。まずテキストから任意のキーの出現回数を得る関数get_rows(
FM-index++を公開しました - Yasuo Tabeiの日記
FM-indexのC++による実装 FM-index++を公開しました。 http://code.google.com/p/fmindex-plus-plus/ FM-index[1〜4]とは、圧縮全文索引の一種でO(n)時間とO(nlgσ)メモリー(n:テキスト長、σ:文字種類数)で構築することができます。最近では、テキスト処理ばかりでなくゲノム検索[5]など、いろいろなところで応用されています。今回は、クエリーに対する検索操作の内、exact検索、ハミング距離による検索、編集距離による検索の３つを実装しました。それぞれの計算時間は、qがクエリーの長さとすると、exact検索がO(q)時間、 ハミング距離による検索がO(q^σ)時間、編集距離による検索がO((q \times q)^σ)時間です。よって、４文字種のDNAや２０文字種のタンパク質など、文字種類数が少ない対象にはハミング距離
Locality Sensitive Hashによる類似ベクトル検索を試す - Negative/Positive Thinking
はじめに 類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、 類似するものを高速に検索することができるので、それを試してみた。 Locality Sensitive Hash 類似するデータが高確率で近い値になる(Locality-Sensitive)ハッシュ関数のこと 高次元データの次元圧縮を行える (P1,P2,r,cr)-sensitiveなHash族とは、 2つの特徴ベクトルp,qについて(P1>P2) ||p-q||P1 ||p-q||>crならPr[h(p)=h(q)] を満たすハッシュ関数h:R^d->U コサイン類似度に対するLSH 2つのk次元ベクトルu,vについて コサイン類似度: u*v / sqrt(|u|*|v|) d個のk次元のランダムベクトルr_iを考え、ハッシュ関数h_i(u)を h_i(u) = 1 (r*u >=0) h_i(u)
How to Identify Algorithmic Trading Strategies | QuantStart
How to Identify Algorithmic Trading Strategies How to Identify Algorithmic Trading Strategies In this article I want to introduce you to the methods by which I myself identify profitable algorithmic trading strategies. Our goal today is to understand in detail how to find, evaluate and select such systems. I'll explain how identifying strategies is as much about personal preference as it is about
Algorithms and Data Structures with Java and C++ implementations
Support us to write more tutorials to create new visualizers to keep sharing free knowledge for you Welcome! Here you find articles on the subjects of data structures, algorithms and programming concepts. Each and every article is supplemented with code snippets in both C++ and Java, so you can turn to the practice right after reading a tutorial. For the very beginners we developed articles about
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Naked Security – Sophos News
Algorithm of the Week: Practical Parallelizing in R - DZone Big Data
The NAG Blog: The NAG Library for Java – An Illustrative Example Using Black And Scholes Pricing
GeeksforGeeks
How to identify algorithmic trading strategies | Hacker News