[Technical] Announcing psqueues
At Better, the engineering team is dedicated to building the best learning experience. This means our app should be fast, even when there are thousands of users accessing our system at the same time. Caching plays an important role here. While there are pre-made solutions available, such as memcached, custom in-memory caches can provide many benefits (e.g., avoiding repeated deserialization) if th
![[Technical] Announcing psqueues](https://cdn-ak-scissors.b.st-hatena.com/image/square/61380fe72f42500f856063c1b3cb48e3005415d8/height=288;version=1;width=512/https%3A%2F%2Fmiro.medium.com%2Fv2%2Fresize%3Afit%3A1000%2F1%2AOoGZbLq_SyV09H3DVj63vQ.png)
遅延評価を活用して線形時間でGoogle Code Jam 2014 Round 1AのB問題を解く - tosの日記
公式の解説で，「遅延評価を使ってもできる」と書いてくれなかったので。 注意：この記事は，Google Code Jam 2014 Round 1AのB問題 Full Binary Tree についてのネタバレを含みます。 この問題は木DPをする典型的な問題であり，公式の解説にもあるように， 木を根付き木にした後， 頂点でのスコアを，子のスコアのうち大きい方から2つを用いて計算する ことで解けます。何を根として選ぶかをすべて試すとO(N2)解法となり，すべての根の可能性について同時にDPをする*1とO(N)解法になります。だから，根の選び方によって隣接頂点のうち「親以外が子となる」ので，隣接頂点のスコアのうち大きい方から3つを保存するような構造を持つ――待ってください。 もちろん，降順ソートされたスコアのすべてを計算すると，O(N2)時間かかってしまいます。しかし，先頭3つを結果的に計算でき
Programming:玉手箱
ちょっとしたお題やパズル，クイズなどを集めたものです． リストの長さの比較pos+連続した n 要素のリストのリストGraph の統合木の統合集合の統合xzipリストをグループ化するn 番飛ばし毎にグループに分けるn 個ずつグループ化する 組合せ論的な生成関数リストの二分割の生成順列の生成重複順列の生成組合せの生成重複組合せの生成順列の生成 素因数分解既約分数拡張ユークリッドの互除法 コメントの除去コメント対応read正規表現置換words4ApacheLog文字列の先頭から等しい文字列を抜き出すお約束の末尾再帰版文字列から一致する部分文字列を抽出するCSV自分自身のソースコードをプリントするプログラム文字列 C が文字列 A, B から構成されているか 関数型表上向きにも辿れる木平衡木赤黒木AVL 木データタイプから再帰を分離探索深さ優先探索幅優先探索Graphical Sequence
Haskellで円周率1億桁を計算する、あるいは円周率計算にHaskellの多倍長整数の改良を見る - 純粋関数空間
きっかけ http://d.hatena.ne.jp/itchyny/20120304 この記事を見て、私も昔円周率を計算したことがあるのを思い出しました。 http://d.hatena.ne.jp/tanakh/20070506#p1 公式は同じくチュドノフスキーを使用、GHCのIntegerをそのまま用いて円周率を計算、 当時（5年前）のマシン（おそらくCore2あたり）で1億桁が15分ほどだったようです。 SPOJというサイトのコンテスト向けに、 $\sqrt{2}$ 200万桁計算の高速化 をCで書くとこから始めて、 ナイーブ乗算、カラツバ法、そしてFFT乗算の実装にいたり、円周率へ。 最初AGMを実装し、 古くて新しい方法、Arctan系の公式の実装を経て Binary Splitting Methodを知り、 チュドノフスキーの公式へ至りました。 さらにHaskellでの実装
Haskell vs F# その後 - Life Goes On
mkotha さんに直してもらったりして、Haskellのコードはだいぶ速くなりました。どうも２重ループの内側がボトルネックのようなので、そこを展開して、データ構造も変えて、UNPACKプラグマは効くので残して、正格評価を１ヶ所だけ。性能と可読性のバランスがそこそことれたかなと思ってます。C++ や F# のコードにも同じような改修を加えたら、Haskell はまた抜かれてしまいました。まぁでも、目くじら立てるほどの差でもないので、そのままにしています。 実行環境が Windows というアドバンテージがあるとはいえ、C++ も超える F# の健闘が光ります。明示的な副作用がない関数プログラミングでこれだけ速いとうれしい。コード書いてても気持ちがいいし、Microsoft でなければもっと流行っていいはず。 最終形のコードを以下に載せておきます。 ついでに Scala でも書いてみました。
ランダムウオークで距離を測ろう - でこすけの日記
モチベーション 最近のウェブサービスは、関連したデータを集めてくるのが上手いですよね。facebookやSPYSEEの「知り合いかも」機能が異常に精度が良くて怖いです。これらは人同士の近さ、親密さを機械学習によって計算しています。 そんなわけで、データ同士の距離を測ってみましょう。最近クローラの話をたまにしていたので、ウェブページのクローラを使って、単語同士の距離を計ってみます。 RW(ランダムウオーク) 酔った人みたいに、一定確率でランダムに隣の場所に歩いていくモデルです。そういえば、今日帰宅途中にお土産を持ってふらふらしているサラリーマンを見ました。 隣の場所に歩くときに、サイコロを振ってランダムにどこにいくか決めるのでモンテカルロ法に分類されます。このランダムウオークが今回の道具です。 RWR(Random Walk with Restart) さきほどのランダムウオークに加えて、一
Faster persistent data structures through hashing
hello mum");a.close()},find_slide_number:function(e){var c=e.indexOf("#");if(c<0){return 0}var b=unescape(e.substr(c+1));var f=document.getElementById(b);if(!f){var d=/\((\d)+\)/;if(b.match(d)){var a=parseInt(b.substring(1,b.length-1));if(a>this.slides.length){a=1}if(--a<0){a=0}return a}d=/\[(\d)+\]/;if(b.match(d)){var a=parseInt(b.substring(1,b.length-1));if(a>this.slides.length){a=1}if(--a<0){a=
純粋関数型アルゴリズム入門
6. 今日の話 この本の解説 Purely Functional Data Structure Chris Okazaki リストとキューの話しかしません （それでも十分難しい） 7. 関数型言語の利点 • 本を読め！ by C.Okazaki – J.Backus 1978 – J.Hughes 1989 – P.Hudak and M.P. Jones 1994 • それだとあんまりなので、適宜説明しま す 8. データ永続性（persistency） • 変数に割り当てられた値は一切変更され ることはない – 破壊的代入が行われない – いつ参照しても同じ値が返ってくる • 永続性により保守性が高まる 例： 1. aにある値を代入 2. bにある値を代入 3. a,bの値を表示 4. aとbにある操作をしてその結果をcに代入 5. a,bの値を表示 この間に値が変わらないのが、永続性
Haskell でスリープソート - あどけない話
Haskeller から見れば、標準出力に表示なんてダサい。orz import Control.Concurrent sleepSort :: [Int] -> IO () sleepSort = mapM_ (forkIO . sleepy) where sleepy n = threadDelay (n * 1000) >> print n
Persistent Vectors and Hash Maps for Haskell
One of the prominent features of Clojure are a core set of immutable data structures with efficient manipulation operations. Two of the most innovative and important are the persistent vector and persistent hash map. As a little project I set myself in order to get to know Haskell better, I have been porting these structures to Haskell. I think it's now at a state where the basics are there and us
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
Haskell で動的計画法を書くための3つの方針 - tosの日記
アルゴリズムの代表っぽい存在とも言えるDPですが，Haskellは参照透明なので書きにくいと思われがちです． しかし，実際は，C言語やSTLなしのC++より遥かに簡単に動的計画法が書けます． リストを用いる 最初に知るであろう方法． フィボナッチ数列の第100項だと， let f = 0 : 1 : zipWith (+) a (tail a) in f!!100 です． 「ずらして足したものを後ろにつなげる」と言えばいいのでしょうか． これについては，他でよく解説されているので詳しくは説明しません． 利点： リストの知識のみでよい． 無限リストの恩恵が受けられる． importが不要． 欠点： 使えるケースが限られる． 書くときに，混乱することも（上の例だと，と考える必要がある． ランダムアクセスができないので，場合によってはO(n)倍の時間がかかる*1． 添字を自由に用いることができな
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Purely Functional Data Structures for On-Line LCA
arithmoi
Private Site
Haskellで書く全域木探索 - Inemuri nezumi diary(2009-07-26)
http://atnd.org/events/1048/