0

所以，这就是交易。（我当前的用例是 C#，但我也对一般算法案例感兴趣）给了我两个对象数组（不幸的是，我无法更改创建这些数组的代码）。每个对象都有（作为它的一部分）一个 .Name 属性，一个字符串。这些字符串对于每个对象都是唯一的，并且它们在另一个对象中有零个或一个匹配的字符串。我需要做的是根据该字符串有效地将这些对象配对到某种允许我访问配对对象的集合中。字符串需要完全匹配才能被视为匹配，所以我不需要任何大写或不区分大小写等。遗憾的是，这些列表没有排序。列表本身可能有 30-50 个项目，但我需要连续对数千个这样的数组对重复该算法，因此效率很重要。

由于我知道有 0 或 1 个匹配，并且我知道它们中的大多数将是 1 个匹配，所以我觉得有一个比 x*y 更有效的算法（foreach item in x, foreach item in y, if x=y then x 和 y 是匹配的）

我认为最有可能的选择是：

保留未排序的列表并只执行 x*y，但是一旦找到它们就从列表中删除它们，这样我就不会检查已经找到的项目，或者：将两者都转换为字典，然后对每个进行索引查找（array2 [currentArray1Item]) 或者：自己对列表进行排序（Array.Sort()），然后对数组进行排序，我可能会做一些聪明的事情，比如跳转到 B 中我希望找到它的索引（无论它在 A 中的哪个位置） ) 然后根据字符串向上或向下移动，直到我找到它或通过它应该在的位置。

然后一旦完成，我需要弄清楚如何存储它，我想我可以制作一个只包含对象 A 和 B 的自定义 ObjectPair 类。这里不需要做任何花哨的事情，因为我只是去 ForEach 对.

所以问题是：上述任何算法是否是最快的方法（如果不是，是什么？），是否有一些现有的 C# 结构可以方便地保存找到的对？

编辑： Array.Sort() 是一种存在的方法，所以我不需要将数组转换为 List 进行排序。很高兴知道。以上更新。

4

2 回答 2

3

我的问题是：如果需要我们对两个输入数组进行排序，我们从特殊处理中获得多少效率？根据Array.Sort的文档，它是O(n log n)平均的，O(n ^ 2)在最坏的情况下（快速排序）。一旦我们对两个数组都进行了排序，我们就会进行另一项O(n)工作，因为我们必须遍历第一个数组。

我将此解释为意味着由于排序和处理所需的迭代次数，总工作量实际上可能会增加。如果您可以在一开始就保证排序数组，那么这当然是另一回事，但正如您所说，您不能。（我还应该注意，您需要创建一个自定义IComparer<T>实现以传递给它，Array.Sort以便它知道使用该.Name属性。这不是运行时工作，但它仍然可以工作:-)

您可能会考虑使用 LINQ 连接，它只对内部数组进行一次迭代（请参阅此处的伪代码）。这与嵌套语句相反，嵌套foreach语句将为外部数组的每个元素迭代内部数组。它与一般情况下的效率差不多，并且不会引入您建议的特殊处理的复杂性。

这是一个示例实现：

var pairs =
    from item1 in array1
    join item2 in array2 on item1.Name equals item2.Name
    select new { item1, item2 };

foreach(var pair in pairs)
{
    // Use the pair somehow
}

这非常清楚地说明了您对数据所做的事情，并且还为您提供了代表每对的匿名类型（因此您不必发明配对）。如果你最终选择了不同的路线，我会对它与这种方法的比较感兴趣。

于 2012-06-18T17:48:11.603 回答
1

使用方法对第二个数组进行排序，然后使用Array.Sort匹配第二个数组中的对象。ArrayBinary Search Algorithm

通常，对于 30-50 个项目，这将比蛮力 x*y 快一点。

于 2012-06-18T16:29:10.550 回答