Tag: 算法

查找点是否位于线段上: 我有由两个点A（x1，y1，z1）和B（x2，y2，z2）和点p（x，y，z）定义的线段。如何检查该点是否位于线段上？

整数数组的C＃哈希码: 我有一个类，内部只是一个整数数组。一旦构造，arrays永远不会改变。我想预先计算一个好的哈希码，以便这个类可以非常有效地用作词典中的键。数组的长度小于约30项，并且整数通常在-1000和1000之间。

洪水填充算法: 这是周末，这意味着我可以玩我的爱好项目了。我已经厌倦了手工创建测试级别，所以我想我会从引擎开发中rest并在级别编辑器上工作：关卡编辑http://gfilter.net/junk/Editor.JPG 我想在编辑器中实现泛洪填充算法，就像在绘图程序中一样。有没有人有任何关于哪种技术对我有用的指针？级别只是一个2d数组，因此可以认为它与位图相同。谢谢！

C＃：寻求PNG压缩算法/库: 我需要压缩或至少降低用户上传到我网站的某些png图像的质量。我已经调整了它的大小，但这对图像大小没有太大作用。为.net 4.0或更低版本寻求png /图像压缩或质量损失算法或库。这是我目前保存/转换图像的方式： Image mainImg = ImageHelper.ResizeImage(bmp, 600, 500, false); mainImg.Save(filePath, System.Drawing.Imaging.ImageFormat.Png);

检测地理位置是否在复杂多边形中: 我们目前正在使用以下算法来检测地理点是否在复杂多边形内。这种方法很好，除非多边形穿过180°经度线。例如，在多边形160,65,0 160,15,0 -160,15,0 -160,65,0 160,65,0中未检测到点（-170,60）看看下图：[Img] http://tinypic.com/r/14x2xl1 [/ img]我想要红色框中的所有内容。不是黄色的盒子！ public static bool IsCoordinateInPolygon(IList polygon, KMLCoordinate testPoint) { bool result = false; int j = polygon.Count – 1; for (int i = 0; i < polygon.Count; i++) { if (polygon[i].Latitude = testPoint.Latitude || polygon[j].Latitude = testPoint.Latitude) { if (polygon[i].Longitude + (testPoint.Latitude – polygon[i].Latitude) […]

