O-O Design Principle

• Single Responsibility Principle
• Dependency Inversion Principle 

• Interface Segregation Principle

• Liskov Substitution Principle
• Open-Closed Principle


Low Coupling, High Cohesion


1.1 Low coupling, High cohesion

  • 높은 응집도, 낮은 결합도(High Cohesion, Low Coupling) 원칙은 1970년대 래리 콘스탄틴(Larry Constantine)과 에 드워드 유던(Edward Yourdon)이 정의했던 아주 고전적 인 원리

  • High Cohesion, Low Coupling을 준수하는 이유
    – 소프트웨어 시스템 고유의 유지 보수성과 적응성을 측정하는 가

    장 좋은 방법이 된다.
    – 응집도가 높고 결합도가 낮은 구조는 변경이나 확장에 유용하다. 

1.1 Low coupling, High cohesion


• 결합도(Coupling)
– 정의:클래스간의서로다른책임들이얽혀있는상호의존도의정도 – 결합도가 높을수록 코드를 읽기 힘들어진다.

• 서로다른책임이산만하고복잡하게얽혀있기때문에가독성이떨 어지고 유지보수가 곤란해진다. 



1.1 Low coupling, High cohesion

• 응집도(Cohesion)
– 정의 : 하나의 클래스가 하나의 기능(책임)을 온전히 순도 높게 담당하

고 있는 정도

– 응집도가 높아질수록 클래스와 프로그램의 구조는 상대적으로 단순, 명

쾌해 진다. 


1.2 SRP : 단일 책임의 원칙

• 하나의 클래스는 하나의 책임만을 가져야 한다. • 책임:클래스가수행하여야할기능/계약

– 클래스를 변경하게 되는 원인

• 주요나쁜냄새
– ‘여러 원인에 의한 변경(divergent change)’ – ‘산탄총 수술(shotgun surgery)’ 


1.3 OCP : 개방-폐쇄 원칙


• 소프트웨어 구성 요소(컴포넌트, 클래스, 모듈, 함수)는 확장에 대해서는 개방돼야 하지만 변경에 대해서는 폐쇄 되어야 한다.

• 변하는 것(확장 가능한 것)
vs. 변하지 않는 것(인터페이스/계약...)

의 구 




1.4 ISP : 인터페이스 분리의 원칙

• 클라이언트는 자신이 사용하지 않는 Method에 의존관 계를 맺으면 안된다.

• 하나의 일반적 인터페이스보다 여러 개의 구체적인 인터 페이스가 낫다. 


1.5 DIP: 의존성 역전의 법칙

  • 고수준의 모듈은 저수준의 모듈에 의존하지 않아야 한다.

  • 구상화된 모듈에 의존하지 않고, 추상화된 모듈에 의존

    해야 한다.

  • 구상 클래스대신 인터페이스/서비스/계약에 의존

  • 헐리우드 원칙: Don‘t call us, we’ll call you!

  • IoC: Inversion of Control

     


1.6 LSP: 리스코프 치환 원칙

  • 서브 타입(상속/유도된 타입)은 언제가 기반(base) 타입으로 대체 가능해야 한다.

  • 서브클래스에서는기반클래스의사전조건과같거나더약 한 수준에서 사전 조건을 대체할 수 있고, 기반 클래스의 사후 조건과 같거나 더 강한 수준에서 사후 조건을 대체할 수 있다

  • 나쁜냄새: 거부된 유산

    • –  부모를 상속한 자식 클래스에서 메쏘드를 지원하는 대신 예외를 던 진다(예를 들어 콜렉션 프레임워크에서 UnsupportedOperationException)

    • –  자식 클래스가 예외를 던지지는 않지만 아무런 일도 하지 않는다.

    • –  클라이언트가 부모보다는 자식을 직접 접근하는 경우가 많다. 


저작자표시

'컴퓨터공학 > OOP' 카테고리의 다른 글

OOP 4 Steps  (0) 2013.01.07
OOP Terminology  (0) 2013.01.05
객체지향 언어가 제공해야 할 3가지 요소..  (0) 2012.05.04

