人工知能プログラミングコンテスト: SamurAI Coding 2016-17

http://samuraicoding.info/index-jp.html#main

xorshiftファミリ比較

概要

xorshift128, xorshift*64, xorshift+128を検証する. 32bitを返すバージョンも作成する.
検証はDieharder 3.31.1を使用する.

jemallocに置き換える

dlmallocを使用していたのですが, jemallocに置き換えます.
ビルドに詰まるところはなかったですが, static linkにする場合,
#include <jemalloc.h>の前に, #define JEMALLOC_EXPORTを入れるのを忘れないように.

Android 7 Nougat と jemalloc

binonicのソースツリーを見ると, Nougatにjemallocがある.
dlmallocから置き換えたってことかな.

Visual Studioの文字列リテラルの文字コードを設定する

#pragma execution_character_set("utf-8")

と書くと翻訳単位毎にリテラルの文字コードを設定できる.

さらに, clのオプション/FIは, 全てのソースファイルに対して強制的にインクルードするファイルを指定する.
forceinclude.hに, execution_character_setを書いて,

cl.exe /FIforceinclude.h

とすれば, やりたいことができるんじゃないかな.

Markdown をプレビューする

MarkdownPreview
MarkdownSharpと.NetのWebbrowserを使ってプレビューを試みる.
Markdownをプレビューするだけの機械.

カンファレンスのメモ取りに, Markdownを使おうとしたことがあった.
しかし, スタンドアロンのエディタに満足できそうなものがない.
VimのMarkdownプレビューも試したが満足できなかった.

時間ができたので作ったよ.
気に入らないところがあれば好きに弄るがいいです.

LOUDSでTrieを作る

LOUDSを用いたTrieです. 文字列をキーとした連想配列で使用することを想定しています.
Trieと 完備辞書はこのために作成しました.
上２つは公開時から不具合修正と機能追加をしています.

LOUDSは, 木構造をビット列で表現します.
節点を幅優先で走査し, 各節点で子の数だけ"1"を並べ, 節点の終端に"0"を置きます.
子のない節点は"0", 子が１つの節点は"10"です.

完備辞書

完備辞書そのものの説明は, ネット検索か,
高速文字列解析の世界<Amazon>で確認してください.

ビット列$B[0,n]\ B[i]\in\{0,1\}$
について, 以下の操作を実現する.
$access(B,i)\ B[i]$を返す
$rank_{b}(B,i)\ B[0,i)$中の$b\in\{0,1\}$の数を返す
$select_{b}(B,i)\ B$中の$i+1$番目に出現した$b\in\{0,1\}$の位置を返す

Trie

トライ木と呼ばれるデータ構造を作成します.
retrievalからtrieなので, treeと同じ発音だそうですが, 日本語ではトライだそうです.
各ノードがそれぞれラベルを持ち, 部分木は共通の接頭辞を持ちます.
"add", "and", "ans"からなるトライ木は以下のようになります.

前処理のための中間データとして作成したため, 効率は考慮していません.

population count

32bitのpopulation count
1のビットを数え上げる
コンパイラ組み込み関数を使わない場合,

inline u32 population_count(u32 v)
{
    v = (v & 0x55555555U) + ((v>>1) & 0x55555555U);
    v = (v & 0x33333333U) + ((v>>2) & 0x33333333U);
    v = (v & 0x0F0F0F0FU) + ((v>>4) & 0x0F0F0F0FU);
    v = (v & 0x00FF00FFU) + ((v>>8) & 0x00FF00FFU);
    return (v & 0x0000FFFFU) + ((v>>16) & 0x0000FFFFU);
}

gccの組み込み関数,

int __builtin_popcount(unsigned int x)

VCの組み込み関数,

unsigned int __popcnt(unsigned int value)

C#クロージャのUnity3Dにおけるコストについて

前回に引き続きクロージャです.

クロージャを実現するために, コンパイラは裏側でクラスを作成します.
もしスマートフォン向けのアプリケーションを開発しているのならば,
これだけでも高いコストを支払っています.

かなり強引な例ですが, 以下のようなコードの場合を考えます.
Destroyボタンを押してから, Unloadボタンを押してもテクスチャは解放されません.
Clearボタンを押してから, Unloadボタンを押すことで解放されます.
クラスはどこかから参照されているかぎり, ガーベージコレクタによって削除されません.
明らかにLoaderの実装に欠点がありますが,
texture変数は, コード上ではスコープから外れて参照が切れているように見えてしまっている、
ことも問題です.

