0
내가 알고리즘 설계 및 분석 과정을 복용하고있어, 두 합계 문제의 변종이다 프로그래밍 질문이 주어졌다에서 매우 느린 두 합계 솔루션의 변형 :목표 C
입력은의 배열입니다 1 백만개의 정수. 양수 및 음수 모두. 입력 파일에서 x + y = t를 만족하는 고유 한 숫자 x, y가 있도록 [-10000,10000] (포함) 간격의 목표 값 t 수를 계산하십시오.
나는 작은 테스트 케이스에 대해 올바르게 문제를 해결 객관적인 C의 솔루션을 작성했습니다:
+ (BOOL)pairExistsForSum:(NSInteger)t dictionary:(NSDictionary *)dictionary
{
__block BOOL exists = NO;
[dictionary enumerateKeysAndObjectsUsingBlock:^(NSString *key, NSNumber *x, BOOL *stop) {
NSInteger y = t - x.integerValue;
NSString *yKey = [NSString stringWithFormat:@"%li", y];
if (y != x.integerValue && dictionary[yKey]) {
exists = YES;
*stop = YES;
}
}];
return exists;
}
+ (NSInteger)twoSumProblem:(NSArray <NSNumber *> *)array interval:(NSInteger)min max:(NSInteger)max
{
NSDictionary *dictionary = [self generateDictionaryOfValuesWithNumbersArray:array];
NSInteger uniquePairs = 0;
for (NSInteger i = min; i <= max; i++) {
uniquePairs += [self pairExistsForSum:i dictionary:dictionary];
}
return uniquePairs;
}
문제는 pairExistsForSum의 각 반복이 전체를 의미 완료 2 초 이상 조금 걸립니다입니다 프로세스를 완료하는 데 몇 시간이 걸릴 것입니다. 외측 변경 상보 가산
2)를 찾기 위해
1) 입력 정리 및 양 및 음 배열로 그것을 분할하고, 이진 검색을 사용하여 다음
은 I와 같은 몇몇 대안적인 접근을 시도 for 루프는 0 - 10000 범위를 탐색 한 다음 양수와 음 합 값에 대한 가수를 동시에 검색합니다.
아무런 성능도 크게 향상되지 않았으며이 문제를 하위 문제로 분해하지 않고 각 문제를 동시에 실행하지 않았습니다 t 스레드.
import time
import bisect
a = []
with open('2sum.txt', 'r') as f:
for line in f:
a.append(int(line.strip()))
a.sort()
ret = set()
for x in a:
lower = bisect.bisect_left(a, -10000 - x)
upper = bisect.bisect_right(a, 10000 - x)
for y in a[lower:upper]:
if x != y and x + y not in ret:
ret.add(x + y)
print len(ret)
이 솔루션은 초 이하의 문제로 실행 :
는 마침내 다음과 같습니다 사람의 파이썬 해결책을 발견했다. 필자는 Python에 익숙하지 않지만 바이너리 검색을 사용하고 있으며 입력 배열의 데이터를 악용하여 속도를 향상시키지 못한다고 생각합니다. 파이썬 코드가 Objective C보다 빨리 실행되기를 기대하지만,이 솔루션들의 차이는 광대합니다.
- 내가 성능 등 광대 한 차이를 설명 할이 두 솔루션의 차이에 대해 누락 것이 있습니다 :
내 질문은 다음과 같습니다?
- Objective c에서 상당한 시간 (즉, 한 시간 미만) 동안이 작업을 수행하기 위해 할 수있는 일이 무엇인지 간과 할 수 있습니까?
(누군가가 여기에 같은 질문을했습니다 : Variant of the 2-sum algorithm with a range of sums) 대답은 주어지지 않았으며, 제 생각에는 더 구체적입니다.
감사합니다.
파이썬 버전 번호를 정렬을 직접 등가물을 가지고 있지만
indexOfObject:inSortedRange:options:usingComparator:을보고 같은 값의 비교의 정의를 "학대"에 대해 조금 생각하지 않습니다 추가 할 후보자를 찾으십시오. 이렇게하면 합계가'[-10000, 10000]'범위를 벗어나는 숫자는 테스트하지 않아도됩니다. – Barmar