자바로 배우는 핵심 자료구조와 알고리즘

저자는 앨런 B. 다우니. 초판은 2018년 6월에 인쇄. 

자바를 공부하는 중이라 자바에 좀더 익숙해지면서 자료구조나 알고리즘 공부도 할겸 선택한 책. 이전에 보았던 '누구나 자료구조와 알고리즘' 책이 자료구조와 알고리즘에 대한 기초적인 지식을 다질 수 있는 입문자용 책이라면, 이 책은 그 보다는 조금 더 현실적으로 접근하는, 즉, 자바 구현한 코드를 이용하여 좀더 실전적으로 익힐 수 있는 책인 듯하다. 물론 이책 또한 자료구조와 알고리즘에 대해여 학구적으로 깊이있게 파고드는 것은 아닌지라 초-중급 정도의 난이도 인 듯하다.   

   책에서 다루는 내용 또는 내용 정리

자료 구조는 Linked List, Array List, Doubly Linked List, Hash Table, Stack, Tree 구현방법 및 특징

Profiler 클래스 : 문제 크기의 범위를 인자로 받아 실행하는 코드를 포함하며 실행시간을 측정하고 결과를 그래프로 출력. 메서드나 클래스의 성능(시간적) 측정할대 사용가능

알고리즘 분석은 자료 구조를 선택하는 지침을 제공하지만, 아래의 조건일 때만 유효

• 응용 프로그램의 실행시간이 중요하다.
• 응용 프로그램의 실행 시간이 선택한 자료 구조에 의존한다. 
• 증가 차수에 따라 어느 자료구조가 나은지 실제로 예측할 수 있을 만큼 문제가 충분히 크다.

크롤링(Crawling) : 웹 페이지를 다운로드하고 파싱하고 텍스트와 다른 페이지로의 링크를 추출하는 프로그램

인덱싱(Indexing) : 검색어를 조회하고 해당 검색어를 포함한 페이지를 찾는데 필요한 자료 구조

검색(Retrieval) : 인덱스에서 결과를 수집하고검색어와 가장 관련된 페이지를 식별하는 방법

 대부분의 웹 브라우저는 DOM(Document object model) 트리를 조사하는 도구를 제공한다. 크롬에서는 웹 페이지를 오른쪽 클릭하고 팝업 메뉴에서 [검사(N)]을 선택

jsoup 라이브러리를 이용하면 웹 페이지를 다운로드하고 파싱하고 DOM트리를 탐색하기가 쉽다. 

Depth-first search

Breadth-first search

불리언 검색(Boolean search)

클래스들의 관계를 추적하는 데 소프트웨어 엔지니어들은 UML(Unified Modeling Language) 클래스 다이어그램을 종종 사용. UML클래스 다이어그램은 클래스 컬렉션에 관한 수많은 정보를 표현하는 간결한 방법. 설계 단계에서 대안적인 설계에 관해 의사소통하는데 도움을 주고, 구현 단계에서는 공유된 프로젝트의 전반적인 윤곽을 보여주며, 배포단계에서는 설계를 문서화하는데 사용

레디스(Remote Dictionary Server, Redis)는 자바 자료 구조와 유사한 영속적인 자료구조를 제공. 일반적으로 원격 서비스로 동작. 따라서 사용하려면 레디스 서버를 실행하고 레디스 클라이언트로 접속 필요. 

RedisToGo 서비스는 무료 요금제가 있는 클라우드 방식의 레디스 서버를 제공.  그리고 클라이언트로는 제디스(Jedis)를 추천. 제디스는 레디스와 적업할 수 있는 클래스와 메서드를 제공하는 자바 라이브러리

Jedis 메서드를 호출할 때마다 클라이언트는 서버로 메시지를 전송하고 서버는 요청받는 행동을 수행하고 다시 메시지를 전송. 다수의 작은 동작을 수행한다면 응답시간이 오래 걸릴 수 있음. 이럴 때는 Transaction객체를 활용하여 다수의 연산을 그룹지어 성능을 향상시킬 수 있음

Insertion sort (삽입정렬)

Merge sort (병합 정렬)

Radix sort (기수 정렬)

Bounded heap sort (제한된 힙 정렬)