木の半径、直径、中心、重心
最近よく見聞きする木の用語を整理しておく。 離心数（eccentricity） 節点vから最も離れた節点をwとする。 このときパス(v, w)の長さをvの離心数と呼ぶ。 記号で表すときは、ε(v)と書く。 木の半径（radius） 離心数の最小値。つまりmin_(v ∈ V) ε(v)。 木の中心から最も遠い節点までの距離とも言える。 木の直径（diameter） 離心数の最大値。つまりmax_(v ∈ V) ε(v)。 最も遠い2点間の距離と言える。 木の中心（center） 離心数が最小の節点。 最も離れたところにある節点までの距離が最小の節点なので、なんとなくグラフの中心にありそうなイメージと合致する。 木の重心（centroid） 節点vを根とした木を考える。 vの直接の子以下の最大部分木の節点数が最小となる場合、vを木の重心と呼ぶ。 木を再帰的に分割して何か処理をしたい場合、木の
JISキーボードの記号の並び
アスキーコード表を眺めていて見たことある並びがあるなと思ったら、JISキーボードの並びと同じだった。 JISキーボードでは、!"#$%&'()の記号が123456789のキーに配置されている。 !"#$%&'()のアスキーコードは21,22,23,24,25,26,27,28,29（16進数表記）であり、連番である。 つまりJISキーボードを見ると、これら9つの記号のアスキーコードの大小がすぐに分かる。いや、それだけではない。アスキーコードを16で割った余りさえも分かってしまうのだ（キーの数字を見ればよい）。 というどうでもいい話に気づいてしまった2016年の正月早朝....
Pythonのdoctestが便利
Pythonの関数のコメント部にテストを仕込めるらしい。 テストサンプルを見ると、その関数が何をするのかぱっと見で分かるので、便利。 import doctest import operator def aggregate_val(f, x): """ aggregate values of a dict "x" with a binary function "f". >>> aggregate_val(operator.add, {'x': 10, 'y': 20}) 30 >>> aggregate_val(min, {'x': 10, 'y': 20}) 10 """ return reduce(f, [v for _, v in x.items()]) if __name__ == '__main__': doctest.testmod() スクリプトから実行して、エラーがあると教
Leaderを選ぶアルゴリズム
CodilityのlessonにあるLeaderを選ぶアルゴリズムが面白い。 非負整数を要素に持つ長さnの配列a[]がある。 配列の中にn/2 回より多く出現する要素がある場合、その要素を配列のleaderと呼ぶ。 例えば、 [1,2,3,1,1,1] という配列の場合、1がleader。 [1,1,1,2,3,4] の場合は、leader不在となる。 配列a[]が与えられた時に、a[]のleaderを求めよ。 mapを使って要素毎の出現回数を数えるだけでしょ。 と思ったら、時間計算量の制限はO(n)らしい。 それなら、unodered_mapで数えればいいでしょ。 と思ったら、空間計算量（※）はO(1)らしい。 （※入力aを格納するのに必要なメモリは除く） いや、分かりません。 ということでマテリアルを読むと、スタックを使ったクレバーな解が紹介されてました。 C++で書いてみました。 #
Normalized compression distanceとNormalized Google distance
# -*- coding: utf-8 -*- import zlib """Normalized compression distance See the page below for more details: https://en.wikipedia.org/wiki/Normalized_compression_distance#Normalized_compression_distance """ def ncd(x,y): if x == y: return 0 z_x = len(zlib.compress(x)) z_y = len(zlib.compress(y)) z_xy = len(zlib.compress(x + y)) return float(z_xy - min(z_x, z_y)) / max(z_x, z_y) if __name__ == '__ma
平方剰余の根
ルジャンドル記号(a/p)を以下のように定義する。 a = 0 (mod p)ならば, (a/p) = 0 aが法pで平方剰余ならば、(a/p) = 1 aが法pで平方剰余でなければ、(a/p) = -1 が成り立つ。よって繰り返し二乗法を用いることで解の存在を簡単に判定出来る。 long long modpow(long long x, long long p, long long mod) { long long ret = 1; while (p) { if (p & 1) ret = ret * x % mod; x = x * x % mod; p >>= 1; } return ret; } // a is a quadratic residue modulo p? int Legendre(long long a, long long p) { long long ret =
キャッシュヒット率の測定
perfというツールを使ってキャッシュヒット率を測定してみた。 キャッシュの影響なんてたかが知れていると甘くみていたら、痛い目るので要注意。 知らない用語がちらほらあったので、簡単にまとめておく。 L1、L2、L3キャッシュ Level1、Level2、Level3の略。 それぞれ速度、容量に違いがある。 速度L1 > L2 > L3 容量L1 < L2 < L3 高速なキャッシュほど容量が小さくヒット率は低い。 容量の大きいキャッシュはヒット率は高いが、低速。 というトレードオフがある。 プロセッサは以下の順序で処理実行に必要なデータを探す。 ①L1キャッシュにアクセスし、ヒットすれば処理実行。ミスの場合は、L2へ。 ②L2キャッシュにアクセスし、ヒットすれば処理実行。ミスの場合は、L3へ。 ③L3キャッシュにアクセスし、ヒットすれば処理実行。ミスの場合はメインメモリへ。 L1dキャッシ
エラトステネスの篩の計算量
蟻本には、エラトステネスの篩の計算量はO(n log log n) と書いてあります。 log log nってなんぞや？どこから出てきたの？とずっと疑問でしたが、何故こうなるか分かったのでメモしておきます。 C++で書く場合は、概ね以下のようなコードが一般的かと思います。 bool isPrime[N]; int main() { for (int i = 2; i < N; i++) isPrime[i] = true; for (int i = 2; i < N; i++) { if (!isPrime[i]) continue; for (int j = 2 * i; j < N; j += i) isPrime[j] = false; } } まず簡単のため、上のソースの”素数でないなら飛ばす”という処理（※）が無かった場合を考えてみます。 （※）if (!isPrime[i] .
連分数
連分数関連の処理をC++で書いて遊んでみました。 連分数の基本については、Continued Fraction By Kardi Teknomo, PhD が分かりやすかったです。 冪級数展開が発散するときでも連分数展開は収束する場合があり、かつ、どちらも収束するようなケースでは連分数展開の方が収束が早い場合が多いらしく、実用的なトピックです。黄金比やネイピア数を連分数展開すると綺麗な形になるというのもまた興味を唆られます。 p/qを連分数展開する場合を考えます。 p/q = [p/q] + (p%q)/q = [p/q] + 1/(q/(p%q)) となります。 ただし、[]はfloor関数です。 a0 = [p/q], a1 = [q/(p%q)], ....となるのでこれを再帰的に考えていくとユークリッドの互除法と同じパターンになることが分かります。 #include <iostre
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
formulaで大きめのフォントで数式を書く