algorithm - programming - 알고리즘 종류




주어진 40 억 개가 아닌 정수를 찾습니다. (20)

인터뷰 질문입니다.

40 억 개의 정수가있는 입력 파일이 있으면 파일에 포함되지 않은 정수를 생성하는 알고리즘을 제공하십시오. 1GB 메모리가 있다고 가정하십시오. 10MB의 메모리 만 있으면 어떻게 할지를 확인하십시오.

내 분석 :

파일의 크기는 4 × 10 9 × 4 바이트 = 16GB입니다.

우리는 외부 정렬을 할 수 있으므로 정수의 범위를 알 수 있습니다. 내 질문에 정렬 된 큰 정수 집합의 누락 된 정수를 검색하는 가장 좋은 방법은 무엇입니까?

내 이해 (모든 대답을 읽은 후) :

우리가 32 비트 정수에 대해 이야기하고 있다고 가정합니다. 2 ^ 32 = 4 * 10 9 개의 고유 한 정수가 있습니다.

사례 1 : 1GB = 1 * 10 9 * 8 비트 = 80 억 비트 메모리. 솔루션 : 하나의 고유 한 정수를 나타내는 1 비트를 사용하면 충분합니다. 우리는 정렬 할 필요가 없습니다. 이행:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

사례 2 : 10MB 메모리 = 10 * 10 6 * 8 비트 = 8 천만 비트

Solution: For all possible 16-bit prefixes, there are 2^16 number of
integers = 65536, we need 2^16 * 4 * 8 = 2 million bits. We need build
65536 buckets. For each bucket, we need 4 bytes holding all possibilities because
 the worst case is all the 4 billion integers belong to the same bucket.

step1: Build the counter of each bucket through the first pass through the file.
step2: Scan the buckets, find the first one who has less than 65536 hit.
step3: Build new buckets whose high 16-bit prefixes are we found in step2
through second pass of the file
step4: Scan the buckets built in step3, find the first bucket which doesnt
have a hit.

The code is very similar to above one.

결론 : 증가하는 파일 통과를 통해 메모리를 줄입니다.

늦게 도착한 사람들에 대한 설명 : 질문에 따르면, 파일에 포함되지 않은 정수가 정확히 하나는 아니라고 말하지 않습니다. 적어도 대부분의 사람들이 해석하는 방식이 아닙니다. 댓글 스레드의 많은 댓글은 작업의 변형에 관한 것입니다. 불행히도 주석 스레드에 소개 된 주석은 나중에 작성자에 의해 삭제되었으므로 이제는 고아 응답이 모든 것을 오해 한 것처럼 보입니다. 매우 혼란 스럽습니다. 죄송합니다.


파일에서 공백과 숫자가 아닌 문자를 제거하고 1을 추가하십시오. 이제 파일에 원본 파일에 나열되지 않은 단일 번호가 포함됩니다.

Carbonetc의 Reddit에서.


1GB RAM 변형의 경우 비트 벡터를 사용할 수 있습니다. 40 억 비트 = 500MB 바이트 배열을 할당해야합니다. 입력에서 읽은 각 숫자에 대해 해당 비트를 '1'로 설정하십시오. 일단 당신이 끝내면, 비트를 반복하고, 여전히 '0'인 첫 번째 것을 찾으십시오. 그것의 색인은 대답입니다.


[0, 2 ^ x - 1] 범위에서 하나의 정수가 누락 된 경우 모두 합쳐서 합치십시오. 예 :

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(이 질문에 정확히 대답하지 않는 것을 알고 있지만 매우 비슷한 질문에 대한 좋은 답변입니다.)


그들은 값이 큰 세트의 일부가 아닌 경우 매우 효율적으로 절대적으로 결정할 수있는 확률 적 블룸 필터에 대해 들어 본 적이 있는지 찾고있을 것입니다 (그러나 확률이 높을 때만 세트의 멤버입니다).


숫자의 범위가 항상 2 ^ n (2의 짝수이면)이라고 가정하면 exclusive-or가 작동합니다 (다른 포스터에서 보여지는 것처럼). 왜까지, 그것을 증명하자 :

이론

하나의 요소가 누락 된 2^n 요소가있는 0부터 시작하는 정수 범위가 주어지면 누락 된 수를 산출하기 위해 알려진 값을 함께 xoring하여 누락 된 요소를 찾을 수 있습니다.

증거

n = 2를 보자. n = 2 인 경우 4 개의 고유 한 정수 0, 1, 2, 3을 나타낼 수있다.

  • 0 ~ 00
  • 1 - 01
  • 2 - 10
  • 3 - 11

