JavaScriptの文字列を反転する１０の方法とそのパフォーマンス - 風と宇宙とプログラム
はじめに JavaScriptで文字列を反転する１０の方法を（無理矢理？）思いついたので、ちょっと簡単に紹介したい。また、それぞれについて、各ブラウザでパフォーマンスを測定してみたので、その結果も合わせて載せる。 文字列のStringオブジェクトには、部分切り出し(substring, slice)や置換(replace)、連結(concat)など豊富な機能があるのに、反転(reverse)機能はない。Arrayのreverseはあるのに、Stringのreverseがないのはどうしてなのだろうか。 各ブラウザとそのバージョンは以下の通り： Chrome Firefox Opera Safari IE 13.0.782.112 m 6.0 11.50 5.1(7534.50) 8.0.7600.16335 rev01: C言語的発想 空の配列を作って、そこに元の文字列の後ろから１文字つづ入
常識を覆すソートアルゴリズム！その名も"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 なん…だと
ランキングのつくりかた:Kenn's Clairvoyance
遅ればせながら、あけましておめでとうございます。 先週には、ベイエリアの友人たちがやっているEchofonがPostUpに買収されるなど、幸先のよい新年のスタートとなりました。 さて、最近ホットなマーケットといえばソーシャルゲームですが、ゲームといえばリーダーボード。ハイスコアのランキングで友人や見知らぬ人たちと競うのは、ビデオゲームが誕生した1970年代から欠かせない要素でした。 ところが、インターネット経由で100万人規模のプレイヤーがつながるようになってきた現在、その全体をランキングづけするのは、技術的にも大きなチャレンジとなってきました。 今回は、そのリーダーボードのつくりかたについて、ぼくらの作っているソーシャルゲーム・プラットフォームであるPankiaの運用で得られた知見を共有したいと思います。 自分の順位を知る方法 リーダーボードの基本的な考え方はシンプルで、それはつまり「ユ
ソート - Wikipedia
ソート (英: sort) は、データの集合を一定の規則に従って並べること[1]。日本語では整列（せいれつ）、並べ替え（ならべかえ）、分類（ぶんるい）などと訳される[1]。 主に配列や連結リストのような、リストデータ構造に分類されるコレクション（コンテナ）に格納されている要素データを、全順序関係によって並べ替えることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、英: ascending order）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、英: descending order）という。 対象となるコレクションのデータ構造や必要とされる出力、また時間的コストと空間的コストの兼ね合いによって、ソートに使われるアルゴリズムは異なる。 効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
計算複雑性理論 - Wikipedia
計算複雑性理論（けいさんふくざつせいりろん、英: computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。 「計算量」と「計算複雑性」はともに computational complexity に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。 計算複雑性理論は計算可能関数の計算の複雑さを扱う。計算理論のもう一つの重要な分野である計算可能性理論では問題の解法があるかどうかだけを扱い、その複雑さや必要とする計算資源量は問わない点が異なる。 具体的に
ぜひ押さえておきたいコンピューターサイエンスの教科書
僕はバイオインフォマティクスという生物と情報の融合分野で研究を行っています。東大の理学部情報科学科にいた頃は同僚のマニアックな知識に驚かされたものですが、そのような計算機専門の世界から一歩外に出ると、それが非常に希有な環境だったことに気が付きました。外の世界では、メモリとディスクの違いから、オートマトン、計算量の概念など、コンピューターサイエンスの基礎知識はあまり知られていませんでした。コンピューターサイエンスを学び始めたばかりの生物系の人と話をしているうちに、僕が学部時代に受けた教育のうち、彼らに欠けている知識についても具体的にわかるようになってきました。 バイオインフォマティクスに限らず、今後コンピュータを専門としていない人がコンピューターサイエンスについて学ぶ機会はますます多くなると思われます。そこで、これからコンピューターサイエンスを学ぼうとする人の手助けとなるように、基礎となる参
細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック
細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック：最強最速アルゴリズマー養成講座（1/3 ページ） 競技プログラミングはレベルの高い人たちの集まり――そんな考えを持っている初心者の方、TopCoderはあなたのコーディングスキルを爆発的に高める魔法のような場です。今回は、初心者にこそお勧めしたいTopCoderの魅力について考えます。 教育的な観点から見るTopCoder 今回からTopCoderに関する実践的アルゴリズムを解説していく予定でしたが、序盤のうちに触れておきたいことがありましたので、今回の枕は“教育的視点から見るTopCoder”というテーマで少し書こうかと思います。 まず、最初に宣言しておきたいことは、この連載は初心者向きである、ということです。「どう考えても上級者向けだろう」という意見はたくさんの方から寄せられていますが、筆者は、まだプログラミングレ
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
GT Nitro: カーレーシング・ドラッグレーシングゲーム - Google Play のアプリ
GT Nitro: Car Game Drag Raceは、典型的なカーゲームではありません。これはスピード、パワー、スキル全開のカーレースゲームです。ブレーキは忘れて、これはドラッグレース、ベイビー！古典的なクラシックから未来的なビーストまで、最もクールで速い車とカーレースできます。スティックシフトをマスターし、ニトロを賢く使って競争を打ち破る必要があります。このカーレースゲームはそのリアルな物理学と素晴らしいグラフィックスであなたの心を爆発させます。これまでプレイしたことのないようなものです。 GT Nitroは、リフレックスとタイミングを試すカーレースゲームです。正しい瞬間にギアをシフトし、ガスを思い切り踏む必要があります。また、大物たちと競いつつ、車のチューニングとアップグレードも行わなければなりません。世界中で最高のドライバーと車とカーレースに挑むことになり、ドラッグレースの王冠
Consistent Hashing を試す
Consistent Hashing は、 複数のノードにレコードを分散させる方法として、 Amazon Dynamo や Cache::Memcached::Fast などで使われているアルゴリズムです。 この文章では、Perl で実際に Consistent Hashing を実装し、 その特徴を理解することを目的とします。 更新履歴 2008-06-01: 公開 サーバー台数で割った余り (mod) を使用する まず Consistent Hashing と比較するために、レコードに対して整数のハッシュ値を求め、 ハッシュ値をノード数で割った余り (mod) で、ノードを選択するという方法を書いてみます。 ここでは、ハッシュ値の算出に CRC (Cyclic Redundancy Check) を使用しています。 use strict; use String::CRC; use Pe
Structure and Interpretation of Computer Programs
Wizard Book n. Hal Abelson's, Jerry Sussman's and Julie Sussman's Structure and Interpretation of Computer Programs (MIT Press, 1984; ISBN 0-262-01077-1), an excellent computer science text used in introductory courses at MIT. So called because of the wizard on the jacket. One of the bibles of the LISP/Scheme world. Also, less commonly, known as the Purple Book. from The New Hacker's Dictionary, 2
編集距離（レーベンシュタイン距離）の計算 - Ceekz Logs (Move to y.ceek.jp)
文字列間の類似度を求める方法の一つとして、編集距離が挙げられます。編集距離は、考案者にちなみレーベンシュタイン距離とも呼ばれますが、具体的には、挿入や削除、置換によって、一方の文字列から他方の文字列に変換するために必要な作業の最小回数です。 use List::Util; sub levenshtein_distance { my ($list_1, $list_2) = @_; my $len_1 = scalar(@{$list_1}); my $len_2 = scalar(@{$list_2}); my @d; foreach my $i (0 .. $len_1) { $d[$i][0] = $i; } foreach my $j (0 .. $len_2) { $d[0][$j] = $j; } foreach my $i (1 .. $len_1) { foreach my
MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
ガベージコレクションの実装法と評価
1.はじめに プログラミング言語とはシステム化する対象物を抽象化し、コンピュータで処理可能なコードを記述するために用いる人工言語である。プログラミング言語はコンピュータの機械語と一対一の対応をもったアセンブラから始まり、コンパイラを用いて機械語に翻訳することを前提としたコンパイラ言語、インタプリタと呼ばれるプログラムがソースコードを解釈し実行するスクリプト言語と、記述できる抽象度を高める方向へと進化してきた。 プログラミング言語はその存在理由から、より抽象度の高い記述が行えること、すばやい開発を行える事が求められる。抽象度の高い記述とは、プログラムがどういう処理を行うか(HOW)ではなく何の処理を行うか(WHAT)を記述しやすい構文、機能を持っていることを、すばやい開発とは記述性の高さ、コードの密度の高さ、バグの発生しにくい構文、機能を持っていることをさす。 この抽象度の高い記述、すばやい
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
アルゴリズムとデータ構造
Google Code Jam
http://labs.cybozu.co.jp/blog/kazuho/archives/2008/06/friends_timeline.php
テクノロジー : 日経電子版
