link もっと前
   2019年 10月 12日 -
      2019年 10月 21日  
link もっと後

link 未来から過去へ表示
link 過去から未来へ表示(*)

日々

link permalink

台風 19号

あの台風 15号(Faxai)(2019年 9月 8日の日記参照)を超える、かつてない規模の台風 19号(Hagibis)が来るということで、窓にガラス飛散防止でダンボールを貼ってみたり、食料、水を買い込んで備えていました。

都内だと多摩川沿いの一部堤防のない地域が水浸し、東日本だと長野、宮城が洪水で大変なことになっているそうで、東京の治水事業には感謝しかありません。


多摩川の水位

我が家からはやや遠いですが、最寄りの大きな川といえば多摩川です。水位が大変なことになっていて、思わずスクリーンショットを撮ってしまいました……。

我が家は北と東に窓がありまして、台風15号のときは北からガンガン風と雨が吹き付けていたため、あまりの風圧に、雨が窓サッシの隙間から侵入していました。壁に飛来物が当たり、ものすごい音もしていました(窓の真横に当たり、窓にはギリギリ当たらず本当に幸運だった)。今回はどうやら西、ないし、南から吹き付けていたようで、15号のときほど被害はありませんでした。

今回は全体的に幸運でしたが、災害への備えは日頃からやっておいて損はないですね。

家財

家の外にある家財は車くらいしかないので、台風が過ぎた後に見に行ってみましたが、特に飛来物が当たった形跡もなく、何ともなかったです。良かった良かった。

[編集者: すずき]
[更新: 2019年 10月 24日 01:35]
link 編集する

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link permalink

Git の小技、コミット ID 取得

最近、会社で CI/CD で自動化のマネごとを始めました。といっても大したことはなくて、ビルドして Debian や RPM パッケージを作って、Web サーバーにぶっこむだけです。

Nightly ビルドのパッケージを作成する際に、パッケージ名の最後に Git のコミット ID を付加しようと思ったのですが、方法が分かりません。調べてみると rev-parse というコマンドを使うそうです。知らなかった。

Git のコミット ID(全体、短縮)を取得する
$ git rev-parse HEAD

5ab7d0ae0c170fc0409d564fe945aac5ce54f86c

$ git rev-parse --short HEAD

5ab7d0ae0c1

ID 全部だと長すぎるため --short オプションを使うとより良いです。

[編集者: すずき]
[更新: 2019年 10月 21日 02:02]
link 編集する

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link permalink

linux-next の不思議なバージョン情報

Linux というか linux-next ですが、リポジトリ内のファイルをオリジナルから変更してビルドした場合、バージョン情報の最後に -dirty が付きます。あれはどうやっているのだろう??と気になりました。

Makefile を眺めていると、scripts/setlocalversion というスクリプトでローカルバージョンを付与しているように見えます。

試しに clean なリポジトリで scripts/setlocalversion を実行すると、-next-20191009 のような localversion のみ(※)が表示され、ファイルを適当に書き換えてから実行すると、-next-20191009-dirty になりました。このスクリプトで当たりっぽいです。

もし Linux Upstream カーネルで試す場合は、CONFIG_LOCALVERSION_AUTO を y にして、make prepare を実行する必要があります。そうしないと scripts/setlocalversion を実行しても "+" しか表示されません。

(※)この文字列はトップディレクトリの localversion-next というファイルに書いてあります。

Git の小技、リポジトリ変更を検知

スクリプト setlocalversion を追いかけてみると git --no-optional-locks status -uno --porcelain で変更を検知して、-dirty を出力するかどうか決めていました。オプション --porcelain のヘルプを見ると「スクリプトなどで処理しやすい形式で status を出力する」とのことです。へえー、こんなのあるんだ。初めて知りました。

オプション --no-optional-locks はロックを取らずに実行するという意味です。ヘルプ曰く、バックグラウンドで status を実行する際に、他の git status プロセスと衝突するので、指定した方が良いとのこと。手動で使うことはなさそうだし、気にしなくて良いでしょう。

