Array linkedList 비교
Array
- 논리적 저장순서와 물리적 저장 순서가 일치한다.
- 인덱스로 해당 원소에 접근이 가능 -> 인덱스를 알고 있다면 O(1)으로 해당 원소에 접근할 수 있다.
- Random Access가 가능하다.
- 배열의 원소를 삭제 또는 삽입시 삽입/삭제한 원소보다 큰 인덱스들을 shift해야하기 때문에 시간복잡도 O(n)이 걸린다.
- 제한적인 크기를 갖는다. 그러나 swift에선 array가 동적 배열
LinkedList
- 자료의 주소값으로 노드를 이용해 서로 연결되어있는 구조를 갖는다.
- 삽입과 삭제의 자체는 O(1)이나 원하는 값을 찾기 위해 리스트를 순회해야 하므로 실제로는 O(n)이다.
메모리할당
-
Array에서 메모리는 Array가 선언되자 마자 Compile time에 할당되어 진다. 이것을 정적 메모리 할당이라고 한다. Stack 영역에 메모리 할당이 이루어진다.
-
LinkedList에서 메모리는 새로운 node가 추가될 때 runtime에 할당되어 진다. 이것은 동적 메모리 할당이라고 한다.Heap 영역에 메모리 할당이 이루어진다.
ArrayList vs LinkedList
ArrayList
- 내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해서 임시 배열을 생성해 데이터를 복사하는 방법을 사용한다.
- 대량의 자료를 추가/삭제 하는 경우 그만큼 데이터의 복사가 많이 일어나게 되어 성능 저하가 발생
- 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 존재해야 한다.
- 반면 인덱스를 가지고 있어서 한 번에 참조가 가능해 데이터 검색에 유리하다.
- ArrayList는 삽입과 삭제를 할 일이 없거나 배열의 끝에서만 하게 될 경우 유용하게 쓰일 수 있다. 원소에 대해 빠르게 접근할 수 있을 뿐만 아니라, 원소들이 메모리에 연속으로 배치해 있어 CPU 캐시 효율도 더욱 높다.
LinkedList
- 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있으면 된다.
- ArrayList와 달리 데이터의 추가, 삭제시 불필요한 데이터의 복사가 없어 데이터의 추가, 삭제시에 유리하다. 반면, 데이터 검색 시에는 처음부터 노드를 순회하기 때문에 성능상 불리하다.
Hash
Hashing(해싱)
- 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것
- Hash Table(해시 테이블)과 Hash Function(해시 함수)으로 구성됨
- 해시테이블(Hash Table, Hash Map이라고도 불림)은 Key와 Value를 갖는 자료구조
Hash Collision(해시 충돌)
Chaining(체이닝)
- 버켓 내에 연결리스트(Linked List)를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식
- 버켓이 꽉 차더라도 연결리스트로 계속 늘려가기에, 데이터의 주소값은 바뀌지 않는다.(Closed Addressing)
Open Addressing(개방 주소법)
- 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식
- 선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
- 제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
- 이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.
Mutex(뮤텍스)와 Semaphore(세마포어)
- 여러 프로세스나 쓰레드가 공유자원에 접근하는 것을 관리하기 위해 상호배제(Mutual Exclusion)를 달성하는 기법 -> 병행처리를 위한 프로세스 동기화기법
Mutex(뮤텍스)
- 임계영역에 들어갈 때 lock을 걸어 다른 프로세스(또는 쓰레드)가 접근하지 못하도록하고, 임계영역에서 나와 해당 락을 해제함
Semaphore(세마포어)
- semWait 연산: 세마포어 값을 감소시킴. 값이 음수가 되면 semWait를 호출한 프로세스는 블락됨. 음수가 아니면, 프로세스는 계속 수행될 수 있음.
- semSignal 연산: 세마포어 값을 증가시킵니다. 만약 값이 양수가 아니면(0 또는 음수), semWait연산에 의해 블록된 프로세스들을 깨움.
swift에선? DispatchSemaphore
let s = DispatchSemaphore(value: 0)초기값으로 0을 가지는 세마포어. 대체로 두개 이상의 스레드를 동기시 보통 0을 넣는다. 이렇게해서 signal과 wait의 쌍을 맞출 수 있다.
s.wait()wait를 호출하면 value가 감소한다. 만약 value가 0이면 signal()이 불릴 때 까지 대기
s.signal()signal 을 호출하게 되면 value 값이 증가한다.
예제
let session = NSURLSession.sharedSession()
...
let task = session.dataTaskWithRequest(someRequest) {
(data, response, error) in
if let data = data {
print("I have got data!")
...
}
}
task.resume()
print("end")위의 코드에서는 "end"가 먼저 출력되고 "I have got data!"가 출력된다.
let session = NSURLSession.sharedSession()
let semaphore = DispatchSemaphore(value: 0)
let task = session.dataTaskWithRequest(someRequest) {
(data, response, error) in
if let data = data {
print("I have got data!")
...
}
semaphore.signal()
}
task.resume()
semaphore.wait()
print("end")이렇게 semaphore를 활용하면 "I have got data!"가 출력되고 "end"가 출력됨
swift 웹소켓?
CocoaAsyncSocket
- objective-C, GCD기반 비동기 소켓 라이브러리
- thread-safe
- TCP/UDP 연결을 지원, 클라이언트, 서버 모두 구현가능
socket.io
- 클라이언트만 구현 가능
CocoaAsyncSocket vs Socket.IO
구현: delegate위주 vs 클로져위주
용량: 비교적 적은 파일 vs 비교적 많은 파일(다른 라이브러리 의존)
문서: 참고레퍼런스 부족 vs 참고 문서 많음
접근성: Swift특화 vs 모든 플랫폼
데이터: 비트단위 vs 원하는 이벤트명을 달아서 데이터 전송가능
참고 및 출처
iOS시작~