objective-c 복잡성 참조

C++ STL의 경우 표준 컨테이너 작업의 복잡성 보장에 대한 정보를 찾으려면 de-jour standard 외에도 de-facto standard location이 있습니다.objective-c 복잡성 참조

NSArray, NSDictionary 등의 복잡성을 보장하는 유사한 웹 접근 문서 목록이 있습니까?

예를 들어, 내가 올바른 [NSArray count]

2012-03-31 JRG

음 ... STL은 C++ 표준입니다. 코코아는 독점적 인 프레임 워크입니다. 나는 그들이 비교할 만하다고 생각하지 않는다. 폐쇄 형 소스이므로 문서 외에도 다른 참조 정보는 없습니다. –

@HeShiming; 다시 읽으십시오. 이것은 코코아가 아닌 objective-c에 관한 질문입니다. – JRG

'NSArray'와'NSDictionary'는 사실'Foundation' 프레임 워크의 일부입니다. 그러나 Heim Shiming이 말한 것은 Apple 프레임 워크이기 때문에 여전히 보유하고 있습니다. – Saphrosit

복잡성을 제공하는 참조를 찾을 수 없습니다. 하나도 없다. C++/STL (필자의 제한된 이해를 기반으로 함)은 중대한 성능에 중점을 둡니다. 목표 -C/Foundation은 기본적으로하지 않습니다.

NSArray, NSDictionary 및 친구들은 인터페이스입니다. 그들은 어떻게 행동하는지가 아니라 어떻게 사용하는지 알려줍니다. 이로 인해 성능상의 이유로 구현 변경을 자유롭게 할 수 있습니다. 요점은, 신경 쓰지 않아도되며, API에서 지정되지 않으므로 원할 경우조차 할 수 없다는 것입니다.)

이 주제에 대한 실제 읽기 내용은 구현 스위치 , 및 기초 클래스와 STL/C 데이터 구조 사이의 대략적인 비교로, blog post about "Our arrays, aren't"

출처

2012-03-31 14:18:55

+1 어리석은 물고기에 대한 링크! – zaph

... 링크 된 게시물을 읽으면 "배열의 값에 대한 액세스 시간이 최악의 O (lg N)임을 보장합니다"라고 표시됩니다. 모든 오브젝트에 대해 유사한 명령문을 포함하는 참조를 원합니다. – JRG

.. 당신은 아주 좋은 지적을합니다. CoreFoundation 소스를 보았을 때, CFArray, CFDictionary 등의 구문이 존재하지만, Foundation 오브젝트와 비슷한 것은 없다고 생각합니다. 그러나 이제는 더 많은 검색을 할 것입니다 ... –

-1

복잡성을 보증을 나열 유사한 웹 액세스 문서가 있는가 (애플 AppKit의 팀에 사람이) 어리석은 물고기를 체크 아웃 NSArray, NSDictionary, 등?

아니요. 다른 컨테이너의 기능을 이해하면 어떻게 동작하는지 (예 : 사전 ==지도 - 거의 일정 시간 조회) 이해할 수 있습니다. 그러나 그들이 change their behavior based on circumstances 일 수 있기 때문에 이러한 구조가 어떻게 행동하는지 정확하게 알고 있다고 가정하지 마십시오. 다시 말해, NSArray와 같은 클래스는 동일한 "순서가 지정된 요소 순서"동작을 가지고 있더라도 C 스타일 배열의 의미로 실제 배열로 구현되지 않을 수도 있습니다.

물론 자신의 코드의 복잡도를 분석 할 수 있습니다. NSArray를 통한 사용자의 바이너리 검색은 항상 O (log n) 연산을 슬라이스 방식으로 수행합니다. NSMutableArray에 요소를 삽입하면 "배열"이 실제로 링크 된 목록 또는 다른 것일 수 있으므로 모든 후속 요소를 이동해야한다고 가정하지 마십시오.

출처

2012-03-31 14:22:29 Caleb

NSDictionary가 해시 맵인 것은 어디에서 언급 되었습니까? 그것은 쉽게 std :: map과 같을 수 있는데, 이는 전형적으로 적색 - 검은 색 트리로 구현됩니다. 두포가 무엇인지 모르지만 map :: find는 O (ln n)이고, map :: begin은 O (1) 등입니다. – JRG

연결된 목록 O (ln n) 걸립니까? std :: list가 :: find 또는 :: lower_bound를 구현하지 않는 이유를 생각해보십시오. – JRG

@JRG 링크 된 목록에서 이진 검색에 O (log n)가 필요하다고 말하지 않았습니다. 저는 자신의 코드를 분석하는 것에 대해 이야기하고있었습니다. NSArray에서 이진 탐색을 수행하는 코드를 작성하면 자연스럽게이 함수가 log n 연산을 수행 할 것으로 기대할 수 있습니다. 그러나 이러한 작업은 NSArray에 대한 작업입니다. 그래서 당신은'-objectAtIndex :'log를 n 번 호출 할 것이라는 것을 알 수 있습니다. 그것은 당신 자신의 코드의 복잡성입니다. 당신은'-objectAtIndex :'의 복잡성에 관여하지 않으며 상황에 따라 변경 될 수도 있습니다. 이점은 단일 알고리즘보다 더 잘 작동하는 코드입니다. – Caleb

objective-c 복잡성 참조

답변

관련 문제