オプション -uno は --untracked-files=no の省略形です。効果は実際に見た方が早いです。以下をご覧ください。

Git リポジトリに変更を加える
#### scripts/setlocalversion を書き換え

$ vim scripts/setlocalversion

#### 未追跡ファイル aaa を作成

$ touch aaa

上記の変更を加えたうえで、オプション -uno なし、オプション -uno ありで、それぞれ実行してみます。

Git リポジトリに変更が生じているか取得する(-uno なし、あり)
$ git status --porcelain

 M scripts/setlocalversion
?? aaa


$ git status -uno --porcelain

下記と同じ

$ git status --untracked-files=no --porcelain

 M scripts/setlocalversion

見た目で明らかだとは思いますが、オプション -uno が指定されていない場合は、未追跡のファイル aaa も表示されますが、-uno を指定すると未追跡のファイルは無視します。

スクリプト内で Git リポジトリが変更されたか?されていないか?を判定する必要は、普通の人はほぼ無いと思うんですけど……、もし必要が生じたら、sed とか grep とかでゴチャゴチャやらずに、オプション --porcelain を使いましょう。

[編集者: すずき]
[更新: 2019年 10月 21日 02:35]
link 編集する

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link permalink

イコライザー

普段ヘッドフォンを使っているのですが、若干、低音が足りないなと思うことがあります。

Windows 標準の Bass Boost は設定項目が 2つと大変シンプルでわかりやすいですが、音の歪みを防止するためなのか、Boost を有効にすると音が全体的に小さくなってしまうのが辛いところです。


Bass Boost

最大値は 24dB ですが、最大値に設定しようものなら非常に音が小さくなります。良いヘッドフォンアンプを持っていればアンプ側で音量を上げれば良いですが、PC のヘッドフォン端子に直接ヘッドフォンを接続している場合は、ボリュームを最大にしても聞こえなくなる可能性があります。


Bass Boost の設定画面

これはイマイチだなあってことで、代わりを探していましたら、VLC Player のイコライザはシンプルデザインかつ設定の幅が広くて、とても良かったです。


VLC イコライザの設定画面

全体の音量(Preamp)と、各帯域ごとの音量を別々に調整できるので、Windows の Bass Boost に似た設定もできる(Preamp を下げ、80Hz 帯を上げる)し、音が歪むのもお構いなしの設定にもできます。あまりやりすぎるとバリバリ言い始めるのでほどほどに、ですけど。

[編集者: すずき]
[更新: 2019年 10月 24日 00:36]
link 編集する

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link permalink

線形探索と 2分探索の話

Twitter で線形探索と 2分探索の性能逆転ポイントはどこか?という話をしていて、気になったので測ってみました。

線形探索と 2分探索は、要素数を N としたとき、処理量オーダーでいうと O(N) と O(logN) となり、圧倒的に 2分探索が速いです。ただし処理量オーダーによる比較は、N が十分に大きい場合に成り立ちます。N が極端に小さい場合は線形探索が 2分探索と同等、もしくは、勝ってしまう領域があるのではないか?という話です。

結論だけ先に言えば 2分探索の圧勝でした。かなり N を小さく(100 程度)しないと、線形探索に勝ち目はなかったです。個人的には N=1000〜2000 程度ならば線形探索が勝つ予想をしていましたが、全くそんなことはなかったです。2分探索スゴい。

探索速度検証

検証方法ですが、線形探索(lsearch)を実装して、C ライブラリ(GNU libc 2.29)に実装されている 2分探索(bsearch)と速度を比較しました。線形探索 lsearch の API は 2分探索と揃えています。

処理の概要は下記の通りです。探索の対象は同じものを使っています。

  • 要素数 N の配列を作る
  • 配列を乱数で埋める
  • 配列をソートする(bsearch はソート済みの配列にしか使えない)
  • 2分探索(bsearch)を M 回実行する、時間を測る
  • 線形探索(lsearch)を M 回実行する、時間を測る

