using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Linq.Expressions;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace MSTestCustomAssertion
{
public class ExpressionAssert
{
public static void IsTrue(Expression<Func<bool>> expr)
{
var result = expr.Compile().Invoke();
if (!result)
throw new FailedException("ExpressionAssert.IsTrue failed");
}
public class FailedException : AssertFailedException
{
public FailedException() : base() { }
public FailedException(string msg) : base(msg) { }
public override string StackTrace
{
get
{
var lines = base.StackTrace.Split(new string[] { Environment.NewLine, }, StringSplitOptions.None);
var index = Array.FindIndex(lines, x => !x.Contains("ExpressionAssert."));
var st = string.Join(Environment.NewLine, lines, index, lines.Length - index);
return st;
}
}
}
}
}
ksksts / junk / source — bitbucket.org
array: 662 (1.00) (IList<T>)array: 6259 (9.45) list: 1325 (2.00) (IList<T>)list: 1592 (2.40) IListArrayWrapper: 1166 (1.76)ksksts / junk / source — bitbucket.org
public class IListArrayWrapper<T> where T : struct
{
public T[] Source { get; set; }
unsafe public T this[int index]
{
get
{
fixed (T* p = &Source[0])
return *(p + index);
}
set
{
fixed (T* p = &Source[0])
*(p + index) = value;
}
}
public IListArrayWrapper(IList<T> source)
{
Source = (T[])source;
}
}
ksksts / junk / source — bitbucket.orgsize: 1000 Array.Sort: 1186 (1.00) List.Sort: 1050 (0.89) Array.OrderBy: 6592 (5.56) List.OrderBy: 3305 (2.78) CombSort Array: 31971 (26.94) CombSort List: 6909 (5.82) NumberRadixSorter.Sort Array: 4943 (4.17) NumberRadixSorter.Sort List: 2291 (1.93) InPlaceMergeSorter.Sort Array: 40326 (33.98) InPlaceMergeSorter.Sort List: 12642 (10.65) MergeSorter.Sort Array: 24463 (20.61) MergeSorter.Sort List: 9604 (8.09) IntroSorter.Sort Array: 22909 (19.30) IntroSorter.Sort List: 4158 (3.50) size: 10000 Array.Sort: 12771 (1.00) List.Sort: 12497 (0.98) Array.OrderBy: 41599 (3.26) List.OrderBy: 41126 (3.22) CombSort Array: 465802 (36.47) CombSort List: 101879 (7.98) NumberRadixSorter.Sort Array: 27803 (2.18) NumberRadixSorter.Sort List: 22234 (1.74) InPlaceMergeSorter.Sort Array: 553976 (43.38) InPlaceMergeSorter.Sort List: 202408 (15.85) MergeSorter.Sort Array: 224039 (17.54) MergeSorter.Sort List: 128939 (10.10) IntroSorter.Sort Array: 158357 (12.40) IntroSorter.Sort List: 52881 (4.14) size: 100000 Array.Sort: 146888 (1.00) List.Sort: 145938 (0.99) Array.OrderBy: 520984 (3.55) List.OrderBy: 518649 (3.53) CombSort Array: 6044506 (41.15) CombSort List: 1311650 (8.93) NumberRadixSorter.Sort Array: 279857 (1.91) NumberRadixSorter.Sort List: 218608 (1.49) InPlaceMergeSorter.Sort Array: 8215845 (55.93) InPlaceMergeSorter.Sort List: 2860999 (19.48) MergeSorter.Sort Array: 2931658 (19.96) MergeSorter.Sort List: 1869126 (12.72) IntroSorter.Sort Array: 1945971 (13.25) IntroSorter.Sort List: 658093 (4.48) size: 1000000 Array.Sort: 1666666 (1.00) List.Sort: 1668472 (1.00) Array.OrderBy: 6961424 (4.18) List.OrderBy: 6901036 (4.14) CombSort Array: 76084478 (45.65) CombSort List: 16674472 (10.00) NumberRadixSorter.Sort Array: 2864637 (1.72) NumberRadixSorter.Sort List: 2245710 (1.35) InPlaceMergeSorter.Sort Array: 110817348 (66.49) InPlaceMergeSorter.Sort List: 38880094 (23.33) MergeSorter.Sort Array: 35271234 (21.16) MergeSorter.Sort List: 20756358 (12.45) IntroSorter.Sort Array: 24093398 (14.46) IntroSorter.Sort List: 8047601 (4.83)ksksts / junk / source — bitbucket.org
size: 1000 IntroSorter.Sort: 20622 (18.78) Array.Sort: 1098 (1.00) size: 10000 IntroSorter.Sort: 139073 (10.98) Array.Sort: 12667 (1.00) size: 100000 IntroSorter.Sort: 1771360 (12.22) Array.Sort: 144995 (1.00) size: 1000000 IntroSorter.Sort: 21275858 (12.85) Array.Sort: 1656005 (1.00)ksksts / junk / source — bitbucket.org
size: 1000 InPlaceMergeSorter.Sort: 37314 (33.24) MergeSorter.Sort: 21869 (19.48) Array.Sort: 1122 (1.00) size: 10000 InPlaceMergeSorter.Sort: 502465 (39.24) MergeSorter.Sort: 198861 (15.53) Array.Sort: 12805 (1.00) size: 100000 InPlaceMergeSorter.Sort: 7425488 (47.00) MergeSorter.Sort: 2556782 (16.18) Array.Sort: 157988 (1.00) size: 1000000 InPlaceMergeSorter.Sort: 98928451 (58.09) MergeSorter.Sort: 31298754 (18.38) Array.Sort: 1703143 (1.00)ksksts / junk / source — bitbucket.org
size: 1000 merge sort: 37580 (30.34) Array.Sort: 1238 (1.00) size: 10000 merge sort: 506318 (41.50) Array.Sort: 12199 (1.00) size: 100000 merge sort: 7170923 (50.21) Array.Sort: 142813 (1.00) size: 1000000 merge sort: 97304833 (60.94) Array.Sort: 1596662 (1.00)ksksts / junk / source — bitbucket.org
public static void Sort<T>(IList<T> list, Func<T, UInt32> converter, SortOrder sortOrder)
struct Pair<TFirst, TSecond>
{
public TFirst First { get; set; }
public TSecond Second { get; set; }
}
このPair型に対して、RadixSorter.Sort(result, x => x.Second, RadixSorter.SortOrder.Ascending); RadixSorter.Sort(result, x => x.First, RadixSorter.SortOrder.Ascending);とすると、次のCompareTo（Firstで比較＆Firstが等しい場合はSecondで比較）でソートした場合と同じ結果が得られる。
public int CompareTo(Pair<TFirst, TSecond> x)
{
var result = First.CompareTo(x.First);
if (result == 0)
result = Second.CompareTo(x.Second);
return result;
}
// histgramming
var histgramOffset = ascending ? 1 : -1;
foreach (var x in list)
{
var y = x;
for (var p = 0; p < tables.Length; p++)
{
tables[p][(y + histgramOffset) & 0xFF]++;
y = y >> 8;
}
}
// sum the histgrams
if (ascending)
{
foreach (var table in tables)
{
table[0] = 0;
for (var n = 1; n < table.Length; n++)
table[n] += table[n - 1];
}
}
else
{
foreach (var table in tables)
{
table[0xFF] = 0;
for (var n = 0xFE; n >= 0x00; n--)
table[n] += table[n + 1];
}
}
// sum the histgrams
if (ascending)
{
for (var p = 0; p < tables.Length - 1; p++)
{
var table = tables[p];
table[0] = 0;
for (var n = 1; n < table.Length; n++)
table[n] += table[n - 1];
}
{
var table = tables[tables.Length - 1];
table[0x80] = 0;
for (var n = 0x81; n <= 0xFF; n++)
table[n] += table[n - 1];
table[0x00] += table[0xFF];
for (var n = 0x01; n < 0x80; n++)
table[n] += table[n - 1];
}
}
else
{
for (var p = 0; p < tables.Length - 1; p++)
{
var table = tables[p];
table[0xFF] = 0;
for (var n = 0xFE; n >= 0x00; n--)
table[n] += table[n + 1];
}
{
var table = tables[tables.Length - 1];
table[0x7F] = 0;
for (var n = 0x7E; n >= 0x00; n--)
table[n] += table[n + 1];
table[0xFF] += table[0x00];
for (var n = 0xFE; n >= 0x80; n--)
table[n] += table[n + 1];
}
}
// histgramming
var histgramOffset = ascending ? 1 : -1;
for (var n = 0; n < list.Count; n++)
{
var y = BitConverter.DoubleToInt64Bits(list[n]);
y ^= -(Int64)((UInt64)y >> 63) | unchecked((Int64)0x8000000000000000); // flip
list[n] = BitConverter.Int64BitsToDouble(y);
for (var p = 0; p < tables.Length; p++)
{
tables[p][(y + histgramOffset) & 0xFF]++;
y = y >> 8;
}
}
// read/write histgram, copy
IList<Double> array = new Double[list.Count];
Action swap = () => { var temp = list; list = array; array = temp; };
for (var p = 0; p < tables.Length - 1; p++)
{
var table = tables[p];
foreach (var x in list)
{
var y = BitConverter.DoubleToInt64Bits(x);
y = (y >> p * 8) & 0xFF;
array[table[y]] = x;
table[y]++;
}
swap();
}
{
var p = tables.Length - 1;
var table = tables[p];
foreach (var x in list)
{
var w = BitConverter.DoubleToInt64Bits(x);
var y = (w >> p * 8) & 0xFF;
w ^= (Int64)((UInt64)w >> 63) - 1 | unchecked((Int64)0x8000000000000000); // flip back
array[table[y]] = BitConverter.Int64BitsToDouble(w);
table[y]++;
}
swap();
}
Decimal 数値のバイナリ表現は、1 ビットの符号、96 ビットの整数、および整数値を除算し、小数部を指定するために使用するスケール ファクタから構成されます。スケール ファクタは黙示的に数値 10 になり、0 から 28 の範囲の指数で累乗されます。Decimal.GetBits メソッドの戻り値はint[]でいまいち分かりにくいから確認用のコードを書いた（下手なコードだと思うけど良い方法を思いつけなかった）。
戻り値は、4 要素の 32 ビット符号付き整数配列です。
この配列の 1 ～ 3 番目の要素は、96 ビット整数の下位 32 ビット、中位 32 ビット、および上位 32 ビットをそれぞれ格納しています。
4 番目の要素は、スケール ファクタと符号を格納しています。この要素は、次に示す部分から構成されています。
ビット 0 ～ 15 の下位ワードは未使用で、0 である必要があります。
ビット 16 ～ 23 には、0 から 28 までの範囲の指数部を格納する必要があります。この指数部は、整数を除算する 10 の累乗を示します。
ビット 24 ～ 30 は未使用で、0 である必要があります。
ビット 31 は符号を格納している必要があります。0 は正、1 は負を表します。
ビット形式では負の 0 と正の 0 が区別されます。これらの値はすべての演算で等値として扱われます。
unsafe private static void PrintDecimal()
{
Func<Decimal, byte[]> toBytes = x =>
{
var p = (byte*)&x;
var bytes = new byte[sizeof(Decimal)];
for (var n = 0; n < bytes.Length; n++)
bytes[n] = *p++;
return bytes;
};
WriteLine("Decimal:");
WriteLine("0.0M", toBytes(0.0M));
WriteLine("-0.0M", toBytes(-0.0M));
WriteLine("0.12M", toBytes(0.12M));
WriteLine("1.2M ", toBytes(1.2M));
WriteLine("12M ", toBytes(12M));
WriteLine("120M ", toBytes(120M));
WriteLine("1200M", toBytes(1200M));
WriteLine("-0.12M", toBytes(-0.12M));
WriteLine("-1.2M ", toBytes(-1.2M));
WriteLine("-12M ", toBytes(-12M));
WriteLine("-120M ", toBytes(-120M));
WriteLine("-1200M", toBytes(-1200M));
WriteLine("Decimal.MinValue", toBytes(Decimal.MinValue));
WriteLine("Decimal.MaxValue", toBytes(Decimal.MaxValue));
WriteLine("");
}
private static void WriteLine(string value)
{
Console.WriteLine(value);
}
private static void WriteLine(string label, byte[] bytes)
{
Console.Write("{0}: 0x", label);
var bs = (byte[])bytes.Clone();
Array.Reverse(bs);
foreach (var x in bs)
Console.Write("{0:X2}", x);
Console.WriteLine();
}
ksksts / junk / source — bitbucket.orgDecimal: 0.0M: 0x00000000000000000000000000010000 -0.0M: 0x00000000000000000000000080010000 0.12M: 0x000000000000000C0000000000020000 1.2M : 0x000000000000000C0000000000010000 12M : 0x000000000000000C0000000000000000 120M : 0x00000000000000780000000000000000 1200M: 0x00000000000004B00000000000000000 -0.12M: 0x000000000000000C0000000080020000 -1.2M : 0x000000000000000C0000000080010000 -12M : 0x000000000000000C0000000080000000 -120M : 0x00000000000000780000000080000000 -1200M: 0x00000000000004B00000000080000000 Decimal.MinValue: 0xFFFFFFFFFFFFFFFFFFFFFFFF80000000 Decimal.MaxValue: 0xFFFFFFFFFFFFFFFFFFFFFFFF00000000
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
namespace IListEnumerationBenchmark
{
class Program
{
static void Main(string[] args)
{
var size = 1000000;
var count = 10;
var sw = new Stopwatch();
Action<IList<int>> run = list =>
{
var useIndexerTicks = 0L;
var useEnumeratorTicks = 0L;
var useForeachTicks = 0L;
for (var c = 0; c < count; c++)
{
var random = new Random(c);
for (var n = 0; n < list.Count; n++)
list[n] = random.Next(int.MinValue, int.MaxValue);
// use indexer
sw.Reset();
sw.Start();
var useIndexerResult = UseIndexer(list);
sw.Stop();
useIndexerTicks += sw.ElapsedTicks;
// use enumerator
sw.Reset();
sw.Start();
var useEnumeratorResult = UseEnumerator(list);
sw.Stop();
useEnumeratorTicks += sw.ElapsedTicks;
// use foreach
sw.Reset();
sw.Start();
var useForeachResult = UseForeach(list);
sw.Stop();
useForeachTicks += sw.ElapsedTicks;
// correctness
if (useIndexerResult != useForeachResult)
Console.WriteLine("useIndexerResult: {0}, useForeachResult: {1}", useIndexerResult, useForeachResult);
if (useEnumeratorResult != useForeachResult)
Console.WriteLine("useEnumeratorResult: {0}, useForeachResult: {1}", useEnumeratorResult, useForeachResult);
}
Console.WriteLine("use indexer: {0} ({1:F})", useIndexerTicks / count, useIndexerTicks / (double)useForeachTicks);
Console.WriteLine("use enumerator: {0} ({1:F})", useEnumeratorTicks / count, useEnumeratorTicks / (double)useForeachTicks);
Console.WriteLine("use foreach: {0} ({1:F})", useForeachTicks / count, useForeachTicks / (double)useForeachTicks);
Console.WriteLine();
};
// int[]
{
Console.WriteLine("int[]: ");
var array = new int[size];
run(array);
}
// List<int>
{
Console.WriteLine("List<int>: ");
var list = new List<int>();
for (var n = 0; n < size; n++)
list.Add(0);
run(list);
}
}
static int UseIndexer(IList<int> list)
{
var result = 0;
for (var n = 0; n < list.Count; n++)
result = unchecked(result + list[n]);
return result;
}
static int UseEnumerator(IList<int> list)
{
var result = 0;
var e = list.GetEnumerator();
while (e.MoveNext())
result = unchecked(result + e.Current);
return result;
}
static int UseForeach(IList<int> list)
{
var result = 0;
foreach (var x in list)
result = unchecked(result + x);
return result;
}
}
}
ksksts / junk / source — bitbucket.orgint[]: use indexer: 578500 (5.57) use enumerator: 87133 (0.84) use foreach: 103895 (1.00) List<int>: use indexer: 132922 (0.76) use enumerator: 154705 (0.89) use foreach: 174277 (1.00)追記: 上の結果はIList<T>を通した結果だから不正確。ksksts's blog: 配列やList<T>をIList<T>型のインデクサでアクセスするとパフォーマンスが悪い(don't use IList<T>'s indexer)を参照。
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
namespace SortBenchmark
{
class Program
{
static void Main(string[] args)
{
for (var size = 1000; size <= 1000000; size *= 10)
Run(size);
}
static void Run(int size)
{
Console.WriteLine("size: {0}", size);
var count = 10;
var sw = new Stopwatch();
var radixSortTicks = 0L;
var combSortTicks = 0L;
var arraySortTicks = 0L;
for (var c = 0; c < count; c++)
{
var random = new Random(c);
var list = new UInt32[size];
for (var n = 0; n < list.Length; n++)
list[n] = (UInt32)random.Next(Int32.MinValue, Int32.MaxValue);
// radix sort
var radixSortResult = (IList<UInt32>)list.Clone();
sw.Reset();
sw.Start();
RadixSort(radixSortResult);
sw.Stop();
radixSortTicks += sw.ElapsedTicks;
// comb sort
var combSortResult = (IList<UInt32>)list.Clone();
sw.Reset();
sw.Start();
CombSort(combSortResult);
sw.Stop();
combSortTicks += sw.ElapsedTicks;
// Array.Sort
var arraySortResult = list.ToArray();
sw.Reset();
sw.Start();
Array.Sort(arraySortResult);
sw.Stop();
arraySortTicks += sw.ElapsedTicks;
// correctness
for (var n = 0; n < size; n++)
{
if (radixSortResult[n] != arraySortResult[n])
Console.WriteLine("radixSortResult[{0}]: {1}, arraySortResult[{0}]: {2}", n, radixSortResult[n], arraySortResult[n]);
if (combSortResult[n] != arraySortResult[n])
Console.WriteLine("combSortResult[{0}]: {1}, arraySortResult[{0}]: {2}", n, combSortResult[n], arraySortResult[n]);
}
}
Console.WriteLine("radix sort: {0} ({1:F})", radixSortTicks / count, radixSortTicks / (double)arraySortTicks);
Console.WriteLine("comb sort: {0} ({1:F})", combSortTicks / count, combSortTicks / (double)arraySortTicks);
Console.WriteLine("Array.Sort: {0} ({1:F})", arraySortTicks / count, arraySortTicks / (double)arraySortTicks);
}
static void RadixSort(IList<UInt32> list)
{
var tables = new int[sizeof(UInt32)][];
for (var p = 0; p < tables.Length; p++)
tables[p] = new int[0xFF + 1];
// histgramming
foreach (var x in list)
{
var y = x;
for (var p = 0; p < tables.Length; p++)
{
tables[p][(y + 1) & 0xFF]++;
y = y >> 8;
}
}
// sum the histgrams
foreach (var table in tables)
{
table[0] = 0;
for (var n = 1; n < table.Length; n++)
table[n] += table[n - 1];
}
// read/write histgram, copy
IList<UInt32> array = new UInt32[list.Count];
Action swap = () => { var temp = list; list = array; array = temp; };
for (var p = 0; p < tables.Length; p++)
{
var table = tables[p];
foreach (var x in list)
{
var y = (x >> p * 8) & 0xFF;
array[table[y]] = x;
table[y]++;
}
swap();
}
}
static void CombSort(IList<UInt32> list)
{
const double shrinkFactor = 1.247330950103979; // 1.0 / (1.0 - 1.0 / Math.Pow(Math.E, Math.PI));
var gap = list.Count;
var swapped = true;
while (gap > 1 || swapped)
{
if (gap > 1)
gap = (int)(gap / shrinkFactor);
swapped = false;
for (int i = 0; i + gap < list.Count; i++)
{
if (list[i].CompareTo(list[i + gap]) > 0)
{
var t = list[i];
list[i] = list[i + gap];
list[i + gap] = t;
swapped = true;
}
}
}
}
}
}
ksksts / junk / source — bitbucket.orgsize: 1000 radix sort: 3541 (2.88) comb sort: 27689 (22.50) Array.Sort: 1230 (1.00) size: 10000 radix sort: 20451 (1.68) comb sort: 417744 (34.33) Array.Sort: 12167 (1.00) size: 100000 radix sort: 207950 (1.45) comb sort: 5288921 (36.95) Array.Sort: 143143 (1.00) size: 1000000 radix sort: 2081360 (1.30) comb sort: 65056745 (40.50) Array.Sort: 1606207 (1.00)
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
namespace BinaryRepresentation
{
class Program
{
static void Main(string[] args)
{
var sw = new Stopwatch();
var random = new Random(0);
var num = 1000000;
var vals = new double[num];
for (var n = 0; n < vals.Length; n++)
vals[n] = random.NextDouble();
// BitConverter.DoubleToInt64Bits
var bc = new long[vals.Length];
{
sw.Reset();
sw.Start();
for (var n = 0; n < vals.Length; n++)
bc[n] = BitConverter.DoubleToInt64Bits(vals[n]);
sw.Stop();
Console.WriteLine("BitConverter.DoubleToInt64Bits: {0}", sw.ElapsedMilliseconds);
}
// unsafe cast
var uc = new long[vals.Length];
unsafe
{
sw.Reset();
sw.Start();
for (var n = 0; n < vals.Length; n++)
{
var val = vals[n];
uc[n] = *(long*)&val;
}
sw.Stop();
Console.WriteLine("unsafe cast: {0}", sw.ElapsedMilliseconds);
}
// correctness
for (var n = 0; n < vals.Length; n++)
if (bc[n] != uc[n])
Console.WriteLine("bc[{0}]: {1:X}, uc[{0}]: {2:X}", n, bc[n], uc[n]);
}
}
}
ksksts / junk / source — bitbucket.org
class Voila {
public:
// Voila
static const string VOILA = "Voila";
// will not interfere with embedded tags.
}
