ズンドコキヨシ with C using 128bit XORshift(擬似乱数生成) - Qiita
#include <stdio.h> #include <stdint.h> // Thaks to http://d.hatena.ne.jp/jetbead uint32_t xor128(void){ static uint32_t x = 123456789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } int main(void) { int idx; uint32_t val; int zuncnt = 0; for(idx = 0; idx <
ナップサック問題でマラソンマッチ入門 - notブログ
マラソンマッチって？ 競技プログラミングのうち、「より良い解を求める」ことを競うコンテストをマラソン形式と呼びます。 例えば厳密解を求めることができない問題について、近似解のスコアを競ったりします。 マラソンでよく使われるアルゴリズム マラソンで頻出なのは「ビームサーチ」と「焼きなまし法」です。 この記事ではナップサック問題を例にしてこの２つのアルゴリズムを解説します。 もちろん、この２つのアルゴリズムはどちらも近似アルゴリズムなので最適解は求められません。 ビームサーチ まずは順番にナップサックに入るだけ入れるコードを書いてみます。 #include <iostream> using namespace std; int main() { // 個数 const int N = 100000; // ナップサックの大きさ const int W = 100000; // 重さ・価値 in
Mathの高速化を検証する - Qiita
Mathは本当に遅いのか 色の距離（色差）を計算するときにちょっとだけ試してみたので，実際によくある（小手先）高速化手法でMathが速くなるのか検証してみた． 検証方法 JavaとAndroidで検証． 単純に実行時間をSystem.nanoTimeで取得し，比較している． 検証順や検証タイミングで最適化がかかったりするので，何回か実行して落ち着いた値で比較している． Javaの検証はIntel Xeon E5 3.5GHzのMac Pro，Androidの検証はQualcomm Snapdragon 800 MSM8974 2.2GHzのSO-02Fで試している． 従来のMathクラスと，実装したDMathクラスで比較した． 10万回実行して1回あたりの実行時間をnano秒で表示している．詳しい方法は一番下を参照． べき乗の高速化 べき乗を計算するMath.pow()は小数のべき乗もサポ
JavaScript開発に役立つ重要なランダムの数式まとめ - ICS MEDIA
プログラムで使うことの多い「乱数」。ゲーム開発やビジュアルアート、ウェブサイトのアニメーションにおいて乱数は非常に重要で、さまざまな用途で利用されています。プログラムで一般に乱数と聞くと、すべての数値が同じ頻度（分布）で出現する「一様乱数」と呼ばれる乱数をイメージする方が多いと思います。 多くの場合はこの「一様乱数」で取得した乱数を用いれば十分でしょう。しかし、場合によっては「一様乱数」ではなく、偏りのある乱数を用いることでコンテンツの見た目や現象の「自然さ」を演出することが可能です。 実は「一様乱数」に一手間加えることで、乱数の分布の偏りを制御できます。今回は乱数を使用して好みの分布を得るためのパターンをいくつか紹介します。 乱数分布のシミュレーションデモ （HTML5製） 次のデモはリアルタイムで乱数の出現頻度を計算し、グラフに可視化するコンテンツです。画面下のプルダウンで乱数の種類を
累積和の使い方を学ぶ – himajinworks::blog
ちょっととあるところで出くわしたので。 アルゴリズム苦手勢として、やったことはまとめておきたい。 あるデータ列Xがあって、Xのk個ずつの区間でのそれぞれの和を必要とする問題。(k≦|X|=N) 安直にやったら t_element x[N], r[N-K]; t_counter i, j; for (i = 0; i < N - K; i++) { r[i] = 0; for (j = 0; j < K; j++) { r[i] += x[i + j]; } } みたいな感じな気がする(コンパイルしてない)。でも超絶遅い。 でぐぐってみたら http://togetter.com/li/617816 の記事というかまとめを発見。累積和なるものを知る。 要は、 こんなことすると速くなるで、ってこと。 残念ながらそれまでの自分の頭のなかは画像の一番最後辺りの # zsh echo $(($(e
音割れ音源、機械学習で復元したくない？その1 〜短時間フーリエ変換と近接勾配法〜 - cocuh's note
このまえHな講義*1を受けてたあとに、@polamjag 氏とダベってたら 「音割れ音源復元できないか」 みたいな話がでて面白そうだったので趣味研究してみた成果だったりします。 信号解析初経験な上に片手間でやった研究なので、かなり穴だらけだと思うのでお気づきのことがありましたら、ご指摘お願いします。 背景 話によると、そこらへんで買った音源って音割れしてるらしい。 audacityで[view]->[show clipping]をオンにすると音割れ箇所を可視化してくれる。 ノーポイッを見てみた図。 (amazon mp3で購入、買ってない方ぜひ買いましょう。 http://www.amazon.co.jp/dp/B017BAK632 ) あかい。。。 ということで、ｻｰﾍﾞｲするこくたんであった。 目的 音割れしている音源(5分ぐらいの)をいい感じに補完して 人間の耳にやさしく 補完する。
乱数のたのしい話と遺伝アルゴリズム - きしだのHatena
金曜日の「プログラマのための数学勉強会＠福岡」で乱数の話をしてきました。 プログラマのための数学勉強会@福岡 #3 - connpass で、乱数の生成だとか、クイックソートや素数判定などの乱択アルゴリズムの話とかをしました。 乱数タノシイヨ 乱数のたのしい話 from なおき きしだ その中で、遺伝アルゴリズムで巡回セールスマン問題(TSP)を解くというのをやってみました。遺伝アルゴリズム、すいぶん昔から名前は知ってて、どういうアルゴリズムかも知ってて、実装もそんな難しくないと知りつつ、書く機会がありませんでした。なので、この機会に書いてみようと。 とりあえず最初に完全にランダムでTSPを解いてみます。 TSP with random ぐちゃぐちゃですね。 下部のグラフはその時点での最短距離。最初に距離が短いものをみつけていくけどだんだんみつかりにくくなる、という感じになっています。 1
魚心あれば水心 − 最適なペアを決めるマッチング・アルゴリズムの話 | タイム・コンサルタントの日誌から
Apple初期にMac OSを開発した中心メンバーに、アンディ・ハーツフェルドという伝説的なプログラマがいた。Appleを退社後、独自にSwitcherというユーティリティ製品を開発するのだが、これはシングルタスクだったMacOS上で、複数のアプリを同時に動かせるという独創的なソフトだった。ところで以前、彼のインタビューをよんでいたら、彼が人生で最初に作ったプログラムが、高校のダンスパーティーの男女ペアを自動算出するものだったと書いてあり、笑ってしまった。世界中どこにいたって、魚心と水心の組み合わせは、つねに揉め事の種なのだ。 男女のお見合いから、研究室の配属、そして就活の就職先選びまで、世の中には「求める側」と「与える側」の組み合わせ問題に満ちている。あるいは、デマンド側とサプライ側、と言いかえてもいい（男女のどっちが供給側かはともかく）。その典型は、サプライチェーンであろう。需要と供給
Python Dask で Out-Of-Core / 並列 LU 分解 - StatsFragments
はじめに 正方行列 を となる下三角行列 と 上三角行列 に分解することを LU 分解という。LU 分解ができると連立方程式の解や逆行列が 前進/後退代入でかんたんに求められてうれしい。 Dask を使って LU 分解を Out-Of-Core / 並列でやりたい。 LU 分解の並列化にはいくつかやり方があるようで、東大講義 スパコンプログラミング(1)、スパコンプログラミング(Ｉ) の 第10回 LU分解法 にまとまっている。この講義、ガイダンス資料の単位取得状況を見るとかなり楽しそうな感じだ。 ここでは、Dask での実装がかんたんそうなブロック形式ガウス法 (資料 P33-) をやりたい。 ブロック形式ガウス法 ブロック形式ガウス法では入力となる行列をいくつかのブロックに区切り、ブロックごとに処理を行う。具体的には、左上の対角ブロックからはじめて、以下の順番で処理していく。 対角ブロ
HL分解 (Heavy-Light Decomposition) - ペケンペイのブログ
HL 分解 (heavy-light decomposition) についてではなく、パスクエリを複数の列クエリに分解するという考え方について説明する。HL 分解は木が与えられて次の二種類のクエリを処理する問題等で用いられる。 uv パス上のすべての頂点にxを加算する uv パス上の値の総和を求める 総和クエリの例。この場合は 2+3+4+9+6+4+7+1=36 が答えになる 木ではなく列であれば segment tree によって効率的に処理できる。HL 分解は木をパスに分解することで、木の問題を列の問題に還元する。木をパスに分解するとはどういうことだろうか。例えば次の図のようなものが木をパスに分解した例になっている。 冒頭で例に出したクエリは次の形に分解できる。 このクエリはsum[16..16] + sum[13..14] + sum[0..1] + sum[6..8]で計算できる
CodeIQについてのお知らせ
2018年4月25日をもちまして、 『CodeIQ』のプログラミング腕試しサービス、年収確約スカウトサービスは、 ITエンジニアのための年収確約スカウトサービス『moffers by CodeIQ』https://moffers.jp/ へ一本化いたしました。 これまで多くのITエンジニアの方に『CodeIQ』をご利用いただきまして、 改めて心より深く御礼申し上げます。 また、エンジニアのためのWebマガジン「CodeIQ MAGAZINE」は、 リクナビNEXTジャーナル( https://next.rikunabi.com/journal/ )に一部の記事の移行を予定しております。 今後は『moffers by CodeIQ』にて、 ITエンジニアの皆様のより良い転職をサポートするために、より一層努めてまいりますので、 引き続きご愛顧のほど何卒よろしくお願い申し上げます。 また、Cod
組み合わせを列挙する - kuidaored’s blog
SRMとかやってると組み合わせをみる必要があったりして、そのたびに同じようなコードを書いていたので、なんとか出来ないかと思って書いてみた。 import java.util.*; public class Combinations<T> implements Iterator{ private List<List<T>> combinations; private List<T> list; private int[] index; private boolean[] visited; private int r; private Iterator<List<T>> iterator; public Combinations(T[] array, int r){ this.list = Arrays.asList(array); this.index = new int[r]; this.
[機械学習] クラスタリングにおけるコサイン類似度に関する性質の証明 - tsubosakaの日記
bayonやCLUTOが爆速な理由 - download_takeshi’s diaryを読んで、すぐには成り立つかどうか分からなかったので証明してみた。 上の記事で述べられていることはクラスタ中のベクトルとその中心ベクトルのコサイン類似度の和と、クラスタ中のベクトルを全て足したベクトルのノルムが一致するというである。 ただしここでクラスタ中の要素ベクトルはすべて大きさ1の規格化されたベクトルであるとする。 証明 今クラスタ内に含まれるベクトルを とする。 このとき全ベクトルを足しこんだ複合ベクトルを とする。またこのクラスタのセントロイドは となる。このときセントロイドと各ベクトルとのコサイン類似度は [tex: s_i = \frac{}{||C|| ||x_i||} = \frac{}{||{C}||}] となる。ここでと正規化されていることを用いた。この類似度の合計は [tex:
![[機械学習] クラスタリングにおけるコサイン類似度に関する性質の証明 - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/437ae042a71338c391758f2afa29457c5ff0c015/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124030345%2F1557332441)
棒倒し法による自動生成の迷路 - 素人がプログラミングを勉強していたブログ
JavaScriptによる自動生成迷路に置いた。 function rand(n) { return Math.floor(Math.random() * n); } const width = 33, height = 33; var wall = (1 << (width - 2)) - 1 << 1; var table = [1 << (width - 2)]; var stripe = 0; var i, j; for (i = 1; i < width; i += 2) { stripe |= 1 << i; } for (i = 1; i < height - 1; i++) { table[i] = i & 1 ? wall : stripe; } table[height - 1] = 2; const top = 0, right = 1, bottom = 2, le
γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー
通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符号化手法の一つで、この無駄を幾分解消します。詳しくは Introduction to Information Retrieval (以下 IIR) の第5章に掲載されています。(http://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html で公開されています) Variable Byte Code はその名の通りバイトレベルの可変長符号で、1バイトの先頭1ビットを continuation ビットとして扱い、続く 7 ビット
微分方程式を解こう！ | _level0 - KAYAC Front Engineer Blog
どうも。こんにちは。梅雨明けも宣言されたそうで、いよいよ暑くなりますね。今回は単振動方程式方程式を用いた最適化のお話です。 高校物理でも登場するバネの方程式、単振動方程式 を簡単な四則計算に分解する方法を紹介します。 まず色々な数学的背景を押しやって、イメージだけ説明すると、物体の位置x、速度v、加速度aの関係は となるので、asの式で考えると、 v += a; x += v; という風になります。ここで単振動の微分方程式から、 a = -K * x; であるから、あわせると、 v -= K * x; x += v; という風になります。下がサンプルで、初期値(_v, _y)やKなんかを変えて挙動が変わることが分かります。 ここでのポイントはvに対して最初の式で破壊的な操作を行っていることです。 v_temp = v; v -= K * x; x += v_temp; 等とすると、ずれてし
数列データベース：On-Line Encyclopedia of Integer Sequences - 発声練習
みなさん、あるアルゴリズムの計算量の上限値や下限値を考えているときに自分で数列の一般式を求めることありませんか？そんなあなたにJohn H. Conway and Richard K. Guy著, 根上 生也訳：数の本に紹介されていました、数列データベースをご紹介いたします。 On-Line Encyclopedia of Integer Sequences この数列データベースはキーワードや数列を検索キーとして登録されているデータベースの中から検索をしてくれます。 例えば、深さnのラベルなし二分木の種類数は、`1, 3, 21, 651, 457653'という数列になります。これを検索キーとして検索すると以下のような検索結果がでます。 Number of binary trees of height n; or products (ways to insert parentheses)
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
栗田多喜夫「サポートベクターマシン入門」（PDF）
実装ノート
ビンパッキング問題の解き方 - Qiita
