Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>ВотАвтор: Evgeny.Panasyuk
Дата: 23.03.16
— там два момента.
А, ну как и было сказано — иногда больше работы не значит лучше. Специально засёк время — 10 минут на код ушло. Блин, но оформление ответа больше потрачу, наверно
Для структур соотношение:
Method | Median | StdDev | Scaled | Min | Lnml(min) | Lnml(max) | Max |
-------------- |------------ |----------- |------- |------------ |---------- |---------- |------------ |
MinCodeJam | 13.5474 us | 4.2560 us | 1.00 | 9.8527 us | 1.00 | 1.00 | 57.8845 us |
MinNaive | 133.8322 us | 37.9869 us | 9.88 | 109.2005 us | 9.78 | 9.78 | 584.1817 us |
MinOk | 17.6527 us | 1.5569 us | 1.30 | 13.9580 us | 1.28 | 1.28 | 25.8633 us |
MinOkComparer | 16.4211 us | 1.2513 us | 1.21 | 13.5474 us | 1.18 | 1.18 | 27.0949 us |
MinDoneRight | 1.6421 us | 0.5551 us | 0.12 | 1.2316 us | 0.12 | 0.12 | 10.2632 us |
для строк:
Method | Median | StdDev | Scaled | Min | Lnml(min) | Lnml(max) | Max |
-------------- |-------------- |------------ |------- |-------------- |---------- |---------- |-------------- |
MinCodeJam | 331.7068 us | 19.2213 us | 1.00 | 289.4224 us | 1.00 | 1.00 | 419.9704 us |
MinNaive | 4,391.0101 us | 622.1757 us | 13.24 | 2,497.2433 us | 12.18 | 12.18 | 5,005.5709 us |
MinOk | 25.0422 us | 5.5940 us | 0.08 | 16.4211 us | 0.07 | 0.07 | 79.2320 us |
MinOkComparer | 313.6436 us | 38.8401 us | 0.95 | 170.3692 us | 0.94 | 0.94 | 474.9812 us |
MinDoneRight | 252.4749 us | 61.4753 us | 0.76 | 155.5902 us | 0.66 | 0.66 | 359.6227 us |
и собственно метод MinOkComparer :
private static T MyMinByComparer<T, TValue>(IEnumerable<T> source, Func<T, TValue> selector)
{
var comparer = Comparer<TValue>.Default;
T result = default(T);
TValue resultValue = default(TValue);
bool hasData = false;
foreach (var item in source)
{
if (!hasData || comparer.Compare(resultValue, selector(item)) > 0)
{
result = item;
resultValue = selector(item);
hasData = true;
}
}
if (!hasData)
throw new Exception("Bla-bla-bla");
return result;
}
на самом деле это уже второй вариант, первый — MinOk — рвал всех за счёт использования Operators<T>, которые не тупят и используют ordinal comparison. Ну ок, пришлось переделывать.
В чём подвох:
1. Тяп-ляп универсальный код, написанный без включения мозга оказался немного быстрее "оптимизированного" для ссылочных полей и на ~20% медленнее — для структур.
2. Не менее тяп-ляп код, написанный для конкретного частного случая выполняется на четверть быстрее для ссылочных полей и в 8 раз быстрее — для структур.
сравниваем, если что, с
вот этим. 5000 строк неэффективной кодогенерации
| Перфтест |
| using System;
using System.Collections.Generic;
using System.Linq;
using CodeJam.Arithmetic;
using CodeJam.Collections;
using CodeJam.PerfTests;
using JetBrains.Annotations;
using NUnit.Framework;
using static CodeJam.AssemblyWideConfig;
using static CodeJam.PerfTests.CompetitionHelpers;
// ReSharper disable once CheckNamespace
namespace CodeJam
{
[PublicAPI]
[TestFixture(Category = PerfTestCategory + ": EnumHelper")]
public class TempPerfTests
{
public class Data
{
public Data(int structField)
{
StructField = structField;
StringField = structField.ToString();
}
public int StructField { get; }
public string StringField { get; }
}
private static readonly Data[] _data = Enumerable
.Range(1, 1000)
.Select(i => new Data(i))
.ToArray();
private static T MyMinBy<T, TValue>(IEnumerable<T> source, Func<T, TValue> selector)
{
var greater = Operators<TValue>.GreaterThan;
T result = default(T);
TValue resultValue = default(TValue);
bool hasData = false;
foreach (var item in source)
{
if (!hasData || greater(resultValue, selector(item)))
{
result = item;
resultValue = selector(item);
hasData = true;
}
}
if (!hasData)
throw new Exception("Bla-bla-bla");
return result;
}
private static T MyMinByComparer<T, TValue>(IEnumerable<T> source, Func<T, TValue> selector)
{
var comparer = Comparer<TValue>.Default;
T result = default(T);
TValue resultValue = default(TValue);
bool hasData = false;
foreach (var item in source)
{
if (!hasData || comparer.Compare(resultValue, selector(item)) > 0)
{
result = item;
resultValue = selector(item);
hasData = true;
}
}
if (!hasData)
throw new Exception("Bla-bla-bla");
return result;
}
[Test]
public void RunMinByIntCase() => Competition.Run<MinByIntCase>(RunConfig);
public class MinByIntCase
{
[CompetitionBaseline]
public Data MinCodeJam() => _data.MinBy(x => x.StructField);
[CompetitionBenchmark(6.98, 15.66)]
public Data MinNaive() => _data.OrderBy(x => x.StructField).FirstOrDefault();
[CompetitionBenchmark(0.81, 1.67)]
public Data MinOk() => MyMinBy(_data, x => x.StructField);
[CompetitionBenchmark(0.83, 1.64)]
public Data MinOkComparer() => MyMinByComparer(_data, x => x.StructField);
[CompetitionBenchmark(0.07, 0.18)]
public Data MinDoneRight()
{
Data result = null;
int resultValue = 0;
var local = _data;
foreach (var other in local)
{
if (result == null || resultValue > other.StructField)
{
result = other;
resultValue = other.StructField;
}
}
return result;
}
}
[Test]
public void RunMinByStringCase() => Competition.Run<MinByStringCase>(RunConfig);
public class MinByStringCase
{
[CompetitionBaseline]
public Data MinCodeJam() => _data.MinBy(x => x.StringField);
[CompetitionBenchmark(8.46, 21.14)]
public Data MinNaive() => _data.OrderBy(x => x.StringField).FirstOrDefault();
[CompetitionBenchmark(0.05, 0.11)]
public Data MinOk() => MyMinBy(_data, x => x.StringField);
[CompetitionBenchmark(0.53, 1.33)]
public Data MinOkComparer() => MyMinByComparer(_data, x => x.StringField);
[CompetitionBenchmark(0.53, 0.86)]
public Data MinDoneRight()
{
Data result = null;
string resultValue = null;
var local = _data;
foreach (var other in local)
{
if (result == null || string.Compare(resultValue, other.StringField) > 0)
{
result = other;
resultValue = other.StringField;
}
}
return result;
}
}
}
}
|
| |
В общем надо знать матчасть, думать, а затем писать. И мерять. Иначе вот такой вот неудобняк получается.
EP>Не прям такое, а уменьшение ветвления по памяти в общем.
EP>То есть например есть класс, он агрегирует другие объекты других классов, те в свою очередь аггрегируют далее. Получается дерево. В большинстве случаев размазывать все под-объекты по памяти не требуется, и достаточно "плоского" "inline"-хранения. На C# структуры имеют ряд ограничений, и по факту многие под-объекты будут классами, даже те которые по смыслу могли быть "inline".
Есть у меня подозрение, что достаточно передать ссылку на "вложенный" объект за пределы класса (или просто вытащить её рефлексией), чтобы обломать всю красоту.