高效的笛卡尔积算法: 有人可以为我演示一个比我目前使用的更有效的笛卡尔积算法（假设有一个）。我环顾四周，谷歌搜索了一下，但看不到任何明显的东西，所以我可能会遗漏一些东西。 foreach (int i in is) { foreach (int j in js) { //Pair i and j } } 这是我在代码中所做的高度简化的版本。两个整数是查找键，用于检索一个/多个对象，两个查找中的所有对象一起配对到新对象中。在一个更大更复杂的系统中，这个小块代码成为一个主要的性能瓶颈，因为它在规模上运行的数据集。其中一些可能通过改进用于存储对象和所涉及的查找的数据结构来减轻，但我认为主要问题仍然是笛卡尔积本身的计算。编辑关于我对算法的具体用法的更多背景，看看是否有任何技巧可以用来回应Marc的评论。整个系统是一个SPARQL查询引擎，它处理一组Graph数据的SPARQL查询，SPARQL是一种基于模式的语言，因此每个查询都包含一系列与Graph匹配的模式。在两个后续模式没有公共变量（它们是不相交的）的情况下，有必要计算由两个模式产生的解的笛卡尔积，以获得整个查询的可能解的集合。可能存在任何数量的模式，我可能需要多次计算笛卡尔积，如果查询由一系列不相交的模式组成，则可能导致可能的解决方案中相当指数级的扩展。不知何故从现有的答案我怀疑是否有任何技巧可以应用更新所以我想我会发布我实施的内容的更新，以便最大限度地减少对笛卡尔积的需求，从而优化查询引擎。请注意，并不总是可以完全消除对产品的需求，但几乎总是可以优化，因此连接的两组的尺寸要小得多。由于作为一组三元模式的每个BGP（基本图形模式）作为一个块执行（实质上），引擎可以自由地重新排序BGP中的模式以获得最佳性能。例如，考虑以下BGP： ?a :someProperty ?b . ?c :anotherProperty ?d . ?ba :Class . 按原样执行查询需要笛卡尔积，因为第一个模式的结果与第二个模式不相交，因此前两个模式的结果是其各自结果的笛卡尔积。这个结果将包含比我们实际需要的结果更多的结果，因为第三个模式限制了第一个模式的可能结果，但我们直到之后才应用此限制。但如果我们这样重新排序： ?ba :Class . ?a :someProperty ?b […]

如何知道分数中的重复小数？: 我已经知道一个分数是重复小数。这是function。 public bool IsRepeatingDecimal { get { if (Numerator % Denominator == 0) return false; var primes = MathAlgorithms.Primes(Denominator); foreach (int n in primes) { if (n != 2 && n != 5) return true; } return false; } } 现在，我正试图获得重复的数字。我正在查看这个网站： http ： //en.wikipedia.org/wiki/Repeating_decimal public decimal RepeatingDecimal() { if (!IsRepeatingDecimal) throw new InvalidOperationException(“The […]

将项目列表转换为树的好的通用方法: 我有类别列表： ╔════╦═════════════╦═════════════╗ ║ Id ║ Name ║ Parent_id ║ ╠════╬═════════════╬═════════════╣ ║ 1 ║ Sports ║ 0 ║ ║ 2 ║ Balls ║ 1 ║ ║ 3 ║ Shoes ║ 1 ║ ║ 4 ║ Electronics ║ 0 ║ ║ 5 ║ Cameras ║ 4 ║ ║ 6 ║ Lenses ║ 5 ║ ║ 7 ║ […]

在关键服务器上（数十亿个文件名）对字符串进行内存约束的外部排序，并将重复数据组合在一起计算: 我们的服务器在其日志文件夹中生成{c521c143-2a23-42ef-89d1-557915e2323a}-sign.xml文件。第一部分是GUID; 第二部分是名称模板。我想计算具有相同名称模板的文件数。例如，我们有 {c521c143-2a23-42ef-89d1-557915e2323a}-sign.xml {aa3718d1-98e2-4559-bab0-1c69f04eb7ec}-hero.xml {0c7a50dc-972e-4062-a60c-062a51c7b32c}-sign.xml 结果应该是 sign.xml,2 hero.xml,1 可能的名称模板的总种类未知，可能超过int.MaxValue 。服务器上的文件总数未知，可能超过int.MaxValue 。要求：最终结果应按名称模板排序。该工具将运行的服务器是超级关键的。在运行工具之前，我们应该能够告诉内存使用情况（MB）和生成的临时文件的数量（如果有），并且不知道日志文件夹的任何特征。我们使用C＃语言。我的想法：对于前5000个文件，计算出现次数，将结果写入Group1.txt 。对于第二个5000个文件，计算出现次数，将结果写入Group2.txt 。重复，直到处理完所有文件。现在我们有一堆组文件。然后我合并所有这些组文件。 Group1.txt Group2.txt Group3.txt Group4.txt \ / \ / Group1-2.txt Group3-4.txt \ / Group1-4.txt Group1-4.txt是最终结果。我和我朋友之间的分歧是我们如何计算事件的数量。我建议使用字典。文件名模板是关键。设m为分区大小。（在这个例子中它是5000.）然后时间复杂度O（m），空间复杂度O（m）。我的朋友建议对名称模板进行排序，然后在一次传递中对事件进行计数，因为相同的名称模板现在都在一起。时间复杂度O（m log m），空间复杂度O（m）。我们无法说服对方。你们看到这两种方法有什么问题吗？

如何“压缩”或“旋转”可变数量的列表？: 如果我有一个包含任意数量列表的列表，如下所示： var myList = new List<List>() { new List() { “a”, “b”, “c”, “d” }, new List() { “1”, “2”, “3”, “4” }, new List() { “w”, “x”, “y”, “z” }, // …etc… }; …有没有办法以某种方式将列表“拉链”或“旋转”成这样的东西？ { { “a”, “1”, “w”, … }, { “b”, “2”, “x”, … }, { “c”, “3”, “y”, … }, { […]