자, 우리가 본다면, 모든 비트는 정확히 두 번 설정됩니다. 따라서 짝수 번 설정되기 때문에 숫자의 배타적 논리합은 0이됩니다. 단일 숫자가 누락 된 경우 배타적 논리합은 누락 된 숫자와 배타적 논리합을 사용하면 따라서 누락 된 수와 결과로 나오는 배제 된 수는 정확히 동일합니다. 2를 제거하면 결과 xor는 10 (또는 2)가됩니다.

이제 n + 1을 살펴 보겠습니다.의 각 비트에 설정 한 횟수 부르 자 n, x각 비트가 설정 횟수를 n+1 y. 의 값은 y동일 할 것이다 y = x * 2있기 때문에 x요소와 n+10으로 설정된 비트 및 x을 가진 요소 n+1가 1로 설정된 비트 이후 2x항상 짝수가 될 것이며, n+1항상 각 비트 횟수로 설정 한 것이다.

그러므로, n=2작품과 n+1작품, xor 메서드는 모든 값에 대해 작동합니다 n>=2.

0 기반 범위 알고리즘

이것은 아주 간단합니다.2 * n 비트의 메모리를 사용하기 때문에 32 비트 이하의 정수이면 32 비트 정수가 작동합니다 (파일 설명자가 사용하는 메모리는 무시). 그리고 파일을 한 번 전달합니다.

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

임의의 범위에 대한 알고리즘

이 알고리즘은 총 범위가 2 ^ n과 같은 한 모든 시작 번호의 범위에서 작동합니다. 기본적으로 범위는 최소 0이되도록 다시 설정됩니다. 그러나 2 번 통과해야합니다 파일을 통해 (첫 번째는 최소값을, 두 번째 값은 누락 된 int를 계산합니다.)

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

임의의 범위

모든 범위는 최소한 2 ^ n의 거듭 제곱을 넘기 때문에이 수정 된 방법을 임의의 범위 집합에 적용 할 수 있습니다. 누락 된 비트가 하나만있는 경우에만 작동합니다. 정렬되지 않은 파일을 2 회 통과하지만 매번 누락 된 단일 번호를 찾습니다.

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

기본적으로 범위를 다시 0으로 설정합니다. 그런 다음 배타적 논리합을 계산할 때 추가 할 정렬되지 않은 값의 수를 계산합니다. 그런 다음 누락 값을 처리하기 위해 정렬되지 않은 값 개수에 1을 더합니다 (누락 값 계산). 그런 다음 n을 2의 거듭 제곱이 될 때까지 매 xoring을 n 값으로 유지하고 매번 1 씩 증가시킵니다. 결과는 다시 원래 기준으로 다시 계산됩니다. 끝난.

다음은 PHP에서 테스트 한 알고리즘입니다 (파일 대신 배열을 사용하지만 같은 개념 임).

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

그 범위 내에서 누락 된 하나의 값을 가진 모든 범위의 값 (나는 네거티브를 포함하여 테스트 됨)을 가진 배열에서 연쇄 적으로 매번 올바른 값을 발견했습니다.

또 다른 접근법

외부 정렬을 사용할 수 있으므로 간격을 확인하는 것이 가장 좋은 이유는 무엇입니까? 이 알고리즘을 실행하기 전에 파일을 정렬한다고 가정하면 :

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;

왜 그렇게 복잡한가? 파일에없는 정수를 요청합니까?

지정된 규칙에 따라 저장해야하는 것은 파일에서 지금까지 만난 가장 큰 정수입니다. 전체 파일을 읽은 후 그보다 큰 숫자 1을 반환하십시오.

규칙에 따라 알고리즘의 반환 값이나 정수의 크기에는 제한이 없으므로 maxint 또는 기타 어떤 것을 사용할 위험이 없습니다.


이 문제에 대한 자세한 논의는 Jon Bentley "Column 1. Cracking the Oyster" 프로그래밍 진주 Addison-Wesley pp.3-10

Bentley는 외부 정렬, 여러 개의 외부 파일을 사용한 병합 정렬 등 몇 가지 접근법에 대해 설명합니다. 그러나 Bentley가 제안한 최선의 방법은 비트 필드를 사용하는 단일 패스 알고리즘으로 "유머 정렬"이라고 유머러스하게 부릅니다 :) 문제가 발생하면 40 억 숫자는 다음과 같이 나타낼 수 있습니다.

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

비트 셋을 구현하는 코드는 간단합니다 ( 솔루션 페이지 에서 가져옴)

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

Bentley의 알고리즘은 파일을 한 번 통과시켜 배열의 적절한 비트를 set 한 다음 위의 test 매크로를 사용하여이 배열을 test 하여 누락 된 번호를 찾습니다.

