なぜ Haskell ではキューが軽んじられているか？ - あどけない話
Haskell ではキューが欲しくなったら Data.Sequence を使えと言われる。Seq は両端キューだし、シーケンスとして使えば、連結(><)や分割(splitAt)が、ならし計算量で O(log N) という優れものである。しかし、内部がfinger treeなのでコードが複雑なのと、計算量が「ならし」なところが玉に傷である。 もっと単純で、最悪計算量を保証する(両端でない)キューが標準で提供されてもいい気がする。その候補には、リアルタイムキューがある。どうして標準でキューが提供されないのだろう？ 僕なりの答えは「需要がない」だ。 問題を解くときにスタックはよく使うが、キューが必要な問題はそんなに思いつかない。僕はネットワーク屋なので、もちろんルータにはキューが必要なことは知っているが、それ以外で有名どころと言えば幅優先探索ぐらいだ。 幅優先探索 でも、Haskellではキュー
逆FizzBuzz問題 (Inverse FizzBuzz) - 平々毎々（アーカイブ）
just another scala quantを日本語にしました。 ちなみに、私の解はこちらに。 最初の解答 はてブに書いた解答方針、Inverse Fizzbuzz (FizzBuzzの逆関数) - Qiita - 与えられた範囲内のすべての解を数え上げてます。 もっと簡潔な解答 逆FizzBuzz問題 解きなおし - Qiita それでは、問題の日本語訳をどうぞ。 逆Fizzbuzz問題 2012年ではなく、2016年のお話。 世の中は大して変わっていない。 OOPと書き換え可能なオブジェクトによって何度もひどい目にあった後、世界はやっとのことでJohn Hughesの考察が正しかったことに気づき、関数型プログラミングに移行した。GoogleはTypesafe社を買収し、ScalaがAndroid上でネイティブに動作するようになっている。Googleに負けず劣らず、AppleはHas
機械学習 はじめよう 記事一覧 | gihyo.jp
運営元のロゴ Copyright © 2007-2025 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
迷路の試験問題を解いてみた - にわとり小屋でのプログラミング
参考：人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。 Lv4に評価されるためには、最短性の完全なチェックが必要だったのでCoqで証明してみた。 まず、accessiblesという関数を定義し、以下の性質を証明した。 ここでplengthはパスの長さを計る関数で、Path x pはpがxを起点としたパスであるという述語。endofはパスの終点を求める関数。 Fixpoint accessibles (start : node) (len : nat) : list path := match len with | O => (PUnit start) :: nil | S n' => div_equiv path_equiv_dec @@ (flat_map expand @@ accessibles start n') end. この関数はstartから始まってlenの長さ
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
anarchy golf
Anarchy Golf This is a golf server. You can enjoy short coding here in several languages (116 languages). The purpose of this server is not serious competition. Joke problems are welcomed and you can speak freely about problems and can release spoilers. For serious competition with ranking, enter Code Golf. IRC channel for this golf server: #anagol in freenode. Please feel free to join the channel
Natural Order String Comparison
by Martin Pool This project has moved to github.com/sourcefrog/natsort. Computer string sorting algorithms generally don't order strings containing numbers in the same way that a human would do. Consider: rfc1.txt rfc2086.txt rfc822.txt It would be more friendly if the program listed the files as rfc1.txt rfc822.txt rfc2086.txt Filenames sort properly if people insert leading zeros, but they don't
イントロソート - Wikipedia
イントロソート（英: introsort）は、David Musser（英語版） が1997年に設計した、クイックソートとヒープソートを組み合わせたソートアルゴリズムである。 最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。時間計算量は最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。 イントロソートは、クイックソートやヒープソートと同様、比較ソートである。 クイックソートは、性能がピボット（データ列を分割する境界値）の選択に強く依存するという欠点があった。 例えばデータ列の先頭や最後尾をピボットに選ぶと、ほぼソートされた入力について最悪の性能を示す。 ニクラウス・ヴィルトはこれを避けるため、データ列の中央の要素をピボットに選ぶようにしたが、工夫をこらした並びに対しては
古くて新しい自動迷路生成アルゴリズム - やねうらおブログ(移転しました)
最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである。 この迷路を見て「ああ、俺様も迷路のことを書かねば！俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば！」と誰も求めちゃいない使命感が
BLOG::broomie.net: 機械学習の勉強を始めるには
thriftとかhadoopなど，何やらいろいろと手を出してしまい，ここのところブログの更新が滞ってしまっていますが，今日は前から書きたかったトピックについて自分へのメモの意味も含めて記しておきたいと思います． はじめに 最近，といっても結構前からなのですが，海外のブログなどで「機械学習の勉強を始めるガイドライン」についてのエントリーがいくつか見られ，かつ，議論も少し盛り上がっています．僕は機械学習が好きなだけで，専門というにはほど遠いのですが，僕も一利用者としてはこのトピックに関してはとても興味があります． 機械学習というと，色々な数学的な知識が必要であったり，統計学や人工知能の知識も必要になったりしまったりと，専門的に学ぶ機会が無かった人にとっては興味が湧いてもなかなか始めるには尻込みしてしまうことかと思います．今日紹介するエントリーは，そんな方々にヒントになるような内容になっていると
Egisonの価値
Egisonの価値 パターンマッチについて考えることは，思っているより非常に重要なことである． 新しい強力なパターンマッチの表現をみつけることは，関数型言語や論理型言語， オブジェクト指向言語などのアイデアと較べるとそこまで重要なことではないという認識があるような気がする． しかし，そんな認識は間違っていて， 新しく開発された超強力なパターンマッチ機能をもつEgisonが， 実はどれだけ影響力を秘めた言語であるかということを今回は書いてみようと思う． プログラミング言語には大雑把に分けて， 計算機を制御するための道具としての捉え方と， アルゴリズムを表現するための道具としての捉え方があるように思う． 前者の捉え方は，入出力やメモリ管理，並列計算，ネットワーク関連の処理などの コンピュータの機能を組み合わせて， 役に立つ便利なアプリケーションを作るハッカー的な捉え方である． 後者の捉え方は，
定期的に繰り返し実行する簡単ではないお仕事 - やねうらおブログ(移転しました)
いやー、この問題は本当に難しい。難しすぎて、どうやって解決すればいいかいまだによくわからない。わからないので、ここに書いてみる。 最初、とあるお客さんのために「ひよこの餌やりプログラム(仮)」を作っていたんだ。開始ボタンを押すとひよこの餌が出てくる。たったそれだけのプログラム。 今回は、これを「定期的に実行する機能が欲しい」と言われた。 この要望を実現するのがすこぶる難しかったんだ。 「やねうらおってそんなプログラムすら書けないの？老害なの？」 とか言わないで欲しい。この問題、本当に難しいんだよ！ ■ １度目のひよこの全滅 まず、この要望に沿って、私の会社のプログラマが当初、次のようなダイアログをつけたわけだ。 繰り返し実行のところにチェックを入れた場合、ここで指定された時間後にも繰り返し実行する。単位は分で指定する。1日ならば60×24 = 1440を指定する。そうすると、ひよこの餌やり
浮動小数点数型と誤差
有限桁 Ｃ言語で扱える実数値は，２進数の有限小数で表された数値である．例えば次のようなものである． 1.5(10) = 1.1(2) 3.25(10) = 11.01(2) 理論的には小数が無限に続く値でも，そのうちの有限個の桁数でその値を表すしかない． 例えば，0.1 を２進数の小数で表すと 0.1(10) = 0.000110011001100110011...(2) と無限に続くが，コンピュータの内部では有限桁で丸められている． このような場合には，本当の値ではなく，近似値でしか表すことができない． 指数表記（浮動小数点表記） 科学計算では非常に大きな実数値や非常に小さな実数値も扱うことがある． そのようなときには，通常の１０進数の表記ではなくて，次のような指数表記で表すれば 無駄な 000...000 という桁を表記しなくてもよくなる． 1234567890000000000000
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
C++プログラミング日記 -逆数平方根の近似(2)
前回の「逆数平方根の近似」の続きです。 逆数平方根の近似を利用して平方根関数を実装してみました。 今回の実装ではcrtのsqrt関数と同等にするため0以下の実数に対する処理を加え精度を上げています。 その状態でもcrtのsqrt関数よりかなり高速です。 ついでに逆数平方根関数にも同等の処理を追加しました。 sqrt float sqrt( const float& V ) { if( *(long*)&V <= 0 ) { if( ( *(long*)&V & 0x7FFFFFFF ) == 0 ) return V; long r_bits = 0xFFC00000; return *(float*)&r_bits; } long x_bits = *(long*)&V + 0xFF800000; long y_bits = 0x5F3759DF - ( *(long*)&V >> 1
数値演算のアルゴリズム
３Ｄの計算処理では、「正確性よりも速度を求める」という場合がよくあります（特にリアルタイム）。 そのあたりで使えそうな、数値演算のアルゴリズムをまとめてみました。 sqrt：平方根を求める C言語では"math.h"の「sqrt」で平方根を計算します。 これと同等の機能をするプログラムは以下のようになります。 浮動小数点での平方根の計算 double mySqrt(double x) { double s,last; if(x<=0.0) return 0.0; if (x > 1) s = x; else s = 1; do { last = s; s = (x / s + s) * 0.5; } while (s < last); return last; } 整数での平方根の計算 int myISqrt(int x) { int s, t; if (x <= 0) return 0;
fast sqrt
高速根号計算 (fast sqrt algorithm) 概要: C言語のsqrt(float)より精度は若干劣るものの，2倍以上速いsqrtのalgorithm． ググって見つけた物が，非常に面白かったのでまとめておく．精度より速度が求められる場面で活躍する． 参考文献 [1] David Eberly, Fast Inverse Square Root (Revisited), http://www.geometrictools.com/Documentation/ FastInverseSqrt.pdf, 1/2002-. 実装 //---Algorithm float(IEEE754)用------ inline float t_sqrtF( const float& x ) { float xHalf = 0.5f * x; int tmp = 0x5F3759DF
平方根を使わずに高速で２点間の距離を近似する - きしだのHatena
２点間の距離の計算では平方根が必要になりますが、平方根は少し重い計算です。ということで、平方根を使わず、掛け算・割り算・足し算と絶対値・最大・最小だけで距離を近似する方法についての記事を翻訳してみました。 flipcode - Fast Approximate Distance Functions (12:02 補足：おそらく今の標準的なCPUでやる意味はほとんどないと思います。近似のアプローチとして面白いというくらいの話。Z80でやりましょう) 距離関数高速近似 by Rafael Baptista (27 June 2003) ２点間のユークリッド距離を求める計算式は次のようになる。 二次元では次のようになる。 この関数の計算には、平方根が必要になる。これは最近のコンピュータでも高価な計算である。平方根は逐次近似によって求められる。つまり、コンピュータは平方根近似のループを行って、与え
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
あなたの知らないハッシュテーブルの世界