Javascript 如何比较两组 1000 个数字？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3942551/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can I compare two sets of 1000 numbers against each other?
提问by baklap
I must check approximately 1000 numbers against 1000 other numbers.
我必须对照 1000 个其他数字检查大约 1000 个数字。
I loaded both and compared them server-side:
我加载了两者并在服务器端进行了比较：
foreach( $numbers1 as $n1 ) {
foreach( $numbers2 as $n2 ) {
if( $n1 == $n2 ) {
doBla();
}
}
}
This took a long time, so I tried to do the same comparison client side using two hidden
divelements. Then compared them using JavaScript. It still takes 45 seconds to load the page (using hidden divelements).
这花了很长时间，所以我尝试使用两个隐藏div元素进行相同的比较客户端
。然后使用 JavaScript 比较它们。加载页面仍然需要 45 秒（使用隐藏div元素）。
I do not need to load the numbers that are not the same.
我不需要加载不相同的数字。
Is there a faster algorithm? I am thinking of comparing them database side and just load the error numbers, then do an Ajax call for the remaining non-error numbers. But is a MySQL database fast enough?
有没有更快的算法？我正在考虑比较它们的数据库端并只加载错误号，然后对剩余的非错误号进行 Ajax 调用。但是 MySQL 数据库是否足够快？
回答by Pointy
Sort the lists first. Then you can walk up both lists from the start, comparing as you go.
首先对列表进行排序。然后你可以从一开始就遍历两个列表，边走边比较。
The loop would look something like this:
循环看起来像这样：
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++;
}
(That's JavaScript; you could do it server-side too, but I don't know PHP.)
（那是 JavaScript；你也可以在服务器端做，但我不懂 PHP。）
Edit— just to be fair to all the hashtable fans (whom I respect of course), it's pretty easy to do that in JavaScript:
编辑- 为了公平对待所有哈希表粉丝（我当然尊重他们），在 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]);
Or if the numbers are or might be floats:
或者如果数字是或可能是浮点数：
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]);
Since numbers are pretty cheap to hash (even in JavaScript, converting to string before hashing is surprisingly cheap), this would be pretty fast.
由于数字散列非常便宜（即使在 JavaScript 中，在散列之前转换为字符串也非常便宜），所以这将非常快。
回答by Phill Pafford
回答by Preet Sangha
In database terms this can a join of 1000 rows to another 1000 rows. Any modern database system can handle this.
在数据库术语中，这可以将 1000 行连接到另外 1000 行。任何现代数据库系统都可以处理这个问题。
select x from table1
inner join table2
on table1.x = table2.y
where table1and table2are the rows concerned and could be the same table.
其中table1和table2是相关的行并且可能是同一个表。
回答by markmnl
What you have shouldnt take that long - what does doBla() do? I suspect that is taking the time? Comparing two sets of 1000000 numbers with the same algorithm takes no time at all..
你不应该花那么长时间 - doBla() 做什么？我怀疑这是花时间？用相同的算法比较两组 1000000 个数字根本不需要时间。
This is hilarious - the number of optimisation techniques as answers - the problem is not your algorithm - it is whatever doBla() does that is taking the time by a factor many times greater than any optimisation would help you :) esp. given the sets are only 1000 long and you have to sort them first..
这很有趣 - 作为答案的优化技术的数量 - 问题不是你的算法 - 无论 doBla() 做什么，它所花费的时间比任何优化对你的帮助都大很多倍:) 特别是。鉴于集合只有 1000 长，你必须先对它们进行排序..
回答by sod
Maybe just intersect the array values to find numbers existing in both arrays?
也许只是将数组值相交以查找两个数组中存在的数字？
$result = array_intersect($numbers1, $numbers2);
foreach ($result as $val)
doBla();
回答by Giovanni Galbo
If you sort list2 first and then do a binary search for each number in list1 you'll see a huge speed increase.
如果您先对 list2 进行排序，然后对 list1 中的每个数字进行二分搜索，您将看到速度大幅提升。
I'm nota PHP guy, but this should give you the idea:
我不是一个 PHP 人，但这应该给你一个想法：
sort($numbers2);
foreach($numbers1 as $n1)
{
if (BinarySearch($numbers2, $n1) >= 0) {
doBla();
}
}
Obviously not being a PHP guy I don't know the library, but I'm sure sorting and binary searching should be easy enough to find.
显然不是一个 PHP 人，我不知道这个库，但我确信排序和二进制搜索应该很容易找到。
Note:In case you're not familiar with a binary search; you're sorting list2 because binary searches need to operate on sorted lists.
注意：如果您不熟悉二分查找；您正在对 list2 进行排序，因为二进制搜索需要对排序列表进行操作。
回答by JRL
Sort them first.
先把它们排序。
回答by munificent
I'm not a PHP expert, so this may need some debugging, but you can do this easily in O(n) time:
我不是 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();
}
}
Regardless, the intersection isn't where your time is going. Even a bad O(n^2) implementation like you have now should be able to go through 1000 numbers in a second.
无论如何，十字路口不是你的时间去的地方。即使像您现在这样糟糕的 O(n^2) 实现也应该能够在一秒钟内处理 1000 个数字。
回答by dethSwatch
Stop- why are you doing this?
停下- 你为什么要这样做？
If the numbers are already in a SQL database, then do a join and let the DB figure out the most efficient route.
如果这些数字已经在 SQL 数据库中，那么进行连接并让 DB 找出最有效的路线。
If they aren't in a database, then I'm betting you've gone off track somewhere and really ought to reconsider how you got here.
如果它们不在数据库中，那么我敢打赌你已经在某个地方偏离了轨道，真的应该重新考虑你是如何到达这里的。
回答by Cesar
$same_numbers = array_intersect($numbers1, $$numbers2);
foreach($same_numbers as $n)
{
doBla();
}
