Skip to content

Instantly share code, notes, and snippets.

@ZacharyPatten
Last active December 3, 2019 21:00
Show Gist options
  • Save ZacharyPatten/b5452ae95cb3a2b09ccc2d39e122d5a5 to your computer and use it in GitHub Desktop.
Save ZacharyPatten/b5452ae95cb3a2b09ccc2d39e122d5a5 to your computer and use it in GitHub Desktop.
Temporary algorithm checker.
using System;
using System.Linq;
using System.Collections.Generic;
namespace ConsoleCoreSandbox
{
class Program
{
static void Main()
{
var zpProbs = CalculateProbabilities(RandomUniqueInts);
Console.WriteLine(nameof(zpProbs));
PrintPriorities(zpProbs);
Console.WriteLine();
var zpProbs2 = CalculateProbabilities(RandomUniqueInts2);
Console.WriteLine(nameof(zpProbs2));
PrintPriorities(zpProbs2);
Console.WriteLine();
var zpProbs3 = CalculateProbabilities(RandomUniqueInts3);
Console.WriteLine(nameof(zpProbs3));
PrintPriorities(zpProbs3);
Console.WriteLine();
var zpProbs4 = CalculateProbabilities(RandomUniqueInts4);
Console.WriteLine(nameof(zpProbs4));
PrintPriorities(zpProbs4);
Console.WriteLine();
var listProbs = CalculateProbabilities(RandomUniqueIntsList);
Console.WriteLine(nameof(listProbs));
PrintPriorities(listProbs);
Console.WriteLine();
}
internal static void PrintPriorities(Dictionary<int, double> results)
{
foreach (var keyVal in results.OrderBy(x => x.Key))
Console.WriteLine(keyVal.Key + ": " + keyVal.Value);
}
internal static Dictionary<int, double> CalculateProbabilities(Func<int, Range, IEnumerable<int>> algorithm)
{
const int size = 5;
const int min = 0;
const int max = 26;
const int iterations = 1000000;
var counts = new Dictionary<int, int>();
for (int i = min; i < max; i++)
counts.Add(i, 0);
for (int i = 0; i < iterations; i++)
foreach (int random in algorithm(size, min..max))
counts[random]++;
var results = new Dictionary<int, double>();
foreach (var keyVal in counts)
results.Add(keyVal.Key, keyVal.Value / (double)iterations);
return results;
}
internal static void Validate(int count, Range range, out int a, out int b)
{
(a, b) = range.End.Value < range.Start.Value
? (range.End.Value, range.Start.Value)
: (range.Start.Value, range.End.Value);
if (count < 0)
throw new ArgumentOutOfRangeException(nameof(count) + " < 0");
if (b - a < count)
throw new ArgumentOutOfRangeException(nameof(count) + " is larger than " + nameof(range));
}
public static IEnumerable<int> RandomUniqueInts(int count, Range range)
{
Validate(count, range, out int a, out int b);
var rolled = new SortedSet<int>();
var random = new Random();
for (int i = 0; i < count; i++)
{
int roll = random.Next(a, b - i);
foreach (int j in rolled)
{
if (j > roll)
break;
roll++;
}
yield return roll;
rolled.Add(roll);
}
}
internal class Node
{
internal int Value;
internal Node Next;
}
public static IEnumerable<int> RandomUniqueInts2(int count, Range range)
{
Validate(count, range, out int a, out int b);
Node head = null;
var random = new Random();
for (int i = 0; i < count; i++)
{
int roll = random.Next(a, b - i);
Node node = head;
Node previous = null;
while (!(node is null))
{
if (node.Value > roll)
break;
roll++;
previous = node;
node = node.Next;
}
yield return roll;
if (previous is null)
head = new Node() { Value = roll, Next = head, };
else
previous.Next = new Node() { Value = roll, Next = previous.Next };
}
}
public static IEnumerable<int> RandomUniqueInts3(int count, Range range)
{
Validate(count, range, out int a, out int b);
var rolled = new int[count];
var random = new Random();
for (int i = 0; i < count; i++)
{
int roll = random.Next(a, b - i);
int index = 0;
foreach (int j in rolled)
{
if (index == i)
break;
if (j > roll)
break;
roll++;
index++;
}
yield return roll;
for (int j = i; j > index; j--)
rolled[j] = rolled[j - 1];
rolled[index] = roll;
}
}
public static IEnumerable<int> RandomUniqueInts4(int count, Range range)
{
Validate(count, range, out int a, out int b);
var rolled = new SortedList<int, int>(count);
var random = new Random();
for (int i = 0; i < count; i++)
{
int roll = random.Next(a, b - i);
foreach (var j in rolled)
{
if (j.Key > roll)
break;
roll++;
}
yield return roll;
rolled.Add(roll, roll);
}
}
public static IEnumerable<int> RandomUniqueIntsList(int count, Range range)
{
Validate(count, range, out int a, out int b);
var possibleRolls = new List<int>();
for (int i = a; i < b; i++)
possibleRolls.Add(i);
var random = new Random();
for (int i = 0; i < count; i++)
{
int rollIndex = random.Next(0, possibleRolls.Count);
int roll = possibleRolls[rollIndex];
possibleRolls.RemoveAt(rollIndex);
yield return roll;
}
}
}
}
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System;
using System.Linq;
using System.Collections.Generic;
namespace ConsoleCoreBenchmarkSandbox
{
class Program
{
static void Main(string[] args)
{
BenchmarkRunner.Run<Benchmarks>();
}
}
public class Benchmarks
{
[Params(10, 1000, 10000, 100000)]
public int N;
object blah;
[Benchmark] public void RandomUniqueIntsList() => blah = RandomUniqueIntsList(5, 0..N).ToArray();
[Benchmark] public void RandomUniqueInts() => blah = RandomUniqueInts(5, 0..N).ToArray();
[Benchmark] public void RandomUniqueInts2() => blah = RandomUniqueInts2(5, 0..N).ToArray();
[Benchmark] public void RandomUniqueInts3() => blah = RandomUniqueInts3(5, 0..N).ToArray();
[Benchmark] public void RandomUniqueInts4() => blah = RandomUniqueInts4(5, 0..N).ToArray();
[GlobalCleanup] public void CleanUp()
{
Console.WriteLine(blah);
}
internal static void Validate(int count, Range range, out int a, out int b)
{
(a, b) = range.End.Value < range.Start.Value
? (range.End.Value, range.Start.Value)
: (range.Start.Value, range.End.Value);
if (count < 0)
throw new ArgumentOutOfRangeException(nameof(count) + " < 0");
if (b - a < count)
throw new ArgumentOutOfRangeException(nameof(count) + " is larger than " + nameof(range));
}
public static IEnumerable<int> RandomUniqueInts(int count, Range range)
{
Validate(count, range, out int a, out int b);
var rolled = new SortedSet<int>();
var random = new Random();
for (int i = 0; i < count; i++)
{
int roll = random.Next(a, b - i);
foreach (int j in rolled)
{
if (j > roll)
break;
roll++;
}
yield return roll;
rolled.Add(roll);
}
}
internal class Node
{
internal int Value;
internal Node Next;
}
public static IEnumerable<int> RandomUniqueInts2(int count, Range range)
{
Validate(count, range, out int a, out int b);
Node head = null;
var random = new Random();
for (int i = 0; i < count; i++)
{
int roll = random.Next(a, b - i);
Node node = head;
Node previous = null;
while (!(node is null))
{
if (node.Value > roll)
break;
roll++;
previous = node;
node = node.Next;
}
yield return roll;
if (previous is null)
head = new Node() { Value = roll, Next = head, };
else
previous.Next = new Node() { Value = roll, Next = previous.Next };
}
}
public static IEnumerable<int> RandomUniqueInts3(int count, Range range)
{
Validate(count, range, out int a, out int b);
var rolled = new int[count];
var random = new Random();
for (int i = 0; i < count; i++)
{
int roll = random.Next(a, b - i);
int index = 0;
foreach (int j in rolled)
{
if (index == i)
break;
if (j > roll)
break;
roll++;
index++;
}
yield return roll;
for (int j = i; j > index; j--)
rolled[j] = rolled[j - 1];
rolled[index] = roll;
}
}
public static IEnumerable<int> RandomUniqueInts4(int count, Range range)
{
Validate(count, range, out int a, out int b);
var rolled = new SortedList<int, int>(count);
var random = new Random();
for (int i = 0; i < count; i++)
{
int roll = random.Next(a, b - i);
foreach (var j in rolled)
{
if (j.Key > roll)
break;
roll++;
}
yield return roll;
rolled.Add(roll, roll);
}
}
public static IEnumerable<int> RandomUniqueIntsList(int count, Range range)
{
Validate(count, range, out int a, out int b);
var possibleRolls = new List<int>(b - a);
for (int i = a; i < b; i++)
possibleRolls.Add(i);
var random = new Random();
for (int i = 0; i < count; i++)
{
int rollIndex = random.Next(0, possibleRolls.Count);
int roll = possibleRolls[rollIndex];
possibleRolls.RemoveAt(rollIndex);
yield return roll;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment