В качестве учебного упражнения я пишу библиотеку для оценки сложности алгоритма. Я делаю это, видя, сколько времени занимает алоргоритм для заданных входов N, а затем делаю полиномиальную регрессию, чтобы определить, лучше ли подходит алгоритм для N, N ^ 2, log (N) и т. Д. c. Я написал юнит-тесты, и они, кажется, работают для N ^ 2 и LogN. Это самый простой случай, N, который приносит мне горе. Для алгоритма порядка N я использую следующее:
uint LinearAlgorithm2(uint n)
{
uint returnValue = 7;
for (uint i = 0; i < n; i++)
{
//Thread.Sleep(2);
double y = _randomNumber.NextDouble(); // dummy calculation
if (y < 0.0005)
{
returnValue = 1;
//Console.WriteLine("y " + y + i);
}
else if (y < .05)
{
returnValue = 2;
}
else if (y < .5)
{
returnValue = 3;
}
else
{
returnValue = 7;
}
}
return returnValue;
}
У меня есть весь этот бессмысленный код просто потому, что я был обеспокоен тем, что компилятор мог оптимизировать мой l oop. В любом случае я думаю, что l oop - это просто l oop от 0 до n, и поэтому это алгоритм или порядок N.
Мой код модульного теста:
public void TestLinearAlgorithm2()
{
Evaluator evaluator = new Evaluator();
var result = evaluator.Evaluate(LinearAlgorithm2, new List<double>() { 1000,1021, 1065, 1300, 1423, 1599,
1683, 1691, 1692, 1696, 1699, 1705,1709, 1712, 1713, 1717, 1720,
1722, 1822, 2000, 2050, 2090, 2500, 2666, 2700,2701, 2767, 2799, 2822, 2877,
3000, 3100, 3109, 3112, 3117, 3200, 3211, 3216, 3219, 3232, 3500, 3666, 3777,
4000, 4022, 4089, 4122, 4199, 4202, 4222, 5000 });
var minKey = result.Aggregate((l, r) => l.Value < r.Value ? l : r).Key;
Assert.IsTrue(minKey.ToString() == FunctionEnum.N.ToString());
}
И я положил класс Evaluator внизу. Возможно, прежде чем смотреть на это, хотя я бы спросил
1) Согласны ли вы, что простые l oop 0 для N должны быть порядка N по сложности? Т.е. время для завершения алгоритма увеличивается как n (не nLogn или n ^ 3 и т. Д. c.)
2). Был ли уже написан некоторый библиотечный код для оценки сложности алгоритма c?
3) Я очень подозреваю, что проблема заключается в оптимизации. В ProjectSettings-> Build в Visual Studio я снял флажок «Оптимизировать код». Что еще я должен делать? Одна из причин, по которой я подозреваю, что компилятор искажает результаты, состоит в том, что я распечатываю время для различных входных значений n. Для 1000 (первая запись) это 2533, а для 1021 - только 415! Я поместил все результаты ниже класса Evaluator.
Спасибо за любые идеи и дайте мне знать, если я могу предоставить больше информации (ссылка на Github?) -Dave
Код для Evaluator.cs
using MathNet.Numerics.LinearAlgebra;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
/// <summary>
/// Library to evaluate complexity of algorithm.
/// Pass in method and necessary data
/// There are methods to set the size of the test data
///
/// Evaluate for LogN, N, NLogN, N^2, N^3, 2^N
///
/// Should be able use ideas from
/// https://en.wikipedia.org/wiki/Polynomial_regression
/// to finish problem. Next need matrix multiplication.
/// Or possibly use this:
/// https://www.codeproject.com/Articles/19032/C-Matrix-Library
/// or similar
/// </summary>
namespace BigOEstimator
{
public enum FunctionEnum
{
Constant = 0,
LogN = 1,
N,
NLogN,
NSquared,
NCubed,
TwoToTheN
}
public class Evaluator
{
//private List<uint> _suggestedList = new List<uint>();
private Dictionary<FunctionEnum, double> _results = new Dictionary<FunctionEnum, double>();
public Evaluator()
{
}
public Dictionary<FunctionEnum, double> Evaluate(Func<uint,uint> algorithm, IList<double> suggestedList)
{
Dictionary<FunctionEnum, double> results = new Dictionary<FunctionEnum, double>();
Vector<double> answer = Vector<double>.Build.Dense(suggestedList.Count(), 0.0);
for (int i = 0; i < suggestedList.Count(); i++)
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
var result = algorithm((uint) suggestedList[i]);
stopwatch.Stop();
answer[i] = stopwatch.ElapsedTicks;
Console.WriteLine($"Answer for index {suggestedList[i]} is {answer[i]}");
}
// linear case - N
results[FunctionEnum.N] = CalculateResidual(Vector<double>.Build.DenseOfEnumerable(suggestedList), answer, d => d);
// quadratic case - NSquared
results[FunctionEnum.NSquared] = CalculateResidual(Vector<double>.Build.DenseOfEnumerable(suggestedList), answer, d => (d*d));
// cubic case - NCubed
results[FunctionEnum.NCubed] = CalculateResidual(Vector<double>.Build.DenseOfEnumerable(suggestedList), answer, d => (d * d * d));
// NLogN case - NLogN
results[FunctionEnum.NLogN] = CalculateResidual(Vector<double>.Build.DenseOfEnumerable(suggestedList), answer, d => (d * Math.Log(d)));
// LogN case - LogN
results[FunctionEnum.LogN] = CalculateResidual(Vector<double>.Build.DenseOfEnumerable(suggestedList), answer, d => ( Math.Log(d)));
// following few lines are useful for unit tests. You get this by hitting 'Output' on test!
var minKey = results.Aggregate((l, r) => l.Value < r.Value ? l : r).Key;
Console.WriteLine("Minimum Value: Key: " + minKey.ToString() + ", Value: " + results[minKey]);
foreach (var item in results)
{
Console.WriteLine("Test: " + item.Key + ", result: " + item.Value);
}
return results;
}
private double CalculateResidual(Vector<double> actualXs, Vector<double> actualYs, Func<double, double> transform)
{
Matrix<double> m = Matrix<double>.Build.Dense(actualXs.Count, 2, 0.0);
for (int i = 0; i < m.RowCount; i++)
{
m[i, 0] = 1.0;
m[i, 1] = transform((double)actualXs[i]);
}
Vector<double> betas = CalculateBetas(m, actualYs);
Vector<double> estimatedYs = CalculateEstimatedYs(m, betas);
return CalculatateSumOfResidualsSquared(actualYs, estimatedYs);
}
private double CalculateLinearResidual(Vector<double> actualXs, Vector<double> actualYs)
{
Matrix<double> m = Matrix<double>.Build.Dense(actualXs.Count, 2, 0.0);
for (int i = 0; i < m.RowCount; i++)
{
m[i, 0] = 1.0;
m[i, 1] = (double)actualXs[i];
}
Vector<double> betas = CalculateBetas(m, actualYs);
Vector<double> estimatedYs = CalculateEstimatedYs(m, betas);
return CalculatateSumOfResidualsSquared(actualYs, estimatedYs);
}
private Vector<double> CalculateBetas(Matrix<double> m, Vector<double> y)
{
return (m.Transpose() * m).Inverse() * m.Transpose() * y;
}
private Vector<double> CalculateEstimatedYs(Matrix<double> x, Vector<double> beta)
{
return x * beta;
}
private double CalculatateSumOfResidualsSquared(Vector<double> yReal, Vector<double> yEstimated)
{
return ((yReal - yEstimated).PointwisePower(2)).Sum();
}
}
}
Результаты одного прогона модульного теста (обратите внимание на расхождения, такие как первый!):
Answer for index 1000 is 2533
Answer for index 1021 is 415
Answer for index 1065 is 375
Answer for index 1300 is 450
Answer for index 1423 is 494
Answer for index 1599 is 566
Answer for index 1683 is 427
Answer for index 1691 is 419
Answer for index 1692 is 413
Answer for index 1696 is 420
Answer for index 1699 is 420
Answer for index 1705 is 438
Answer for index 1709 is 595
Answer for index 1712 is 588
Answer for index 1713 is 426
Answer for index 1717 is 433
Answer for index 1720 is 421
Answer for index 1722 is 428
Answer for index 1822 is 453
Answer for index 2000 is 497
Answer for index 2050 is 518
Answer for index 2090 is 509
Answer for index 2500 is 617
Answer for index 2666 is 653
Answer for index 2700 is 673
Answer for index 2701 is 671
Answer for index 2767 is 690
Answer for index 2799 is 685
Answer for index 2822 is 723
Answer for index 2877 is 714
Answer for index 3000 is 746
Answer for index 3100 is 753
Answer for index 3109 is 754
Answer for index 3112 is 763
Answer for index 3117 is 2024
Answer for index 3200 is 772
Answer for index 3211 is 821
Answer for index 3216 is 802
Answer for index 3219 is 788
Answer for index 3232 is 775
Answer for index 3500 is 848
Answer for index 3666 is 896
Answer for index 3777 is 917
Answer for index 4000 is 976
Answer for index 4022 is 972
Answer for index 4089 is 1145
Answer for index 4122 is 1047
Answer for index 4199 is 1031
Answer for index 4202 is 1033
Answer for index 4222 is 1151
Answer for index 5000 is 1588
Minimum Value: Key: NCubed, Value: 5895501.06936747
Test: N, result: 6386524.27502984
Test: NSquared, result: 6024667.62732316
Test: NCubed, result: 5895501.06936747
Test: NLogN, result: 6332154.89282043
Test: LogN, result: 6969133.89207915