사용 가능한 메모리가 0.466GB보다 작 으면 Bentley는 입력을 사용 가능한 메모리에 따라 범위로 나누는 k-pass 알고리즘을 제안합니다. 아주 간단한 예를 들자면, 1 바이트 (예 : 8 개의 숫자를 처리하는 메모리)를 사용할 수 있었고 범위가 0에서 31까지였던 경우이를 0에서 7, 8-15, 16-22의 범위로 나누었습니다 32/8 = 4 패스 각각에서이 범위를 처리하십시오.

HTH.


이것은 바이너리 검색의 변형을 사용하여 매우 적은 공간에서 해결할 수 있습니다.

  1. 허용되는 숫자 범위 ( 0 ~ 4294967295 부터 시작하십시오.

  2. 중간 점을 계산하십시오.

  3. 얼마나 많은 숫자가 같은지, 중간 값보다 작거나 높은지를 계산하여 파일을 반복합니다.

  4. 숫자가 같지 않으면 완료됩니다. 중점 번호가 답입니다.

  5. 그렇지 않은 경우 숫자가 가장 적은 범위를 선택하고 2 단계부터이 새 범위로 반복하십시오.

파일을 통해 최대 32 개의 선형 스캔이 필요하지만 범위와 카운트를 저장하는 데 몇 바이트의 메모리 만 사용합니다.

이것은 본질적으로 Henning의 솔루션 과 동일합니다. 단 16k가 아닌 2 개의 bin을 사용한다는 점이 다릅니다.


통계적으로 정보가 제공되는 알고리즘은 결정 론적 접근 방식보다 적은 수의 패스를 사용하여이 문제를 해결합니다.

매우 큰 정수가 허용되면 O (1) 시간에 고유 한 숫자를 생성 할 수 있습니다. GUID 와 같은 의사 - 무작위 128 비트 정수는 집합의 기존 40 억 정수 중 하나와 만 충돌 할 수 있습니다.

정수가 32 비트로 제한되는 경우 10MB보다 훨씬 적게 사용하여 단일 패스에서 고유 할 가능성이있는 숫자를 생성 할 수 있습니다. 의사 랜덤 32 비트 정수가 40 억 개의 기존 정수 중 하나와 충돌 할 확률은 약 93 % (4e9 / 2 ^ 32)입니다. 1000 개의 의사 무작위 정수가 모두 충돌 할 확률은 12,000,000,000,000,000,000 (1 대 충돌 = 1000)에서 1 미만입니다. 따라서 프로그램이 1000 개의 의사 무작위 후보를 포함하는 데이터 구조를 유지하고 알려진 정수를 반복하면서 후보와의 일치를 제거하면 파일에없는 정수 하나를 찾는 것이 확실합니다.


10MB 메모리 제약 조건의 경우 :

  1. 숫자를 이진 표현으로 변환하십시오.
  2. left = 0 및 right = 1 인 곳에 이진 트리를 만듭니다.
  3. 이진 표현을 사용하여 트리에 각 숫자를 삽입하십시오.
  4. 숫자가 이미 삽입 된 경우 리프가 이미 만들어졌습니다.

완료되면 요청한 번호를 생성하기 전에 이전에 생성되지 않은 경로를 가져옵니다.

40 억 번호 = 2 ^ 32, 즉 10MB는 충분하지 않을 수 있습니다.

편집하다

최적화가 가능합니다. 두 개의 leaf가 만들어지고 공통 부모가있는 경우 제거가 가능하고 부모는 솔루션이 아닌 것으로 플래그가 지정됩니다. 이것은 분기를 줄이고 메모리에 대한 필요성을 줄입니다.

EDIT II

나무를 완전히 만들 필요도 없습니다. 숫자가 유사한 경우에만 깊은 브랜치를 작성하면됩니다. 우리가 가지를 잘랐다면,이 해결책이 실제로 작동 할 수도 있습니다.


"정수"는 32 비트를 의미한다고 가정합니다 . 10MB의 공간을 사용하면 주어진 16 비트 접두사가있는 입력 파일에 몇 개의 숫자가 있는지 계산할 수 있습니다. 한 번에 모든 가능한 16 비트 접두사를 찾습니다. 입력 파일 버킷 중 적어도 하나는 2 ^ 16보다 적게 칠 것입니다. 해당 버킷에서 가능한 숫자 중 어느 것이 이미 사용되었는지 찾기 위해 두 번째 패스를 수행합니다.

32 비트 이상이지만 제한된 크기를 의미하는 경우 위와 같이 수행하여 32 비트 범위 (부호있는 또는 부호없는, 선택 사항)의 범위를 벗어나는 모든 입력 번호를 무시합니다.

"정수"가 수학 정수를 의미하는 경우 : 입력을 한 번 읽고 가장 긴 숫자 중에서 가장 긴 숫자의 길이를 추적하십시오. 작업이 끝나면 최대 한 자리에 하나 이상의 숫자가있는 임의의 숫자를 더한 값을 출력 하십시오 . (파일의 숫자 중 하나는 10MB 이상을 필요로하는 bignum 일 수 있지만 입력이 파일이면 적어도 맞는 파일의 길이 를 나타낼 수 있습니다.


비트 제거

한 가지 방법은 비트를 제거하는 것입니다. 그러나 실제로 결과를 얻지 못할 수도 있습니다 (가능성은 없습니다). Psuedocode :

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

비트 수

비트 수를 추적하십시오. 값을 생성하기 위해 가장 적은 양의 비트를 사용하십시오. 다시 말하지만 올바른 값을 생성 할 수는 없습니다.

범위 논리

목록 정렬 된 범위를 추적하십시오 (시작순 정렬). 범위는 구조에 의해 정의됩니다.

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

파일의 각 값을 검토하여 현재 범위에서 제거하십시오. 이 방법은 메모리 보장이 없지만 꽤 잘 수행됩니다.


Ryan이 기본적으로 말했듯이 파일을 정렬 한 다음 정수로 넘어 가서 값을 건너 뛰면 다음과 같이됩니다. :)

downvoters에서 편집 : OP는 파일이 정렬 될 수 있다고 언급 했으므로 유효한 방법입니다.


나는 1 GB 버전에 대답 할 것이다 :

질문에 충분한 정보가 없으므로 먼저 몇 가지 가정을 설명 할 것입니다.

정수는 32 비트이고 범위는 -2,147,483,648에서 2,147,483,647 사이입니다.

의사 코드 :

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

완벽을 기하기 위해 실행하는 데 아주 오랜 시간이 걸리지 만 메모리는 거의 사용하지 않는 매우 간단한 솔루션이 있습니다.

가능한 모든 정수가 int_minto 에서 to 범위가 되도록하고 int_max, bool isNotInFile(integer)파일에 특정 정수가 포함되지 않은 경우 true를 반환하고 파일에서 각 정수와 특정 정수를 비교하여 false를 반환하는 함수를 반환합니다.

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

우리가 창조적 인 답변을하는 한 여기 또 하나가 있습니다.

외부 정렬 프로그램을 사용하여 입력 파일을 숫자순으로 정렬하십시오. 이것은 필요한 모든 용량의 메모리에서 작동합니다 (필요한 경우 파일 저장 공간을 사용합니다). 정렬 된 파일을 읽고 누락 된 첫 번째 숫자를 출력하십시오.


2 128 * 10 18 + 1 ((2 8 ) 16 * 10 18 +1) - 오늘날 보편적 인 대답이 될 수 없는가? 이것은 현재 파일 시스템의 최대 파일 크기 인 16 EB 파일에 보관할 수없는 숫자를 나타냅니다.


32 비트 제약 조건을 가정하지 않으면 무작위로 생성 된 64 비트 숫자 (또는 비관적 인 경우 128 비트) 만 반환하면됩니다. 충돌 가능성은 1 in 2^64/(4*10^9) = 4611686018.4(대략 40 억에 1). 당신은 대부분의 시간 맞을거야!

농담하는거야.)


