큰 정수 집합의 최대 서브 세트 찾기

Question

.txt 파일에 부호없는 정수가있는 거대한 세트 (S)가 있습니다.

P{X1,X2,X3,...,Xn) | X1>=(Xn/4) 

자세한 내용 :

1. 내가 최대 집합 내가 N 요소의 최대 수 (와 하위 집합을 의미하는 말을 어떻게 다음과 같은 속성을 사용하여 최대 부분 집합 S의 (Pmax에를) 찾을 수 있습니다 -> 최대).
2. 제한된 메모리로 인해 .txt를 배열로로드 할 수 없습니다.
3. 내 시스템 메모리는 200MB입니다.
4. txt 파일의 크기는 10^6입니다. 각 정수는 부호없는 32 비트 부호 일 수 있습니다.
5. 는 I는 조건 S의 최대 집합을 찾을 필요

X1 < X2 < X3 < ... < 내지 Xn-1 < Xn에 같은 X1> = (XN/4)

4,10 (

P1 :이 가능한 부분 집합 다음 15,14,13,4,2,2,3,10,1,2,2 예 :

는 TXT 파일은 다음 경우 , 13, 14, 15)

,451,515,

P2 (3,4,10)

P3 (1,2,2,2,2,3,4)

그래서을 Pmax에 (1,2,2,2,2,3,4) 더 많은 요소가 있기 때문입니다.

실제로 나는 정확히 Pmax를 찾고 싶지 않습니다. 저는 단지 부분 집합 Pmax의 원소의 수를 찾고 싶습니다. 그래서 여기에 7입니다.

알고리즘이 정말 빨라야합니다.

나는 내 일을하는 사람을 찾지 않습니다. 문제를 해결할 필요가 있으므로 효율적인 솔루션을 찾을 수 있습니다. 미리 감사드립니다 !!!

Answer 1

쉬운 솔루션은 다음 목록은 제 (복잡도 O (nlogn) 이동 윈도우

가 최대 허용 가능한 윈도우를 찾을

1. 정렬.(복잡도 O (n))

복잡도 : O (nlogn). 2 단계에 대한

자세한 내용 :

가장 낮은 요소와 높은 가장 높은 요소의 낮은 킵 트랙을 보자.

초기화 : 첫 번째 요소를 low로 설정하십시오. 4 * x [낮음]에 대한 이진 검색을 수행하면 그 위치가 가장 좋습니다. maxWindow = high-low + 1로 설정하십시오.

모든 단계에서 : 1 씩 증가하고 x [낮음]> = x [높음]로 낮게 증가시킵니다. 요소 수 = high-low + 1을 계산하고 이에 따라 maxWindow를 업데이트하십시오.

Answer 2

조건이 "부분 집합의 모든 요소가 X1을 4로 나눈 값"이라고 가정하면 간단한 중첩 루프 2 개와 보조 변수가 필요합니다. 이 같은

의사에서 뭔가 작업을해야합니다 :

var idx = 0, largest = 0, currentIdx = 0; 

while(var current = getIntegerFromFileById(currentIdx)) 
{ 
    var size = 1; 
    while(getIntegerFromFileById(currentIdx + size++) > current/4); 
    if(size > largest) { 
    idx = currentIdx; 
    largest = size; 
    } 
    currentIdx++; 
} 
print "Longest subset is at index {idx}."; 
print "It contains {largest} consecutive elements."; 

이것은 또한 사실상 최적의 구현입니다. 가장 명백한 최적화는 이중 I/O 작업을 방지하기 위해 스캔 중에 인 메모리 버퍼에 점진적으로 정수를로드하는 것입니다.

대부분의 다른 조건에 쉽게 적응할 수있는 조건을 잘못 이해 한 경우 주변 알고리즘이 그대로 유지되므로 내부에서 조건을 수정하면됩니다.