ONE SIZE DOES NOT FIT ALL

  • 전통적인 RDBMS
    – 관계형 데이터 모델, ER-Diagram, SQL – 스키마, 정규화, 데이터 무결성 ...
    – 트랜잭션, ACID 속성 ...
    – 병행처리(Concurrency control), 2PLP... – 회복, 로그 ...

  • 전통적 DBMS의 문제점
    – Scalability: 오라클을 10,000대에 설치/관리할 수 있나??
    – Performance: 오라클에서 초당 만건 이상의 변경을 처리할 수 있나? 

    – Schema: 정형화된 스키마가 없으면?
    – Reliability는 필요 없으니 더 빠를 수는 없나?
    – Persistent는 필요 없으니 더 쉬울 수는 없나?
    – 복잡한데이터모델은필요없으니더간단할수없나? 


NoSQL

• "Not only SQL"

• 전통적인 RDBMS와는 다른 종류의 새로운 데이터 저장/ 관리 시스템 


NoSQL의 장/단점

• 장점
– 유연한 스키마
– 쉽고 빠른 설치/관리
– Massive Scalability
– 완화된 일관성(consistency)àHigh Performance & Availability

• 단점
– SQL과같은표준질의언어부족à프로그래밍모델도입 

– 완화된 일관성àACID가 보장 안됨 



NoSQL 종류

• MapReduce / Hadoop

  • –  대용량 데이터 분석 (OLAP)

  • –  Google: MapReduce + Google File System

–  Apache: Hadoop + Hadoop Distributed File System

• Key-Value

  • –  High Performance 병렬 해시

  • –  잦은 변경, 빠른 반응 속도 (OLTP)

–  Dynamo (Amazon), Cassandra (Facebook/Apache), BigTable (Google), HBase (Facebook/Apache)

• Document

– Key + 문서 (XML, JSON 과 같은 반구조화/비구조화 자료구조) – MongoDB, CouchDB (Apache), SimpleDB (Amazon)

• Graph
    – Node/Edge, RDF, Semantic Web – 예: Neo4j, Allegro 



MapReduce

• Map: 문제를 sub-problem으로 나누어 분산 해결 

– map(item)à<key, value>

• Reduce: sub-problem 별로 결과를 취합 

– reduce(key, <list of values>)àvalue

• 예)책한권에서단어별출연빈도수세기

  • –  Map: 아이들 각각에게 한 페이지씩 나누어주고, <단어, 빈도수>를 각각

    포스트잇에 적어 보고하도록 함.

  • –  Reduce: A/B/C/D/E... 별로 포스트잇을 취합하여 각각 숫자를 더함 



MapReduce 프레임워크

• Apache Hive (Facebook/Netflix) – Hadoop + Data warehouse
    – HiveQL(SQL 유사 질의 언어) 지원

• Apache Pig (Yahoo)
    – Pig Latin: High-level language for Hadoop

• Apache ZooKeeper

  • –  분산환경에서설정공유,이벤트처리,분산관리등

  • –  open source centralized configuration service and naming registry for large distributed systems 

Key/Value

• 단순한 데이터 모델: (key, value)

• 단순한 연산: put, get, update, delete

• 장점

– Efficiency: 빠른 처리 속도

– Scalability: 필요에 따른 손쉬운 서버 확장 

– Fault-tolerance: 데이터 복제 


DHT: Distributed Hash Tables

• Hash
    – put(key, value)
    – valueßget(key)

• Distributed
    – 임의의 노드에 분산 저장
    – 노드의 추가/삭제가 자유로움

• 대표적인구현방법 – Chord(1):

• Ring형태 구성
• m비트의 키와 노드 ID사용
• O(log N)의 라우팅 테이블 크기
• O(logN)홉만에데이터도달보장 



BSP (Bulk Synchronous Parallel)

• 병렬계산을위한계산모델

  • Pregel: A System for Large-Scale Graph Processing, SIGMOD 2010 by Google

  • Apache Hama: http://hama.apache.org/

  • Apache Giraph: http://incubator.apache.org/giraph/ 