어떤 이유로,이 문제를 읽 자마자 대각선 화를 생각했습니다. 저는 임의로 큰 정수를 추측하고 있습니다.

첫 번째 숫자를 읽으십시오. 네 번째 비트가 40 억이 될 때까지 0 비트로 왼쪽 패드합니다. 첫 번째 (상위) 비트가 0이면 출력 1입니다. 그렇지 않으면 출력 0입니다. (실제로는 왼쪽 패드가 필요하지 않습니다. 숫자에 충분한 비트가 없으면 1을 출력합니다.) 두 번째 숫자는 두 번째 비트를 사용하는 것을 제외하고는 두 번째 숫자와 동일하게 수행하십시오. 이 방법으로 파일을 계속 진행하십시오. 한 번에 한 비트 씩 40 억 비트의 비트를 출력하며이 숫자는 파일의 모든 것과 동일하지 않습니다. 증명 : 그것은 n 번째 숫자와 같았고, n 번째 비트에서 동의 할 것이지만, 그들은 건설에 의한 것이 아닙니다.


입력 파일의 사이즈, 다음 출력 확인 임의 인 수의 파일이 크기로 표시하기에 너무 큰있다. 이것은 싼 속임수처럼 보일지 모르지만, 인터뷰 문제에 대한 창조적 인 해결책이며, 기억 문제를 깔끔하게 회피합니다. 기술적으로 O (n)입니다.

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

10 bitcount - 1을 출력해야 하는데, 항상 2 bitcount 보다 커야 합니다. 기술적으로 파일에 다른 정수가 있다는 것을 알고 있기 때문에 2 비트 카운트 (4 * 10 9 - 1) 이며, 완벽한 압축을하더라도 최소한 각각 1 비트.







algorithm