C#クロージャのコストについて

プログラマ向けのテーマではないです. プログラムも行うデザイナ向けです.
もちろん, ちょっとしたツールを作るときはあなたの自由にプログラミングを楽しむべきです.

Visual Studio 2013 .Net Framework 4.5でコンパイルしました.
実験にはILSPYを使用しました.

URIは失念しましたが, このような実験を行った先人はいます.
疑問を持ったら, せっかく便利なツールがあるのですから, まず自分でやってみるべきです.

GameObjectをキャッシュして使い回すScrollRect

Unity3DのScrollRect.
DynamicScrollRectから見れば, GameObjectがキャッシュされているかは知らなくてよいこと.

_mm_load1_ps(_mm_load_ps1), _mm_set1_ps(_mm_set_ps1)

_mm_load1_ps(_mm_load_ps1)と, _mm_set1_ps(_mm_set_ps1)
どちらも, movssとshufpsになる.
最初から参照のものは_mm_load1_ps,
定数や参照でないものは_mm_set1_ps,
という使い分けでいいと思われる.

_mm_load1_psの存在意味がわからないな.
他のロード系命令との対応と, _mm_set1_ps(*x)と書かなくてもよいぐらい?

ポインタのエイリアスを意識したプログラムを書いてないので,
ここだけ頑張っても, という気もする

Unity3DのTime.time

float endTime = Time.time + duration;
while(Time.time<endTime);

というコードをよく見るので調べてみた.
もちろん私はこのようなコードは書かない.

ACES Filmic Tone Mapping Curve の近似の近似

ACES Filmic Tone Mapping Curve(Krzysztof Narkowicz)

float3 ACESFilm(float3 x)
{
    float a = 2.51f;
    float b = 0.03f;
    float c = 2.43f;
    float d = 0.59f;
    float e = 0.14f;
    return saturate((x*(a*x+b))/(x*(c*x+d)+e));
}

の近似. 定義域を[0 2]に狭める.

//domain x: [0 2]
float3 ACESFilmApprox(float3 x)
{
    return -0.053173 + x*(2.170622 + x*(-2.132296 + x*(0.996822 + x*-0.176583)));
}

Ray Tracing in One Weekend

Ray Tracing in One Weekend,
Ray Tracing: the Next Week,
がKindle向けに出ている.

Realistic Ray Tracing の共著者の一人,
Peter Shirley さんの本であってるかな?

Physically Based Rendering, Third Edition

Link to Amazon Japan, Physically Based Rendering, Third Edition: From Theory To Implementation

POSTD Memo

http://postd.cc/are-haskell-engineers-second-rate/

Xorshift*, Xorshift+

出力が64ビット.

Xorshiftの出力が32, 16, 8ビットで速度比較したサイトを見た記憶があるけれど,
ちょっと検索しただけじゃ見つからないな.
まあ, 演算数は変わらないし, 追加で内部状態のコピーぐらいだから, そう速くはならないよね.
デメリットの方が大きいぐらい.

XorshiftがGPLとかいう都市伝説が.
開発者のソースコードがあるなら, それはGPLかもしれない.
論文内のコードにGPLが適用されるのかね.
GPL的には, 誰が書いても同じになってしまうような短いコードには,
ライセンス適用すべきでないといってる. そらそうよ.

Dieharder
乱数のテストにどうぞ.

UnityEngine.UI.Imageを継承した, 任意Polygon描画クラス

適当に作る.
Github

一応はWYSIWYGと言えるかも.
要望次第で, Polygon Collider 2Dの編集インターフェイスと同じにするかもしれません.

タイルベースのレンダリングプロセスには, 扇形は細長い三角形を生成しがちなので良くない.
足りなければ考える.

C#でHopscotch Hashing

https://github.com/taqu/TinyCollections

C#で実装した場合, メモリを多く使った手法に比べて,
2倍くらいの検索時間になる.
挿入処理は, 空き領域の検索に時間がかかる.
私の用途では, 検索速度しか問題にしないが.

ハッシュの衝突が少なかった場合だけ,
C#のSystem.Collections.Generic.Dictionaryより
検索が速くなる.