适用于 .NET 的大 O 算法分析器
一个启发式图形工具，用于通过无限渐近线和仪器化来帮助发现“大 O 表示法”函数。
文章索引评分
- 开发者 (5) / 5 (中级)
- 架构师 (1.67) / 5 (初级)
- 平面设计师 (3.33) / 5 (中级)
下载 Article_Demo.zip - 64.83 KB
下载 Article_Src.zip - 110.18 KB
目录
引言
在对“大 O 表示法”进行了一些研究后，我读了一些开发者的帖子，他们解释说必须在脑子里进行“大 O 方程”。 也许他们在开玩笑？ 我不知道。 但这给了我创建这个工具的想法，它可以帮助找到给定算法的“大 O 函数”。 该应用程序使用 C# 反射来访问目标 .net 程序集。 无限渐近线和仪器化被用来绘制函数相对于时间的图。 在使用无限渐近线时，有必要创建一个接受整数作为输入的函数或属性。 整数值是无穷点，函数计算为无穷大的点。 这个点可以是时间、值等。 在示例中，计算了斐波那契函数。
这是两个线性递归斐波那契函数的图：
这是原始原型绘制的指数递归斐波那契函数
图 1 - 指数斐波那契
我在 Demo 中使用了 Derek Bartram 的 WPFGraph，它不适用于商业或非营利用途。 如果您需要将此工具用于商业或非营利目的，可以扩展原型的功能。 我的 WPFGraph 实现存在一些小问题。 主要问题在于性能缩放。 在我的原型中，我使用了取模缩放，这是非常精确的。 我尝试在 Derek 的图中使用相同的缩放，但性能网格线与网格上的点不完全匹配。 如果您需要精确的网格线和快速的性能，请扩展原型。
图 2 - 原型显示 O(n log n) 斐波那契的示例
该应用程序是样板，这应该能让您根据自己的规范扩展功能。 这是使用 Derek 的图的相同图形
图 3 - 修改后的图形，带有网格线和幂函数图
另一个小问题是图线开头的时间基准跳跃。 使用非常大的无穷值进行绘图可以改善这一点，但可能需要线程修复。 我已经向 MSDN 提交了一个修复请求。 一旦收到修复，我将发布它。
该工具使用启发式方法来查找“最佳猜测”大 O 函数
图 4 - 也可以显示启发式图
并允许用户查看详细信息
图 5 - 启发式计算结果
特别感谢 Derek 的辛勤工作！ 出色的图形！
数学方法:
计算大 O 的数学方法是使用函数索引来标记算法。 这是开发者在在线帮助线程中讨论的“需要脑子”的方法。 以下是我在互联网上找到的一个示例，说明了“标记”和计算。
int foo(int n)
{
int p = 1; //c1 x 1
int i = 1; //c1 x 1
while(i < n) //c2 x n
{
int j = 1; //c1 x (n - 1)
while(j < i)//c2 x ((1/2)n^2 - (3/2)n + 2)
{
p = p * j;//(c1+c3) x ((1/2)n^2 - (3/2)n + 1)
j = j + 1;//(c1+c4) x ((1/2)n^2 - (3/2)n + 1)
}
i = i + 1; //(c2+c4) x (n - 1)
}
return p; //c5 x 1
}
其中
c1 = 赋值
c2 = 比较
c3 = 乘法
c4 = 加法
c5 = 返回
数学方程被简化为
步骤 1
(c1 + 1/2c2 + 1/2c3 + 1/2c3)n^2 +
(-c1 - 1/2c2 - 3/2c3 - 1/2c4)n +
(2c1 + 2c2 + c3 + c5)
第二步
(c1 + 1/2c2 + 1/2c3 + 1/2c3)n^2
步骤 3
n^2
因此，该 foo 算法的大 O 是 n^2 或二次。
完整的示例可以在以下位置查看：
大 O 表示法 - CS 动画
关于代码:
该应用程序使用了 Model, Viewer, Presenter; Factory, 和 Publisher / Subscriber 模式。 Viewer 是 XAML Window，它允许设计师轻松进行设计，Presenter 在 window 的 xaml.cs 中实现。 Factory 和 Publisher-Subscriber 模式在 AnalysisFactory 中实现。 MVP 模式是原型开发的一个良好垫脚石，因为它可以轻松创建自定义抽象而不会牺牲代码库。
关于示例:
此演示中的示例使用斐波那契数列来说明计算给定索引的斐波那契数法的不同方法。 这些示例将在未来与无限渐近线方法一起使用，本文将更新使用仪器化方法的示例。
渐近线是“运行时间”渐近线，而不是“操作计数”渐近线。 理解这一点很重要。 数学和计算机代码都可以使用大 O 表示法来表示操作计数，这与本文目前介绍的评估方式不同。 将来会增加反编译引用代码并计算操作计数和运行时间的功能。 运行时间确实提供了“真实世界”的值，这些值在使用操作计数方法时不会被发现。 例如：正在测试的代码有一个算法以对数时间运行，而表面上看该算法可能看起来是线性的。 操作系统和应用程序后台进程也会影响真实世界的结果。
要创建简单的渐近线测试，只需要方法调用是公开可见的，并且它接受一个参数，即要运行的迭代次数。 执行逻辑的代码使用 .NET 反射来访问程序集并显示公共方法。
以下是示例中使用的斐波那契算法的一些示例
图 1 - 闭式斐波那契类
class fib
{
double n = 0;
int n2 = 0;
public double next
{
get
{
return n;
}
set
{
n = Math.Floor(((Math.Pow(fib.golden(),
Convert.ToDouble(value))) -
Math.Pow((1 - fib.golden()),
Convert.ToDouble(value))) / Math.Sqrt(5));
}
}
private static double golden()
{
return (1 + Math.Sqrt(5)) / 2;
}
}
图 2 - 闭式测试代码 O(1)
public static double ClosedFormFib(double n)
{
fib f = new fib();
f.next = n;
return f.next;
}
图 3 - 线性斐波那契 - 实际上是 O(n log n)
发布此算法的作者错误地将其标记为线性解决方案，而实际上它以对数时间运行。
public static double LinerFib(double n)
{
double previous = -1;
double result = 1;
double sum = 0;
for (double i = 0; i <= n; ++i)
{
sum = result + previous;
previous = result;
result = sum;
}
return result;
}
图 4 - 线性递归斐波那契 - 同样是 O(n log n)
public static double LinerRecursiveFib(double n)
{
return Fib(n, 1, 1);
}
private static double Fib(double n, double n1, double n2)
{
if (n == 1 || n == 2)
{
return 1;
}
else if (n == 3)
{
return n1 + n2;
}
else
{
return Fib(n - 1, n1 + n2, n1);
}
}
图 5 - 指数斐波那契 - O(n^2)
public static int ExponentialRecursiveFib(double n)
{
if (n == 1 || n == 2)
return 1;
else
return ExponentialRecursiveFib(n - 1) +
ExponentialRecursiveFib(n - 2);
}
此时您可能在想“如果算法接受整数作为输入来加载，这当然很好。 其他不接受的算法怎么办，例如排序等？” 要回答这个问题，首先必须考虑数据类型和算法。 例如，字符串数组的冒泡排序。 要使用渐近线方法测试此算法，我将在要测试的类中创建一个构造函数。 例如：
图 6 - 测试非数字数据类型和算法
ArrayList al = new ArrayList();
void LoadMe(){ LoadMe(1000); }
void LoadMe(double d)
{
//create random string elements and add to string array
//add each element to the ArrayList.
}
public static double TestBubbleSort(double n)
{
//Get each string array from ArrayList then call the bubble sort
//on the string array.
}
此方法可用于加载和测试，而无需自定义仪器化测试代码。 数据加载 ArrayList 的代码应在启动时产生，但大小必须硬编码到测试代码中。
关注点:
关于启发式方法的一些有趣之处
启发式方法使用 Meta.Numerics.Statistics 类库来查找两个系列项目之间的强相关性。 系列 1（测试结果）包含测试实际形式和值的运行结果。 系列 2（对照组）是来自方程的值系列，形式如下：
图 7 - 大 O 函数系列生成
//O(n log n)
static double nLogn(int n)
{
double r = Math.Log(n) * n;
if (r.ToString() == "NaN" ||
r.ToString().IndexOf("Infinity")
!= -1)
return 0;
else
return r;
}
public static DecoratedMarker nLognLine(int n)
{
double[] ret = new double[n];
for (int y = 0; y < n; y++)
ret[y] = Functions.nLogn(y);
return new DecoratedMarker(ret, "O(n log n)", null);
}
以上是对每个正在测试的大 O 函数计算的。 解决方案中可以找到一个函数库，并且可以轻松更新。 使用的确切统计公式是“Person's Rio”。 有关 Person's Rio 的更多信息可以在其他维基上找到。 也可以使用其他公式。 我考虑过的一些想法是：查找曲线下方区域的公式、比率相关性等。 统计包放在自己的类中，因此可以轻松加载或重载其他包。关于图形的一些有趣之处
我并不完全理解取模的魔力。 但我重视它的力量。 我不得不调整取模方程以使缩放函数在原型中工作。 也许我需要复习一下取模。 以下是用于缩放的取模函数：
((dm.Point[1] * PointScale % infinityPoint) / 10) * PointRullerDivision; // 获取垂直缩放。
(aggT * TimeScale % totTime) / 10 * TimeScaleDivision; // 获取水平缩放。
PointScale 通过将 100 除以 infinityPoint 来计算（这是一个反函数），使函数成为 100 为基数。 PointRullerDivision 通过将图的 Canvas 除以 100 来计算（作为反函数的补充）。 水平轴（x 轴，时间）的计算方式相同，但使用聚合时间； aggT，代替点索引 dm.Point[1]。 总时间是使用 LINQ to Object lambda 函数计算的（对我来说也是纯粹的魔法）。
Math.Round(dms.Sum(p => p.Point[0]),0)
totTime 四舍五入到零位小数而不四舍五入 aggT 会导致性能图出现位移，其中 x 轴的网格线与图上的点不匹配，但除非将总时间四舍五入，否则无法与 Derek 的图一起使用。 原型工作完美。另一个有趣的点是 Derek 的网格点。 如果您获取其中一个网格点的渲染几何图形，则其边界评估为无穷大。 我尝试了所有获取位置的方法来纠正舍入误差。 没有奏效！ 一定是魔法。 因此，该应用程序提供了许多用于集成
WPFGraph 的解决方法。幂函数图
幂函数图是我认为的一种可视化被测算法性能的巧妙方法。 使用的公式仅为加权度量。
伪代码
如果单元 n-1 是 n 的两倍，则颜色值 = 颜色值 - 10
这当然依赖于网格线，网格线在垂直方向上以 10 为增量等距分布，然后在水平方向上根据新点与 x,y 轴的交叉点不对称分布。 这会产生一种视觉效果，而不会扭曲图的数学公式，例如线性、对数或指数。
结论与下一阶段:
总而言之，我发现这项研究与我所做和演示的工作是独特的。 虽然它目前引起争议，但我认为它是在“实际应用”方面的一项重大进步。 算法的数学证明可能很有用，但当涉及到工程时，证明并不能代表一切！ 理论、开发和工程中常常如此。 我希望这个工具能对数学家和工程师有用，用于建立算法在实际时间中运行的实际和实时估算。 我计划完成这个原型并添加功能，允许在应用程序本身中编写算法，而无需使用 Visual Studio。 我还将把 MVP 模式转换为 MVVM 模式。 并进一步研究启发式模型，这似乎是引起争议的原因。 如果有任何有专业知识的人愿意加入我，请告诉我。 最终产品将发布在 CodePlex 上，并在 Code Project 上发布后续文章，以展示其有用性和不适用的领域。 目前就到这里，这篇文章到此结束！
外部链接:
原型研究
- 平面设计师 (3.33) - 开发者 (5) - 架构师 (1.67)
修订历史