如何比较两组1000个数字？

Question

我必须检查大约1000个数字和1000个其他数字.

我加载了两个并比较了服务器端:

foreach( $numbers1 as $n1 ) {
  foreach( $numbers2 as $n2 ) {
    if( $n1 == $n2 ) {
      doBla();
    }
  }
}

这需要很长时间,所以我尝试使用两个隐藏div元素进行相同的比较客户端 .然后使用JavaScript比较它们.加载页面仍然需要45秒(使用隐藏div元素).

我不需要加载不相同的数字.

有更快的算法吗？我正在考虑比较它们的数据库端,只是加载错误号,然后对剩余的非错误号进行Ajax调用.但MySQL数据库是否足够快？

Answer 1

首先对列表进行排序.然后你可以从头开始走两个列表,比较你去的地方.

循环看起来像这样:

var A = getFirstArray().sort(), B = getSecondArray().sort();

var i = 0, j = 0;
while (i < A.length && j < B.length) {
    if (A[i] === B[j]) {
        doBla(A[i]);
        i++; j++;
    }
    else if (A[i] < B[j]) {
        i++;
    }
    else
        j++;
}

(那是JavaScript;你也可以在服务器端做,但我不懂PHP.)

编辑 - 为了公平对待所有哈希表粉丝(我当然尊重他们),在JavaScript中这很容易做到:

var map = {};
for (var i = 0; i < B.length; ++i) map[B[i]] = true; // Assume integers.
for (var i = 0; i < A.length; ++i) if (map[A[i]]) doBla(A[i]);

或者,如果数字是或可能是浮点数:

var map = {};
for (var i = 0; i < B.length; ++i) map['' + B[i]] = true; // Assume integers.
for (var i = 0; i < A.length; ++i) if (map['' + A[i]]) doBla(A[i]);

由于哈希数字相当便宜(即使在JavaScript中,在散列之前转换为字符串也非常便宜),这将非常快.

Answer 2

• array_intersect() 返回匹配
• array_diff() 返回差异

Answer 3

在数据库术语中,这可以是1000行到另外1000行的连接.任何现代数据库系统都可以处理.

select x from table1
inner join table2
on table1.x = table2.y

其中,table1和table2是有关行,可能是同一个表.

Answer 4

你不应该花那么长时间 - doBla()做什么？我怀疑是花时间吗？使用相同的算法比较两组1000000个数字根本不需要时间.

这很有趣 - 作为答案的优化技术的数量 - 问题不是你的算法 - 它是什么doBla()做的是花费时间比任何优化可以帮助你多倍的因子:) esp.鉴于套装只有1000长,你必须先对它们进行排序..

Answer 5

也许只是交叉数组值来查找两个数组中存在的数字？

$result = array_intersect($numbers1, $numbers2);
foreach ($result as $val)
  doBla();

Answer 6

如果您首先对list2进行排序,然后对list1中的每个数字进行二进制搜索,您将看到速度大幅提升.

我不是一个PHP人,但这应该给你的想法:

sort($numbers2);

foreach($numbers1 as $n1)
{
   if (BinarySearch($numbers2, $n1) >= 0) {
     doBla();
 }
}

显然不是一个PHP人我不知道库,但我确信排序和二进制搜索应该很容易找到.

注意:如果您不熟悉二进制搜索; 你正在对list2进行排序,因为二进制搜索需要对排序列表进行操作.

Answer 7

先排序它们.

Answer 8

我不是PHP专家,所以这可能需要一些调试,但你可以在O(n)时间内轻松完成:

// Load one array into a hashtable, keyed by the number: O(n).
$keys1 = [];
foreach($numbers1 as $n1) $keys1[$n1] = true;

// Find the intersections with the other array:
foreach($numbers2 as $n2) { // O(n)
  if (isset($keys1[$n2]) { // O(1)
     doBla();
  }
}

无论如何,交汇点不是你的时间.即使像你现在这样糟糕的O(n ^ 2)实现也应该能够在一秒钟内完成1000个数字.

Answer 9

停 - 你为什么要这样做？

如果数字已经在SQL数据库中,那么进行连接并让DB找出最有效的路由.

如果他们不在数据库中,那么我打赌你已经离开了某个地方,真的应该重新考虑你是如何到达这里的.