问题标签 [algorithm]

• 您将模型检查用于哪些类型的应用程序？
• 你用的是什么模型检查工具？
• 您如何总结您使用该技术的经验，特别是在评估其交付更高质量软件的有效性方面？

在我的学习过程中，我有机会使用Spin，它引起了我的好奇心，即实际进行了多少模型检查以及组织从中获得了多少价值。在我的工作经验中，我从事过业务应用程序，其中（自然）没有考虑将形式验证应用于逻辑。我真的很想了解 SO 人的模型检查经验和对该主题的想法。模型检查会成为我们应该在我们的工具包中使用的更广泛使用的开发实践吗？

我想将一个应用程序（可能是网页）的屏幕截图与之前截取的屏幕截图进行比较，以确定该应用程序是否正确显示自身。我不想要完全匹配比较，因为方面可能略有不同（对于 Web 应用程序，取决于浏览器，某些元素可能位于稍微不同的位置）。它应该衡量屏幕截图的相似程度。

是否有已经这样做的库/工具？你将如何实施它？

在编程或特定语言特性方面，哪种算法教给你最多？

我们都有过这样的时刻，突然我们知道，只是知道，我们已经为未来吸取了重要的一课，基于最终理解程序员编写的算法，在进化阶梯上走了几步。谁的想法和代码对你有魔力？

如何计算经纬度指定的两点之间的距离？

为了澄清起见，我想要以公里为单位的距离；这些点使用 WGS84 系统，我想了解可用方法的相对准确性。

我使用简单的堆栈算法开发了一个方程解析器，该算法将处理二进制（+、-、|、&、*、/ 等）运算符、一元（！）运算符和括号。

然而，使用这种方法，所有东西都具有相同的优先级——不管运算符如何，它都是从左到右评估的，尽管可以使用括号来强制执行优先级。

所以现在“1+11*5”返回 60，而不是人们可能期望的 56。

虽然这适用于当前项目，但我希望有一个通用例程，可用于以后的项目。

为清楚起见进行了编辑：

什么是优先解析方程的好算法？

我对一些易于实现和理解的东西感兴趣，我可以自己编写代码以避免可用代码出现许可问题。

语法：

我不明白语法问题 - 我是手写的。这很简单，我认为不需要 YACC 或 Bison。我只需要用诸如“2+3 * (42/13)”之类的等式计算字符串。

语言：

我在 C 中这样做，但我对算法感兴趣，而不是特定于语言的解决方案。C 足够低级，如果需要，它可以很容易地转换为另一种语言。

代码示例

我发布了上面提到的简单表达式解析器的测试代码。项目需求发生了变化，因此我不需要针对性能或空间优化代码，因为它没有被合并到项目中。它是原始的详细形式，应该很容易理解。如果我在运算符优先级方面对其进行进一步处理，我可能会选择宏 hack，因为它与程序的其余部分相匹配。但是，如果我在实际项目中使用它，我会选择更紧凑/更快的解析器。

相关问题

数学解析器的智能设计？

-亚当

我不确定以下代码是否能确保 Comparator 的 Javadoc 中给出的所有条件。

上面的代码是否会对任何类的所有实例进行总排序，即使该类没有实现 Comparable？

我实际上对我的问题有一个答案，但它没有并行化，所以我对改进算法的方法很感兴趣。无论如何，它可能对某些人有用。

也许我可以一起使用多个BitArrays 和BitArray.And()？

您认为描述用于在 2D 环境中进行碰撞检测的算法或技术的最佳资源（书籍或网页）是什么？

我只是渴望学习不同的技术来制作更复杂、更高效的游戏。

我有一个简单的联系人数据库，但我遇到了用户输入重复数据的问题。我已经实现了一个简单的数据比较，但不幸的是输入的重复数据并不完全相同。例如，姓名拼写错误，或者一个人会输入“Bill Smith”，而另一个人会为同一个人输入“William Smith”。

那么是否有某种算法可以给出一个条目与另一个条目的相似程度的百分比？

我需要知道不同 XML 工具（解析器、验证器、XPath 表达式评估器等）的性能如何受输入文档的大小和复杂性的影响。是否有资源可以记录 CPU 时间和内存使用情况如何受到...的影响……嗯，什么？文档大小（以字节为单位）？节点数？关系是线性的、多项式的还是更糟的？

更新

在 IEEE 计算机杂志第 41 卷第 9 期，2008 年 9 月的一篇文章中，作者调查了四种流行的 XML 解析模型（DOM、SAX、StAX 和 VTD）。他们运行了一些非常基本的性能测试，表明当输入文件的大小从 1-15 KB 增加到 1-15 MB 或大约 1000 倍时，DOM 解析器的吞吐量将减半。其他模型的吞吐量没有受到显着影响。

不幸的是，他们没有进行更详细的研究，例如将吞吐量/内存使用作为节点数/大小的函数。

文章在这里。

更新

我找不到任何正式的方法来解决这个问题。对于它的价值，我做了一些实验，测量 XML 文档中的节点数作为文档大小（以字节为单位）的函数。我正在开发一个仓库管理系统，XML 文档是典型的仓库文档，例如提前发货通知等。

下图显示了以字节为单位的大小与节点数之间的关系（在 DOM 模型下，它应该与文档的内存占用成正比）。不同的颜色对应不同种类的文件。比例为对数/对数。黑线最适合蓝点。有趣的是，对于所有类型的文档，字节大小和节点大小之间的关系是线性的，但是比例系数可能会有很大的不同。

_{（来源：flickr.com）}