ソースコードは下記のとおりです。

線形探索と 2分探索の速度比較プログラム

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

int comp(const void *key, const void *val)
{
	int k = *(int *)key;
	int v = *(int *)val;

	return k - v;
}

void *lsearch(const void *key, const void *base,
	      size_t nmemb, size_t size,
	      int (*compar)(const void *, const void *))
{
	void *v = (void *)base;
	size_t i;

	for (i = 0; i < nmemb; i++) {
		if (compar(key, v) == 0)
			return v;
		v += size;
	}

	return NULL;
}

int main(int argc, char *argv[])
{
	int *array, *keys;
	int **fb, **fl;
	size_t n, kn, i;
	struct timeval start_b, end_b, ela_b;
	struct timeval start_l, end_l, ela_l;

	if (argc < 3) {
		fprintf(stderr, "usage:\n\t%s n loop\n", argv[0]);
		return -1;
	}

	n = atoi(argv[1]);
	kn = atoi(argv[2]);
	if (n == 0 || kn == 0) {
		fprintf(stderr, "usage:\n\t%s n loop\n", argv[0]);
		return -1;
	}

	srand(time(NULL));

	array = (int *)malloc(n * sizeof(int));
	keys = (int *)malloc(kn * sizeof(int));
	fb = (int **)malloc(kn * sizeof(int *));
	fl = (int **)malloc(kn * sizeof(int *));

	for (i = 0; i < n; i++) {
		array[i] = rand() % (int)n;
	}
	for (i = 0; i < kn; i++) {
		keys[i] = rand() % (int)n;
	}

	qsort(array, n, sizeof(int), comp);

	gettimeofday(&start_b, NULL);
	for (i = 0; i < kn; i++) {
		fb[i] = bsearch(&keys[i], array, n, sizeof(int), comp);
	}
	gettimeofday(&end_b, NULL);
	timersub(&end_b, &start_b, &ela_b);

	gettimeofday(&start_l, NULL);
	for (i = 0; i < kn; i++) {
		fl[i] = lsearch(&keys[i], array, n, sizeof(int), comp);
	}
	gettimeofday(&end_l, NULL);
	timersub(&end_l, &start_l, &ela_l);

	for (i = 0; i < kn; i++) {
		if (fb[i] && fl[i] && *fb[i] == *fl[i])
			continue;

		if (fb[i] != fl[i])
			printf("diff %d: key:%d, fb:%d, fl:%d\n",
				(int)i, keys[i],
				(fb[i]) ? *fb[i] : -1,
				(fl[i]) ? *fl[i] : -1);
	}

	printf("n:%d, loop:%d, bin: %d.%06d[s], lin: %d.%06d[s]\n",
		(int)n, (int)kn,
		(int)ela_b.tv_sec, (int)ela_b.tv_usec,
		(int)ela_l.tv_sec, (int)ela_l.tv_usec);

	return 0;
}

コピペしていたり、エラー処理が甘かったり、適当な書き方で申し訳ないですが、性能比較が目的なのでそこは見逃していただくとして。測ってみるとこんな結果になりました。

環境は Ryzen 7 2700, Debian 10 (Linux 5.2.0-3-amd64) です。コンパイラは gcc 9.2.1 で、最適化レベルは -O2 です。

線形探索と 2分探索の速度比較(100万回)
$ for i in 1 `seq 25 25 500`; do ./a.out $i 1000000; done

n:1, loop:1000000, bin: 0.001702[s], lin: 0.001710[s]
n:25, loop:1000000, bin: 0.019114[s], lin: 0.011656[s]
n:50, loop:1000000, bin: 0.022469[s], lin: 0.018549[s]
n:75, loop:1000000, bin: 0.026413[s], lin: 0.023774[s]
n:100, loop:1000000, bin: 0.028008[s], lin: 0.028900[s]
n:125, loop:1000000, bin: 0.029601[s], lin: 0.034308[s]  ★この辺りで逆転される★
n:150, loop:1000000, bin: 0.030671[s], lin: 0.040280[s]
n:175, loop:1000000, bin: 0.031898[s], lin: 0.045664[s]
n:200, loop:1000000, bin: 0.032771[s], lin: 0.048153[s]
n:225, loop:1000000, bin: 0.033985[s], lin: 0.052148[s]
n:250, loop:1000000, bin: 0.034322[s], lin: 0.055871[s]
n:275, loop:1000000, bin: 0.034761[s], lin: 0.059935[s]
n:300, loop:1000000, bin: 0.035766[s], lin: 0.065683[s]
n:325, loop:1000000, bin: 0.036407[s], lin: 0.070435[s]
n:350, loop:1000000, bin: 0.037010[s], lin: 0.072971[s]
n:375, loop:1000000, bin: 0.036926[s], lin: 0.077805[s]
n:400, loop:1000000, bin: 0.037422[s], lin: 0.082656[s]
n:425, loop:1000000, bin: 0.037844[s], lin: 0.086240[s]
n:450, loop:1000000, bin: 0.038894[s], lin: 0.089354[s]
n:475, loop:1000000, bin: 0.038516[s], lin: 0.093286[s]
n:500, loop:1000000, bin: 0.038590[s], lin: 0.100021[s]

結果の見方ですが、最初の n: は配列の要素数です。次の loop: は何回検索するかを表しています。bin: は 2分探索 bsearch、lin: は線形探索 lsearch を表し、それぞれ loop 回実行し終わるまでの時間を出しています。

線形探索と 2分探索の逆転ポイントは実行するたびに割とズレますが、N=500 にもなれば、もはや線形探索に勝ち目はありません。2分探索強いです。

ループ回数を増やしても大勢に影響はありませんが、ループ回数を増やすほど lsearch がわずかに有利になるようです。N=1 のとき lsearch が勝つことが多いので、関数の呼び出しコストが低いのかも?

個人的に予想していた N=1000〜2000 のレンジでは、線形探索は桁違いに遅かった(2分探索の 10倍近く時間がかかる)です。私の予想は当てにならんなあ。

[編集者: すずき]
[更新: 2019年 10月 24日 00:45]
link 編集する

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
   2019年 10月 12日 -
      2019年 10月 21日  
link もっと後

管理用メニュー

link 記事を新規作成

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDF ファイル RSS 1.0
QR コード QR コード

最終更新: 11/11 11:44

カレンダー

<2019>
<<<10>>>
--12345
6789101112
13141516171819
20212223242526
2728293031--

最近のコメント 5件

  • link 19年09月01日
    すずき 「私も正直びっくりです。間違って違う製品を...」
    (更新:09/04 23:39)
  • link 19年09月01日
    hdk 「車向けの製品の中でも、車載コンピューター...」
    (更新:09/02 23:20)
  • link 19年07月18日
    hdk 「あっ、AAMはマニュアルのオペレーション...」
    (更新:07/25 00:02)
  • link 19年07月18日
    すずき 「AAM(ASCII Adjust AX ...」
    (更新:07/24 22:22)
  • link 19年07月18日
    hdk 「加算減算は符号のありなしどちらも命令が同...」
    (更新:07/24 07:25)

最近の記事 3件

link もっとみる
  • link 19年11月07日
    すずき 「[独自の apt サーバー - その 6 - ソースコードパッ] ...」
    (更新:11/11 11:44)
  • link 19年08月29日
    すずき 「[独自の apt サーバー - その 5 - 複数のセクション] ...」
    (更新:11/08 00:41)
  • link 19年08月13日
    すずき 「[独自の apt サーバー - その 4 - まとめ] 独自の a...」
    (更新:11/08 00:41)

こんてんつ

open/close wiki
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報