NSMutableDictionary에서 keysSortedByValueUsingComparator 메서드를 사용하는 속도는 무엇입니까

Question

NSMutableDictionary를 정렬 된 순서대로 키 : 낮은 값의 키가 먼저 인쇄되는 키와 같은 값으로 인쇄하고 싶습니다.

이렇게하려면 아래의 NSDictionary의 keysSortedByValueUsingComparator : 메서드를 사용하고 있습니다.

기본 구현에서 빠른 정렬과 같은 접근 방식을 사용하고 O (N * logN)을 달성하는지 또는 모든 객체를 O (N^2) 복잡도로 이끄는 다른 모든 객체와 비교하는지 아는 사람이 있습니까?

는

예 : - 물론 O는 (N 로그 N)

NSMutableDictionary *hashTable = [[NSMutableDictionary alloc] init]; 
.... 
code that adds a bunch of Objects to the hashtable dictionary with key = NSString and value = NSNumber object 
.... 
NSArray * sortedKeys = [hashTable keysSortedByValueUsingComparator:^(id _Nonnull obj1, id _Nonnull obj2) { 
      if ([obj1 integerValue] > [obj2 integerValue]) 
      { 
       return (NSComparisonResult)NSOrderedDescending; 
      } 

      if ([obj1 integerValue] < [obj2 integerValue]) 
      { 
       return (NSComparisonResult)NSOrderedAscending; 
      } 

      return (NSComparisonResult)NSOrderedSame; 
     }]; 

for (NSString *nextKey in sortedKeys) 
{ 
    NSLog(@"%@: %@",nextKey,hashTable[nextKey]); 
} 

Answer 1

이 병합 정렬을 사용하여 나타납니다. 다른 정렬 방법은 quicksort를 사용하는 것으로 알려져 있습니다.

추측 방법 : 비교기 블록 안에 중단 점을 배치하고 적중 될 때 스택 추적을 읽습니다. 코드에서 비교기가 CFSimpleMergeSort에 의해 호출되는 것을 볼 수 있습니다. Apple 프로그래머가 흥미로운 이름 지정 체계를 가지고 있지 않으면 병합 정렬이라고 생각하는 것이 좋습니다!

아마도 NS 메인 콜렉션은 CF 대응 브릿지로 수신자 부담이며, CF 소스는 애플의 오픈 소스 사이트에서 구할 수 있습니다. CFArray.c, CFDictionary.c 등을 검색하면 소스를 찾을 수 있습니다. 여기에는 모든 NS 메서드가 포함되지 않으므로 "찾을 수 있습니다."하지만 이러한 형식의 작동 방식을 보여줍니다.

HTH