比较高性能的int数组

本文关键字：数组 int 高性能 比较 | 更新日期: 2023-09-27 18:07:56

我不记得从我在大学的日子，如何比较两个未排序的int数组和找到匹配的数量?每个值在它自己的数组中是唯一的，并且两个数组的大小相同。

例如

int[5] a1 = new []{1,2,4,5,0}
int[5] a2 = new []{2,4,11,-6,7}
int numOfMatches = FindMatchesInPerformanceOfNLogN(a1,a2);

有人记得吗?

比较高性能的int数组

如果您可以将其中一个数组的内容存储在HashMap中，那么您可以通过查看另一个数组中的元素是否存在HashMap来检查它们是否存在。这是O(n)

必须对一个数组进行排序，以便在n*log(n)内进行比较。也就是说，对于未排序数组(n)中的每个项，对排序数组(log(n))执行二分搜索。如果两者都未排序，我不认为有办法在n*log(n)中进行比较。

这个怎么样:

  1. 连接两个数组
  2. 快速排序结果
  3. 从array[1]到array[array]。检查数组[i]与数组[i-1]是否一致

如果它们是相同的，你有一个重复。这也应该是O(n*log(n))，并且不需要每次检查都进行二进制搜索。

你可以使用LINQ:

var a1 = new int[5] {1, 2, 4, 5, 0};
var a2 = new int[5] {2, 4, 11, -6, 7};
var matches = a1.Intersect(a2).Count();

我不确定你是想要一个直接的方法还是最快/最好的方法…

我知道你有两个方法(ref: http://www2.cs.siu.edu/~mengxia/Courses%20PPT/220/carrano_ppt08.ppt):

)递归(伪代码)

Algorithm to search a[first] through a[last] for desiredItem
if (there are no elements to search)
    return false
else if (desiredItem equals a[first])
    return true
else    
    return the result of searching a[first+1] through a[last]
效率

May be O(log n) though I have not tried it.

顺序搜索(伪代码)

public boolean contains(Object anEntry)
{   
    boolean found = false;
    for (int index = 0; !found && (index < length); index++) {
    if (anEntry.equals(entry[index]))
            found = true;
    } 
    return found;
}

顺序搜索的效率

Best case  O(1)
    Locate desired item first
Worst case  O(n)
    Must look at all the items
Average case O(n)
    Must look at half the items 
    O(n/2) is still O(n)

我不知道O(log n)搜索算法，除非它是排序的。

我不知道这是不是最快的方法但是你可以这样做

int[] a1 = new []{1,2,4,5,0};
int[] a2 = new []{2,4,11,-6,7};
var result = a1.Intersect(a2).Count();

当Intersect()操作IEnumerable时，值得将此方法与其他针对int优化的方法进行比较。

这个问题也适用于并行化:生成n1个线程，并让每个线程比较a1的一个元素与a2的n2个元素，然后求和值。可能比较慢，但考虑起来很有趣，是产生n1 * n2个线程同时进行所有比较，然后减少。如果第一种情况下P>> max(n1, n2)第二种情况下P>> n1 * n2，你可以在第一种情况下用O(n)来完成整个过程，第二种情况下用O(log n)

相关文章：