NewSQL (?)

  • VoltDB by Michael Stonebraker
    – Automatic partitioning across a shared nothing server cluster
    – Main memory data architecture
    – Elimination of multi-threading and locking overhead
    – Built-in High Availability using synchronous multi-master replication 

    – Review of VoltDB's stored procedure interface

  • Vertica (HP) by Michael Stonebraker – Real-Time Loading & Querying
    – Advanced In-Database Analytics
    – Columnar Storage & Execution

    – Aggressive Data Compression
    – Scale-Out MPP Architecture
    – Automatic High Availability
    – Optimizer, Execution Engine & Workload Management – Native BI, ETL, & Hadoop/MapReduce Integration 


분석 전용 DBMS

• 기존DBMS • 분석전용DBMS
– Concurrency Control – No concurrency
– Row-기반 저장구조 – Column-기반 저장구조 – 중앙집중서버 – 병렬/분산처리
– 고수준의 트랜잭션 레벨 – 약화된 트랜잭션 레벨 – 디스크기반 – 메인메모리기반

참고: Key Features of EXASOL

  • Relational database management system

  • Standard hardware cluster

  • In-memory query processing

  • Massively parallel data processing

  • Column by column storage

  • Intelligent and innovative compression algorithms

  • Self-learning and self-optimising system

  • Simple integration thanks to standard interfaces 



Column-Oriented DBMS

• 컬럼순서로데이터저장

고객ID

이름

주소

나이

전화번호

CE1

박현민

서울

24

....

CE2

이강선

대전

20

....

CE3

홍길동

서울

18

....

• 이점
    – 컬럼단위의대한분석에용이
    – 압축이 효과적à메모리 기반 처리 용이
    – 병렬 처리에 유리 (SIMD: Single Instruction, Multiple Data) 


저작자표시

'컴퓨터공학 > DataBase' 카테고리의 다른 글

Relational Model의 주요 개념  (0) 2013.01.14
Database 이론  (0) 2013.01.14

  • Domain (type): Attribute가 가질 수 있는 값의 집합

  • Attribute (column)

  • Tuple (row, record): set of values for attributes

  • Relation (table): set of tuples

• Database: set of relations 




Schema & Instance

• Schema
– the logical structure of the database
– type information of a variable in a program
– Physical schema: database design at the physical level – Logical schema: database design at the logical level

• Instance
– actual contents at a particular point in time – the value of a variable 


NULL

• special value for “unknown” or “undefined” • 숫자0,빈문자열“”등과는다름
• 모든 Domain은 NULL값을 포함 함 


Key

• Key: Tuple을 구별하기 위한 Attribute 집합 – Relation은 동일한 tuple이 있을 수 없음

• Superkey (수퍼키)
– Relation에서 Tuple을 식별할 수 있는 Unique한 Attribute의 집합

  • Candidate Key (후보키)

    • –  Superkey 중에서 Minimal 한 Key

    • –  Minimal: 하나의 Attribute라도 빼면 더 이상 Key가 아님

  • Primary Key (기본키, PK)

    • –  Candidate Key 중 하나 (Relation을 정의할 때 선택)

    • –  Entity Integrity : NULL이 될 수 없음

  • Foreign Key (참조키, FK)

    • –  타 relation을 참조하는 attribute

    • –  참조하는 relation에서 key는 아니지만, 참조되는 relation에서 primary key임.

    • –  Referential Integrity: 반드시 참조된 relation의 PK 값에 존재하거나 NULL이어야 함 

저작자표시

'컴퓨터공학 > DataBase' 카테고리의 다른 글

NOSQL  (0) 2013.01.21
Database 이론  (0) 2013.01.14

DATABASE ?

- 한 조직의 여러 응용 시스템들이 공용(Shared)하기 위해 통합(Integrated), 저장(Stored)한 운영 데이타(Operational data) 의 집합

 

DBMS란?

  • DB관리를 위한 컴퓨터 시스템
    – 전사적인 정보 관리
    – 관련된 데이터의 집합
    – 데이터에 접근하는 프로그램 집합 – 효율적이고 편한 사용을 위한 환경

  • DBMS 응용의 예:
    – Banking: all transactions
    – Airlines: reservations, schedules
    – Universities: registration, grades
    – Sales: customers, products, purchases
    – Online retailers: order tracking, customized recommendations – Manufacturing: production, inventory, orders, supply chain
    – Human resources: employee records, salaries, tax deductions 


DBMS특징

- Massive

- Persistent

- Safe

- Multi-user

