続 C# は高級アセンブラ

C# は高級アセンブラの続きです。
何とかして高速化しようと思い試してみました。まずはボツ案から。

	<#@ template debug="false" hostspecific="true" language="C#" #>
	<#@ assembly name="System.Core" #>
	<#@ import namespace="System.IO" #>
	<#@ import namespace="System.Linq" #>
	<#@ output extension=".cs" #>
	using System.Reflection;
	class UnsafePoh {
	static readonly byte[] bytes = new byte[]{
	<#= string.Join(Environment.NewLine, File.ReadAllBytes(Host.ResolvePath("Unsafe.dll")).Select((b, i) => new { b, i }).GroupBy(a => a.i / 16, a => string.Format("0x{0:X2}, ", a.b), (_, g) => string.Concat(g))) #>
	};
	static void Main() {
	Assembly.Load(bytes).GetType("Unsafe").InvokeMember("Main", BindingFlags.Public|BindingFlags.Static|BindingFlags.InvokeMethod, null, null, null);
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub

あ、はい、ごめんなさい。

---

時計屋さんからこのようなヒントを頂きました。

@haxe メモリが余裕ありそうなので、バケツぶっかけてどーなるか今から試してみよっかなって
— 時計屋 (@NetSeed) December 7, 2013

@haxe ソート自体をO(n)で完了してるんですが、逆に定数が若干多めって言うかなんていうか。。。その辺が問題じゃないかなって
— 時計屋 (@NetSeed) December 7, 2013

これを元にソート方法を見直し…というよりソート行為がほぼ不要になったためについでにzero copyも取り入れたところ、逆にコードがキレイになってしまいました。

	using System;
	static class CsPoh {
	static int Calculate(byte[] input, byte[] prices, byte[] output) {
	int ii = 0, temp, oi = 0, price;
	var itemCount = 0;
	while ((temp = input[ii++] - '0') >= 0)
	itemCount = itemCount * 10 + temp;
	var days = 0;
	while ((temp = input[ii++] - '0') >= 0)
	days = days * 10 + temp;
	while (--itemCount >= 0) {
	price = 0;
	while ((temp = input[ii++] - '0') >= 0)
	price = price * 10 + temp;
	prices[price] = 1;
	}
	var low0 = 10;
	while (prices[low0] == 0)
	low0++;
	while (--days >= 0) {
	var targetPrice = 0;
	while ((temp = input[ii++] - '0') >= 0)
	targetPrice = targetPrice * 10 + temp;
	price = 0;
	/* TODO: 同一価格商品２つにはならない模様
	if (targetPrice % 2 == 0 && prices[targetPrice / 2] > 1)
	price = targetPrice;
	else */ {
	var low = low0;
	var high = targetPrice - low;
	while (prices[high] == 0)
	high--;
	do {
	temp = low + high;
	if (temp == targetPrice) {
	price = temp;
	break;
	}
	if (temp < targetPrice) {
	if (price < temp)
	price = temp;
	while (prices[++low] == 0)
	;
	} else
	while (prices[--high] == 0)
	;
	} while (low < high);
	}
	#if true
	/* TODO: 商品は必ず見つかり 0 にならない模様
	if (price == 0)
	output[oi++] = (byte)'0';
	else */ {
	temp = 100000 <= price ? 1000000 <= price ? 1000000
	: 100000
	: 10000 <= price ? 10000
	: 1000 <= price ? 1000
	: 100 <= price ? 100
	: 10;
	do {
	output[oi++] = (byte)('0' + price / temp);
	price %= temp;
	temp /= 10;
	} while (temp > 1);
	output[oi++] = (byte)('0' + price);
	}
	#else
	if (100000 <= price) {
	if ((temp = price / 1000000) > 0) {
	output[oi++] = (byte)('0' + temp); price %= 1000000;
	}
	output[oi++] = (byte)('0' + price / 100000); price %= 100000;
	output[oi++] = (byte)('0' + price / 10000); price %= 10000;
	output[oi++] = (byte)('0' + price / 1000); price %= 1000;
	output[oi++] = (byte)('0' + price / 100); price %= 100;
	output[oi++] = (byte)('0' + price / 10); price %= 10;
	} else if ((temp = price / 10000) > 0) {
	output[oi++] = (byte)('0' + temp); price %= 10000;
	output[oi++] = (byte)('0' + price / 1000); price %= 1000;
	output[oi++] = (byte)('0' + price / 100); price %= 100;
	output[oi++] = (byte)('0' + price / 10); price %= 10;
	} else if ((temp = price / 1000) > 0) {
	output[oi++] = (byte)('0' + temp); price %= 1000;
	output[oi++] = (byte)('0' + price / 100); price %= 100;
	output[oi++] = (byte)('0' + price / 10); price %= 10;
	} else if ((temp = price / 100) > 0) {
	output[oi++] = (byte)('0' + temp); price %= 100;
	output[oi++] = (byte)('0' + price / 10); price %= 10;
	} else if ((temp = price / 10) > 0) {
	output[oi++] = (byte)('0' + temp); price %= 10;
	}
	output[oi++] = (byte)('0' + price);
	#endif
	output[oi++] = 10;
	}
	return oi;
	}
	static void Main() {
	const int valueLength = 2 + 200000 + 75;
	var input = new byte[valueLength * 7];
	Console.OpenStandardInput().Read(input, 0, valueLength * 7);
	var output = new byte[75 * 7];
	Console.OpenStandardOutput().Write(output, 0, Calculate(input, new byte[1000001], output));
	}
	}

view raw CsPoh.cs hosted with ❤ by GitHub

スコアも上々で、0.02 / 0.02 / 0.03となりました。

---

更に続きを書きました。続続 C は高級アセンブラ