는 목표 - C로 목표 - C 파일 (문자열)에

Question

새로운 가장 빈번한 단어를 인쇄,이 문제를 해결하는 데 도움이 필요합니다 :

는 두 개의 매개 변수를받는 함수 쓰기 :

• 1 텍스트 문서를 나타내는 문자열 및

• 2 반환 할 항목 수를 제공하는 정수입니다. 가장 자주 발생하는 단어 인 단어 빈도 순으로 정렬 된 문자열 목록을 반환하도록 함수를 구현합니다. 단어가 어떻게 분리되는지를 판단하기 위해 최선의 판단을 사용하십시오. 솔루션은 O (n) 시간에 실행해야합니다. 여기서 n은 문서의 문자 수입니다. 프로덕션/상업용 시스템 에서처럼이 기능을 구현하십시오. 표준 데이터 구조를 사용할 수 있습니다. 내가 지금까지 (작업 진행 중) 시도 무엇

: 진행

// -(NSString *) wordFrequency:(int)itemsToReturn inDocument:(NSString *)textDocument ; 
// Get the desktop directory (where the text document is) 

NSURL *desktopDirectory = [[NSFileManager defaultManager] URLForDirectory:NSDesktopDirectory inDomain:NSUserDomainMask appropriateForURL:nil create:NO error:nil]; 

// Create full path to the file 
NSURL *fullPath = [desktopDirectory URLByAppendingPathComponent:@"document.txt"]; 

// Load the string 
NSString *content = [NSString stringWithContentsOfURL:fullPath encoding:NSUTF8StringEncoding error:nil]; 
// Optional code for confirmation - Check that the file is here and print its content to the console 
// NSLog(@" The string is:%@", content); 

// Create an array with the words contain in the string 
    NSArray *myWords = [content componentsSeparatedByString:@" "]; 

// Optional code for confirmation - Print content of the array to the console 
// NSLog(@"array: %@", myWords); 
// Take an NSCountedSet of objects in an array and order those objects by their object count then returns a sorted array, sorted in descending order by the count of the objects. 

    NSCountedSet *countedSet = [[NSCountedSet alloc] initWithArray:myWords]; 
    NSMutableArray *dictArray = [NSMutableArray array]; 
    [countedSet enumerateObjectsUsingBlock:^(id obj, BOOL *stop) { 
    [dictArray addObject:@{@"word": obj, 
           @"count": @([countedSet countForObject:obj])}]; 
    }]; 

    NSLog(@"Words sorted by count: %@", [dictArray sortedArrayUsingDescriptors:@[[NSSortDescriptor sortDescriptorWithKey:@"count" ascending:NO]]]); 
} 
return 0; 
} 

Answer 1

에`// 함수 작업이 을지도-감소에 대한 고전적인 일이다. 나는 객관적으로 매우 익숙하다. 그러나 내가 아는 한,이 개념은 매우 쉽게 구현되어있다.

첫 번째 map-reduce는 발생 횟수를 계산합니다.
이 단계는 기본적으로 단어에 따라 요소를 그룹화 한 다음 계산합니다.

map(text): 
    for each word in text: 
     emit(word,'1') 
reduce(word,list<number>): 
    emit (word,sum(number)) 

맵 - 감소 사용에 대한 대체가 반복 계산 단어마다 차례 나오는 수를 카운트하는 것 히스토그램 해시 맵을 사용하는 것이다.

숫자와 출현 목록을 얻은 후에 실제로해야 할 일은 실제로 최고 k를 얻는 것입니다. 이 스레드에서 잘 설명됩니다 : Store the largest 5000 numbers from a stream of numbers.
여기에서 '비교 자'는 이전 단계에서 계산 된 각 단어의 일치도입니다.

기본 개념은 최소 힙을 사용하고 k 첫 번째 요소를 저장하는 것입니다.
이제 나머지 요소를 반복하고 새 요소가 힙의 최소 요소보다 큰 경우 윗 요소를 제거하고 새 요소로 바꿉니다.

끝에는 k 개의 가장 큰 요소가 들어있는 힙이 있으며 이미 힙에 있습니다. 따라서 그들은 이미 정렬되어 있습니다 (역순으로 처리되지만 상당히 쉽습니다).

복잡성 O(nlogK)

당신이 최고-K를 얻기 위해 대신 최소 힙 솔루션의 selection algorithm를 사용하고 검색된 요소를 정렬 할 수 있습니다 O(n + klogk)을 달성하는 것입니다.