我怎样才能比较两组1000个号码?

我必须检查大约1000个数字与其他1000个数字。

我加载和比较他们的服务器端:

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

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

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

有一个更快的algorithm? 我想比较他们的数据库端,只是加载错误号码,然后做一个Ajax调用其余的非错误号码。 但是MySQL数据库是否足够快?

25 Solutions collect form web for “我怎样才能比较两组1000个号码?”

首先对列表进行sorting。 然后,你可以从一开始就走上这两个​​名单,比较你走。

循环看起来像这样:

 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中,散列之前转换为string是惊人的便宜),这将是非常快。

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

在数据库方面,这可以将1000行连接到另外1000行。 任何现代数据库系统都可以处理。

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

其中table1table2是有关的行,可能是同一个表。

你不应该花这么长时间 – doBla()做什么? 我怀疑是花时间? 用相同的algorithm比较两组1000000个数字根本不需要任何时间。

这很搞笑 – 优化技术的数量作为答案 – 问题不是你的algorithm – 它是doBla()所花费的时间的倍数比任何优化都要多很多倍,可以帮助你。 鉴于套只有1000长,你必须先sorting

也许只是相交的数组值来find两个数组中存在的数字?

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

如果您先对list2进行sorting,然后对list1中的每个数字进行二进制search,则会看到速度的大幅提升。

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

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

显然不是一个PHP的家伙,我不知道这个库,但我相信sorting和二进制search应该很容易find。

注意:如果您不熟悉二进制search, 你正在sortinglist2,因为二进制search需要对sorting列表进行操作。

先sorting。

我不是一个PHP专家,所以这可能需要一些debugging,但你可以在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个数字。

停止 – 你为什么这样做?

如果这些数字已经在一个SQL数据库中,那么做一个连接,让数据库找出最有效的路线。

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

 $same_numbers = array_intersect($numbers1, $$numbers2); foreach($same_numbers as $n) { doBla(); } 

对两个列表进行sorting,然后使用旧主控新主控顺序更新模式同时移动两个列表。 只要您可以对数据进行sorting,那么这是自从您真正只在列表中走一次的最快方式,到最大列表的最长长度。

你的代码只是需要更复杂的。

假设你正在寻找的是每个位置的数字匹配(而不仅仅是数组包含相同的数字),你可以将你的循环平铺为一个单一的。

 <?php // Fill two arrays with random numbers as proof. $first_array = array(1000); $second_array = array(1000); for($i=0; $i<1000; $i++) $first_array[$i] = rand(0, 1000); for($i=0; $i<1000; $i++) $second_array[$i] = rand(0, 1000); // The loop you care about. for($i=0; $i<1000; $i++) if ($first_array[$i] != $second_array[$i]) echo "Error at $i: first_array was {$first_array[$i]}, second was {$second_array[$i]}<br>"; ?> 

使用上面的代码,你将只循环1000次,而不是循环1000000次。

现在,如果您只需检查数字是否出现在数组中,请使用array_diff和array_intersect,如下所示:

 <?php // Fill two arrays with random numbers as proof. $first_array = array(1000); $second_array = array(1000); for($i=0; $i<1000; $i++) $first_array[$i] = rand(0, 1000); for($i=0; $i<1000; $i++) $second_array[$i] = rand(0, 1000); $matches = array_intersect($first_array, $second_array); $differences = array_diff($first_array, $second_array); ?> 

也许我没有看到这里的东西,但这看起来像是一个经典的交集。 这里有几行perl就可以做到。

foreach $ e(@a,@b){$ union {$ e} ++ && $ isect {$ e} ++}

@union =键%union; @isect =键%isect;

在@isect这些代码行的末尾将包含@a和@b中的所有数字。 我敢肯定,这是可以直接转换为PHP或多或less。 FWIW,这是我最喜欢的Perl Cookbook的一段代码。

如果使用桶sorting,则可以在O(n)时间内完成。 假设你知道数字可以达到的最大值(虽然有办法)。

http://en.wikipedia.org/wiki/Bucket_sort

我认为使用内build的array_intersect函数会容易得多。 用你的例子,你可以做到:

 $results = array_intersect($numbers1, $numbers2); foreach($results as $rk => $rv) { doSomething($rv); } 

更好的方法是做这样的事情:

 // 1. Create a hash map from one of the lists. var hm = { }; for (var i in list1) { if (!hm[list1[i]]) { hm[list1[i]] = 1; } else { hm[list1[i]] += 1; } } // 2. Lookup each element in the other list. for (var i in list2) { if (hm[list2[i]] >= 1) { for (var j = 0; j < hm[list2[i]]; ++j) { doBla(); } } } 

这是保证O(n)[假设在哈希映射中插入查找是O(1)摊销]。

