두 세트의 1000 개 숫자를 서로 어떻게 비교할 수 있습니까?

두 세트의 1000 개 숫자를 서로 어떻게 비교할 수 있습니까?

---

약 1000 개의 숫자와 1000 개의 다른 숫자를 비교해야합니다.

둘 다로드하고 서버 측을 비교했습니다.

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

시간이 오래 걸리기 때문에 두 개의 숨겨진 div요소를 사용하여 동일한 비교 클라이언트 측을 시도했습니다 . 그런 다음 JavaScript를 사용하여 비교했습니다. 페이지를로드하는 데 여전히 45 초가 걸립니다 (숨겨진 div요소 사용).

동일하지 않은 번호를로드 할 필요가 없습니다.

더 빠른 알고리즘이 있습니까? 데이터베이스 측을 비교하고 오류 번호를로드 한 다음 나머지 비 오류 번호에 대해 Ajax 호출을 수행 할 생각입니다. 하지만 MySQL 데이터베이스가 충분히 빠르나요?

---

먼저 목록을 정렬하십시오. 그런 다음 처음부터 두 목록을 모두 살펴보고 비교할 수 있습니다.

루프는 다음과 같습니다.

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]);

숫자는 해시하기가 매우 저렴하기 때문에 (자바 스크립트에서도 해싱하기 전에 문자열로 변환하는 것이 놀랍도록 저렴합니다), 이것은 매우 빠릅니다.

---

• array_intersect() 반환 일치
• array_diff() diff를 반환합니다.

---

데이터베이스 용어로 이것은 1000 개의 행을 다른 1000 개의 행에 결합 할 수 있습니다. 모든 최신 데이터베이스 시스템이이를 처리 할 수 ​​있습니다.

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

관련된 행은 어디에 table1있으며 table2동일한 테이블이 될 수 있습니다.

---

그렇게 오래 걸리지 말아야 할 것은 doBla ()는 무엇을합니까? 시간이 걸리는 것 같아요? 같은 알고리즘으로 1000000 개의 숫자 두 세트를 비교하는 것은 시간이 전혀 걸리지 않습니다.

이것은 재밌습니다-최적화 기술의 수-문제는 알고리즘이 아닙니다-doBla ()가 수행하는 모든 작업은 최적화가 도움이 될 것보다 몇 배나 많은 시간을 소비합니다 :) esp. 세트의 길이가 1000 개에 불과하므로 먼저 정렬해야합니다.

---

두 배열에 존재하는 숫자를 찾기 위해 배열 값을 교차 할 수 있습니까?

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

---

list2를 먼저 정렬 한 다음 list1의 각 숫자에 대해 이진 검색을 수행하면 엄청난 속도 증가를 볼 수 있습니다.

난 하지 PHP는 사람, 그러나 이것은 당신에게 아이디어를 줄 것이다 :

sort($numbers2);

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

분명히 PHP 녀석은 아니지만 라이브러리를 모르지만 정렬 및 바이너리 검색이 쉽게 찾을 수있을 것입니다.

참고 : 이진 검색에 익숙하지 않은 경우; 이진 검색은 정렬 된 목록에서 작동해야하기 때문에 list2를 정렬하고 있습니다.

---

먼저 정렬하십시오.

---

저는 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) 구현도 1 초에 1000 개의 숫자를 통과 할 수 있습니다.

---

그만 -왜 이러는거야?

숫자가 이미 SQL 데이터베이스에있는 경우 조인을 수행하고 DB가 가장 효율적인 경로를 알아 내도록합니다.

그들이 데이터베이스에 없다면, 나는 당신이 어딘가에서 벗어난 것을 장담하고 당신이 여기에 어떻게 왔는지 정말로 재고해야합니다.

---

$same_numbers = array_intersect($numbers1, $$numbers2);

foreach($same_numbers as $n)
{
  doBla();
}

---

두 목록을 모두 정렬 한 다음 이전 마스터 새 마스터 순차 업데이트 패턴을 사용하여 동시에 두 목록을 살펴 봅니다. 데이터를 정렬 할 수있는 한 가장 큰 목록의 가장 긴 길이까지 목록을 한 번만 걸어 가기 때문에 가장 빠른 방법입니다.

