Skip to content

Instantly share code, notes, and snippets.

@zaus
Last active August 29, 2015 14:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save zaus/399ca9081912bd6efd7f to your computer and use it in GitHub Desktop.
Save zaus/399ca9081912bd6efd7f to your computer and use it in GitHub Desktop.
Partitioning performance comparisons -- via http://stackoverflow.com/a/13745058/1037948. Essentially runs each scenario 10000 times wrapped in a timer and compares the elapsed times.
void Main()
{
test(100, 9);
test(1000, 9);
test(100, 25);
test(10000, 100);
}
// Define other methods and classes here
void test(int populationSize, int segmentSize) {
"Testing for {0} into {1}-sized segments".TitleFormat(populationSize, segmentSize);
var e = Enumerable.Range(0, populationSize);
var size = segmentSize;
new Perf/*<IEnumerable<IEnumerable<int>>>*/ {
{ "partition", n => e.Partition(size) },
{ "split", n => e.Split(size) },
{ "BreakIntoPages", n => e.BreakIntoPages(size) },
{ "partition nawfal", n => e.NawfalPartition(size) },
{ "NawfalPartitionAsArray", n => e.NawfalPartitionAsArray(size) },
{ "partition elmer", n => e.ElmerPartition(size) },
{ "FredPartition", n => e.FredPartition(size) },
{ "NawfalSplit", n => e.NawfalSplit(size) },
}.Vs("Pure Method");
new Perf<int> {
{ "partition", n => e.Partition(size).Sum() },
{ "split", n => e.Split(size).Sum() },
{ "BreakIntoPages", n => e.BreakIntoPages(size).Sum() },
{ "partition nawfal", n => e.NawfalPartition(size).Sum() },
{ "NawfalPartitionAsArray", n => e.NawfalPartitionAsArray(size).Sum() },
{ "partition elmer", n => e.ElmerPartition(size).Sum() },
{ "FredPartition", n => e.FredPartition(size).Sum() },
{ "NawfalSplit", n => e.NawfalSplit(size).Sum() },
}.Vs("Do Something");
}
public static class X {
private const int FLIP_EVERY = 3;
public static int Sum(this IEnumerable<IEnumerable<int>> lists,
int sum = 0) {
int flip = 0;
foreach(var list in lists) foreach(var item in list) sum += (flip++ % FLIP_EVERY == 0 ? 1 : -1) * item;
return sum;
}
public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> items,
int partitionSize)
{
int i = 0;
return items.GroupBy(x => i++ / partitionSize).ToArray();
}
public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> items,
int numOfParts)
{
int i = 0;
return items.GroupBy(x => i++ % numOfParts);
}
/// <summary>
/// Breaks the IEnumerable into pages of the given size. (@etaylor)
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="pageSize"></param>
/// <returns></returns>
public static List<List<T>> BreakIntoPages<T>(this IEnumerable<T> list, int pageSize)
{
int total = list.Count();
int pages = total / pageSize;
if (total % pageSize > 0) pages++;
var resultPages = new List<List<T>>();
for (int i = 0; i < pages; i++)
{
var thisPage = list.Skip(i * pageSize).Take(pageSize).ToList();
resultPages.Add(thisPage);
}
return resultPages;
}
// http://stackoverflow.com/a/13745058/1037948
public static IEnumerable<IEnumerable<T>> NawfalPartition<T>(this IEnumerable<T> items,
int partitionSize)
{
if (partitionSize <= 0)
throw new ArgumentOutOfRangeException("partitionSize");
int innerListCounter = 0;
int numberOfPackets = 0;
foreach (var item in items)
{
innerListCounter++;
if (innerListCounter == partitionSize)
{
yield return items.Skip(numberOfPackets * partitionSize).Take(partitionSize);
innerListCounter = 0;
numberOfPackets++;
}
}
if (innerListCounter > 0)
yield return items.Skip(numberOfPackets * partitionSize);
}
/// <summary>
/// Break a list into segments/pages, each no more than <paramref name="partitionSize"/> long. Similar to Library.GlobalHelper.BreakIntoPages, but faster. See http://stackoverflow.com/a/13745058/1037948
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="items"></param>
/// <param name="partitionSize"></param>
/// <returns></returns>
public static IEnumerable<IEnumerable<T>> NawfalPartitionAsArray<T>(this IEnumerable<T> items, int partitionSize)
{
if (partitionSize <= 0)
throw new ArgumentOutOfRangeException("partitionSize");
var innerListCounter = 0;
var numberOfPackets = 0;
var enumerable = items as T[] ?? items.ToArray();
foreach (var item in enumerable)
{
innerListCounter++;
if (innerListCounter == partitionSize)
{
yield return enumerable.Skip(numberOfPackets * partitionSize).Take(partitionSize);
innerListCounter = 0;
numberOfPackets++;
}
}
if (innerListCounter > 0)
yield return enumerable.Skip(numberOfPackets * partitionSize);
}
// http://stackoverflow.com/a/13744322/1037948
public static IEnumerable<IEnumerable<T>> NawfalSplit<T>(this IEnumerable<T> items, int numberOfChunks) {
var count = items.Count();
if (numberOfChunks <= 0 || numberOfChunks > count)
throw new ArgumentOutOfRangeException("numberOfChunks");
int sizePerPacket = count / numberOfChunks;
int extra = count % numberOfChunks;
for (int i = 0; i < numberOfChunks - extra; i++)
yield return items.Skip(i * sizePerPacket).Take(sizePerPacket);
int alreadyReturnedCount = (numberOfChunks - extra) * sizePerPacket;
int toReturnCount = extra == 0 ? 0 : (count - numberOfChunks) / extra + 1;
for (int i = 0; i < extra; i++)
yield return items.Skip(alreadyReturnedCount + i * toReturnCount).Take(toReturnCount);
}
// http://stackoverflow.com/a/1225050/1037948
public static IEnumerable<IEnumerable<T>> ElmerPartition<T>(this IEnumerable<T> instance, int partitionSize)
{
return instance
.Select((value, index) => new { Index = index, Value = value })
.GroupBy(i => i.Index / partitionSize)
.Select(i => i.Select(i2 => i2.Value));
}
// http://stackoverflow.com/a/4835541/1037948
public static IEnumerable<T> TakeFromCurrent<T>(this IEnumerator<T> enumerator, int count)
{
while (count > 0)
{
yield return enumerator.Current;
if (--count > 0 && !enumerator.MoveNext()) yield break;
}
}
public static IEnumerable<IEnumerable<T>> FredPartition<T>(this IEnumerable<T> seq, int partitionSize)
{
var enumerator = seq.GetEnumerator();
while (enumerator.MoveNext())
{
yield return enumerator.TakeFromCurrent(partitionSize);
}
}
}

