두다지 서버 개발자 양성 프로그램 Week 2

두다지 서버 개발자 양성 프로그램 Week2

2번 째 멘토링

한 주 간 과제로 공부하고 작성한 Priority Queue와 Hash Table을 리뷰하는 시간을 가졌다. 멘티들이 공부해온 자료구조의 특성과 구조를 멘토님께 설명한 후, 작성한 코드가 어떻게 작동하는지에 대하여 이야기하였다. 이후에는 작성한 코드에 대한 리뷰와 자료구조라는 과목이 왜 중요한지 그리고 어떻게 사용되는지에 대한 추가적 설명을 듣는 시간을 가졌다. 자료구조를 학습하며 전산학에서 중요한 과목이라는 말을 수도 없이 들었지만 정작 왜 그리고 어떻게 사용되는지에 대해 깊게 고민해본 적이 없었는데 멘토님의 설명을 들으며 자료구조의 중요성에 대해 이해할 수 있었던 시간이었다.

Code Review

Coding Convention

• method name은 항상 underscore와 lowercase로 구성되어야 함
  • ex) def perc_up:
• method name을 구성하는 영단어는 full로 사용하는 것이 이해하기에 좋음
  • ex) def percolate_up:
• class name은 Camel case로 작성
  • ex) class PriorityQueue:
• underscore + capitalize 조합만큼은 피하자
  • ex) class Priority_Queue (ugly!)
• Tab과 Space의 혼용은 가장 **'지양'**해야 할 Coding Convention
  • ex) 소스 코드를 merge하고자 하는데 충돌이 일어남. 그러나 소스 코드 전체를 뒤엎고 있는
    Tab/Spaces의 indentation 충돌로 인해 정작 중요한 충돌 지점을 찾지 못하는 경우가 생길 수 있음
  • show whitespace option + use 4 spaces as an indentaion option

Feedback

• Data Structure의 Basic concepts 익힌 후에는 직접 구현해보는 것이 가장 좋음
• +) Test case를 구상해가며 코드 작성과 Test를 함께 하는 습관을 들이는 것이 좋음
  • Performance 까지 측정해보면 better!
• 3개월 후가 중요하다!
  • 3개월 뒤에 코드를 읽었을 때 짧은 시간 안에 작성했던 context를 이해할 수 있도록 작성하는 것이 중요
    
    

Data Structure Review

Priority Queue

• 다른 많은 구조적 장점을 포기하고, Find min(or max)를 Constant time(O(1))에 하기 좋은 자료구조
  • Heap을 사용한다면 삽입과 삭제는 O(logN)의 시간 복잡도를 지니게 됨
  • 따라서 Heap을 이용한 Prioirty Queue의 구현을 위해서는 Heap의 특성을 유지하도록 하는 'heapify' 연산이 가장 중요
• 우선순위 큐가 실제 전산학에 사용되는 예
  • OS의 Job Scheduling
    • 다음 작업의 Scheduling을 위해서는 가장 상단의 Job만 참조하면 되기 때문에 모든 Job들의 우선순위를 확인할 필요(Full Scan)가 없어짐
  • Network traffic control

Hash Table

• Hash Table의 size는 Prime number로 정의하는 것이 Open slot(Open addressing)을 찾는데 효율적
• Hash Table의 가장 중요한 척도는 Load Balance
  • 실제 Table의 index를 우리가 원하는 key로 접근하지 못할 수도 있음
    • ex) a[99]가 아닌 a['사과']로 검색하고 싶다면?
  • Hash Function은 단순하되 Key값을 정해진 Table의 slot에 올바르게 mapping하는 것이 중요
  • Collison로 인해 생기는 Clustering은 Load balance를 망침
  • Sharding: 데이터가 아닌 데이터베이스 자체를 분할하여 분산 저장(CRUD 연산 성능 향상 가능)
• Hash Table의 size를 resizing 할 때는 기존에 들어가 있는 값들의 위치에 대한 고려를 해야 함
  • 번거롭더라도 기존에 저장된 값들을 모두 꺼낸 후, resizing을 위해 새로 작성한 hash function에 맞게 값을 저장하는 것이 좋음
• 전산학에서는 O(1)과 O(logN)의 시간 복잡도를 'elegant' 하다고 여김
  • 단순한 doubling 기법이 효율적인 이유
    
    

Conclusion

• 내가 원하는 Common case의 속도 최적화를 위해 다른 부분을 포기하는 것이 중요할 때가 많음
  • 이것이 Data Structure를 공부하는 이유(어떤 자료구조가 어떤 연산에 특화되었는지를 이해할 수 있어야 하므로)
  • 전산학 자체가 모두 이같은 최적의 개념으로부터 시작
    • A를 위해 B를 포기하거나, A와 B 모두 중간 단계의 속도로 맞추거나 등...
• 즉, Common case fast를 중요한 모토로 삼아야 함
  • 서비스의 Common case를 찾는 것 또한 중요한 과정
  • Common case를 발견한 후, 이를 위해 어떤 구조체를 사용할 것인지까지 결정하고 나면 나머지 작업 역시 해결되는 경향이 강함
  • 실생활에서 이와 같이 코드를 작성해야 할 일이 정말 많을 것
• Main Language에서 제공하는 기본 Data Structure가 내부적으로 어떻게 작동하는지를 아는 것 또한 중요함
  
  

다음 주 까지 Assignment

1. Test case를 포함하여 Priority Queue와 Hash Table 재구현 및 테스트
2. 우선순위 Queue를 이용한 Job Scheduler 작성
   • [요구사항]
     1. CLI 혹은 Web으로 서비스 구현
     2. add 21:32 'process name'와 같이 작업 추가
     3. Queue에 들어있는 명령어 보여주는 listing 명령어 추가
     4. 2개의 thread 사용(시간 체크하는 thread / 명령어 받고 해석하는 shell thread)
3. 김종현 교수 <컴퓨터구조론> 읽고, 중요 내용 요약
4. 상속과 인터페이스의 차이 이해하기
   • 상속의 단점: 왜 Go lang은 '상속'을 버렸을까?
   • Strategy pattern의 이해