---

귀하의 코드는 더 복잡해야 할 필요가 있습니다.

찾고있는 것이 각 위치의 숫자가 일치한다고 가정하면 (배열에 동일한 숫자가 포함되어있을뿐만 아니라) 루프를 단일 for로 평면화 할 수 있습니다.

<?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>";

?>

위의 코드를 사용하면 1000000 회 반복하는 것과 달리 1000 회만 반복합니다.

이제 숫자가 배열에 나타나는지 또는 나타나지 않는지 확인해야하는 경우 다음과 같이 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);

?>

---

아마도 여기에 뭔가가 보이지는 않지만 이것은 교차로의 고전적인 경우처럼 보입니다. 여기에 그것을 할 펄의 몇 줄이 있습니다.

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

@union = 키 % union; @isect = 키 % isect;

이 코드 줄의 끝에 @isect는 @a와 @b 모두에있는 모든 숫자를 포함합니다. 나는 이것이 PHP로 거의 직접 번역 할 수 있다고 확신합니다. FWIW, 이것은 Perl Cookbook에서 가장 좋아하는 코드입니다.

---

버킷 정렬을 사용하면 O (n) 시간에 할 수 있습니다. 숫자가 취할 수있는 최대 값을 알고 있다고 가정합니다 (그 주위에 방법이 있지만).

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

---

내장 된 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) 상각 된 것으로 가정]입니다.

업데이트 :이 알고리즘의 최악의 경우는 O (n ² )이며 프로그램의 의미를 변경하지 않는 한 줄일 방법이 없습니다. 이는 최악의 경우 두 목록의 모든 숫자가 동일 하면 프로그램이 doBla () n ² 번을 호출하기 때문입니다 . 그러나 두 목록에 고유 한 번호가있는 경우 (즉, 일반적으로 목록 내에서 고유함) 런타임은 O (n)을 향하는 경향이 있습니다.

---

Visual Basic에서 GUI 인터페이스를 만들고 숫자를 추적 할 수 있는지 확인합니다.

---

두 목록을 병합하고 두 목록의 시작 부분에서 시작한 다음 각 목록에서 유사한 숫자를 동시에 검색합니다.

따라서 의사 코드에서는 다음과 같이됩니다.

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++;

}

If I'm right, the speed of this algorithm is O(n logn).

---

I'm not sure why Mrk Mnl was downvoted but the function call is the overhead here.

Push out the matched numbers into another array and doBla() on them after the comparisons. As a test // out doBla() and see if you are experiencing the same performance issue.

---

Would it be possible to put these numbers into two database tables, and then do an INNER JOIN? This will be very efficient and provide only the numbers which are contained in both tables. This is a perfect task for a database.

---

1. Create two duplicate collections, preferably ones with fast lookup times, like HashSet or perhaps TreeSet. Avoid Lists as they have very poor lookup times.

2. As you find elements, remove them from both sets. This can reduce lookup times by having fewer elements to sift through in later searches.

---

If you're trying to get a list of numbers without any duplicates, you can use a hash:

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

It's going to be slightly (very slightly) slower than the array walk method, but it's cleaner in my opinion.

---

This code will call doBla() once for each time a value in $numbers1 is found in $numbers2:

// 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();
        }
    }
}

If you only need to call doBla() once if a match is found:

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

If $numbers1 and $numbers2 will only contain unique values, or if the number of times any specific value occurs in both arrays is not important, array_intersect() will do the job:

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

I agree with several earlier posts that the calls to doBla() are probably taking more time than iterating over the arrays.

---

This problem can be break into 2 tasks. 1st task is finding all combinations (n^2-n)/2. For n=1000 the solution is x=499500. The 2nd task is to loop through all x numbers and compare them with the function 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]);
  }
 } 

---

Merge, sort and then count

<?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));
?>

Output / the values with a count of three are the ones you want

Array
(
    [1001] => 2
    [1002] => 3
    [1003] => 3
    [1004] => 3
    [1005] => 3
    [1006] => 1
)

---

Use WebAssembly rather than JavaScript.

참고URL : https://stackoverflow.com/questions/3942551/how-can-i-compare-two-sets-of-1000-numbers-against-each-other