- Convenient

- Efficient

- Reliable


Key People

-DBMS implementer

-Database designer

-Database application developer

-Database administrator


파일 시스템의 문제점

  • 데이터의 중복(Redundancy) 와 일관성(Consistency) 문제
    – Multiple file formats, duplication of information in different files

  • 데이터 접근의 어려움
    – 각 작업마다 별도의 프로그램 작성 – 각각별도의방법이필요할수있음

  • 데이터 종속성 (Dependency)
    – 데이터의 포맷이나 접근 방법 등이 프로그램 코드에 종속됨. – 프로그램의 변경이나 데이터 형태, 종류 등의 변경이 불가능

  • 데이터 독립성 (Isolation)
    – 여러 프로그램에서 동시에 데이터를 수정하면?
    – 하나의수정작업이다른작업에영향을줄수있음 

  • 변경의 원자성(Atomicity) 문제

    • –  일련의 작업 중 시스템의 failure가 발생하면??

    • –  예)계좌이체중 내계좌에서돈이나갔는데,다른계좌에가기전에정전이일 어난다면?

  • 동시 사용성(Concurrency) 제어 문제

    • –  동시에 일련의 작업들이 이루어질 경우 올바른 수행을 보장할 수 있는가? (일관

      성에 문제)

    • –  예) 두 명이 동시에 한계좌에서 돈을 인출하려고 하면?

  • 데이터 무결성 (Integrity) 문제
    – Integrity constraints (예. account balance > 0) 가 프로그램 코드 속에 기술

    • 프로그램코드를복잡하게만들고유지보수를어렵게함

– 제약조건 변경이나 추가 등이 힘들다.

• 보안
– 보안을 보장하기 힘듬: 다양한 파일, 다양한 접근 경로, 다양한 프로그램의 이용 




• DBMS 벤치마크 사이트: http://www.tpc.org – 데이터베이스 시스템의 성능 벤치마크
– DBMS + H/W System + Middle Ware System ... – 분류

• TPC-C: 트랜잭션 시스템 (OLTP)
– 2013년 1월 현재 1위: 100억원, 분당 3000만 트랜잭션

• TPC-H: 의사결정 시스템 (OLAP) 


저작자표시

'컴퓨터공학 > DataBase' 카테고리의 다른 글

NOSQL  (0) 2013.01.21
Relational Model의 주요 개념  (0) 2013.01.14

다음과 같은 xml 문서를 sunlight hilighter를 이용해서 하고 싶다고 가정을 하자.

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="fill_parent"
    android:layout_gravity="center_horizontal"
    android:gravity="center_horizontal"
    android:orientation="vertical" >
</LinearLayout>

이 때, 일반 코드를 사용할 때 처럼 


<?xml version="1.0" encoding="utf-8"?>

<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"

    android:layout_width="match_parent"

    android:layout_height="fill_parent"

    android:layout_gravity="center_horizontal"

    android:gravity="center_horizontal"

    android:orientation="vertical" >

</LinearLayout>


를 그대로 입력하면 나오지가 않는다.


html 코드에 


< : &lt;

> : &gt;


로 대체를 해서 입력을 하자.


<> 는 html에서 tag의 시작과 끝으로 인식하기 때문이다.

저작자표시

'컴퓨터공학 > Tool(IDE, Git, Etc)' 카테고리의 다른 글

[Git] Github에 Local Project를 처음 올릴 때  (0) 2017.05.28
[Scala] 개발환경 설정  (0) 2016.03.08
Convention over Configuration  (0) 2013.01.05
system 설계 고려사항  (0) 2013.01.03
플랫폼  (0) 2013.01.03

high-level : stream file


socket buffer(Queue)


low-level : packet byte


send buffer blocking : 꽉찬 상태에서 send호출

recv buffer blocking : 텅빈 상태에서 recv호출


block해결 방법 : (Async) select 호출 

- select : send, recv 버퍼의 상태를 알려주는 함수



stream : 1-dimension array -> close() 호출할 때 까지 수행





저작자표시

Heap Definition 


• Completebinarytree

•Partial order : for every node v, the key stored in v is greater(smaller) than or equal to its parent’s key. 


• A max tree is a tree in which the key value in each node is no smaller than the key values in its children (if any).

