어떻게 하면 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++;
}
(그것은 자바스크립트입니다; 당신은 서버 쪽에서도 할 수 있지만, 저는 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]);
숫자는 해시하기에 꽤 저렴하기 때문에(자바스크립트에서도 해시하기 전에 문자열로 변환하는 것이 놀라울 정도로 저렴합니다), 이것은 꽤 빠를 것입니다.
데이터베이스 측면에서는 1000개 행을 다른 1000개 행에 조인할 수 있습니다.모든 최신 데이터베이스 시스템이 이를 처리할 수 있습니다.
select x from table1
inner join table2
on table1.x = table2.y
table1그리고.table2관련된 행이며 동일한 테이블일 수 있습니다.
당신이 가지고 있는 것은 그렇게 오래 걸리지 않아야 합니다 - Bla()는 무엇을 합니까?그것이 시간이 걸리는 것이 아닌가요?1000000 숫자의 두 집합을 동일한 알고리즘으로 비교하는 것은 시간이 전혀 걸리지 않습니다.
이것은 정말 웃깁니다. 답변으로서의 최적화 기술의 수 - 문제는 당신의 알고리즘이 아닙니다 - 어떤 최적화보다 몇 배 더 많은 시간이 걸리는 Bla()가 무엇을 하든지 간에: 특히 세트가 단지 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();
}
두 목록을 정렬한 다음 이전 마스터 새 마스터 순차 업데이트 패턴을 사용하여 두 목록을 동시에 이동합니다.데이터를 정렬할 수 있는 한 이 방법은 목록을 한 번만 걷게 되므로 가장 빠른 방법입니다. 가장 큰 목록 중 가장 긴 길이입니다.
당신의 코드는 필요 이상으로 복잡합니다.
각 위치의 숫자가 일치하고 배열에 동일한 숫자만 포함되어 있지 않다고 가정하면 루프를 단일 위치로 평탄화할 수 있습니다.
<?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);
?>
여기서 뭔가 보이지 않을 수도 있지만 이것은 전형적인 세트 교차로처럼 보입니다.여기 펄로 된 몇 줄이 있습니다.
각 $e(@a, @b) {$union{$e}+++ & $isect{$e}++}에 대해
@union = 키 %union; @isect = 키 %isect;
이러한 코드 줄 끝에 @isect는 @a와 @b에 있는 모든 숫자를 포함합니다.저는 이것이 어느 정도 직접적으로 php로 번역될 수 있다고 확신합니다.FWIW, 이것은 펄 쿡북에서 내가 가장 좋아하는 코드 조각입니다.
버킷 정렬을 사용하면 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(n2)이며 프로그램의 의미를 변경하지 않는 한 줄일 방법이 없습니다.이는 최악의 경우 두 목록의 모든 번호가 동일할 경우 프로그램이 doBla()를2 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++;
}
제 말이 맞다면, 이 알고리즘의 속도는 O(nlogn)입니다.
Mrk Mnl이 왜 부결되었는지는 모르겠지만 함수 호출은 여기서 오버헤드입니다.
일치하는 숫자를 다른 배열로 밀어내고 비교 후 Bla()를 수행합니다.테스트로 // Bla()를 실행하여 동일한 성능 문제가 발생하는지 확인합니다.
이 숫자들을 두 개의 데이터베이스 테이블에 넣고 다음을 수행할 수 있습니까?INNER JOIN이는 매우 효율적이며 두 표에 포함된 숫자만 제공합니다.이것은 데이터베이스에 완벽한 작업입니다.
중복 컬렉션을 두 개 만듭니다. 가급적이면 HashSet 또는 TreeSet과 같이 조회 시간이 빠른 컬렉션을 만듭니다.목록의 조회 시간이 매우 낮으므로 목록을 피합니다.
요소를 찾으면 두 집합에서 요소를 제거합니다.이렇게 하면 이후 검색에서 자세히 살펴볼 요소가 적어 조회 시간을 줄일 수 있습니다.
중복되지 않은 숫자 목록을 가져오려는 경우 해시를 사용할 수 있습니다.
$unique = array();
foreach ($list1 as $num) {
$unique[$num] = $num;
}
foreach ($list2 as $num) {
$unique[$num] = $num;
}
$unique = array_keys($unique);
어레이 워크 방식보다 약간 느리겠지만, 제 생각에는 더 깨끗합니다.
이 코드는 다음을 호출합니다.doBla()값을 매회 한 번$numbers1에서 찾을 수 있습니다.$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();
}
}
}
전화만 하면 되는 경우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();
나는 전화가 온 몇 개의 이전 게시물에 동의합니다.doBla()어레이를 반복하는 것보다 더 많은 시간이 소요될 수 있습니다.
이 문제는 두 가지 과제로 나눌 수 있습니다.첫 번째 과제는 모든 조합(n^2-n)/2를 찾는 것입니다.n=1000의 경우 솔루션은 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]);
}
}
병합, 정렬 및 카운트
<?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));
?>
출력 / 카운트가 3인 값이 원하는 값입니다.
Array
(
[1001] => 2
[1002] => 3
[1003] => 3
[1004] => 3
[1005] => 3
[1006] => 1
)
JavaScript 대신 WebAssembly를 사용합니다.
언급URL : https://stackoverflow.com/questions/3942551/how-can-i-compare-two-sets-of-1000-numbers-against-each-other
'programing' 카테고리의 다른 글
| 메이븐에서 Spring Boot 테스트를 실행하지 않음 (0) | 2023.08.26 |
|---|---|
| FFMPEG 라이브러리를 사용하여 RTSP 스트림 수신 (0) | 2023.08.26 |
| PHP는 cron 작업에서 실행되는지 명령줄에서 실행되는지 탐지할 수 있습니까? (0) | 2023.08.21 |
| python's sorted()는 어떤 알고리즘을 사용합니까? (0) | 2023.08.21 |
| Kubernetes에 MariaDB ColumnStore를 설치하는 방법은 무엇입니까? (0) | 2023.08.21 |