正規表現ばかりに頼ってはいけない - id:anatooのブログ
文字列のパースをする必要がある時、どんな文字列にでも何でもかんでも正規表現で処理しようとするエンジニアをたまに見かける。 正規表現は確かに文字列を扱うための強力な手段だが、万能ではない。正規表現の性質上、そもそもパースできない文法があるからだ。従ってそういうケースの時には正規表現ではなく別の方法を使ったほうが良い。正規表現を無理やり使っても、バグを埋め込んだり、メンテナンスが難しかったり、正しく文字列をパース出来なかったりで良いことはあまりない。 正規表現がパースできない文字列 正規表現が苦手とする文法で一番よく言われるのは、再帰的な構文を含む文法である。例えば、括弧つきの数式なんかがそうで、1+1 でも (1+1) でも ( (1+1) ) でも ( ( (1+1) ) ) でも ( ( ( ( 1+1) ) ) ) でも、という風にいくらでも入れ子にできる。正規表現では、こういった文字
動的計画法は再帰で表せ
動的計画法の説明は常に再帰関数で書き表すことにしています．いやゆるメモ化再帰です．参照透過な関数は，同じ引数に対して同じ値を返すので，保存しておけばいいという感覚です．計算量の見積もりも簡単で，引数の異なり数に関数中のループの上限をかければおしまいです．特に再帰で書くことに慣れていれば自明に書けますし，テーブルを使ったDPと違って，ループの順番を意識する必要がありません．このテクニックは学部時代に@ohkuraに教えてもらいました．関数型言語に触れた今でこそ当たり前に見えますが，当時は目から鱗だったのを覚えています． メモ化再帰と不動点に関する@kinabaさんの日記や，プログラミングコンテスト的には@chokudaiさんの記事が参考になります． 今更ですが，ちょっと例で説明します．フィボナッチ数を計算する関数fib(x)は再帰式で，fib(x) = fib(x - 1) + fib(x
「末尾再帰」の勝ち組的学び方 - ウィリアムのいたずらの、まちあるき、たべあるき
ウィリアムのいたずらが、街歩き、食べ物、音楽等の個人的見解を主に書くブログです（たま～にコンピューター関係も） 末尾再帰ってあるじゃないですか・・・ って、書いて、？？といわれると、先に話が進まないので、説明しちゃうと、 自分を呼び出す再帰プログラムの場合、 int a(x) { if ( x == 1 ) { return 1; } return x + a(x-1); } とかやってしまうと、a(x-1)の再帰をやった後で、xと掛ける作業が必要ななので、このxの領域を保存しておかなきゃいけない、ってことは、再帰を行うたびに、メモリ領域ががんがん増えていくので、よくないなどと、Ｃ言語では、言われてたわけです。 でもね、もし、再帰のあとに、なーんにも命令がなかったら、つまり、 int a_oya(x) { int hikisu; hikisu = 0; a(&hikisu,x); retu
再帰理論の初歩シリーズ「再帰定理」 - とりマセ
あ、超おひさしぶりです。 最近めっきり筆不精になってしまったので、リハビリ代わりに、再帰理論の初歩的な定理を紹介するシリーズでも始めようかなあ。 でも、シリーズとか言っておきながら、一回で終わったりするかも。せめて二回くらいはやれるように頑張ります。たぶん。 再帰理論と再帰定理 数学基礎論の一分野である再帰理論は、20世紀前半頃から研究され始めたそこそこ新しい分野です。といっても、数学基礎論自体が19世紀末から20世紀初頭に生まれた新しい分野なので、再帰理論は数学基礎論の分野としては結構古い部類だったりはします。 というわけで再帰理論の初歩シリーズ第一回は、再帰理論の再帰の名を冠する定理「再帰定理」の紹介。 この定理は、もしかしたら、プログラマさんとかの間では常識なのかも。 「再帰定理」とは、大雑把に言うと、 「プログラムに自己言及を含ませることができるよ〜」 「自己増殖をするプログラム
再帰プログラムの意味論について
∗ 1 semantics of programming languages recursion ∗ 59 (2007), 180–191 1 2 2.1 fact(x) ≡ if x = 0 then 1 else x × fact(x−1) well-defined Z * Z Z * Z F : (Z * Z) → (Z * Z) F(f)(x) = 1 (x = 0) x × f(x − 1) (x 6= 0, f(x − 1) ) ( ) F F fact fact [[fact]] : Z * Z [[fact]](x) = ( x! (x ≥ 0) ( ) 2 F f [[fact]] F([[fact]])(x) = 1 (x = 0) x × y (x 6= 0, [[fact]](x−1) = y) ( ) = ( x! (x ≥
スタックオーバーフロー - Wikipedia
スタックオーバーフロー (英: stack overflow) は、コンピュータプログラムにおいて、コールスタック領域の限界を超えたデータプッシュにより発生する、バッファオーバーフローの一種である。スタックバッファオーバーフロー (英: stack buffer overflow) とは別の概念である。 プログラムにおいて、サブルーチン（関数／プロシージャ）呼び出しに関する情報を格納するためのスタックメモリ領域（コールスタック）が確保される。サブルーチン呼び出しのたびにデータがスタックに積まれ（プッシュ）、サブルーチンが終わって制御フローが呼び出し元に戻るとスタックからデータが降ろされる（ポップ）。オペレーティングシステムや実行オプションにもよるが、コールスタックに格納できる情報量には上限がある。コールスタックに蓄積されるデータ量が限界を超えるとスタックは「オーバーフロー」し、未定義動作を
JavaScriptによるマルチスレッドの実現‐Concurrent.Threadの裏側
function f ( ) { do_something(); do_another(); do_one_more(); } このプログラムでは順番に3つの関数を呼び出していますが、各関数呼び出しの間でいったんスレッドの実行権を他のJavaScriptコードに渡したいとします。これは次のように、各関数呼び出しをそれぞれ別の関数に分けて、間にsetTimeoutを挿むようにプログラムを書き換えることで実現できます。 function f ( ) { do_something(); setTimeout(f1, 1); // 1ミリ秒後にf1を呼び出す } function f1 ( ) { do_another(); setTimeout(f2, 1); } function f2 ( ) { do_one_more(); } こうして書き換えた関数fを、 f(); f(); のようにし
JavaScriptの再帰の回数制限を超える実験をしてみる - あと味
JavaScriptで再帰をすると、ブラウザによって再帰できる回数が違います。 ブラウザごとに何回再帰できるかを検証する記事がいくつかありました。 各ブラウザのJSランタイムがどこまで再帰できるか試してみた、という。 - muddy brown thang javascriptの再帰処理の限界 - 電脳戦士ハラキリ -SE道とは死ぬ事と見つけたり- JS の再帰 (追試) - 冬通りに消え行く制服ガールは✖夢物語にリアルを求めない。 - subtech Firefoxだと3,000回あたりが再帰回数の限界のようですね。 実験の概要 ということで、単純な等差数列の和を求めるコードを実行して、再帰回数の限界について実験してみました。*1 実験1 Firefoxで3,000回実行できるかどうか確認してみます。 var arithmetic_progression = function(n) {
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Tumblr