• A max heap is a complete binary tree that is also a max tree.



• A min tree is a tree in which the key value in each node is no larger than the key values in its children (if any).

• A min heap is a complete binary tree that isalso a min tree 



Insert into a Min Heap 


• Put into the next available leaf node

• (this is simple since it is array)

– Look at the parent of this element and swap if the parent is larger (note that the partial ordering is preserved)

– Repeat with the parent (sifting up) 


• Array representation of heap

Since the heap is a complete binary tree, we can easily locate

the parent of any element, i.e., parent(i) is at |_i/2_| 


• Analysis of insert_max_heap

The algorithm follows a path from the new leaf of the max heap to the root until it either reaches the root or reaches a position i such that the value in the parent of i is no smaller than that of i.


Since the height of the heap is log (n + 1) , O(log n) 




Delete from a Min Heap 

• Remove the root from the tree and return its value

• Remove the right most leaf and place it at the root

• Perform sifting down operations(if the key is larger than the smaller of its two children, then swap these two. Repeat this)

• Insertion / deletion : O(n) 

Application of Heap 

• Priority Queue 

• Heap Sort 


•Heap Sorting : Storing n keys in O(n), and then repetitively applying DeleteMin() operations in O(n logn). The most basic algorithm.

• Graph algorithms
– Shortest path finding algorithm
– Minimum spanning tree finding algorithm

• Scheduling algorithms 


Heap Sort 

• Ascending
– Using the Min Heap

• Descending
– Uisng the Max Heap 



Implement Heap As Array 


• Easy to use array to implement heap – array[i]’s parent is array[i/2]

– array[i]’s left child is array[2*i]
– array[i]’s right child is array[2*i+1]

• Easy to swap child and parent 


저작자표시

'컴퓨터공학 > Data structure' 카테고리의 다른 글

HashTable by Java  (0) 2016.01.26
Traversing Tree  (0) 2013.01.07
Balance? - Tree  (0) 2013.01.07

1. class definition

2. class declaration

3. instantiation

4. invocation

저작자표시

'컴퓨터공학 > OOP' 카테고리의 다른 글

객체지향 설계 기본 원칙  (0) 2013.01.24
OOP Terminology  (0) 2013.01.05
객체지향 언어가 제공해야 할 3가지 요소..  (0) 2012.05.04

  • Preorder

  • Postorder

  • Level order

• NOTE :The inorder traversal is the special case for binary trees.

(another definition possible) 


- inorder는 binary-tree에서만 존재한다.


 preorder traversal

– To move down the tree to the left until a null node is reached

– The null node’s parent is then “visited”, and the traversal continues with the node that is one to the right

– If there is no move to the right, the traversal continues with the last unvisited node at the next higher level of the tree 




• Vertex -> Left subtree -> Right subtree 

– Root : 1st position in traversal
– Bottom right child: latest position 










 postorder traversal

– To move down the tree to the left until a null node is reached

– The traversal continues with the null node’s parent and then to the right

– If there is no move to the right (null node), the null node’s parent is then “visited”, and the traversal continues with the node at the next higher level of tree 





• Left subtree -> Right subtree -> Vertex 

– Root: latest position in traversal
– Bottom left child: 1st position 

- EX) % rm -r /user/bit 







inorder traversal of a binary tree

– In an inorder traversal a node is visited after its left subtree and before its right subtree 







• Left subtree -> Vertex -> Right subtree
– Bottom left child : 1st position
– Bottom right child :latest position in traversal 








저작자표시

'컴퓨터공학 > Data structure' 카테고리의 다른 글

HashTable by Java  (0) 2016.01.26
Heap  (0) 2013.01.08
Balance? - Tree  (0) 2013.01.07

1. Root to leaf 가 동일하다


=> leaf는 동일 level 에 위치


2. root는 최소 2개 이상의 Sub-Tree를 가진다.


3. 각 노드는 구조체의 자원을 절반 이상 사용한다.

저작자표시

'컴퓨터공학 > Data structure' 카테고리의 다른 글

HashTable by Java  (0) 2016.01.26
Heap  (0) 2013.01.08
Traversing Tree  (0) 2013.01.07

+ Recent posts

티스토리툴바