更新:这种algorithm的最坏情况是O(n 2 ),没有办法减less – 除非你改变程序的语义。 这是因为在最坏的情况下,如果两个列表中的所有数字都相同,程序将调用doBla()n 2次。 但是,如果两个列表都有唯一的数字(即在列表中通常是唯一的),那么运行时间将趋向于O(n)。

我将在Visual Basic中创build一个GUI界面,看看我能否跟踪这些数字

合并两个列表,从两个列表开始,然后在每个列表中同时search相似的数字。

所以,在伪代码,它会像…

 Mergesort (List A); Mergesort (list B) $Apos = 0; $Bpos = 0; while( $Apos != A.Length && $Bpos != B.length) // while you have not reached the end of either list { if (A[$Apos] == B[$Bpos])// found a match doSomething(); else if (A[$Apos] > B[$Bpos]) // B is lower than A, so have B try and catch up to A. $Bpos++; else if (A[$Apos] < B[$Bpos]) // the value at A is less than the value at B, so increment B $Apos++; } 

如果我是对的,这个algorithm的速度是O(n logn)。

我不知道为什么Mrk Mnl是downvoted,但函数调用是在这里的开销

在匹配后,将匹配的数字推出到另一个数组,doBla()。 作为一个testing/ /出doBla(),看看你是否遇到同样的性能问题。

有可能把这些数字放到两个数据库表中,然后做一个INNER JOIN ? 这将是非常有效的,只提供了两个表中包含的数字。 这对于数据库来说是一个完美的任务。

  1. 创build两个重复的集合,最好是具有快速查找时间的集合,比如HashSet或者TreeSet。 避免列表,因为他们有很差的查找时间。

  2. 当你find元素,从两个集合中删除它们。 这可以通过在稍后的search中筛选更less的元素来减less查找时间。

如果你想获得一个没有任何重复的数字列表,你可以使用哈希:

 $unique = array(); foreach ($list1 as $num) { $unique[$num] = $num; } foreach ($list2 as $num) { $unique[$num] = $num; } $unique = array_keys($unique); 

这将比数组步行方法略微(稍微)慢一些,但是在我看来,它更干净。

这段代码将每次在$numbers1中find$numbers2的值时调用doBla()

 // get [val => occurences, ...] for $numbers2 $counts = array_count_values($numbers2); foreach ($numbers1 as $n1) { // if $n1 occurs in $numbers2... if (isset($counts[$n1])) { // call doBla() once for each occurence for ($i=0; $i < $counts[$n1]; $i++) { doBla(); } } } 

如果您只需要在find匹配项时调用doBla()一次:

 foreach ($numbers1 as $n1) { if (in_array($n1, $numbers2)) doBla(); } 

如果$numbers1$numbers2将仅包含唯一值,或者如果两个数组中出现任何特定值的次数都不重要,则array_intersect()将执行该任务:

 $dups = array_intersect($numbers1, $numbers2); foreach ($dups as $n) doBla(); 

我同意以前的几个post,对doBla()的调用可能需要比遍历数组花费更多的时间。

这个问题可以分解成2个任务。 第一个任务是find所有组合(n ^ 2-n)/ 2。 对于n = 1000,解决scheme是x = 499500。 第二项任务是遍历所有x个数字,并将它们与函数doBla()进行比较。

 function getWayStr(curr) { var nextAbove = -1; for (var i = curr + 1; i < waypoints.length; ++i) { if (nextAbove == -1) { nextAbove = i; } else { wayStr.push(waypoints[i]); wayStr.push(waypoints[curr]); } } if (nextAbove != -1) { wayStr.push(waypoints[nextAbove]); getWayStr(nextAbove); wayStr.push(waypoints[curr]); } } 

合并,sorting,然后数

 <?php $first = array('1001', '1002', '1003', '1004', '1005'); $second = array('1002', '1003', '1004', '1005', '1006'); $merged = array_merge($first, $first, $second); sort($merged); print_r(array_count_values($merged)); ?> 

输出/数值为三是你想要的

 Array ( [1001] => 2 [1002] => 3 [1003] => 3 [1004] => 3 [1005] => 3 [1006] => 1 ) 
  • 从date范围中生成date
  • 通过ID删除数百万行的最佳方法
  • ORDER BY IN值列表
  • search数据库的所有表,行和列中的string
  • 通过SQLAlchemy获取随机行
  • dynamic数据库模式
  • 如何从MySQL中select删除?
  • 如何在PATINDEX模式参数中转义下划线字符?
  • PostgreSQL函数中语言sql和语言plpgsql的区别
  • CodeIgniter会自动阻止SQL注入吗?
  • SQL Server脚本来创build一个新的用户