Algorithm Introduction #18 B-Treeはてなで行われたアルゴリズム・イントロダクション勉強会第18章B-Treeの資料です． - Download as a ZIP, PPTX or view online for free
ヒープ - Wikipedia
親要素が常に2つの子要素より大きくならない（またはその逆）構造になっている。 挿入、削除がO(log n)で可能。探索は。 ルートが常に最小（または最大）要素となっているので、ルートの削除を繰り返すことで、ソートを行うことができる。 このときの計算量は。(ヒープソート) 木の高さの低い方（または深さの浅い方）から、また同じ高さでも左または右のどちらかに要素を寄せた木構造を作る。深さ の要素がすべて使われるまで、深さ の要素は作成しない。要素の添字を 1 から開始すると、要素 の親は 、子は および となる（添字を 0 から開始すると親は 、子は と である）。 後述する手順に従って操作すれば、データの出現順序に関わらず、このような構造を容易に維持できることがヒープの利点である。 構造の節で述べたように、任意の要素に対する親要素と子要素は添字の計算で特定することができる。また要素が存在するか
二分探索木 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "二分探索木" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年3月) 二分探索木 二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。 構造は二分木と同じだが、「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ。左の子孫の値と右の子孫の値の両方に等号をつけているが、実際にはどちらかに統一しておく必要がある。 平衡（左右のバランスがとれている状態）し
二分木 - Wikipedia
簡単な二分木。大きさ9、深さ3、根は値2を持つ 二分木（にぶんぎ）は、データ構造の1つである。二進木（にしんぎ）やバイナリツリー（英: binary tree）とも呼ばれ、根付き木構造の中で、全てのノード（節点 node）が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。 たとえば、二分探索や二分ヒープを実装するために使われる。 以後、括弧の中は英語表記。 親から子へ有向線分（辺、エッジ edge）が引かれる。子を持たないノードを葉（リーフ leaf）ないし外部ノード (external node) と呼ぶ。葉でないノードを内部ノード (internal node) と呼ぶ。あるノードの「深さ」(depth) はルート（root 「根」にあたるノード）からそのノードまでにたどる経路（パス path）の長さ（経路の種類ではなく、ノード-ノードを1と数え
)
木構造 (データ構造) - Wikipedia
この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。 適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。（2023年1月） 木構造は、一般のグラフ構造と同様の、ノード（節点、頂点）とノード間を結ぶエッジ（枝、辺）あるいはリンクで表すこともできるが、木構造専用の、特に有向の根付き木となるような表現が使われることも多い。 データ構造として使われる木は、ほとんどの場合、根となるノードが決められた根付き木である。さらに、有向木であることも多い。[注 1] ノード間の関係は家系図に見立てた用語で表現される。木構造内の各ノードは、0個以上の子ノード (英: child node) を持ち、子ノードは木構造内では下方に存在する（木構造の成長方向は下とするのが一般的である）。子ノードを持つノードは、子ノードから見れば親ノード (英
最近傍探索 - Wikipedia
最近傍探索（英: Nearest neighbor search, NNS）は、距離空間における最も近い点を探す最適化問題の一種、あるいはその解法。近接探索（英: proximity search）、類似探索（英: similarity search）、最近点探索（英: closest point search）などとも呼ぶ。問題はすなわち、距離空間 M における点の集合 S があり、クエリ点 q ∈ M があるとき、S の中で q に最も近い点を探す、という問題である。多くの場合、M には d次元のユークリッド空間が採用され、距離はユークリッド距離かマンハッタン距離で測定される。低次元の場合と高次元の場合で異なるアルゴリズムがとられる。 ドナルド・クヌースは、The Art of Computer Programming Vol.3（1973年）で、これを郵便局の問題で表した。これはすな
おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？…
二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？ 条件は次の通りです １．集合Pはあらかじめ、任意の順番でソートしておける ２．点ｐの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる ターゲットの言語はjavascriptで、200msぐらいの間隔で検索を続けるつもりです 集合P の個数が 1000 ~ 10000 点くらいだったらどうしますか？ みなさんのアイディアを貸してください
2006-06-13
ここのバージョン５を参考に http://www.nminoru.jp/~nminoru/programming/bitcount.html import Bits bitCount1 :: Int -> Int bitCount1 b = (foldl f) b [(1,0x55555555),(2,0x33333333),(4,0x0f0f0f0f), (8,0x00ff00ff),(16,0x0000ffff)] where f :: Int -> (Int,Int) -> Int f b (n,a) = (b .&. a) + ((shiftR b n).&. a)実行結果 *Main> bitCount1 1 1 *Main> bitCount1 2 1 *Main> bitCount1 3 2 *Main> bitCount1 4 1 *Main> bitCount1 5 2
Sticks(10) - カメヲラボ
最短コード250B 270byteあたりからは、ロベールさんと私でじわりじわりと削り合い。ちなみに、前回までで紹介しているコードは、はてな用に私が新しく書きなおしたものなので当時のコードとは違う部分もある。どんなインプットでも通るコードというのは、実は260byteくらいまでしか短縮することが出来ない。それ以上縮めるには探索時間やメモリを犠牲にしていかなければならないのだ。 260byte程まで縮んだところで、ロベールさんがTLE(Time Limit Exceed)に掛からない程度に探索ループを書き換え254byte。そして私がそこからさらに短縮して251byte。 L,F,*I; c(n,l,p,j){ --I[p]; for(j=l-=p;F*j;--j)I[j]&&c(n,l,j); for(j=F=--n?F:0;!I[j];)--j;l||c(n,L,j); ++I[p]; }
Sticks(9) - カメヲラボ
意外と読める超短いコード 昨日のコードをさらに短くすると以下のようなコードになる。ここまでくると変数名を一文字にした方が逆に読みやすい。え？読みにくい？そうですか..(´ω｀) int L,F,*I; c(n,l,p,j){ --I[p]; F=n?F:0;for(l-=p,j=l<p?l:p;j;--j)F*I[j]&&c(n,l,j); for(j=50;!I[j];)--j;l||c(n-1,L,j); ++I[p]; } main(s){ for(;s;L&&printf("%d\n",L-1)){ int w[51]={s=F}; scanf("%d",I=w); for(;w[0]--;++w[L],s+=F<L?F=L:L)scanf("%d",&L); for(L=F;F;++L)s%L||c(s/L,L,F); } } if文の代わりに&&や||を使うのはコード短縮の常套
Sticks(8) - カメヲラボ
準備 コードを短縮するには、通常のプログラミングで「だめ！」と言われていることをやっていかなければならない。ここからはプログラミングというよりパズルの問題。いかに少ない文字数で、同等の処理をさせられるか。 まず、手始めにシンボル名をすべて一文字にする。 また、配列の初期化はどうしても文字数が増えてしまうため初期化の代わりに新しく宣言しなおすことにする*1 改行コード・空白を省くと330byte程度。まだまだ短縮可能だ。 int L,F,*I; c(n,l,p,j){ --I[p]; if(n==0)F=1; if(!F){ if(l-=p){ for(j=l<p?l:p;j>0;--j) if(I[j])c(n,l,j); } else { for(j=50;!I[j];)--j; c(n-1,L,j); } } ++I[p]; } main(s,b,m){ for(;s;printf("
Sticks(7) - カメヲラボ
計算量を減らす ちょっとした演算でも数十万回呼ばれる可能性があるのであれば、それなりに時間がかかってしまう。演算回数を減らす努力は、再帰の仕組みを真面目に考えるきっかけになり、コードはスマートになっていく。そして、最終的にはコード短縮につながる。 昨日のコードで無駄な部分は、in[n]のデクリメント・インクリメントを2箇所で行っている点。再帰なら一度ずつで済むはずだ。 ということを考えて修正すると、700byte弱になった。シンボル名を一文字にして改行コードを除けば半分程度になるだろうから、これを短縮すればおそらく300byteくらいにできるだろう。 int length,finish,in[51]; check(count, len, plen) { int j; --in[plen]; if(count==0)finish=1; if(!finish){ if(len-=plen){
ラベルは無駄やの - Cozy Ozy
とりあえず変数を減らしていく inputの値は最大64個、それにあわせてlabelも64個。さらにinputはソートしなければならないとなれば、最短コードを目指すには無駄が多すぎる。簡単な方法はlabelを使わないことだが、inputを0で潰す方法は再帰コードで書くとbacktrackし辛い(一つ余分に変数が必要になる)。 この問題のテストケースは、inputの値が最大でも50と問題に書かれている。ということは、inputの値を配列番号にしてその数のカウントをデータにしてしまえばスッキリする。たとえばこれまでの例で使用したinput 15 11 8 8 8 4 3 2 1は、新しい配列(in[51])を使えば in[15]=1, in[11]=1, in[8]=3, in[4]=1, in[3]=1, in[2]=1, in[1]=1 それ以外のin[n]はすべて0再帰する場合1引いて、b
Sticks(5) - カメヲラボ
サンプルコード とりあえず、今まで書いたことを元にそのままコードを書いてみることにする。それなりに読める形で1100byte強。これを最終的に250byteほどに短縮するわけだが、このままではどう考えても不可能だ。基本的なアルゴリズムは変えずに、まずデータ構造をシンプルにしなければならない。 以下はソースコードベタ貼りなので、興味ない人はスルー 001 int input[64],label[64],length; 002 int n;//inputの個数 003 004 int check(int count) 005 { 006 int i=0; 007 if(count!=0) 008 { 009 while(label[i])i++;label[i]=1; 010 if(!search(length-input[i],i+1,count))label[i]=0; 011 } 012
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Loading...
sideways addition
http://www.ic-net.or.jp/home/takaken/nt/index.html
アルゴリズムとデータ構造編 トップページ●Programing Place
時事・strlen - Chasoの日記