☰

Unix 조인 명령 복잡성

tag-icon • tag-icon performance join
Unix 조인 명령 복잡성

joinUnix 명령의 복잡성을 아는 사람이 있는지 궁금합니다 . 두 파일을 모두 정렬해야 하기 때문에 선형일 수 있다고 가정합니다.

어떤 사람들은 그것이 대수적이라고 주장하는데, 나는 그것이 의심스럽습니다. 아니면 파일에 따라 다르며 N*log(N)파일 중 하나가 더 작을 때 로그(또는)일 수 있고 두 파일이 모두 크면 선형에 가까울 수 있습니까?

답변1

BSD join구현은 따르기가 매우 쉽고 파일의 줄 수에 따라 선형적으로 확장되는 것 같습니다. 이는 최소한 BSD 4.4 Lite2부터 모든 BSD 시스템에서 본질적으로 변경되지 않았습니다. 다음 스 니펫은현재 OpenBSD 시스템, 비교하려고,다음은 BSD 4.4 Lite2 코드에 대한 링크입니다.원래 1991년 Keith Bostic이 제출한 것입니다(이 유틸리티의 이전 버전을 대체함).

/*
 * We try to let the files have the same field value, advancing
 * whoever falls behind and always advancing the file(s) we output
 * from.
*/
while (F1->setcnt && F2->setcnt) {
        cval = cmp(F1->set, F1->joinf, F2->set, F2->joinf);
        if (cval == 0) {
                /* Oh joy, oh rapture, oh beauty divine! */
                if (joinout)
                        joinlines(F1, F2);
                slurp(F1);
                slurp(F2);
        }
        else {
                if (F1->unpair
                && (cval < 0 || F2->set->cfieldc == F2->setusedc -1)) {
                        joinlines(F1, NULL);
                        slurp(F1);
                }
                else if (cval < 0)
                        /* File 1 takes the lead... */
                        slurp(F1);
                if (F2->unpair
                && (cval > 0 || F1->set->cfieldc == F1->setusedc -1)) {
                        joinlines(F2, NULL);
                        slurp(F2);
                }
                else if (cval > 0)
                        /* File 2 takes the lead... */
                        slurp(F2);
        }
}

내가 찾고 있어요joinGNU coreutils의 코드, 그러나 GNU 코드에는 내가 할 수 있는 것이 너무 많습니다.추측하다, 코드의 주석에 따르면 거의 동일한 유형의 알고리즘을 구현합니다.

/* Keep reading lines from file1 as long as they continue to
   match the current line from file2.  */

[...]

/* Keep reading lines from file2 as long as they continue to
   match the current line from file1.  */

[...]

정렬을 고려하고 정렬 알고리즘을 가정하면 값이 클수록 N*log(N)전체 시간 복잡도는 N*(1 + log(N))or가 됩니다. 즉, JOIN 작업이 정렬보다 빠릅니다.N*log(N)N

JOIN 작업을 사용하면 행을 건너뛸 수 없기 때문에 선형 작업보다 더 나은 작업을 수행할 수 없습니다(일부 설명에 대한 미리 계산된 인덱스가 있고 시간 복잡도에 인덱스를 포함하지 않는 경우). 가장 좋은 경우는 연결된 줄이 없다는 것입니다. 이 경우 두 파일 중 하나에서 모든 줄을 읽고 이를 다른 파일의 첫 번째 줄과 비교해야 합니다. 최악의 경우는 모든 행이 연결되는 것입니다. 이 경우 두 파일을 모두 읽고 두 행 집합 간에 쌍별 비교를 수행해야 합니다(정렬된 파일에 대한 선형 연산). 사용자가 짝이 없는 줄을 보라고 요청하면 두 파일을 모두 완전히 읽어야 합니다.

선형 JOIN만 사용하는 것보다 더 나쁜 작업을 수행한다면 잘못된 작업을 수행하는 것입니다.

관련 정보