PCREの範囲の正規表現を可視化してくれるサイト - 唯物是真 @Scaled_Wurm
最近書いた再帰を使った正規表現を可視化しようと思ってGoogle検索してみたのですが、上位に出てくるサイトでも日本語が使えなかったりサポートしている正規表現にPCREの範囲(というか再帰)が含まれていなかったりいろいろでした いくつか正規表現の可視化サイトを試したので簡単に表にしました google: regex visualizer の検索結果上位3件を試したメモ サイト 日本語対応 正規表現の範囲 画像ダウンロード その他 Regexper ◯ 再帰はダメだった SVG, PNG Generated images licensed: CC BY 3.0と書いてあるので、生成した画像のライセンスが縛られているかも(？) Debuggex: Online visual regex tester. JavaScript, Python, and PCRE. △微妙に文字幅の計算がおかしいのか
拡張ユークリッドの互除法 - 唯物是真 @Scaled_Wurm
\(a, b\)の2つの正の整数が与えられたときに\(ax+by=\gcd(a, b)\)となるような整数\(x, y\)のうちの1つの組を計算するアルゴリズム たとえば5リットルの入れ物と7リットルの入れ物を使って11リットルの水を汲む方法などが計算できる 昔こんなツイートをしてたようですがようやく理解できた気がします(遅すぎ。中国の剰余定理の方はまだ) 中国の剰余定理とか拡張ユークリッドの互除法とかわかってない(´・ω・｀)— 無限猿(id:sucrose)@39月病 (@Scaled_Wurm) 2014年12月23日 Wikipediaの説明を読んだらよくわからなくて？？？となったがいろいろググってなんとか理解した \(a, b\)の2つの整数についてユークリッドの互除法をやるときに、\(ax_1+by_1=a\)と\(ax_2+by_2=b\)みたいに両辺がある形で考えて\(a(
シェルスクリプトで文字列の大小比較をする - 唯物是真 @Scaled_Wurm
シェルスクリプトのif文で文字列の辞書順の大小関係を条件判定したかったので調べました bashなどには[[]]コマンドがあるので、簡単に文字列比較ができます(ところで[[]]って検索しづらいですね [](test)コマンドの方でも文字列の大小比較はできますが、以下のように>や<をエスケープする必要があります(手元で試したらbashでは動いてzshでは動かなかった) [ string1 \< string2 ] [ string1 \> string2 ][[]]を使うと以下のように自然に書くことができます [[ string1 = string2 ]] [[ string1 == string2 ]] [[ string1 != string2 ]] [[ string1 < string2 ]] [[ string1 > string2 ]]久しぶりに書くと[]の内側や演算子の周りに空白
読書記録『勝てる野球の統計学――セイバーメトリクス』☆☆☆ - 唯物是真 @Scaled_Wurm
野球のデータを統計的に見ていくセイバーメトリクスの入門書 セイバーメトリクス - Wikipedia アウトカウントと走者の状況別のその後の得点期待値を見ると、得点期待値は送りバントをすると下がってしまうが、得点確率を見ると状況によっては上がるらしい、などという感じに野球を統計データを使って見ていく為の本 日本のプロ野球のデータを使っているところがよい 入門書だからか天下り式に数式が突然出てきて説明があまりないものが多いのは難点 たとえば以下のピタゴリアン期待値は勝率と強い相関があるらしいけど、どこからこの式が湧いてきたんだろうという感じにもなる(必ずしも2乗でなくてデータから何乗にするのがよいか決めるらしい) $$ピタゴリアン期待値 = \frac{得点^2}{得点^2 + 失点^2}$$ その他にも打者や投手、守備の指標などいろいろと出てくる 見てみたらわりとWikipediaにもいろ
5分でわからない統計的検定 - 唯物是真 @Scaled_Wurm
社内でABテストとか統計的仮説検定の話題が出ていたので、統計的検定を知らない人向けに「5分でわかる統計的検定」というLTをしようかと思ったけど、まったく5分で終わる気がしなかったのでとりあえずブログにまとめてみる ちなみに社内では統計的検定は数名の人が個人的に趣味で使っている程度 個人的には統計的検定をやることをそんな重要視してないけど(PVとかユーザー数多ければだいたい有意差出るし、数値を見て明らかに差があるような変更でないとあまり意味がないような気がする) 自分は統計やABテストなどにあまり詳しいわけではないので注意 間違いはコメントやTwitterなどで教えていただけると嬉しいです 統計的検定とは 雑にいうと、得られた結果が偶然得られたものどうかを確かめる方法(特定の仮定のもとで) ABテストでは別々のものをユーザーに見せた結果が偶然の差ではなく統計的に意味のある差(有意差)が得られ
PHP の mt_rand() は一貫して壊れている(consistently broken)らしい - 唯物是真 @Scaled_Wurm
PHPでMersenne Twister法で擬似乱数を生成する関数のmt_rand()にバグがあり出力がおかしい、という話が流れてきておもしろかったので簡単にまとめておく kusanoさんがmt_rand()の実装に9年以上前から1文字違いでバグがあったことを見つけて、数ヶ月後にマージされる(追記: 正確には、PHP版の実装が他と異なっているのは前から知られていたらしい*1 ) PHPに送った1文字修正するプルリクエストがマージされた🎉 mt_rand()の返す値が元のメルセンヌツイスタと異なっていた。https://t.co/Z5WJhHVyNd— kusanoさん@がんばらない (@kusano_k) February 17, 2016 その後、生成される擬似乱数列が変わってしまうので、後方互換性を壊す変更は議論してからmergeすべきということでrevertされるこの前マージされた
キャラソートのアルゴリズムについて調べた - 唯物是真 @Scaled_Wurm
「キャラソート」とは 以下のページのようにキャラ(あるいは人物などの何らかの要素)を2つずつ表示して「どちらか好きか？」という質問に連続で答えていくことで全体のランキングを作るWebサービス(「◯◯キャラソート」、「◯◯ソート」など)が様々な作品について存在している 東方キャラソート どんなアルゴリズムを使っているのかに興味がわいたので調べてみました ソートのアルゴリズム 以下の解説記事を読むとわかるようにマージソートやヒープソートといったソートアルゴリズムを人間にそのままやらせているらしい ただし単純にソートアルゴリズム使うだけではなく、計算量を減らすため引き分けなどの場合にはそのペアのデータを一つにまとめたものとして扱うように工夫している ハロプロ・ソートの解説 咲-saki-キャラソート - 勤々惰々 管理しないsabakan » キャラソートアルゴリズムについて ソートアルゴリズム
bag of wordsのbagがmultisetという意味だったことを今更知った - 唯物是真 @Scaled_Wurm
自然言語処理や情報検索などでよく使われるbag of wordsモデルというのがある これはテキストデータを単語(形態素？)の位置は無視して単語ごとの出現回数だけで表す方法で、このモデルで表したデータを適当に機械学習の分類器にかけるだけでそれなりによい結果が得られたりする Bag-of-words model - Wikipedia, the free encyclopedia 画像でもbag of visual wordsという似たようなものが使われることがあるaidiary.hatenablog.com あまり名前の意味を考えたことがなかったけど、bagは多重集合(multiset)の別名らしいというのをTwitterで見かけた(Wikipediaにも書いてある) 多重集合 - Wikipedia 多重集合は同じ要素を複数個入れられる集合なので、名前はモデルをそのまま表していたらしい
組み合わせの個数(二項係数)を計算する - 唯物是真 @Scaled_Wurm
Pythonで組み合わせ(Combination)を計算 - 唯物是真 @Scaled_Wurm 数年前に上のような記事を書きましたが、ライブラリを使わない場合の計算について書いてなかったので記事にしました 組み合わせとは いくつかの要素の中から、順番を区別せずにいくつかの要素を選ぶ方法 組合せ (数学) - Wikipedia 具体的なそれぞれの組み合わせを得たい場合、Pythonならitertools.combinationsで引数に与えたiterableの組み合わせを返すイテレータが得られます C++ならnext_permutationが使えますが、あらかじめソートしておかないといけないので注意が必要です 組み合わせの数 \(n\)個の要素の中から、\(k\)個要素を選ぶ方法の個数は以下のように階乗(!)を使って計算できます $${\binom nk} = \frac{n!}{k!(
じゃんけんが終わるまでの平均回数を求める - 唯物是真 @Scaled_Wurm
じゃんけんをするときに人数が多いとあいこが増えて、なかなか終わらなかった経験があると思います \(n\)人でじゃんけんした時に、ただ1人の勝者が決まるまでの回数の期待値(平均回数)を計算してみました また大人数でもすぐに勝負がつくゲーマーじゃんけんも取り上げています この記事ではある人がグー・チョキ・パーを出す確率はそれぞれ等しいとします じゃんけん まず結果が知りたい人のために最初にグラフを載せておきます 横軸が人数、縦軸がただ一人の勝者が決まるまでのじゃんけんの平均回数です \(10\)人で約\(24\)回、\(15\)人で約\(159\)回と、人数が増えると回数の期待値が急激に増えていくのがわかると思います 人数 回数の期待値 1 0 2 1.5 3 2.25 4 3.21428571429 5 4.48571428571 6 6.2198156682 7 8.64673579109
来年は機械学習のコンペにもうちょっと参加したい - 唯物是真 @Scaled_Wurm
今年はいろいろ開催されたのに全然参加できなかった 目標に「kaggleに参加する」とか書いてた気がするんだけど…… 画像認識系だとまったく手が出ないのもなんとかしたい 機械学習のコンペは、訓練データが与えられてそれで何かしら予測モデルを作って予測結果を提出するっていう形式が多いです 途中のランキング用のデータと最終評価用のデータが別にあってうまく予測できているかを競います 賞金付きなのが結構多く、学生限定とかの出場制限もあまりありません ちなみに素性エンジニアリングとかをがんばるのなら時間がある方が有利かなと思うので学生の人におすすめです(？) コンペが開催されてるサイト kaggle(英語) 一番の大手。参加者が多くて相手が強すぎる感じもする 終了後にフォーラムとかブログとかで手法が公開されていることが多いので参考になる no free hunch | the sport of data
サザエさんのジャンケンの次の手を決定木で予測+可視化してみた - 唯物是真 @Scaled_Wurm
前に決定木の可視化をしようと思ってやってなかったのでやっておきます 決定木のライブラリは例のごとくscikit-learnを使う pythonの機械学習ライブラリscikit-learnの紹介 - 唯物是真 @Scaled_Wurm 決定木とは 決定木は教師あり学習で使われるモデルで、ルールを木として学習します 例えば身長、体重から性別を予測したい場合、身長が170cm以上で体重60kg以上なら男、みたいなルールを学習します 性能はあまりよくないモデルですが、人間にもわかりやすいルールを出力する(他のモデルと比べれば)という特徴があります 簡単に説明すると、ある変数が一定値以上であるかという条件で分けた時に、データのラベル(性別なら男女)ごとの分布がどちらかに偏るような条件で木を作っていきます 予測するときには、データが条件を満たしているノードをたどって木の一番下の葉ノードまでいって、葉ノ
Derangement - 唯物是真 @Scaled_Wurm
Derangement - Wikipedia, the free encyclopedia 完全順列 - Wikipedia Derangementは\(1, 2, \dots, n - 1, n\)を要素とする順列のうち、すべての\(i\)番目の要素が\(i\)と等しくない順列のこと(不動点の個数が\(0\)) たとえば\(1, 2, 3\)を要素とする順列は以下の6通りのものがあります(不動点に下線を引いています) \(\underline 1, \underline 2, \underline 3\) \(\underline 1, 3, 2\) \(2, 1, \underline 3\) \(2, 3, 1\) \(3, 1, 2\) \(3, \underline 2, 1\) この内、Derangementは以下の2通りになります \(2, 3, 1\) \(3, 1, 2
素因数分解とかエラトステネスの篩(ふるい)とかのメモ - 唯物是真 @Scaled_Wurm
素数を求めたり素因数分解するのは競技プログラミングでたまに出てきます 計算量とか詳細をあまり知らなかったので基本的なアルゴリズムについて調べてみました アルゴリズムや数学についてはあまり詳しくないので間違いがあったら指摘してください ランダウの記号\(O(\cdot)\)とか使ってますが理解はゆるふわです ランダウの記号 - Wikipedia まずは基本的なところから始めていきます 以下では正の整数についてだけ考えます 素数 \(1\)とそれ自身でしか割ることができない整数(\(1\)は含まれない) $$ 2, 3, 5, 7, 11, 13, 17, 19, \dots $$ 素因数分解 整数を素因数(約数になる素数)の積で表す $$ 60 = 2^2 \times 3 \times 5 $$ 試し割り(\(\sqrt n\)以下のすべての整数) Trial division - Wi
Pythonのcollectionsモジュールが地味に便利 - 唯物是真 @Scaled_Wurm
PythonのcollectionsモジュールにはdefaultdictやCounterなどの便利なデータ構造があります。 いくつかメモ代わりに紹介しておきます defaultdict 辞書にキーが含まれない場合のデフォルト値を指定できます。 リストをデフォルトで持つ辞書などが作れます。 defaultdictへの引数としては初期値のものを返す関数を与えます from collections import defaultdict d = defaultdict(list) d['Hello'].append('World') 変わった使い方としては以前別の記事でも紹介しましたが単語にIDを割り振るのに便利です 単語などをIDにマッピングする - 唯物是真 @Scaled_Wurm 以下のようなコードを書くと未知の単語が辞書に与えられたら、その単語に新たなIDを振っていくことができます。 w
TopCoder マラソンマッチ AlleleClassifier に参加した(11/154位) - 唯物是真 @Scaled_Wurm
マラソンマッチというのは10日間ぐらいの期間で問題を分析しコードを書いてスコアを競う競技です。 今回ので3回めのマラソンマッチ参加。 序盤は上位にいられたのですが、終盤は失速してしまいましたorz 順位表 http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15876 問題の説明 AlleleClassifier 問題の内容は与えられたデータ点(\(x, y\)の2次元の値)の6つのラベルへの分類でした。 与えられたデータ点はいくつかのマップごとに与えられています。 ラベルは'0'、'0 or 1'、'1'、'1 or 2'、'2'、'>2'となっていて、マップ内のデータ点は\(z = x - y\)の値の昇順に6つのラベルに分けられています。 問題文にも書いてあるのですが、マップごとに大きく値とラ
幾何分布の期待値の導出 - 唯物是真 @Scaled_Wurm
TLで以下のツイートと続く議論を見かけたのでメモ。 長縄跳び、1000回に1回しか失敗しない人を、30人集めてやったら、飛べる回数の期待値は、どれぐらいなんだろう。 2014-01-18 09:28:49 via web 長縄跳び、30人がジャンプ成功する確率はp=0.999^30。x回で失敗する確率a(x)=(1-p)*(p^x)として、S(Y)=Σ{x*a(x)} (x=0,...,Yの総和)を、S(Y)-pS(Y)から求め、Y→∞にしてp/(1-p)がでたけど、もっと楽な誘導があったような… 2014-01-18 13:28:03 via web 幾何分布 こういう◯◯が連続して\(k\)回まで成功する確率をあらわしている分布として幾何分布というものがある 幾何分布 - Wikipedia 図は英語版のWikipedia(Author: Skbkekas)より $$P(X=k)=p(
大量のテキストからランダムに少数の行を抽出したい - Reservoir Sampling - 唯物是真 @Scaled_Wurm
前に以下のような記事を書きましたが、大量のテキストではうまくいかなかったので新たに書きました ファイルからランダムにN行取り出す(shufコマンド) - 唯物是真 @Scaled_Wurm 上の記事ではテキストをランダムに\(k\)行取り出したい時"shuf -n k"コマンドでランダムにシャッフルした\(k\)行を取り出していました ところが非常に大きなテキストファイルに対して上のコマンドを実行すると、一度にデータを全部メモリに読み込み始めているのか、すごい勢いでメモリを消費していきました(sort -Rでも) そこでメモリをあまり使わずにランダムに\(k\)行取り出す方法について調べました まず基本的な非復元抽出のアルゴリズムは以下の記事の発展手法とか追記のあたりの話がわかりやすいと思います 非復元抽出の高速かつ実装が簡単な方法を考える - 睡眠不足？！ この記事の話も一度全部の要素を
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
