仕事でコードを書いていますがどうしても同期と比べて仕事が遅いです。早くコードを書くコツや短くまとめるコツなどがあれば教えてほしいです。あと普段どんなことを意識してコー��
私は昔、趣味で作っていたアプリに機能を「追加」する度に、アプリケーション(実行ファイル)の総サイズを「減らす」、というのを繰り返していたよ。速度も同様に。 これによって「あるパターンはこう簡潔に直せる」というパターン知識が積み上がっていった気がするな。 さらに、それを実現する過程で、限界に見えた状況を打開するために色んな既存アルゴリズムを勉強して実際に使って身につけていくことになった。 ある問題があるときに、的確に適合するアルゴリズムや構成が発見(選択)できると、劇的に簡潔になることがある。そこにたどり着けるかどうか考えるのが楽しい。 あと、同じコードを何年も「育てる」という経験をすると、保守性の低いコードがどう困るかが身に染みるようになるよね。ソースコードは「人が読む物」でもあり、読みやすいというのも保守するなら重要なパラメータになる。これはコメントを書けという意味じゃない。コメ
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
せっかくの夏休みだから、今こそまとめて買っておきたいコンピュータ書５冊 - 思っているよりもずっとずっと人生は短い。
と言えばやっぱりこれですよね。 The Art of Computer Programming,Volume 4, Fascicle 0 Introduction to Combinatorial Algorithms and Boolean Functions 日本語版 (ASCII Addison Wesley Programming Se) 作者: Donald E. Knuth,和田英一出版社/メーカー: アスキー・メディアワークス発売日: 2009/10/22メディア: 大型本購入: 1人 クリック: 40回この商品を含むブログ (13件) を見るThe Art of Computer Programming Volume 4, Fascicle 1 Bitwise Tricks & Techniques; Binary Decision Diagarms 日本語版 (ASCII
実用的な同時並行ソートを実装する話 - akihiro4chawonの日記
scala の parallel collection は、普通の collection を使うように使っているだけで、並列計算の恩恵を受けられる場合も多いのですが、そうではない場合も多いです。 その典型例が、ソートです。実は、並列のソートは、まだ実装されていません。 じゃあ、自分で実装すればいいのか、というと、これは半分正しくて半分間違いです。 どういう事かというと、シングルスレッドの java.util.Arrays.sort がとても高速なので、これより速いソートを自前で実装するのは難しいのです。Arrays.sort が速いのは、単にアルゴリズムだけの問題ではありません。自分で Array の整列処理を書くとすると、当然、配列の要素に添字でアクセスしますよね。すると、JVMは配列の範囲内かどうかをチェックしますよね。このオーバヘッドがあるために、java.util.Arrays.s
Home
Knife throwing is both an art and a skill that’s difficult to master...
4chan BBS - Genius sorting algorithm: Sleep sort
1 Name: Anonymous : 2011-01-20 12:22 Man, am I a genius. Check out this sorting algorithm I just invented. #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 Oh god, it works. But I don't like to wait 218382 seconds to sort '(0 218382)
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
ソートアルゴリズムを映像化してみた - jsdo.it - Share JavaScript, HTML5 and CSS
よくあるやつです。ぼんやり眺めてると、とても癒されます。 2014/2/25 追記: 全面的に書き直しました。 // https://github.com/norahiko/sort-visualize var helper = { range: function(min, max) { var res = []; for(var i = min; i < max; i++) { res.push(i); } return res; }, shuffle: function(ary) { for(var i = ary.length - 1; 0 <= i; i--) { var rnd = Math.random() * (i + 1) | 0; helper.swap(ary, i, rnd); } }, swap: function(ary, a, b) { if(a < 0 ||
アルゴリズマーのそだてかた - chokudaiのブログ
日本発の「Topcoderトレーニング講座」は最強最速アルゴリズマーへの最短経路 こんな記事も出して貰えたところですし、凄く簡単に、自分の中での教育論みたいな部分を少し話してみようかと思います。 ある物事を習得するのに必要なのは何か？という話をした時に、僕が絶対に必要だと思っているのは、「すげぇ！！」ってなることだと思っています。当然だとは思いますが、せっかくなので具体例を見ていきましょう。 Wikipediaにおける、動的計画法の記事を見ると、このようになっています。 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法である。分割統治法がトップダウン的な手法であるのに対し、
ランキングのつくりかた:Kenn's Clairvoyance
遅ればせながら、あけましておめでとうございます。 先週には、ベイエリアの友人たちがやっているEchofonがPostUpに買収されるなど、幸先のよい新年のスタートとなりました。 さて、最近ホットなマーケットといえばソーシャルゲームですが、ゲームといえばリーダーボード。ハイスコアのランキングで友人や見知らぬ人たちと競うのは、ビデオゲームが誕生した1970年代から欠かせない要素でした。 ところが、インターネット経由で100万人規模のプレイヤーがつながるようになってきた現在、その全体をランキングづけするのは、技術的にも大きなチャレンジとなってきました。 今回は、そのリーダーボードのつくりかたについて、ぼくらの作っているソーシャルゲーム・プラットフォームであるPankiaの運用で得られた知見を共有したいと思います。 自分の順位を知る方法 リーダーボードの基本的な考え方はシンプルで、それはつまり「ユ
リストモナドを使ってみる - みずぴー日記
このエントリはScala Advent Calendar jp 2010 : ATNDの25日のものです。 メリークリスマス! クリスマスは楽しくみんなでパズルを解いて遊びましょう。 パズルみたいな探索問題をScalaで解く場合は、リストモナドを使うとキレイに書けます。 例: SEND+MORE=MONEY 例として覆面算を解いてみましょう。 各アルファベットに異なる数字が割り当てれる。その数字は何か? ただし最上位桁が0ではない。 普通にforループを使って解くと、ネストの深さが酷いことになります:)。 // int(1,2,3)を123にする関数 def int(xs : Int*) : Int = xs.foldLeft(0)( _ * 10 + _) // SEND+MORE=MONEYの答えを探索する def solve : (Int,Int,Int) = { for( s <-
AVL tree applet
The inset below illustrates the behaviour of binary search trees. Donald Knuth. "The Art of Computer Programming": Searching and Sorting Algorithms. G.M. Adelson-Velskii and E.M. Landis. "An algorithm for the organization of information", 1962 D. Sleator and R. Tarjan. "Self-adjusting Binary Search Trees", 1985 "Symmetric binary B-trees. Data structure and maintenance algorithms.": R
w.l.o.g. ギャップバッファ
04:40 04/06/04 ピーステーブル PieceTable とも言う。文字列の Piece（小片）を繋げて、 一つの巨大な文書を表現する方式。 検索すると引っかかる文書のほとんどが AbiWord 関係なので、 このワープロソフトの主要な内部データ構造ということなのかな。 他に、MS-WordやOpenOffice.org関連の文書にも登場していて、 基本的に単なるテキストエディタよりは、文字に付加情報をくっつける系の 編集ソフトに使われる場面が今のところ多いみたいです。 余談ですがAbiWordは、綱渡り的にですがBeOS版の開発が続いている貴重なワープロソフトなのです。感謝感謝。 概要 ファイルを読み込んだとしましょう。ABCDEFG、という７文字のファイル。 とりあえず、７文字分のOrigという名前のバッファを用意して、そこに格納します。 それと別に、Addという名前の空のバ
平方根のアルゴリズム
平方根である。sqrtである。私の数学知識は非常に乏しく、かろうじて平方根の何たるかを解するばかりであるが、ふと、平方根を計算するアルゴリズムが知りたくなった。理由は、constexprなsqrtを実装してみたくなったからだ。 日本語では、いい情報がWeb上に存在しないので、ここに書いておく次第。この説明は、私のように数学の知識を持たない人間にも理解できるはずである。 ここで使うのは、バビロニア人の方法（Babylonian method）と呼ばれている、歴史あるアルゴリズムである。この方法は、手動でも、プログラミングでも、非常に簡単に計算できる、大変便利で汎用的なアルゴリズムである。しかも、速度もそれほど遅くない。 √Sに対して、 任意の正の整数を初期値X0と定める（できるだけ平方根に近い値が望ましい） Xn+1を、Xnと S / Xnの平均値とする（平均値は相加平均で求める） 必要な精
Compressed Suffix Arrayの記事まとめ - EchizenBlog-Zwei
一応CSAの記事を書き終えたので、各記事へのリンクリストを。 補足:記事を7つも読むの面倒くさい人は、↓にもう少し簡単な圧縮法の解説を書いておいたので参照されたい。 15分でわかる(とうれしい)Suffix Arrayの簡単な圧縮法 Compressed Suffix Arrayの解説(1) -Suffix Array- Compressed Suffix Arrayの解説(2) -SAの計算量- Compressed Suffix Arrayの解説(3) -圧縮の方針- Compressed Suffix Arrayの解説(4) -unary記法- Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- Compressed Suffix Arrayの解説(6) -B Vectorと Ψ Vector- Compressed Suffix
15分でわかる(とうれしい)Suffix Arrayの簡単な圧縮法 - EchizenBlog-Zwei
文字列が超長い場合SuffixArrayが大きすぎてメモリが一杯になってしまう。 ので圧縮して小さくしたい。基本的な圧縮法である差分圧縮を使った簡単なSuffixArrayの圧縮法を紹介する。 参考: 5分でわかる(かもしれない)圧縮の基本 5分でわかる(気がする)Suffix Array さて以下のSuffixArrayを差分圧縮したい。 文字列 : b a n a n a SuffixArray: 6 4 2 1 5 3SuffixArrayの差分を取る。 SuffixArray: 6 4 2 1 5 3 差分 : 6 -2 -2 -1 4 -2マイナスの数がたくさん出てきた。負の数があると差分圧縮できない。ので差分が正の数になるようにSuffixArrayをいじる。 SuffixArrayのそれぞれの数字に1から順に番号をふる。 Index : 1 2 3 4 5 6 SuffixA
素数10億まで3秒 - ita’s diary
404 Blog Not Found: C - で素数を数え直したら、範囲10億で10秒切ったお むむ、以前自分が書いた奴だと、ホットスポットでやってる事はほとんど同じなのに30秒ほどだった。 for (p=2, 3, 5, 7, 11, ...) for(i=istart; i<size;i += p*2) pflag[i]=0; danさんの場合, 1bit でフラグを記憶してるのでメモリが1/8 で済む。そこでメモリアクセスの時間が効いてるんだろう。それならキャッシュに収まる位のブロックに計算を分割しその内側で素数pのループ回せばもっと速くなるかも？と思いやってみた。見事3秒で終わった! 以下コード danさんのbitmap.cに以下を追加 bitmap *bitmap_block(bitmap *parent, size_t offset, size_t size){ if (!s
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
２つの文字列の編集距離を求める - Alone Like a Rhinoceros Horn
https://www.ic-net.or.jp/home/takaken/pz/pz4/index.html
最も簡単に fib を高速化する方法 - ドレッシングのような