(tables via http://www.tablesgenerator.com/markdown_tables)

Testing for 100 into 9-sized segments

Pure Method

Key Value
NawfalSplit 9533 ticks elapsed (0.9533 ms)
FredPartition 10082 ticks elapsed (1.0082 ms)
NawfalPartitionAsArray 10239 ticks elapsed (1.0239 ms)
partition nawfal 10883 ticks elapsed (1.0883 ms)
split 11863 ticks elapsed (1.1863 ms)
partition elmer 34316 ticks elapsed (3.4316 ms)
partition 1214650 ticks elapsed (121.465 ms)
BreakIntoPages 1272839 ticks elapsed (127.2839 ms)

winner: NawfalSplit

Output for Do Something

Key ValueΞΞ
partition -1584
split -1656
BreakIntoPages -1584
partition nawfal -1584
NawfalPartitionAsArray -1584
partition elmer -1584
FredPartition -1584
NawfalSplit -1584

Do Something

Key Value
FredPartition 490661 ticks elapsed (49.0661 ms)
NawfalSplit 907588 ticks elapsed (90.7588 ms)
split 1001806 ticks elapsed (100.1806 ms)
partition nawfal 1140396 ticks elapsed (114.0396 ms)
NawfalPartitionAsArray 1251589 ticks elapsed (125.1589 ms)
partition 1482663 ticks elapsed (148.2663 ms)
BreakIntoPages 1653566 ticks elapsed (165.3566 ms)
partition elmer 2053580 ticks elapsed (205.358 ms)

winner: FredPartition

Testing for 1000 into 9-sized segments

Pure Method

Key Value
FredPartition 2709 ticks elapsed (0.2709 ms)
NawfalSplit 3020 ticks elapsed (0.302 ms)
partition nawfal 3038 ticks elapsed (0.3038 ms)
NawfalPartitionAsArray 3130 ticks elapsed (0.313 ms)
split 6026 ticks elapsed (0.6026 ms)
partition elmer 23612 ticks elapsed (2.3612 ms)
partition 10553378 ticks elapsed (1055.3378 ms)
BreakIntoPages 47808852 ticks elapsed (4780.8852 ms)

winner: FredPartition

Output for Do Something

Key ValueΞΞ
partition -165834
split -160506
BreakIntoPages -165834
partition nawfal -165834
NawfalPartitionAsArray -165834
partition elmer -165834
FredPartition -165834
NawfalSplit -165834

Do Something

Key Value
FredPartition 4793845 ticks elapsed (479.3845 ms)
NawfalSplit 7052324 ticks elapsed (705.2324 ms)
split 7184650 ticks elapsed (718.465 ms)
partition 12688420 ticks elapsed (1268.842 ms)
partition elmer 19601317 ticks elapsed (1960.1317 ms)
NawfalPartitionAsArray 41528631 ticks elapsed (4152.8631 ms)
partition nawfal 48255737 ticks elapsed (4825.5737 ms)
BreakIntoPages 51079066 ticks elapsed (5107.9066 ms)

winner: FredPartition

Testing for 100 into 25-sized segments

Pure Method

Key Value
FredPartition 2698 ticks elapsed (0.2698 ms)
partition nawfal 2812 ticks elapsed (0.2812 ms)
NawfalPartitionAsArray 2910 ticks elapsed (0.291 ms)
NawfalSplit 2929 ticks elapsed (0.2929 ms)
split 12521 ticks elapsed (1.2521 ms)
partition elmer 22665 ticks elapsed (2.2665 ms)
BreakIntoPages 666834 ticks elapsed (66.6834 ms)
partition 868214 ticks elapsed (86.8214 ms)

winner: NawfalPartitionAsArray

Output for Do Something

Key ValueΞΞ
partition -1584
split -1584
BreakIntoPages -1584
partition nawfal -1584
NawfalPartitionAsArray -1584
partition elmer -1584
FredPartition -1584
NawfalSplit -1584

Do Something

Key Value
FredPartition 426394 ticks elapsed (42.6394 ms)
partition nawfal 666776 ticks elapsed (66.6776 ms)
NawfalPartitionAsArray 852222 ticks elapsed (85.2222 ms)
BreakIntoPages 957209 ticks elapsed (95.7209 ms)
partition 1089342 ticks elapsed (108.9342 ms)
split 1156275 ticks elapsed (115.6275 ms)
partition elmer 1575129 ticks elapsed (157.5129 ms)
NawfalSplit 1692889 ticks elapsed (169.2889 ms)

winner: FredPartition

Testing for 10000 into 100-sized segments

Pure Method

Key Value
FredPartition 2819 ticks elapsed (0.2819 ms)
NawfalSplit 2962 ticks elapsed (0.2962 ms)
partition nawfal 2984 ticks elapsed (0.2984 ms)
NawfalPartitionAsArray 3082 ticks elapsed (0.3082 ms)
split 5547 ticks elapsed (0.5547 ms)
partition elmer 21290 ticks elapsed (2.129 ms)
partition 54661099 ticks elapsed (5466.1099 ms)
BreakIntoPages 394426459 ticks elapsed (39442.6459 ms)

winner: FredPartition

Output for Do Something

Key ValueΞΞ
partition -16658334
split -16658334
BreakIntoPages -16658334
partition nawfal -16658334
NawfalPartitionAsArray -16658334
partition elmer -16658334
FredPartition -16658334
NawfalSplit -16658334

Do Something

Key Value
FredPartition 40963408 ticks elapsed (4096.3408 ms)
split 68464936 ticks elapsed (6846.4936 ms)
partition 71701677 ticks elapsed (7170.1677 ms)
partition elmer 136707109 ticks elapsed (13670.7109 ms)
NawfalPartitionAsArray 366461729 ticks elapsed (36646.1729 ms)
NawfalSplit 398528237 ticks elapsed (39852.8237 ms)
partition nawfal 401966834 ticks elapsed (40196.6834 ms)
BreakIntoPages 418891239 ticks elapsed (41889.1239 ms)

winner: FredPartition

// helper extensions for testing/dumping performance results;
// may not have all methods present
/// <summary>Silly convenience initializer for creating Vs tasks with a dictionary;
/// can use <code>new Perf { { "task1", n => whatever }, {"task2", n => bar}...}.Vs()</code>
/// <para>see http://stackoverflow.com/a/14000325/1037948 </para>
/// </summary>
/// <remarks>Doesn't automatically call <see cref="Vs"/> because...</remarks>
public class Perf : Dictionary<string, Action<int>> {}
/// <summary>Silly convenience initializer for creating Vs tasks with a dictionary that can also provides some output;
/// can use <code>new Perf&lt;T&gt; { { "task1", n => whatever }, {"task2", n => bar}...}.Vs()</code>
/// <para>see http://stackoverflow.com/a/14000325/1037948 </para>
/// <example><code>
/// var p = new Perf{string} {
/// { "int", n => i.GetType().Name },
/// { "double", n => d.GetType().Name },
/// { "string", n => s.GetType().Name },
/// { "object", n => o.GetType().Name },
/// { "struct", n => t.GetType().Name },
/// { "anon", n => a.GetType().Name },
/// }.Vs("gettype");
/// </code></example>
/// </summary>
/// <remarks>Doesn't automatically call <see cref="Vs"/> because...</remarks>
public class Perf<T> : Dictionary<string, Func<int, T>> {}
public static class PerfExtensions {
/// <summary> Performance check -- how long do X repetitions of a task take?</summary>
public static TimeSpan Perf(this string reportTitle, Action<int> task, int repetitions = 10000, bool noShow = false, bool showProgress = false) {
Util.ProgressBar pb = null;
double progress = 0;
if(showProgress) {
pb = new Util.ProgressBar("Perf Progress " + reportTitle);
pb.Dump();
}
// http://stackoverflow.com/questions/28637/is-datetime-now-the-best-way-to-measure-a-functions-performance
Stopwatch sw = Stopwatch.StartNew();
for (int i = 0; i < repetitions; i++) {
task(i);
if(showProgress) pb.Percent = (int)(progress += 100D/(double)repetitions);
}
sw.Stop();
if( !noShow ) perfElapsed(sw.Elapsed).Dump(string.IsNullOrEmpty(reportTitle) ? null : string.Format("{0} ({1}x)", reportTitle, repetitions));
return sw.Elapsed;
}
private static string perfElapsed(TimeSpan ts) {
return string.Format("{0} ticks elapsed ({1} ms)", ts.Ticks, ts.TotalMilliseconds);
}
private static int indexOfMost<T>(IEnumerable<T> list, Func<T, T, bool> compare) {
int i = 0, j = 0;
T min = list.First();
foreach(var s in list) {
if(compare(min, s)) {
min = s;
j = i;
}
i++;
}
return j;
}
/// <summary> Performance check -- how long do 10K repetitions of the listed tasks take? Can also print the results (1 or more) of each task.
/// <example><code>
/// var p = new Perf{string} {
/// { "int", n => i.GetType().Name },
/// { "double", n => d.GetType().Name },
/// { "string", n => s.GetType().Name },
/// { "object", n => o.GetType().Name },
/// { "struct", n => t.GetType().Name },
/// { "anon", n => a.GetType().Name },
/// }.Vs("gettype", outputTimes: 10);
/// </code></example>
/// </summary>
public static TimeSpan[] Vs<T>(this Dictionary<string, Func<int,T>> tasks, string reportTitle = null, int repetitions = 10000, bool noShow = false, int outputTimes = 1, bool showProgress = false) {
if(outputTimes > 0) {
string outputTitle = "Output" + (reportTitle == null ? null : " for " + reportTitle);
if(outputTimes == 1) tasks.Do().Dump(outputTitle);
else tasks.Do(outputTimes).Dump(outputTitle);
}
return tasks.ToDictionary(k => k.Key, v => { Action<int> a = n => v.Value(n); return a; }).Vs(reportTitle, repetitions, noShow, showProgress);
}
/// <summary> Performance check -- how long do 10K repetitions of the listed tasks take?</summary>
public static TimeSpan[] Vs(this Dictionary<string, Action<int>> tasks, string reportTitle = null, int repetitions = 10000, bool noShow = false, bool showProgress = false) {
// tasks.Dump();
Util.ProgressBar pb = null;
double progress = 0;
if(showProgress) {
pb = new Util.ProgressBar(reportTitle + " Progress");
pb.Dump("Note that performance calculation will be affected by this display");
}
var n = tasks.Count();
var r = new Dictionary<string, TimeSpan>();
foreach (var task in tasks)
{
r.Add(task.Key, task.Key.Perf(task.Value, repetitions, true, showProgress));
if(showProgress) pb.Percent = (int)(progress += 100D/(double)tasks.Count());
}
if (!noShow)
{
reportTitle = (reportTitle ?? "Vs");// + ": (" + string.Join(") vs (", tasks.Keys) + ")";
// get the best
var minIndex = indexOfMost(r, (a, b) => a.Value > b.Value);
r
.OrderBy(kv => kv.Value)
.Select(kv => new KeyValuePair<string, string>(kv.Key, perfElapsed(kv.Value)))
// .ToDictionary(kv => kv.Key, kv => perfElapsed(kv.Value))
// r.Select(ts => perfElapsed(ts)).Concat(new[] { "winner: " + (hasSubs ? subReportTitles.ElementAt(minIndex) : minIndex + "th") })
/*
Tuple.Create(
r.Select(ts => perfElapsed(ts))
, "winner: " + (hasSubs ? subReportTitles.ElementAt(minIndex) : minIndex + "th")
)
*/
.Dump(reportTitle);
(">> winner: " + tasks.Keys.ElementAt(minIndex)).Dump();
}
return r.Select(kv => kv.Value).ToArray();
}
/// <summary> Performance check -- how long do X repetitions of the listed tasks take?</summary>
public static TimeSpan[] Vs(this string reportTitle, IEnumerable<string> subReportTitles, int repetitions, bool noShow, params Action<int>[] tasks) {
return Vs(Enumerable.Range(0, tasks.Length).ToDictionary(i => null == subReportTitles || subReportTitles.Count() <= i ? i.ToString() : subReportTitles.ElementAt(i), i => tasks[i])
, reportTitle, repetitions, noShow);
}
/// <summary> Performance check -- how long do 10K repetitions of the listed tasks take?</summary>
public static TimeSpan[] Vs(this string reportTitle, IEnumerable<string> reportTitles, params Action<int>[] tasks) {
return reportTitle.Vs(reportTitles, 10000, false, tasks);
}
/// <summary> Performance check -- how long do 10K repetitions of the listed tasks take?</summary>
public static TimeSpan[] Vs(this string reportTitle, params Action<int>[] tasks) {
return reportTitle.Vs(null, tasks);
}
public static void Do(this Dictionary<string, Action<int>> tasks) {
foreach(var kv in tasks) {
kv.Value(1);
}
}
/// <summary>Helpers for evaluating Perf</summary>
public static Dictionary<string,T> Do<T>(this Dictionary<string, Func<int,T>> tasks) {
return tasks.ToDictionary(kv => kv.Key, kv => kv.Value(1));
}
/// <summary>Helpers for evaluating Perf</summary>
public static Dictionary<string, object> Do<T>(this Dictionary<string, Func<int,T>> tasks, int repetitions) {
// HorizontalRun lists things horizontally vs. vertically -- even objects! http://stackoverflow.com/questions/3555317/linqpad-extension-methods
return tasks.ToDictionary(kv => kv.Key, kv => Util.HorizontalRun(true, Enumerable.Range(0,repetitions).Select(i => kv.Value(i))));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment