2019-10-18

名前付きイベントだけを使ってプロセス間通信を行う(C#)

説明

特徴

名前付きイベントだけを使ってプロセス間通信できるんじゃね？と思って試してみたかっただけの代物。
ソケットとか共有メモリとかファイルとか一切使えないけど「名前付きイベント」だけは使えるという特殊な状況下でプロセス間通信したい時に使えるかも。
遅くて、実用的ではない。
- コンパクトさを目指したので、多少速くする余地はあると思う。
- 数十バイト程度の数回の通信なら気にならないと思う。

仕様

送受信データは文字列
'\0' は送れない。
一方通行 (クライアント ⇒ サーバー)

使い方

サーバー側プロセスで NRecver.NRecv(ident, recved) を実行しておく。
- 引数
  - ident -- イベントの名前に使用する。ぶつかりにくく無難な文字列 (UUIDなど) にすること。クライアント側と同じであること。
  - recved -- 文字列を受信する度に呼ばれる。
- ブロッキングモードで動作する。
  - 停止するには別スレッドで NRecver.NRecvEnd(ident) を実行する。
クライアント側プロセスで NSender.NSend(ident, message) を実行する。
- 引数
  - ident -- サーバー側と同じ文字列
  - message -- 送信するメッセージ

サーバー側 (受信側)

public class NRecver
{
	public void NRecv(string ident, Action<string> recved)
	{
		using (var s = new EventWaitHandle(false, EventResetMode.AutoReset, ident + "S"))
		using (var k = new EventWaitHandle(false, EventResetMode.AutoReset, ident + "K"))
		using (var b = new EventWaitHandle(false, EventResetMode.AutoReset, ident + "B"))
		using (var r = new EventWaitHandle(false, EventResetMode.AutoReset, ident + "R"))
		{
			MemoryStream mem = new MemoryStream();
			byte chr = 0;
			bool recving = false;

			// cleanup
			k.WaitOne(0); // 2bs
			b.WaitOne(0);

			for (int i = 0; ; )
			{
				s.WaitOne();
				if (k.WaitOne(0)) break;
				bool bit = b.WaitOne(0);
				r.Set();

				if (recving)
				{
					if (bit)
						chr |= (byte)(1 << i);

					if (8 <= ++i)
					{
						if (chr == 0)
						{
							recved(Encoding.UTF8.GetString(mem.ToArray()));
							mem = new MemoryStream();
							recving = false;
						}
						else
							mem.WriteByte(chr);

						i = chr = 0;
					}
				}
				else
					recving = bit;
			}
		}
	}

	public void NRecvEnd(string ident)
	{
		using (var s = new EventWaitHandle(false, EventResetMode.AutoReset, ident + "S"))
		using (var k = new EventWaitHandle(false, EventResetMode.AutoReset, ident + "K"))
		{
			k.Set();
			s.Set();
		}
	}
}

クライアント側 (送信側)

public class NSender
{
	private const int SEND_TIMEOUT_MILLIS = 2000;

	public void NSend(string ident, string message)
	{
		using (var s = new EventWaitHandle(false, EventResetMode.AutoReset, ident + "S"))
		using (var b = new EventWaitHandle(false, EventResetMode.AutoReset, ident + "B"))
		using (var r = new EventWaitHandle(false, EventResetMode.AutoReset, ident + "R"))
		{
			r.WaitOne(100); // cleanup

			foreach (byte[] bMes in new byte[][]
			{
				new byte[] { 0x00, 0x80 },
				Encoding.UTF8.GetBytes(message.Replace("\0", "")),
				new byte[] { 0x00 }
			})
			{
				for (int i = 0; i / 8 < bMes.Length; i++)
				{
					if ((bMes[i / 8] & (1 << (i % 8))) != 0)
						b.Set();

					s.Set();

					if (!r.WaitOne(SEND_TIMEOUT_MILLIS))
						throw new TimeoutException();
				}
			}
		}
	}
}

デモ・プログラム

ビルド済み配布物
http://stackprobe.ccsp.mydns.jp/NectarDemo
src
https://github.com/stackprobe/CSharp/tree/master/NectarDemo

2019-10-18

ナップサック問題(C#)

入力

public class Item // アイテム
{
	public int Value;  // このアイテムの価値 : 0 ～ 1,000,000 の範囲でランダムに生成
	public int Weight; // このアイテムの重さ : 0 ～     1,000 の範囲でランダムに生成
}

public class Condition // 与えられた条件
{
	public Item[] Items;       // 選択可能なアイテムリスト : 個数 0 ～ 1,000 の範囲でランダムに生成
	public int WeightCapacity; // 最大総重量               :      0 ～ 1,000 の範囲でランダムに生成
}

Solve0001

総当りで解く

public static Item[] Solve0001(Condition cond)
{
	Item[] best = null;
	bool[] selecteds = new bool[cond.Items.Length];
	bool forward = true;
	int index = 0;

	for (; ; )
	{
		if (forward)
		{
			if (cond.Items.Length <= index)
			{
				Item[] selectedItems = Enumerable.Range(0, cond.Items.Length).Where(i => selecteds[i]).Select(i => cond.Items[i]).ToArray();

				if (selectedItems.Select(item => item.Weight).Sum() <= cond.WeightCapacity)
					if (best == null || best.Select(item => item.Value).Sum() < selectedItems.Select(item => item.Value).Sum())
						best = selectedItems;

				forward = false;
			}
			else
			{
				selecteds[index] = true;
			}
		}
		else
		{
			if (selecteds[index])
			{
				selecteds[index] = false;
				forward = true;
			}
		}

		if (forward)
		{
			index++;
		}
		else
		{
			if (index <= 0)
				break;

			index--;
		}
	}
	return best;
}

Solve0002

動的計画法？で解く

private class SelectedItem
{
	public int ItemIndex;
	public int TotalValue;
	public SelectedItem Prev;
}

public static Item[] Solve0002(Condition cond)
{
	SelectedItem[,] table = new SelectedItem[cond.Items.Length, cond.WeightCapacity + 1];
	SelectedItem best = null;
	SelectedItem seli;

	for (int i = 0; i < cond.Items.Length; i++)
	{
		if (cond.Items[i].Weight <= cond.WeightCapacity)
		{
			table[i, cond.Items[i].Weight] = seli = new SelectedItem()
			{
				ItemIndex = i,
				TotalValue = cond.Items[i].Value,
				Prev = null,
			};

			if (best == null || best.TotalValue < seli.TotalValue)
				best = seli;
		}
	}
	for (int i = 0; i < cond.Items.Length; i++)
	{
		for (int w = 0; w <= cond.WeightCapacity; w++)
		{
			if (table[i, w] != null)
			{
				for (int ni = i + 1; ni < cond.Items.Length; ni++)
				{
					int nw = w + cond.Items[ni].Weight;

					if (nw <= cond.WeightCapacity)
					{
						int nv = table[i, w].TotalValue + cond.Items[ni].Value;

						if (table[ni, nw] == null || table[ni, nw].TotalValue < nv)
						{
							table[ni, nw] = seli = new SelectedItem()
							{
								ItemIndex = ni,
								TotalValue = nv,
								Prev = table[i, w],
							};

							if (best == null || best.TotalValue < seli.TotalValue)
								best = seli;
						}
					}
				}
			}
		}
	}
	List<Item> ret = new List<Item>();

	while (best != null)
	{
		ret.Add(cond.Items[best.ItemIndex]);
		best = best.Prev;
	}
	return ret.ToArray();
}

Extra

テスト用コード

public const int ITEM_VALUE_MIN = 0;
public const int ITEM_VALUE_MAX = 1000000;

public const int ITEM_WEIGHT_MIN = 0;
public const int ITEM_WEIGHT_MAX = 1000;

public const int ITEM_COUNT_MIN = 0;
//public const int ITEM_COUNT_MAX = 1000;

public const int WEIGHT_CAPACITY_MIN = 0;
public const int WEIGHT_CAPACITY_MAX = 1000;

public class Item
{
	public int Value;
	public int Weight;
}

public class Condition
{
	public Item[] Items;
	public int WeightCapacity;
}

public static Condition MakeCondition(int itemCountMax)
{
	Condition cond = new Condition();

	cond.Items = new Item[SecurityTools.CRandom.GetRange(ITEM_COUNT_MIN, itemCountMax)];
	cond.WeightCapacity = SecurityTools.CRandom.GetRange(WEIGHT_CAPACITY_MIN, WEIGHT_CAPACITY_MAX);

	for (int index = 0; index < cond.Items.Length; index++)
	{
		cond.Items[index] = new Item()
		{
			Value = SecurityTools.CRandom.GetRange(ITEM_VALUE_MIN, ITEM_VALUE_MAX),
			Weight = SecurityTools.CRandom.GetRange(ITEM_WEIGHT_MIN, ITEM_WEIGHT_MAX),
		};
	}
	return cond;
}

/// <summary>
/// 動作テスト
/// </summary>
public static void Test01()
{
	int testCnt = 0;

	while (Console.KeyAvailable == false)
	{
		Console.WriteLine("testCnt: " + (++testCnt));

		Condition cond = MakeCondition(17);
		//Condition cond = MakeCondition(18);
		//Condition cond = MakeCondition(19);
		//Condition cond = MakeCondition(20);

		Item[] ret1 = Solve0001(cond);
		Item[] ret2 = Solve0002(cond);

#if false
		// 最善の組み合わせが複数ある場合、異なる組み合わせを選ぶ可能性がある。

		if (ret1.Length != ret2.Length)
			throw null; // different !!!

#if false
		// 並びが一致するとは限らない。

		if (Enumerable.Range(0, ret1.Length).Any(index => ret1[index] != ret2[index]))
			throw null; // different !!!
#else
		if (ret1.Any(item => ret2.Contains(item) == false))
			throw null; // different !!!
#endif
#else
		if (ret1.Select(item => item.Value).Sum() != ret2.Select(item => item.Value).Sum())
			throw null; // different !!!
#endif
	}
}

/// <summary>
/// 速度テスト
/// </summary>
public static void Test02()
{
	int testCnt = 0;

	while (Console.KeyAvailable == false)
	{
		Console.WriteLine("testCnt: " + (++testCnt));

		Condition cond = MakeCondition(1000);

		DateTime stTm = DateTime.Now;
		Solve0002(cond);
		DateTime edTm = DateTime.Now;

		Console.WriteLine("実行時間 = " + (edTm - stTm).TotalMilliseconds.ToString("F3") + " ミリ秒");
	}
}

// Solve0001() 省略
// Solve0002() 省略

2019-10-18

Brainfuck Interpreter

https://github.com/stackprobe/Annex/blob/master/Hatena/a20191018_Brainfuck/Brainfuck.c

#include "C:\Factory\Common\all.h"

static autoList_t *Memory;
static uint Ptr;

static uint Increment_Ptr(void)
{
	errorCase(Ptr == UINTMAX); // ? Overflow
	Ptr++;
	return 0;
}
static uint Decrement_Ptr(void)
{
	errorCase(!Ptr); // ? Overflow
	Ptr--;
	return 0;
}
static uint Increment(void)
{
//	errorCase(refElement(Memory, Ptr) == UINTMAX); // ? Overflow
	putElement(Memory, Ptr, refElement(Memory, Ptr) + 1);
	return 0;
}
static uint Decrement(void)
{
//	errorCase(!refElement(Memory, Ptr)); // ? Overflow
	putElement(Memory, Ptr, refElement(Memory, Ptr) - 1);
	return 0;
}
static uint PrintChar(void)
{
	uint chr = refElement(Memory, Ptr);

	if(chr == 0x09) // ? Tab
	{
		cout("\t");
	}
	else if(chr == 0x0d || chr == 0x0a) // ? CR || LF
	{
		cout("\n");
	}
	else if(m_isHalf(chr))
	{
		cout("%c", (int)chr);
	}
	else
	{
		cout("[%02x]\n", chr);
	}
	return 0;
}
static uint InputChar(void)
{
	int chr = readChar(stdin);

	if(m_isRange(chr, 0x00, 0xff))
	{
		putElement(Memory, Ptr, (uint)chr);
	}
	else
	{
		cout("[INPUT_ERROR]\n");
	}
	return 0;
}
static uint EnterLoop(void)
{
	return m_01(refElement(Memory, Ptr));
}
static uint End(void)
{
	termination(0);
	return 0; // dummy
}

typedef struct Command_st
{
	uint (*Method)(void);
	struct Command_st *Next[2];
}
Command_t;

static Command_t *MakeCommand(Command_t *p, uint (*method)(void))
{
	Command_t *i = memAlloc(sizeof(Command_t));

	i->Method = method;
	i->Next[0] = NULL;
	i->Next[1] = NULL;

	p->Next[0] = i;

	return i;
}
static Command_t *LoadProgram(char *sourceFile)
{
	char *source = readText_b(sourceFile);
	char *p;
	autoList_t *stack = newList();
	Command_t *command;
	Command_t entry;

	command = &entry;

	for(p = source; *p; p++)
	{
		switch(*p)
		{
		case '>': command = MakeCommand(command, Increment_Ptr); break;
		case '<': command = MakeCommand(command, Decrement_Ptr); break;
		case '+': command = MakeCommand(command, Increment); break;
		case '-': command = MakeCommand(command, Decrement); break;
		case '.': command = MakeCommand(command, PrintChar); break;
		case ',': command = MakeCommand(command, InputChar); break;
		case '[':
			command = MakeCommand(command, EnterLoop);
			addElement(stack, (uint)command);
			break;

		case ']':
			command->Next[0] = (Command_t *)unaddElement(stack);
			command = command->Next[0];
			command->Next[1] = command->Next[0];
			break;

		default:
			break;
		}
	}
	errorCase(getCount(stack));

	MakeCommand(command, End);

	memFree(source);
	releaseAutoList(stack);

	return entry.Next[0];
}
int main(int argc, char **argv)
{
	Command_t *i = LoadProgram(getArg(0)); // g

	Memory = newList();

	for(; ; )
	{
		i = i->Next[i->Method()];
	}
}

　
　
.bf プログラム　https://en.wikipedia.org/wiki/Brainfuck#Hello_World!

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

実行結果

Hello World!

2019-10-18

ビット操作

一番下の立ち上がっているビットを得る

uint LowestBit(uint value)
{
	return value & ~value + 1;
}

// - - -
動作確認用

uint LowestBit_TEST(uint value)
{
	int bit;

	for(bit = 0; bit < 32; bit++)
		if(value & 1u << bit)
			return 1u << bit;

	return 0u;
}

立ち上がっているビットを数える

int GetBitCount(uint value)
{
	value = ((value & 0xaaaaaaaa) >>  1) + (value & 0x55555555);
	value = ((value & 0xcccccccc) >>  2) + (value & 0x33333333);
	value = ((value & 0xf0f0f0f0) >>  4) + (value & 0x0f0f0f0f);
	value = ((value & 0xff00ff00) >>  8) + (value & 0x00ff00ff);
	value = ((value & 0xffff0000) >> 16) + (value & 0x0000ffff);

	return value;
}

0002

int GetBitCount2(uint value)
{
	int count = 0;

	while(value)
	{
		value ^= LowestBit(value);
		count++;
	}
	return count;
}

// - - -
動作確認用

int GetBitCount_TEST(uint value)
{
	int count = 0;
	int bit;

	for(bit = 0; bit < 32; bit++)
		if(value & 1u << bit)
			count++;

	return count;
}

ビット列の並びを反転する

uint ReverseBits(uint value)
{
	value = (value <<  1 & 0xaaaaaaaa) | (value >>  1 & 0x55555555);
	value = (value <<  2 & 0xcccccccc) | (value >>  2 & 0x33333333);
	value = (value <<  4 & 0xf0f0f0f0) | (value >>  4 & 0x0f0f0f0f);
	value = (value <<  8 & 0xff00ff00) | (value >>  8 & 0x00ff00ff);
	value = (value << 16 & 0xffff0000) | (value >> 16 & 0x0000ffff);

	return value;
}

// - - -
動作確認用

uint ReverseBits_TEST(uint value)
{
	uint ret = 0;
	int bit;

	for(bit = 0; bit < 32; bit++)
		if(value & 1u << bit)
			ret |= 1u << 31 - bit;

	return ret;
}

2019-10-16

再帰的探索の再起呼び出(し|さない)

再起呼び出し

// protected bool IsInvalid(int index);        :  0 ～ (index - 1) の element の並びが間違っていれば ture そうでなければ false
// protected bool IsEnd(int index);            :  0 ～ (index - 1) の element の並びで完成していれば true そうでなければ false
// protected void Ended(int count);            :  element の並びが完成したことを通知する。count は element の個数
// protected void ResetElement(int index);     :  index の element を初期化する。次の MoveNextElement によって最初の値に遷移する。
// protected bool MoveNextElement(int index);  :  index の element を次の値に遷移する。次の値が無い場合のみ false を返す。

public virtual void Perform()
{
	this.Search(0);
}

private void Search(int index)
{
	if (this.IsInvalid(index))
		return;

	if (this.IsEnd(index))
	{
		this.Ended(index);
		return;
	}
	this.ResetElement(index);

	while (this.MoveNextElement(index))
	{
		this.Search(index + 1);
	}
}

再起呼び出さない

Search()を再帰的に呼び出さないように変更

public override void Perform()
{
	this.Search();
}

private void Search()
{
	int index = -1;

forward:
	if (this.IsInvalid(++index))
		goto back;

	if (this.IsEnd(index))
	{
		this.Ended(index);
		goto back;
	}
	this.ResetElement(index);

next:
	if (this.MoveNextElement(index))
		goto forward;

back:
	if (0 <= --index)
		goto next;
}

再起呼び出さない_2

-= goto;

public override void Perform()
{
	this.Search();
}

private void Search()
{
	bool forward = true;
	int index = 0;

	for (; ; )
	{
		if (forward)
		{
			if (this.IsInvalid(index))
			{
				forward = false;
			}
			else if (this.IsEnd(index))
			{
				this.Ended(index);
				forward = false;
			}
			else
			{
				this.ResetElement(index);
				forward = this.MoveNextElement(index);
			}
		}
		else
		{
			forward = this.MoveNextElement(index);
		}

		if (forward)
		{
			index++;
		}
		else
		{
			if (index <= 0)
				break;

			index--;
		}
	}
}

2019-10-16

swap (int a, int b)

int a = rand(); // any value
int b = rand(); // any value

// ...

{
	int tmp = a;
	a = b;
	b = tmp;
}

{
	a ^= b;
	b ^= a;
	a ^= b;
}

{
	a -= b;
	b += a;
	a = b - a;
}

{
	a += b;
	b = a - b;
	a -= b;
}

{
	a = b - a;
	b -= a;
	a += b;
}

/*
requires:
	1 <= a &&
	1 <= b &&
	(__int64)a * b <= INT_MAX
*/

{
	a *= b;
	b = a / b;
	a /= b;
}

2019-10-16

FizzBuzzいろいろ

t0001.c

#include <stdio.h>

int main()
{
	int n;

	for(n = 1; n <= 100; n++)
	{
		if(n % 15 == 0)
			printf("FizzBuzz\n");
		else if(n % 3 == 0)
			printf("Fizz\n");
		else if(n % 5 == 0)
			printf("Buzz\n");
		else
			printf("%d\n", n);
	}
}

t0002.c

#include <stdio.h>

int main()
{
	int n;

	for(n = 1; n <= 100; n++)
	{
		int f = 1;

		if(n % 3 == 0)
		{
			printf("Fizz");
			f = 0;
		}
		if(n % 5 == 0)
		{
			printf("Buzz");
			f = 0;
		}
		if(f)
			printf("%d", n);

		printf("\n");
	}
}

t0003.c

#include <stdio.h>

#define FIZZU 3
#define BUZZU 5

int main()
{
	int n;

	for(n = 1; n <= 100; n++)
	{
		if(n % FIZZU == 0)
		{
			if(n % BUZZU == 0)
				printf("FizzBuzz\n");
			else
				printf("Fizz\n");
		}
		else if(n % BUZZU == 0)
			printf("Buzz\n");
		else
			printf("%d\n", n);
	}
}

t0004.c

#include <stdio.h>

int main()
{
	char *fmts[] =
	{
		"%d\n",
		"Fizz\n",
		"Buzz\n",
		"FizzBuzz\n"
	};
	int n;

	for(n = 1; n <= 100; n++)
	{
		printf(fmts["300102100120100"[n % 15] - '0'], n);
	}
}

t0005.c

#include <stdio.h>

int main()
{
	int n;

	for(n = 1; n <= 100; n++)
	{
		printf("%d\n\0Fizz\n\0______FizzBuzz\n" + (n % 3 + 1 >> 1 ^ 1 ^ ((n % 5 + 3 >> 2 ^ 1) * 5)) * 4, n);
	}
}

t1001.cs

Enumerable.Range(1, 100)
	.Select(v => new { n = v, s = "" })
	.Select(v => v.n % 3 == 0 ? new { n = v.n, s = v.s + "FIZZ" } : v)
	.Select(v => v.n % 5 == 0 ? new { n = v.n, s = v.s + "BUZZ" } : v)
	.Select(v => v.s == "" ? "" + v.n : v.s)
	.ToList()
	.ForEach(v => Console.WriteLine(v));

stackprobe7s_memo

何処にも披露する見込みの無いものを書き落とす場所

名前付きイベントだけを使ってプロセス間通信を行う(C#)

説明

特徴

仕様

使い方

サーバー側 (受信側)

クライアント側 (送信側)

デモ・プログラム

ナップサック問題(C#)

入力

Solve0001

総当りで解く

Solve0002

動的計画法？で解く

Extra

テスト用コード

Brainfuck Interpreter

ビット操作

一番下の立ち上がっているビットを得る

立ち上がっているビットを数える

0002

ビット列の並びを反転する

再帰的探索の再起呼び出(し|さない)

再起呼び出し

再起呼び出さない

再起呼び出さない_2

swap (int a, int b)

FizzBuzzいろいろ

t0001.c

t0002.c

t0003.c

t0004.c

t0005.c

t1001.cs