文字列の繰り返しと計算量 - odz bufferref:http://blog.livedoor.jp/dankogai/archives/51172176.html なんか、計算量が絡むとひどいなー。 問題1 C で Dan さんが挙げられた 2 つのアルゴリズムと同様のものを実装せよ。 問題2 n を変化させながら、計算時間がどのように変化するか観察せよ。 問題3 2 つのアルゴリズムについて計算量はどうなるか。
ビット数を数えるルーチン - Weblog on mebius.tokaichiba.jp
かつてＪＲ横浜線 十日市場駅近くのMebius (CPU:Pentium 150MHz)より発信していたウェブログです。 32bitの立っているビット数を高速に数えるアルゴリズムとして、 int bitcount(unsigned long n) { n = ((n&0xaaaaaaaa) >> 1) + (n&0x55555555); n = ((n&0xcccccccc) >> 2) + (n&0x33333333); n = ((n&0xf0f0f0f0) >> 4) + (n&0x0f0f0f0f); n = ((n&0xff00ff00) >> 8) + (n&0x00ff00ff); n = ((n&0xffff0000) >> 16) + (n&0x0000ffff); return n; } こういうのが良く知られている。1行目で2ビットずつ足し合わせることで2ビットの中の
2の冪 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "2の冪" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2024年6月) 2の冪 2n の直方体による図示。 左上1 (=20) から右下 1024 (=210) まで。 2の冪（にのべき、（英: power of two）は、2 を底とし整数の指数を持つ冪である。2の冪は、指数を n として一般に、2n の形で表される（例えば n = 0, 1, 2, 3, … に対してそれぞれ 20 = 1, 21 = 2, 22 = 4, 23 = 8, …）。 1に2倍のみを繰り返すことによって得られる数であり、ごく基本的な数量操作で得られる
深さ優先探索（バックトラック法） - Wikipedia
深さ優先探索のイメージ 深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。 形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。 深さ優先探索の空間計算量は幅優先探索の空間計算量より最悪のケースでは同じだが一般的なケースではずっと小さい。また、探索の種類によっては、分岐を選択するためのヒューリスティックな方
幅優先探索 - Wikipedia
ドイツの都市間の接続を示した例 フランクフルトから幅優先検索を行った場合にできる木構造 幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。 幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。
冪乗 - Wikipedia
数学における冪乗（べきじょう、べき乗、英: 仏: 独: exponentiation）または冪演算（べきえんざん）とは、底 (てい、英: base) および冪指数 (べきしすう、英: exponent) と呼ばれる二つの数に対して定まる数学的算法のことである。 その結果は冪 (べき、英: power) と呼ばれる。表現の揺れにより同じ概念は日本語で「累乗（るいじょう）」とも表現されており、初等教育ではこちらの表現のほうが多くなっている（本文参照）。 底（英語版） b および冪指数 n をもつ冪は、底の右肩に冪指数を乗せて bn のように書かれる。 であり、bn は b の n-乗や、n-次の b-冪などと呼ばれる。 特定の冪指数に対して、固有の名前が付けられている。例えば、冪指数が 2 である冪（2 乗） b2 は「b の平方 (square of b)」または「b-自乗 (b-squar
スターリングの近似 - Wikipedia
この記事には参考文献や外部リンクの一覧が含まれていますが、脚注によって参照されておらず、情報源が不明瞭です。 脚注を導入して、記事の信頼性向上にご協力ください。（2015年12月） log n! と n log n − n は n → ∞ のとき漸近する スターリングの近似（英: Stirling's approximation）またはスターリングの公式（英: Stirling's formula）は、階乗、あるいはその拡張の一つであるガンマ関数の漸近近似である。名称は数学者ジェイムズ・スターリング（英語版）にちなむ。 スターリングの近似は精度に応じていくつかの形がある。応用上よく使われる形の公式は、ランダウの記号を用いて、 である。O(log n) における次の項は (1/2)log 2πn である。故に、次によい近似の漸近公式（英語版）は である[1]。（ここで記号 は両辺の比が（n
スターリングの公式
階乗n!というものは、nが大きくなると計算が大変である。 5!=1×2×3×4×5=120 ぐらいなら簡単だが 13!=1×2×3×4×5×6×7×8×9×10×11×12×13=6227020800 あたりになると、かなり大変である。 そこで、階乗の計算を別の式で近似しようというのがスターリングの公式というものである。 これは あるいは とあらわされる。 定積分がうまくできない場合、積分がグラフ上の面積を求めることであることから、積分領域を長方形に分割して近似的に計算してしまう方法がある。（参考：Excelで積分する） この上の赤い部分の面積を計算する代わりに、下のように分割した長方形の面積を求める。 これと逆の発想で、長方形の面積の合計を積分で表すことを考える。 20!を求めてみよう。 いきなり20!を求めるのではなく、ちょっと工夫してloge20!を求めてみる。 l
文字列繰り返しベンチマーク take 2 - moriyoshiの日記
追記: もっとよいアルゴリズムについて教えてもらいました (1, 2)。新しい結果とコードはこちら。 TraceMonkeyの結果が不正確だったので取り直した件ですが…。 速くはなったけど、あまり変わらず。 という残念な結果に。 Chrome FF3.0 FF3.1b2 IE6 IE8 Opera9.63 Safari WebKit concat_op 98 193 138 1230820.5 375 172 263.5 175.5 join 109.5 258 166.5 1398.5 398.5 648.5 200 82.5 hybrid 20.5 93.5 82 70 39 31.5 36 33 bulk 1 104.5 86 17633 23 15.5 55 54 (単位は ms)
同じ文字列のn回繰り返しを作る「最速」の方法 - by edvakf in hatena
同じ文字列のn回繰り返しを作る最速の方法を探求してみた - muddy brown thang パズルっぽくておもしろかったのでやってみた。と、別のところにも書いたのだけど、あそこじゃあ反応が薄いので、見てる人が多そうなこっちで聞いてみる。 function(s,n){ var q = ''; while(n){ if(n%2) q += s; s += s; n >>= 1; } return q; } javascript:alert((function(s,n){var q='';while(n){if(n%2)q+=s;s+=s;n>>=1;}return q;})('hoge',10)) //=> hogehogehogehogehogehogehogehogehogehoge 速さのベンチはこっちの一番下にある data:uri をアドレス欄に入れてみたらいいと思います。 もっ
同じ文字列のn回繰り返しを作る最速の方法を探求してみた - moriyoshiの日記
注意: FF3.1b2の結果が不正確です。取り直したのはこちら。 ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。 あらまし JavaScriptの文字列型 (およびStringオブジェクト) はJavaのようにイミュータブルなので、こういう文字列構築を行う方法としては、以前から、+や+=演算子を用いるよりも、一旦Array()に入れておき最後にjoin()するという方法が有効だと言われていてですね、まあ確かに、文字列用メモリ領域の確保
jpn.ph - このウェブサイトは販売用です！ - jpn リソースおよび情報
This webpage was generated by the domain owner using Sedo Domain Parking. Disclaimer: Sedo maintains no relationship with third party advertisers. Reference to any specific service or trade mark is not controlled by Sedo nor does it constitute or imply its association, endorsement or recommendation.
Sorting Algorithms Animations
KEY Black values are sorted. Gray values are unsorted. A red triangle marks the algorithm position. Dark gray values denote the current interval (shell, merge, quick). A pair of red triangles marks the left and right pointers (quick). DISCUSSIONThese pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to: Show how each algorithm operates.
Internationale Fachkommunikation | Hochschule Flensburg
Studierendensekretariat studierendensekretariat@hs-flensburg.de Telefon: +49 (0)461 805 - 1308 Info Point infopoint@hs-flensburg.de Telefon: +49 (0)461 805 - 1444 Kontakt Hochschule Flensburg Kanzleistraße 91–93 24943 Flensburg Telefon: +49 (0)461 805 - 01 Telefax: +49 (0)461 805 - 1300 infopoint@hs-flensburg.de
Counting sort - Wikipedia
, where k is the range of the non-negative key values. In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small positive integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that possess distinct key values, and applying prefix sum on those counts to determine the positions of each key va
Schwartzian transform - Wikipedia
This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2024) (Learn how and when to remove this message) In computer programming, the Schwartzian transform is a technique used to improve the efficiency of sorting a list of items. This idiom[1] is appropriate for
ALGORITHM NOTE
X×Y個のセルから成るグリッド上のスタート地点から出発し、全５種類のパチクリ（生物）を捕まえた状態でゴール地点まで行く最短コストを求める問題です。各パチクリはそれぞれ、火、氷、木、土、水の属性を持ち、火のパチクリは氷のパチクリを捕まえることができ、氷のパチクリは木のパチクリを捕まえることができ、といったように火→氷→木→土→水→火というような属性の関連があります。スタート地点で最初に持つパチクリを１つ選ぶことができます。グリッドのサイズx, y はそれぞれ2以上1000以下で、各属性のパチクリの数はそれぞれ0以上1000以下です（全体の数は5000以下）。 最初に１つのパチクリを選んだ後のパチクリを捕まえる順番は、上記属性の関連の順番になります。例えば最初に火の属性をもつパチクリを持っていれば、氷、木、土、水の属性をもつパチクリを順番に捕まえてゴールに行けばよいので、下図に示すDAG（Di
計算量を具体的に見てみる 2009-01-06 - きしだのはてな
アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();
Firebugで探索アルゴリズムを見ていこう
Firebugで探索アルゴリズムを見ていこう：コーディングに役立つ！ アルゴリズムの基本（6）（1/4 ページ） プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部） 今回紹介するのは探索のアルゴリズムです。探索もアルゴリズムのテーマとしてはメジャーなもので、とても重要な用語や考え方が出てきます。 あるデータの集合があったとします。それぞれのデータには、個々を識別するためのIDが付いています。このIDをキーと呼びます。このキーに対応するデータを探すのが探索です。 データベースを知っている方なら主キーで検索する動作だと思ってください。例えば、商品のリストがあり、それぞれの商品に商品コードが付いています。商品コード「7100」に対応する商品データ「トマト」を検索するプログラム
第4回 memcachedの分散アルゴリズム | gihyo.jp
株式会社ミクシィの長野です。第2回、第3回と前坂がmemcachedの内部について紹介しました。今回は内部構造から離れて、memcachedの分散についての紹介をいたします。 memcachedの分散 連載の1回目に紹介しましたが、memcachedは「分散」キャッシュサーバと言われていますが、サーバ側には「分散」の機能は備わっていません。サーバ側には当連載の第2回、第3回で前坂が紹介したメモリストレージの機能のみが組み込まれており、非常にシンプルな実装となっています。では、memcachedの分散はどのように実現しているのかと言うと、すべてクライアントライブラリによって実現されます。この分散方法はmemcachedの大きな特徴です。 memcachedの分散とは ここまで数度「分散」という言葉を用いてきましたが、あまり詳しく触れてきませんでした。ここでは各クライアントの実装に共通する大ま
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
