如何加速37倍

连续投硬币一千次，连续出现10次正面或反面的概率 §

如果不考虑使用数学解法，通过程序暴力解题
首先的解题思路是贴近原文：
随机生成1000个1或0存到长度1000的数组中，然后再从前到后从数组中取出10个数和10个0与10个1的数组进行对比是否相同，如果其中一个相同就代表出现了这个结果，再将这个过程重复很多次查看这个结果占所有结果的比例

private readonly int _rollCount = 1_000;  
  
[Benchmark]
public void Loop1()
{
	int matchCount = 0;
	int[] lz = Enumerable.Repeat(1, 10).ToArray();
	int[] ll = Enumerable.Repeat(0, 10).ToArray();
	int[] lt = new int[1000];
	for (int i = 0; i < _rollCount; i++)
	{
		for (int j = 0; j < 1000; j++)
		{
			lt[j] = Random.Shared.Next(0, 2);
		}

		if (ContainsSubArray(lt, lz) || ContainsSubArray(lt, ll))
			matchCount++;
	}
	
	Console.WriteLine((double)matchCount/_rollCount*100 + "%");
}

static bool ContainsSubArray(int[] mainArray, int[] subArray)
{
	if (subArray.Length == 0 || subArray.Length > mainArray.Length)
		return false;

	for (int i = 0; i <= mainArray.Length - subArray.Length; i++)
	{
		if (mainArray.Skip(i).Take(subArray.Length).SequenceEqual(subArray))
			return true;
	}

	return false;
}

耗时：38.706 ms 😀

我们很容易可以看出优化思路，因为每次的投掷都是独立事件，所以就算是并行运算也不影响结果，我们可以并行化for循环，使用多核处理器

private readonly int _rollCount = 1_000;  

[Benchmark]
public void Loop2()
{
	int matchCount = 0;
	int[] lz = Enumerable.Repeat(1, 10).ToArray();
	int[] ll = Enumerable.Repeat(0, 10).ToArray();
	int[] lt = new int[1000];
	Parallel.For(0, _rollCount, _ =>
	{
		for (int j = 0; j < 1000; j++)
		{
			lt[j] = Random.Shared.Next(0, 2);
		}

		if (ContainsSubArray(lt, lz) || ContainsSubArray(lt, ll))
			matchCount++;
	});

	Console.WriteLine((double)matchCount/_rollCount*100 + "%");
}

耗时：20.083 ms 😉

使用数组对比因为涉及装箱所以非常耗时，我们可以通过使用字符串拼接的方法将1000个0或1拼接在一起再使用contain判断是否含有10个1或0的字符串即可，不仅更快速而且代码也更简单

private readonly string _lzstr = "1111111111";  
private readonly string _llstr = "0000000000";  
private readonly int _rollCount = 1_000;

[Benchmark]
public void Loop3()
{
	int matchCount = 0;
	Parallel.For(0, _rollCount, _ =>
	{
		string lt = "";
		for (int i = 0; i < 1000; i++)
		{
			lt += Random.Shared.Next(0, 2);
		}

		if (lt.Contains(_lzstr) || lt.Contains(_llstr))
			matchCount++;
	});
	
	Console.WriteLine((double)matchCount/_rollCount*100 + "%");
}

耗时：73.133 ms 😯

为什么优化的耗时更长了呢，String的拼接实际上非常耗时，我们改成StringBuilder呢

private readonly string _lzstr = "1111111111";  
private readonly string _llstr = "0000000000";  
private readonly int _rollCount = 1_000;

[Benchmark]
public void Loop4()
{
	int matchCount = 0;
	Parallel.For(0, _rollCount, _ =>
	{
		StringBuilder sb = new StringBuilder(1000);
		for (int i = 0; i < 1000; i++)
		{
			sb.Append(Random.Shared.Next(0, 2));
		}

		string lt = sb.ToString();
		if (lt.Contains(_lzstr) || lt.Contains(_llstr))
			matchCount++;
	});
	
	Console.WriteLine((double)matchCount/_rollCount*100 + "%");
}

耗时：1.884 ms 🤗

在不涉及GC以及unsafe代码下，我们还能更快吗？
答案是可以
我们知道二进制数每一位都是0或1，这和我们构造的字符串十分相似，那我们只需要每次都随机构造一个很长的二进制数，然后再查看其内部是否含有10个连续的0或1不就可以了。当然我们的前提是每一位出现0或1的概率都是相等的，那我们的随机二进制数应该是从000…000~111…111这样的范围，这样每位都可能表示两个数字，所以概率是一致的，将其转化成十进制数后也是一一对应，我们只需要在十进制数的0到最大二进制数的十进制数之间随机取数即可，因为int最大表示31位二进制数，我们每次构造25位的二进制数，重复40次即可构造出1000位的二进制数

private readonly string _lzstr = "1111111111";  
private readonly string _llstr = "0000000000";  
private readonly int _base2end = 0B1111111111111111111111111;  
private readonly int _rollCount = 1_000;
  
[Benchmark(Baseline = true)]
public void Loop5()
{
	int matchCount = 0;
	Parallel.For(0, _rollCount, _ =>
	{
		StringBuilder sb = new StringBuilder(1000);
		for (int i = 0; i < 40; i++)
		{
			sb.Append(Convert.ToString(Random.Shared.Next(0, _end), 2).PadLeft(25, '0'));
		}

		string lt = sb.ToString();
		if (lt.Contains(_lzstr) || lt.Contains(_llstr))
			matchCount++;
	});
	
	Console.WriteLine((double)matchCount/_rollCount*100 + "%");
}

耗时：1.047 ms 🤩

全体跑分：

我们从Loop1到Loop5加速了37倍！