반응형
Docker_python3.7

Docker ubuntu16.04 + python3.7 venv 패키지유지 환경

ubuntu16.04 에 python 3.7 을 venv 로 가상 환경으로 만들어서 필요할 때 마다 pip 로 패키지를 추가하고 컨테이너 종료시에 사라지지 않고, 유지할 수 있는 도커 이미지를 만들어 보자.

도커 커맨드를 잘 이용하면 금방 만들 수 있을 것이라 생각했지만 쉽지 않았다. 특히 pip로 패키지를 설치한 것을 계속 유지하는 부분과 venv 환경으로 작동하게 하는 부분.
마지막으로 jupyter notebook을 필요한 경우 작동할 수 있도록 하였다.

결론부터

바로 이미지를 받아 실행하고자 한다면 다음을 참고한다.
아래 커맨드를 실행하면, 위 구성한 도커 이미지를 받아 컨테이너를 구동하게 된다. 현재 디렉터리에 py37 이라는 venv 폴더가 생성되고 패키지를 유지하도록 된다.

C:\hub\docker_ubuntu16.04-python3.7>type b.bat
docker run -it -v /c/hub/docker_ubuntu16.04-python3.7/py37:/root/py37 crazyj7/ubuntu16.04-python3.7

C:\hub\docker_ubuntu16.04-python3.7>type j.bat
docker run -it -v /c/hub/docker_ubuntu16.04-python3.7/py37:/root/py37 -p 8888:8888 crazyj7/ubuntu16.04-python3.7 jupyter notebook --ip=0.0.0.0 --port=8888 --allow-root --NotebookApp.token='' --NotebookApp.password=''
  • b.bat : python3.7 구성환경 구동하여 bash 쉘 구동. python을 실행할 수 있다.

image
위 쉘에서 pip로 패키지를 추가할 수 있다. 나중에 다시 컨테이너 구성시에도 패키지가 항상 유지(보관)된다.

생성된 py37 폴더에 소스코드를 작성하고 작업 디렉터리로 사용해도 되고, 별도 공유 폴더를 만들어 볼륨을 연결해서 사용해도 된다.
image
종료시에는 ^C를 두 번 입력하면 종료된다.

image

만드는 과정

아래 github에 내가 작성한 소스가 있다.
https://github.com/crazyj7/docker_ubuntu16.04-python3.7

먼저 나의 작업 디렉터리 구조이다.
c:\hub\docker_ubuntu16.04-python3.7

Dockerfile을 만들어 보자.

Dockerfile

FROM ubuntu:16.04
MAINTAINER crazyj7@gmail.com

RUN apt-get update -y
RUN apt-get upgrade -y
#RUN apt-get install -y build-essential binutils libtool make gcc g++ openjdk-8-jdk git dos2unix vim wget
RUN apt-get install -y build-essential wget vim dos2unix
RUN apt-get install -y zlib1g-dev libncurses5-dev libgdbm-dev libnss3-dev libssl-dev libreadline-dev libffi-dev wget software-properties-common
RUN apt-get install -y ocl-icd-opencl-dev
RUN add-apt-repository -y ppa:deadsnakes/ppa
RUN apt-get update -y
RUN apt-get install -y python3.7
RUN apt-get install -y python3.7-venv

# env
WORKDIR /root
ENV HOME /root
SHELL ["/bin/bash", "-c"]

ENV PATH "/root/py37/bin:$PATH"
RUN echo "source /root/py37/bin/activate" >> .bashrc

COPY ./requirements.txt /root/requirements.txt
COPY ./initvenv.sh /root/initvenv.sh

ENTRYPOINT ["/bin/bash", "-c", "/root/initvenv.sh \"$@\"", "--"]
VOLUME /root/py37
CMD ["/bin/bash"]
  • 앞에 RUN은 기본 ubuntu 16.04를 베이스로 하여 시스템에 필요한 패키지를 설치한다. 그리고 python 3.7을 설치하였다.
  • 환경 설정 부분에서 작업 디렉터리를 /root로 하고, 기본 쉘을 bash로 변경. 환경 설정 파일들을 추가.
  • bash 구동 스크립트에 /root/py37의 venv를 활성화 시키도록 하였다.
  • 최초 구성할 기본 python 패키지들을 requirements.txt에 몰아 넣어 구축시 설치되도록 하였다.
  • 그리고 entry point로 initvenv.sh 스크립트를 추가하여 항상 구동하게 하였다. 뒤에 파라미터는 cmd로 별도로 파라미터로 줄 경우 쉘로 구동할 수 있도록 받게 하였다.
  • 볼륨은 /root/py37로 공유 연동 가능하도록 설정.

initvenv.sh

#!/bin/bash

ENVNAME=/root/py37
if [ "$(ls -A $ENVNAME)" ]; then
#	echo Env $ENVNAME exists. skip init.
	source $ENVNAME/bin/activate
else
	echo Env $ENVNAME not exists. init env.
	python3.7 -m venv $ENVNAME
	source $ENVNAME/bin/activate
	pip install --upgrade pip
	pip install -r requirements.txt
fi

if [ $# ]; then
	$*
else
	/bin/bash
fi

py37 폴더 존재여부에 따라 최초 초기화 여부를 수행한다. 별도 지정한 cmd가 있으면 cmd를 수행하도록 하였음. (jupyter notebook 등)

도커 빌드
build.bat

docker build -t crazyj7/ubuntu16.04-python3.7 .

Author: crazyj7@gmail.com

'Python' 카테고리의 다른 글

set에 set 추가? frozenset  (0) 2021.02.24
Jupyter Notebook 소스 복구  (0) 2020.06.16
딕셔너리에서 키삭제  (0) 2019.12.07
파이썬 충돌해결 module conflict  (0) 2019.12.01
파이썬 개발환경/가상환경구축  (0) 2019.12.01
반응형
git

Git simple guide


crazyj7@gmail.com

Start git repository download

git clone http://github.com/crazyj7/...git
git clone ssh://git@192.168…:2222/home/git/repos/…git

Work

make new branch and work

최신 master 브랜치를 받아서 작업 브랜치를 만들고 작업한다.

git pull
git branch alpha
[work to do…]

commit and push

변경된 파일들을 index표시를 하고 커밋한다. 그 후 원격 서버에 올린다.

git status .
git add -u
git add [files/dirs]
git commit -m “update message”
git push (or git push origin master)

merge to master

마스터 브랜치를 기준으로 새 작업 브랜치를 가져와 병합 한다.
병합후 변경내역을 원격 서버에 올린다.

git branch : 현재 브랜치 확인
git checkout master
현재 브랜치가 master로 변경됨
git merge alpha
현재 브랜치 기준으로 alpha 브랜치를 가져와 병합한다.
git push

rollback

작업한 파일을 원래대로 되돌리기(Warn!)

git checkout [file] or [. (current dir)]

마지막 커밋은 취소하고 수정했던 것도 전부 취소하기(Warn!)

cancel last commit
git reset --hard HEAD^ (HEAD~1 in Windows)
위 옵션에서 --hard 옵션을 빼면 커밋만 취소하고 수정 파일은 그대로 유지한다. (주의!!! 수정내역이 없어지므로 필요시 백업!)
git reset HEAD^

Cancel Merge (병합 취소)
merge후 conflict나고 처리가 복잡할 경우 바로 이전으로 돌아가기

git merge --abort


History

GUI로 히스토리를 확인할 수 있다.

gitk

한글이 깨질 경우 hangul encoding 변경 후, 다시 시작

git config --global gui.encoding utf-8


Errors

pull fail?

cancel all worked here. cancel commit.
변경 내역을 되돌리고, 다시 pull로 원격에서 업데이트한다.(Warn! 주의!!! 작업내용삭제됨!!! 일단 백업해 두는 것을 추천.)

git reset --hard HEAD^ (HEAD~1 in Windows) or HEAD
git pull

그래도 pull이 실패한다면 stash로 작업내역을 백업하고 다시 받는다.

git stash
git pull

참고

git reset --soft HEAD~ 는 HEAD를 한 커밋 이전으로 이동시킨다.
git reset HEAD~ 는 HEAD 이동 및 index도 이동한다.
git reset --hard HEAD~ 는 HEAD 이동, index 이동, working dir도 이전으로 돌린다.
git stash 는 reset을 하지만 변경내역은 백업을 해 둔다. 파일명 지정시 git stash save [file] , git stash list , git stash pop/apply 로 불러오기. 다른 브랜치에 잘못 작업한 것을 원래 브랜치로 이동시킬 때 사용가능

cancel git add?

git reset [file/dir]

conflict?

edit conflicted file and git add/ git commit
or choose one side

작업하고 commit을 하고 원격으로 push하는데 conflict가 발생할 수 있다. 이것은 원격에 이미 checkout받은 브랜치가 변경되었다는 것이다.

git push : 리모트에서 거부 발생!!!
git pull
conflict!!! 자동병합 충돌 발생!!! 충돌 파일 확인!!
git status : 충돌파일 정보
파일이 병합처리되어 >>>(원격) <<<(로컬) 등 문자 포함
이 때는 파일을 수정하고 다시 커밋하고 푸시하는 방식이 있고, 어느 한 쪽을 선택할 수도 있다.

충돌 발생시 충돌 파일을 수정하든지 어느 한 쪽을 골라야 한다.
현재 브랜치 기준으로 내것과 원격의 것을 잘 구분해야 한다.

git checkout --ours [file] : 로컬파일이 진짜다. 로컬 우선!!!
git checkout --theirs [file] : 서버에 있는 최신것을 따르겠다. (주의!!! 로컬 파일 내용은 없어짐!!! 로컬을 무시하겠다.)

or edit file (양쪽을 모두 반영하겠다. >>> <<< 파일 수정 )
git add -u
git commit -m “update”
git push

cancel delete local file

파일을 잘못 삭제했을 경우 복구하는 법

git status . ; check which file is deleted.
git checkout HEAD [file]

cancel work

git reset . ; reset all worked
git checkout . ; go before work


Ignore files

If you dont want to upload some files or dirs,
create .gitignore file in the current directory.
add files or dirs
ex)

build/
*.obj
dataset/
*.o


Branch merge

  • fast-forward
    only one branch is changed or it doesn’t exist same file changed.)
    a -> b(master) : no change
    b(newbranch) -> x ->y(bugfix)
    merge : a->b->x->y (master=bugfix)
    git push or git pull
    특별히 겹치는 부분이 없으면 자동으로 충돌없이 병합된다.
  • merge commit
    Both branches are changed. Update conflict files and commit
    git checkout master : 마스터를 가져와서 (항상 메인을 기준으로)
    git merge alpha : 알파를 불러와 현재(마스터)와 합친다.
    충돌이 나면 해당 파일을 수정하고 병합한다. 여러 브랜치가 하나의 브랜치(현재 브랜치)로 합쳐진다. 과거 히스토리 유지.
  • rebase
    a -> b -> c -> d (master)
    b -> x -> y (alpha(bugfix))
    위 버그 수정 브랜치를 마스터로 반영하고, 마스터만 유지하고 싶다. 그런데 버그패치동안에 마스터가 변경된 상태다.
    merge: a->b->c->d ->x->y (master=bugfix)
    git checkout alpha : 수정 브랜치를 가져와서
    git rebase master : 마스터에 연결시도
    update conflict files : 충돌발생 파일 수정(c,d,x,y)
    git add -u
    git rebase --continue : 리베이스 계속 진행
    git checkout master : 마스터를 가져와서
    git merge alpha : 알파를 현재로 불러와서 병합.
    베이스를 새로 지정한다. 위의 브랜치 트리가 한 줄로 만들어진다. 과거 히스토리 변경 주의.

Delete branch

브랜치 삭제 -d 옵션으로 안되면 -D 옵션으로 한다.

git branch -d [alpha]


Delete file

로컬 및 저장소에서 파일 삭제

  • Remove the file in both local and remote github
    git rm [file]

저장소에서만 삭제하고 로컬 파일은 보존

  • Remove remote file in github but remain it in local
    git rm --cache [file]

Delete all .git files

리눅스에서 모든 .git 폴더 제거하기(incude subdir)

check files…
find . -name ‘.git’
WATCHOUT!!!
find . -name ‘.git’ -prune -exec rm -rf {} +

윈도우에서 모든 .git 폴더 제거하기(incude subdir)

batch file create
FOR /r “c:\temp” %%f IN (.git) DO RD /s /q “%%f”

삭제하기 전에 목록 출력만(rd /s /q 대신 echo) 해서 확인을 하는 것이 좋다.

Repository mirror

저장소 복사

git clone --mirror [가져올 URL]
git push --mirror [가져욜 URL]

# git remote -v 
원격지 저장소 주소 확인

# git clone --mirror https://user@a.c.com/maypp/test.git
먼저 옮길 내용을 클론으로 받는다.

올릴 곳의 주소로 설정
# git remote set-url --push origin http://local.com/mobile/android.git
# git push --mirror
이제 로컬의 내용을 변경된 주소로 올린다.

Tag

태그는 버전명을 주거나 할 때 지정해 준다.

  • 먼저 checkout으로 받고, 그 안으로 들어가서 작업한다.
  • 현재 갖고 있는 태그 목록
git tag
  • 현재 받은 checkout에 tag를 만들어 걸기
git tag v1.0
git push origin v1.0
-- 이렇게 해서 서버로 올린다.
  • 태그로 받기
git checkout v1.0
  • 태그 삭제
git tag -d v1.0

-태그 v.1.0을 수정할 때는 1.1 브랜치를 만들어서 작업

태그로 가져와서
git checkout v1.0
브랜치를 만들고
git branch 1.1
해당 브랜치로 전환(이걸 안해주면 소스 날릴 수도)
git checkout 1.1
수정작업
git add -u
git commit -m "patch 1.1"
git push

-master로 위 브랜치 합치기

마스터로 가서
git checkout master
브랜치 1.1을 가져와 머지함
git merge 1.1
git status
충돌파일 편집 수정
git add -u
git commit -m "merge 1.1"
git push
태그를 추가
git tag v4.0
git push origin v4.0

Author : crazyj7@gmail.com

'Develop > Linux_Unix' 카테고리의 다른 글

[도커] tomcat, mariadb 환경 war hang/slow  (0) 2021.04.28
Bash Tip 작업속도를 빠르게  (0) 2021.03.03
리눅스 백그라운드 실행(터미널종료에도)  (1) 2021.02.23
Ubuntu18/tomcat8 setup  (0) 2019.11.08
VI 사용법  (0) 2015.06.02
반응형
sort compare

Sort Algorithm Compare

  • 시험 방법
    정렬 알고리즘들을 500~550개(랜덤)의 값을 만들어 정렬하는 것을 5000번 반복한 시간을 측정하였다.
qsort test
ALG=selection_sort
OK cnt=5000 FAIL cnt=0
4029 ms
ALG=bubble_sort
OK cnt=5000 FAIL cnt=0
3190 ms
ALG=insertion_sort
OK cnt=5000 FAIL cnt=0
2257 ms
ALG=merge_sort
OK cnt=5000 FAIL cnt=0
361 ms
ALG=quick_sort
OK cnt=5000 FAIL cnt=0
236 ms
  • 랜덤한 값들을 정렬할 경우 알고리즘별로 시간 측정 결과 대략적으로 다음과 같은 순서로 성능이 좋았다. 퀵소트 이름이 괜히 퀵이 아니다.
  • quick > merge > insertion > bubble > selection
  • 위 결과는 정렬할 대상의 상태(값 배열)에 따라 달라질 수 있다.
#include <iostream>
#include <vector>
#include <ctime>
#include <chrono>

void selection_sort(int arr[], int size) {
    for(int i = 0 ; i < size - 1 ; i++) 
        for (int j = i + 1 ; j < size ; j++) 
            if(arr[i] > arr[j]) {
                // swap(arr[i], arr[j]);
                int t = arr[i] ;
                arr[i] = arr[j] ;
                arr[j] = t ;
            }
}


void bubble_sort(int a[], int n){
    int i, j, t;
    for (i = 0; i < n - 1; i++) {
        int bchanged=0 ;
        for (j = 1; j < n - i; j++) // j=(1,10)
        {
            if (a[j - 1] > a[j]){
                t = a[j - 1];
                a[j - 1] = a[j];
                a[j] = t;
                bchanged=1 ;
            }
        }
        if (bchanged==0) break ;
    }
}


void insertion_sort(int arr[], int size) {
    for(int i = 1 ; i <= size - 1 ; i++) 
        for (int j = i-1 ; j >= 0 ; j--) 
            if(arr[j] > arr[j+1]) {
                // swap(arr[j], arr[j+1]);
                int t = arr[j] ;
                arr[j] = arr[j+1] ;
                arr[j+1] = t ;
            } 
            else
                continue;
} 



void merge_sort(int arr[], int size) {
    // std::cout << "merge_sort size=" << size << std::endl ;

    if (size > 2) {
        // 왼쪽 반, 오른쪽 반을 나누어 반복.
        merge_sort(arr, size / 2);
        merge_sort(arr + size / 2, size - size / 2);
        
        // 왼쪽, 오른쪽 반이 각각 정렬된 상태임. merge한다.
        int leftCursor = 0;
        int rightCursor = size / 2;
        //int buff[50];
        int *buff = new int[size] ;

        int buffCursor = 0;
        // 두 그룹을 각각 스캐닝하면서 순서대로 기록. (어느 한쪽이 끝날때까지)
        while (leftCursor < size / 2 && rightCursor < size) {
            if (arr[leftCursor] < arr[rightCursor]) {
                buff[buffCursor++] = arr[leftCursor++];
            } else {
                buff[buffCursor++] = arr[rightCursor++];
            }
        }
        // 남은 한 그룹의 데이터를 append 
        for (int i = leftCursor ; i < size / 2 ; i++)
            buff[buffCursor++] = arr[i];
        for (int j = rightCursor ; j < size ; j++) 
            buff[buffCursor++] = arr[j];
        memcpy(arr, buff, size * sizeof(int));
        delete[] buff ;
    } else { // 원소 개수가 2개 이하인 경우, 비교하여 정렬한다.
        if (arr[0] > arr[1]) {
            // swap(arr[0], arr[1]);
            int tmp = arr[0] ;
            arr[0] = arr[1] ;
            arr[1] = tmp ;
        }
    }
}



// a: 정렬할 데이터 array
// n: 데이터 개수
void quick_sort(int a[], int n){
	int v, t;
	int i, j;
	if (n > 1){
		v = a[n - 1]; // v=축값. 마지막 노드값을 사용
		i = -1; 
		j = n - 1; 
		while (1){ // 분할
			// while (a[++i] < v); // 왼쪽에서부터 축값보다 크거나 같은 값이 있는지? -> 없다면??? 없을수는 없다. 자신끼리 비교가 마지막.
            while (a[++i]<v) {
                // std::cout << "debug : i=" << i << std::endl ; 
            }

			// while (a[--j] > v); // 오른쪽에서부터 축값보다 작거나 같은 값이 있는지? -> 가장작은값이 pivot이면?? index out range???
            while( a[--j]>v) {
                // std::cout << "debug : j=" << j << std::endl ; 
                // minus index로 갔는데 에러가 발생하지 않았지만, 쓸데없는 오버로드다. 다른 언어였으면 indexerror이다. 
                if (j==0)   // 전체 검색 완료이므로 더 이상 할 필요없다.
                    break ;
            }
			if (i >= j) 
                break; // i와 j의 위치가 뒤바뀌었으면 분할 끝. 좌우 분할이 이미 잘되어 있다. 
            // i와 j의 위치가 좌, 우 상태 그대로 라면 
			t = a[i]; // 두 값을 바꿈. 
			a[i] = a[j];
			a[j] = t;
		}
        // 피봇이 들어갈 자리는? 왼쪽을 기준으로 정렬이 다 된 상태에서 마지막 i자리에 큰 값이 와 있다. 
		t = a[i]; // 축 값과 축값의 위치에 있는 값을 바꿈
		a[i] = a[n - 1];
		a[n - 1] = t;
        // i위치 기준으로 좌우 대소 분할 완료.
		quick_sort(a, i); // 왼쪽 구간 퀵정렬. (i개만 한다. 즉, i위치는 개수에 포함 안함.)
		quick_sort(a + i + 1, n - i - 1); // 오른쪽 구간 퀵정렬 (index로 치면 a+i+1부터 a+n-1. 따라서 개수는 a+n-1 - (a+i+1)+1 )
	}
}



void print_array(int *a, int n) {
    for(int i=0; i<n; i++)
    {
        std::cout << a[i] << " " ;
    }
    std::cout << std::endl ;
}

int check_asc(int *a, int n) {
    if (n<=1) return 1 ;
    for (int i=1; i<n; i++) {
        if (a[i-1]>a[i])
            return 0 ;
    }
    return 1 ;
}

int test_alg(void (*pfunc)(int[], int)) {
    int cnt = std::rand()%50+500 ;
    int *a = new int[cnt] ;
    int bcheck=0 ;

    if (true) {
        // 랜덤값 생성
        for (int i=0; i<cnt; i++) {
            a[i]=  std::rand()%1000 ;
        }
    } else {
        // 이미 정렬된 상태값 생성
        for (int i=0; i<cnt; i++) {
            a[i]=  i ;
        }
    }

    // print_array(a,cnt) ; // 정렬 전.
    // (*pfunc)(a, cnt) ;   // 이렇게 해도 가능.
    pfunc(a,cnt) ;
    // print_array(a,cnt) ; // 정렬 후.
    bcheck = check_asc(a,cnt) ;

    delete[] a ;
    return bcheck ;
}


uint64_t getmilli() {
    using namespace std::chrono;
    return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count() ;
}


int main() {

    std::cout << "sort test" << std::endl ;
    std::srand(std::time(NULL)) ;

    // int a[] = {3,8,5,1,9,4,2,6,7, 10} ;
    // int a[10] ;
    // for (int i=0; i<10; i++) {
    //     a[i] = std::rand()%50 ;
    // }
    // int n = sizeof(a)/sizeof(int) ;
    // print_array(a, n) ;
    // quick_sort(a, n) ;
    // merge_sort(a, n) ;
    // bubble_sort(a, n) ;
    // print_array(a, n) ;
    // return 0 ;

    int bcheck=0 ;
    int okcnt = 0, failcnt=0 ;
    uint64_t ts, te ;


    const char *pfunc_name[] = { "selection_sort",  "bubble_sort", "insertion_sort", "merge_sort",  "quick_sort",   NULL} ;
    void(*pfunc[])(int[], int) = { selection_sort, bubble_sort, insertion_sort, merge_sort, quick_sort,  NULL };
    int pfunc_cnt = sizeof(pfunc) / sizeof(pfunc[0]) ;

    for (int kk=0; kk<pfunc_cnt; kk++) {
        okcnt=0 ;
        failcnt=0 ;
        if (pfunc[kk]==NULL)
            break ;
        std::cout << "ALG=" << pfunc_name[kk] << std::endl ;

        ts = getmilli() ;
        for (int i=0; i<5000; i++) {
            bcheck = test_alg(pfunc[kk]) ;
            if (bcheck) {
                okcnt++ ;
                // std::cout << "OK" << std::endl ;
            } else {
                failcnt++ ;
                // std::cout << "FAIL" << std::endl ;
            }
        }
        te = getmilli() ;
        std::cout << "OK cnt=" << okcnt << "  FAIL cnt=" << failcnt << std::endl ;
        std::cout << te-ts << " ms" << std::endl ;
    }

    return 0 ;
}

만약 이미 정렬된 상태를 다시 정렬을 시키면?

qsort test
ALG=selection_sort
OK cnt=5000 FAIL cnt=0
1507 ms
ALG=bubble_sort
OK cnt=5000 FAIL cnt=0
16 ms
ALG=insertion_sort
OK cnt=5000 FAIL cnt=0
1439 ms
ALG=merge_sort
OK cnt=5000 FAIL cnt=0
164 ms
ALG=quick_sort
OK cnt=5000 FAIL cnt=0
1329 ms
  • 위 경우, bubble, merge가 성능이 좋았다. bubble이 좋았던 이유는 바로 이미 정렬되어 있는지를 처음 루프에서 알아낼 수 있기 때문에 그 조건으로 루프 탈출이 가능하기 때문이다.
  • 위 조건은 quick 소트 입장에서는 worst case이다. 먼저 이미 정렬되었는지 검사하는 루틴을 추가한다면 이런 경우를 방지할 수 있을 것이다.

Author: crazyj7@gmail.com

'Develop > C&CPP' 카테고리의 다른 글

[알고리즘] 정렬5: quick sort  (0) 2019.12.15
[알고리즘] 정렬4: merge sort  (0) 2019.12.15
[알고리즘] 정렬3: Insertion sort  (0) 2019.12.15
[알고리즘] 정렬2: bubble sort  (0) 2019.12.13
[알고리즘] 정렬1: selection sort  (0) 2019.12.13
반응형

Quick Sort

시간복잡도 : O(Nlog_2N) 이지만 최악의 경우는 마찬가지로 O(N^2)

퀵 정렬은 아주 빠른 속도를 나타낼뿐만 아니라 원리도 간단해서 많은 응용 분야에서 사용되고 있다.
퀵 정렬은 연속적인 분할에 의해서 정렬한다.

축(Pivot)값을 중심으로 왼쪽은 이 축값보다 작은 값으로 오른쪽은 모두 이 축값보다 큰 값을 배열시키는 것이다.
이렇게 하여 축값의 왼쪽과 오른쪽 부분을 각각 또다시 분할하고 하는 과정을 분할의 크기가 1이 될 때까지 반복하면 전체적으로는 정렬이 완료된다.

-리스트 마지막 인덱스의 값을 pivot으로 정함.
피봇을 뺀 나머지 배열에서 가장 양쪽 끝 인덱스를 저장. 왼쪽은 i, 오른쪽은 j (인덱스 2개 사용)
i는 오른쪽으로 가면서 해당 값이 pivot보다 작아야 한다. 큰 것이 발견되면 멈춤.
j는 왼쪽으로 가면서 해당 값이 pivot보다 커야 한다. 작은 것이 발견되면 멈춤.
i위치와 j위치의 값을 바꿈.
그런데, i, j가 만나게 되는 경우. (i>=j) 해당 위치가 pivot이 들어갈 자리.
i위치의 값과 pivot 값 swap한다.
pivot을 기준으로 왼쪽, 오른쪽으로 리스트를 나누어, 각각 처음부터 다시 소팅한다.

알고리즘

  1. 만약 n>1 이면
  2. 1 N 크기의 a 배열을 분할 하여 축값의 위치를 mid로 넘긴다.
  3. 2 퀵 정렬 알고리즘(a, mid)
  4. 3 퀵 정렬 알고리즘 (a+mid-1, N-mid-1)
void quick_sort(int a[], int n){
    int v, t;
    int i, j;
    if (n > 1){
        v = a[n - 1]; // v=축값. 마지막 노드값을 사용
        i = -1; 
        j = n - 1; 
        while (1){ // 분할
            while (a[++i] < v); // 왼쪽에서부터 축값보다 크거나 같은 값이 있는지?
            while (a[--j] > v){ // 오른쪽에서부터 축값보다 작거나 같은 값이 있는지? -> 가장작은값이 pivot이면?? index out range 위험 아래 체크 필요.
                if (j==0) break ;
            }
            if (i >= j) break; // i와 j의 위치가 뒤바뀌었으면 분할 끝
            t = a[i]; // 아니면 두 값을 바꿈
            a[i] = a[j];
            a[j] = t;
        }
        t = a[i]; // 축 값과 축값의 위치에 있는 값을 바꿈
        a[i] = a[n - 1];
        a[n - 1] = t;
        quick_sort(a, i); // 왼쪽 구간 퀵정렬
        quick_sort(a + i + 1, n - i - 1); // 오른쪽 구간 퀵정렬
    }
}

퀵 정렬은 난수 배열이나 반쯤 정렬된 배열에 대해서는 빠른 속도를 보이지만 이미 정렬된 배열이나 역순 배열에 대해서는 성능이 엄청나게 떨어진다.
퀵 정렬의 이상적인 경우는 분할이 정확하게 구간을 양분하는 것이다. 이 경우 재귀의 깊이는 logN이 되며 가장 빠른 속도를 나타낸다.
이렇게 퀵 정렬은 분할할 축값이 어느 정도 그 구간의 중앙을 나누느냐에 성능이 좌우된다.
재귀 호출로 인해서 내부 스택이 사용된다. 따라서 퀵 정렬이 속도가 빠른 반면에 메모리의 희생이 있다.
N이 커지면 커질수록 스택의 크기가 커지며 스택 오버플로우가 발생할 수 있다.

성능개선: 이미 정렬된 상태인지를 체크하는 것을 추가한다.

ex)

0,1,2,3,4,5,6,7,8 : 인덱스
5,3,8,4,9,1,6,2,7 : 값

qsort

  1. 피봇을 마지막 번째 노드 값으로 정하자. (보통 첫번째나 마지막번째로 정함.)
    남은 데이터의 양쪽 끝에서 가운데로 스캔해 나가면서 왼쪽에서는 피봇보다 큰 값을 찾으면 멈추고, 오른쪽에서는 피봇보다 작은 값을 찾으면 멈추고, 둘을 교환한다.

pivot=7, scan index=0, 7 start find over or below than pivot.
stop index=2(큰값발견),7(작은값발견) value 8>7>2 ;swap
0,1,2,3,4,5,6,7,8
5,3,2,4,9,1,6,8,7

pivot=7, stop index=4, 6 value 9>7>6 ;swap
0,1,2,3,4,5,6,7,8
5,3,2,4,6,1,9,8,7

pivot=7, stop index=6> 5 ; cross
stop. index=5, 4 인덱스가 교차되면 멈추고, 피봇(오른쪽 파트위치로 인덱스를 잡았으므로 right part에 속해야 한다. left part의 마지막 스캔 위치 인덱스6, 피봇보다 큰 수를 처음 발견한 지점에 들어가야 한다. )과 left last index(6)와 swap
0,1,2,3,4,5,6,7,8
5,3,2,4,6,1,7,8,9
피봇을 기준으로 좌우 분리가 끝남.
피봇 위치가 바뀌면 한 싸이클이 끝난 것임. (pivot 7을 기준으로 좌(low)우(high) 분리 완료)

  1. 좌우 파트("532461", "89")에 대해 각각 qsort 수행. 파트의 원소 개수가 1이면 스킵.
    2-2.
    0 1 (실제 인덱스는 7,8)
    8 9
    pivot=9, stop=N, 0. 왼쪽값을 찾지 못함. 즉, 모두 작다. 이미 피봇은 가장 우측이라 변경할 필요가 없다. 리턴

2-1.
0,1,2,3,4,5
5,3,2,4,6,1
new pivot=1, start 0, 4

pivot=1, stop 0, N; 왼쪽에서는 큰 값을 찾았는데, 오른쪽에서는 작은 값을 찾지 못함. left part last index=0과 swap
0,1,2,3,4,5
1,3,2,4,6,5

  1. 좌우 파트 수행 : "", "32465". 왼쪽 파트는 1개이하라 스킵. 오른쪽 파트 수행
    0 1 2 3 4 (실제 인덱스 : 1,2,3,4,5)
    3 2 4 6 5
    new pivot=5 ; start 0, 3
    pivot=5, stop=3>2.cross! last left index=3. change
    0 1 2 3 4 (실제 인덱스 : 1,2,3,4,5)
    3 2 4 5 6

  2. 좌우 파트 수행 : "3 2 4", "6" ; 오른쪽 파트는 스킵.
    0 1 2 (실제 인덱스 : 1,2,3)
    3 2 4
    pivot=4, stop=N, 1 no swap. break

  3. 좌우 파트 수행 "32", ""
    0 1 (실제 인덱스 : 1,2)
    3 2
    pivot=2, start=0,0
    pivot=2, stop=0, N ; swap with index 0
    0 1 (실제 인덱스 : 1,2)

2 3
6. 좌우 분할 ; "", "3" ; 모두 리턴

0,1,2,3,4,5,6,7,8 : 인덱스
1,2,3,4,5,6,7,8,9 : 값

vector<double>  QuickSort(vector<double>& vec1){
  double i =  0;
  double j = vec1.size()-2;
  double tmp;
  int pivotindex = vec1.size()-1  ;
  double pivot = vec1[pivotindex];
  if  ( vec1.size()<=1  )
    return vec1 ;
  cout <<  "QuickSort: ";
  printvector(vec1)  ;

  while  (i <= j)  {
    while  (vec1[i]  < pivot)
      i++;
    while  (vec1[j]  > pivot)
      j--;
    if  (i <= j)  {
      tmp = vec1[i];
      vec1[i]  = vec1[j];
     vec1[j]  = tmp;
     i++;
     j--;
    }
  }

  // pivot change
  vec1[pivotindex]  = vec1[i]  ;
  vec1[i]=pivot ;
  pivotindex=i ;

  cout <<  "pivotting: ";
  printvector(vec1)  ;

  if  (vec1.size()<=2  )
       return vec1 ;

    // partition
    vector<double> left_vec, right_vec ;
    vector<double>::iterator pivotiter = vec1.begin()+pivotindex ;
    copy(vec1.begin(), pivotiter, back_inserter(left_vec))  ;
    copy(pivotiter+1, vec1.end(), back_inserter(right_vec))  ;

    cout <<  "left: ";
    printvector(left_vec)  ;
    cout <<  "right: ";
    printvector(right_vec)  ;

    if  (left_vec.size()>0  )  {
        QuickSort(left_vec);
        copy(left_vec.begin(), left_vec.end(), vec1.begin())  ;
    }

    if  (right_vec.size()>0  )  {
        QuickSort(right_vec);
        copy(right_vec.begin(), right_vec.end(), pivotiter+1)  ;
    }
    return vec1;
}
반응형

Merge Sort

bottom-up으로 하위 그룹의 정렬부터 상위 그룹 정렬로 올라가며 정렬한다.
머지 정렬은 bottom-up으로 정렬 그룹이 2개 이하일 때를 종료 조건으로 하고, 하위 그룹의 머지 정렬이 끝나면 상위 그룹에서 두 개의 그룹을 합치는 것으로 동작한다.
작은 그룹들이 밑에서부터 미리 정렬되어 있기 때문에 정렬된 그룹간의 정렬이 빠르다는 것을 이용한다. linear하게 비교하면서 merge만 하면 바로 정렬된 상위 그룹을 만들 수 있다.
재귀함수를 사용하여 구현한다.

ex)
5 1 9 3 4 6 2 : 반씩 나눈다.
5 1 9 || 3 4 6 2 : 반
5 | 1 9 || 3 4 | 6 2 : 반
5 | 1 9 || 3 4 | 2 6 : 두 개 이하가 되면 정렬하고 리턴함.
1 5 9 || 2 3 4 6 : 두 그룹을 정렬한다. 리턴한다.
1 2 3 4 5 6 9 : 두 그룹을 정렬한다. 리턴한다.
완료

void mergeSort(int arr[], int size) {
 if (size > 2) {
  // 왼쪽 반, 오른쪽 반을 나누어 반복.
  mergeSort(arr, size / 2);
  mergeSort(arr + size / 2, size - size / 2);

  // 왼쪽, 오른쪽 반이 각각 정렬된 상태임. merge한다.
  int leftCursor = 0;
  int rightCursor = size / 2;
  int buff[50];
  int buffCursor = 0;
  // 두 그룹을 각각 스캐닝하면서 순서대로 기록. (어느 한쪽이 끝날때까지)
  while (leftCursor < size / 2 && rightCursor < size) {
    if (arr[leftCursor] < arr[rightCursor]) {
    buff[buffCursor++] = arr[leftCursor++];
   } else {
     buff[buffCursor++] = arr[rightCursor++];
   }
  }
  // 남은 한 그룹의 데이터를 append 
  for (int i = leftCursor ; i < size / 2 ; i++)
    buff[buffCursor++] = arr[i];
  for (int j = rightCursor ; j < size ; j++) 
    buff[buffCursor++] = arr[j];
  memcpy(arr, buff, size * sizeof(int));
 }else { // 원소 개수가 2개 이하인 경우, 비교하여 정렬한다.
  if (arr[0] > arr[1])
    swap(arr[0], arr[1]);
 }
}
반응형

Insertion Sort

: 삽입 정렬은 왼쪽 부터 항을 1개씩 정렬해나가면서 하나씩 항목을 추가해가면서 뒤에서부터 삽입해서 정렬되는 위치까지 삽입시키는 알고리즘이다.

--> 루프0
index 1을 왼쪽으로 한 칸씩 가면서 들어갈 자리를 찾는다.
index 0과 비교하여 작으면 위치를 바꾼다.
index 1까지 정렬 완료
--> 루프 1
index 2를 왼쪽으로 한 칸씩 가면서 들어갈 자리를 찾는다.
index 1과 비교 : 작으면 위치를 swap하고 계속 진행. 크면 break(루프 탈출)
index 0과 비교 : 작으면 위치를 swap하고 계속 진행. 크면 break(루프 탈출)
index 2까지 정렬 완료
--> 루프2
index 3를 왼쪽으로 한 칸씩 가면서 들어갈 자리를 찾는다.
index 2과 비교 : 작으면 위치를 swap하고 계속 진행. 크면 break(루프 탈출)
index 1과 비교 : 작으면 위치를 swap하고 계속 진행. 크면 break(루프 탈출)
index 0과 비교 : 작으면 위치를 swap하고 계속 진행. 크면 break(루프 탈출)
index 3까지 정렬 완료
...

ex)
loop i=1, j=0 ; index 1의 위치 찾기.
5 1 9 3 4 : index 1을 왼쪽을 비교하여 작으면 swap 크면 break 한다. swap
1 5 9 3 4 : 결과

loop i=2, j=1~0 ; index2의 위치 찾기
1 5 9 3 4 : index 2를 왼쪽을 비교하여 작으면 swap 크면 break 한다. break

loop i=3, j=2~0 ; index 3의 위치 찾기
1 5 9 3 4 : index 3를 왼쪽을 비교하여 작으면 swap 크면 break 한다. swap
1 5 3 9 4 : index 2를 왼쪽을 비교하여 작으면 swap 크면 break 한다. swap
1 3 5 9 4 : index 1를 왼쪽을 비교하여 작으면 swap 크면 break 한다. break
1 3 5 9 4 : 결과

loop i=4, j=3~0 ; index 4의 위치찾기
1 3 5 9 4 : index 4를 왼쪽을 비교하여 작으면 swap 크면 break 한다. swap
1 3 5 4 9 : index 3를 왼쪽을 비교하여 작으면 swap 크면 break 한다. swap
1 3 4 5 9 : index 2를 왼쪽을 비교하여 작으면 swap 크면 break 한다. break
1 3 4 5 9 : 결과

void insertion_sort(int arr[], int size) {
    for(int i = 1 ; i <= size - 1 ; i++) 
        for (int j = i-1 ; j >= 0 ; j--) 
            if(arr[j] > arr[j+1]) {
                // swap(arr[j], arr[j+1]);
                int t = arr[j] ;
                arr[j] = arr[j+1] ;
                arr[j+1] = t ;
            } 
            else
                continue;
} 

'Develop > C&CPP' 카테고리의 다른 글

[알고리즘] 정렬5: quick sort  (0) 2019.12.15
[알고리즘] 정렬4: merge sort  (0) 2019.12.15
[알고리즘] 정렬2: bubble sort  (0) 2019.12.13
[알고리즘] 정렬1: selection sort  (0) 2019.12.13
ASN.1c  (0) 2019.08.01
반응형

Bubble

복잡도: O(n^2)
이중 루프를 돌면서 두 개씩 쌍으로(옆에 있는 것끼리) 비교하여 순서를 맞춘다. (swap) 오른쪽으로 한 칸씩 이동하면서 반복한다.
위 작업을 마치면 마지막에는 가장 큰 값이 들어가게 된다.
다시 전 작업을 반복하는데, 끝 지점을 한 칸 왼쪽으로 이동시킨다. (가장 큰 값은 찾았으므로)

-> 루프0
index 0, 1 비교. (swap)
index 1, 2 비교.
...
index n-2, n-1(마지막인덱스) 비교.
결과 ; n-1인덱스에 가장 큰 값! ; 전체 n-1 번 비교

-> 루프1
index 0, 1 비교.
index 1, 2 비교.
...
index n-3, n-2비교. (마지막 인덱스를 1씩 감소)
결국 n-2에 다음으로 큰 값! ; 전체 n-2번 비교.
...

ex)
loop i=0. j=1-4
5 1 9 3 4 : 인덱스 0, 1을 비교하여 정렬 (before) swap
1 5 9 3 4 : 인덱스 1, 2를 비교하여 정렬
1 5 9 3 4 : 인덱스 2, 3를 비교하여 정렬 swap
1 5 3 9 4 : 인덱스 3, 4를 비교하여 정렬 swap
1 5 3 4 9 : 결과
마지막 인덱스에 가장 큰 값 찾기 완료.
loop i=1. j=1-3
1 5 3 4 9 : 인덱스 0, 1을 비교하여 정렬 (before)
1 5 3 4 9 : 인덱스 1, 2를 비교하여 정렬 swap
1 3 5 4 9 : 인덱스 2, 3를 비교하여 정렬 swap
1 3 4 5 9 : 결과
마지막 전 인덱스에 2번째 큰 값 찾기 완료.
...
(왼쪽 시작부터 버블 모양으로 비교를 한다. 이후 버블을 한 개씩 감소. )

void bubble_sort(int a[], int n){
    int i, j, t;
    for (i=0; i<n-1; i++) {
        for (j=1; j<n-i; j++){
           if (a[j-1] > a[j]){
            t = a[j-1];
            a[j-1] = a[j];
            a[j] = t;
            }
        }
    }
}
  • 성능개선안: swap 교환 횟수가 0이 되면 더 이상 할필요없으므로 리턴하면 된다.

void bubble_sort(int a[], int n){
    int i, j, t;
    for (i = 0; i < n - 1; i++) {
        int bchanged=0 ;
        for (j = 1; j < n - i; j++) // j=(1,10)
        {
            if (a[j - 1] > a[j]){
                t = a[j - 1];
                a[j - 1] = a[j];
                a[j] = t;
                bchanged=1 ;
            }
        }
        if (bchanged==0) break ;
    }
}

'Develop > C&CPP' 카테고리의 다른 글

[알고리즘] 정렬4: merge sort  (0) 2019.12.15
[알고리즘] 정렬3: Insertion sort  (0) 2019.12.15
[알고리즘] 정렬1: selection sort  (0) 2019.12.13
ASN.1c  (0) 2019.08.01
벡터 구조체 필드 기준으로 최대값 최소값 찾기  (0) 2019.05.31
반응형

정렬 알고리즘을 구현해 보고, 성능을 비교해 보자.
대략적으로 성능이 좋지 않은 순서대로 해 보겠다.

Selection Sort

복잡도: O(n^2)

아무 생각없이 바로 만들 수 있는 sorting 코드.
이중 루프를 돌면서 왼쪽부터 가장 작은 값을 찾아 넣음. (크면 바꾼다. swap 이것을 계속 반복하면 가장 작은 값이 index 0에 들어가게 된다.)
(일반적으로 성능 상관없이 정렬 작업할 때)

루프가 하나 끝나면 index 0가 최소값이 되고, 다음 루프로 index 1에 그 다음 작은 값이 들어가는 것을 반복한다.

-> 루프 0
index 0자리를 선택하여 나머지 전체에서 가장 작은 값을 넣고, (n-1번 비교)
index 0를 선택한 것을 index 1 부터 n-1까지 비교하면서 작은값이 있으면 swap. ; n-1인덱스에 가장 큰값이 이동됨.
-> 루프 1
index 1을 선택하여 그 다음 작은 값을 찾아 넣고. (n-2번 비교)
index 1을 선택한 것을 index 2부터 n-1까지 비교. ; n-2인덱스에 그 다음으로 큰 값이 이동됨.
...

ex)
loop i=0. j=1-4
5 1 9 3 4 : 인덱스 0, 1을 비교하여 대소위치 변경. swap
1 5 9 3 4 : 인덱스 0, 2를 비교하여 대소위치 변경
1 5 9 3 4 : 인덱스 0, 3를 비교하여 대소위치 변경
1 5 9 3 4 : 인덱스 0, 4를 비교하여 대소위치 변경
1 5 9 3 4 : 결과
인덱스0에 가장 작은 값 찾기 완료.
loop i=1. j=2-4
1 5 9 3 4 : 인덱스 1, 2을 비교하여 대소위치 변경
1 5 9 3 4 : 인덱스 1, 3를 비교하여 대소위치 변경 swap
1 3 9 5 4 : 인덱스 1, 4를 비교하여 대소위치 변경
1 3 9 5 4 : 결과
인덱스1에 2번째 작은 값 찾기 완료.
...
(왼쪽부터 위치를 하나 찍고 이후 나머지 것들과 모두 비교. 오른쪽으로 한 칸씩 이동)


void selection_sort(int arr[], int size) {
    for(int i = 0 ; i < size - 1 ; i++) 
        for (int j = i + 1 ; j < size ; j++) 
            if(arr[i] > arr[j]) {
                // swap(arr[i], arr[j]);
                int t = arr[i] ;
                arr[i] = arr[j] ;
                arr[j] = t ;
            }
}

'Develop > C&CPP' 카테고리의 다른 글

[알고리즘] 정렬3: Insertion sort  (0) 2019.12.15
[알고리즘] 정렬2: bubble sort  (0) 2019.12.13
ASN.1c  (0) 2019.08.01
벡터 구조체 필드 기준으로 최대값 최소값 찾기  (0) 2019.05.31
smart pointer 스마트포인터?  (0) 2018.07.19
반응형
derivative_br_91

91. ddxx3,definition\frac{d}{dx}x^3, definition

ddxx3=limh0(x+h)3x3h=3hx2+3h2x+h3h=limh03x2+3hx+h2=3x2 \begin{aligned} &\frac{d}{dx}x^3\\ &=\lim_{h\to0}\frac{(x+h)^3-x^3}{h}=\frac{3hx^2+3h^2x+h^3}{h}\\ &=\lim_{h\to0}3x^2+3hx+h^2=3x^2 \end{aligned}


92. ddx3x+1,def.\frac{d}{dx} \sqrt{3x+1}, def.

ddx3x+1=limh03(x+h)+13x+1h=limh0(3x+3h+1)(3x+1)h(3x+3h+1+3x+1)=limh03(3x+3h+1+3x+1)=323x+1 \begin{aligned} &\frac{d}{dx} \sqrt{3x+1}\\ &=\lim_{h\to0} \frac{\sqrt{3(x+h)+1}-\sqrt{3x+1}}{h}\\ &=\lim_{h\to0} \frac{(3x+3h+1)-(3x+1)}{h(\sqrt{3x+3h+1}+\sqrt{3x+1})}\\ &=\lim_{h\to0}\frac{3}{(\sqrt{3x+3h+1}+\sqrt{3x+1})}\\ &=\frac{3}{2\sqrt{3x+1}} \end{aligned}


93. ddx12x+5,def.\frac{d}{dx} \frac{1}{2x+5}, def.

ddx12x+5=limh012(x+h)+512x+5h=2h(2x+2h+5)(2x+5)h=limh02(2x+2h+5)(2x+5)=2(2x+5)2 \begin{aligned} &\frac{d}{dx} \frac{1}{2x+5}\\ &=\lim_{h\to0} \frac{\frac{1}{2(x+h)+5}-\frac{1}{2x+5}}{h}=\frac{ \frac{-2h}{(2x+2h+5)(2x+5)}}{h}\\ &=\lim_{h\to0} -\frac{2}{(2x+2h+5)(2x+5)}\\ &=-\frac{2}{(2x+5)^2} \end{aligned}


94. ddx1x2,def.\frac{d}{dx}\frac{1}{x^2}, def.

ddx1x2=limh01(x+h)21x2h=2xhh2x2(x+h)2h=2xhx2(x+h)2=2xx4=2x3 \begin{aligned} &\frac{d}{dx}\frac{1}{x^2}\\ &=\lim_{h\to0} \frac{\frac{1}{(x+h)^2}-\frac{1}{x^2}}{h}= \frac{\frac{-2xh-h^2}{x^2(x+h)^2}}{h}=\frac{-2x-h}{x^2(x+h)^2}\\ &=\frac{-2x}{x^4}=-\frac{2}{x^3} \end{aligned}


95. ddxsinx,def.\frac{d}{dx}sinx, def.

ddxsinx=limh0sin(x+h)sin(x)h=limh0sin(x)cos(h)+cos(x)sin(h)sin(x)h=limh0sinx(cos(h)1)h+cos(x)sin(h)hcos(h)=1h22!+h44!...limh0cos(h)1h=hc+h3c+..=O(h)=0sin(h)=hh33!+...limh0sin(h)h=1O(h2)=1=sin(x)0+cos(x)1=cos(x) \begin{aligned} &\frac{d}{dx} sinx=\lim_{h\to0} \frac{sin(x+h)-sin(x)}{h}\\ &=\lim_{h\to0} \frac{ sin(x)cos(h)+cos(x)sin(h)-sin(x)}{h}\\ &=\lim_{h\to0} \frac{sinx(cos(h)-1)}{h}+cos(x)\frac{sin(h)}{h}\\ & cos(h)=1-\frac{h^2}{2!}+\frac{h^4}{4!}-...\\ & \lim_{h\to0} \frac{cos(h)-1}{h}=hc+h^3c+..=O(h)=0 \\ & sin(h)=h-\frac{h^3}{3!}+...\\ & \lim_{h\to0} \frac{sin(h)}{h}=1-O(h^2)=1\\ & \therefore =sin(x)0+cos(x)1=cos(x) \end{aligned}


96. ddxsecx,def.\frac{d}{dx}secx, def.

ddxsec(x)=limh0sec(x+h)sec(x)h=limh01/cos(x+h)1/cos(x)h=cos(x)cos(x+h)cos(x+h)cos(x)h=cos(x)cos(x)cos(h)+sin(x)sin(h)(cos(x)cos(h)sin(x)sin(h))cos(x)h=1cos(h)+tan(x)sin(h)h(cos(x)cos(h)sin(x)sin(h))=lim1cos(x)cos(h)sin(x)sin(h)(lim1cos(h)h+limtan(x)sin(h)h)=1cos(x)(0+tan(x))=sec(x)tan(x) \begin{aligned} &\frac{d}{dx}sec(x)=\lim_{h\to0}\frac{\sec(x+h)-\sec(x)}{h}\\ &=\lim_{h\to0}\frac{1/\cos(x+h)-1/\cos(x)}{h}=\frac{cos(x)-cos(x+h)}{cos(x+h)cos(x)h}\\ &=\frac{cos(x)-cos(x)cos(h)+sin(x)sin(h)}{(cos(x)cos(h)-sin(x)sin(h))cos(x)h}\\ &=\frac{1-cos(h)+tan(x)sin(h)}{h(cos(x)cos(h)-sin(x)sin(h))}\\ &=\lim \frac{1}{cos(x)cos(h)-sin(x)sin(h)} (\lim \frac{1-cos(h)}{h}+\lim \frac{tan(x)sin(h)}{h}) \\ &=\frac{1}{cos(x)}(0+tan(x))=sec(x)tan(x) \end{aligned}


97. ddxarcsinx,def.\frac{d}{dx}arcsinx, def.

ddxarcsinx=limh0arcsin(x+h)arcsin(x)h \begin{aligned} &\frac{d}{dx}arcsinx=\lim_{h\to0} \frac{arcsin(x+h)-arcsin(x)}{h}\\ \end{aligned}

fail

ddxarcsinx=limh0arcsin(x+h)arcsin(x)hsin(ab)=sinacosbsinbcosaarcsinsin(ab)=arcsin(sinacosbsinbcosa)ab=arcsin(sinacosbsinbcosa)a=arcsin(x+h),b=arcsin(x)arcsin(x+h)arcsin(x)=arcsin(sin(arcsin(x+h))cos(arcsin(x))sin(arcsin(x))cos(arcsin(x+h)))=arcsin((x+h)cos(arcsin(x))xcos(arcsin(x+h)))(cos(x)=1sin2(x))We know,limx0sinxx=1,limx0sin(x)=limx0xSo,limx0sin1(x)=limx0x=arcsin((x+h)1x2x1(x+h)2)ddxarcsinx=limh0arcsin(x+h)arcsin(x)h=limh0arcsin((x+h)1x2x1(x+h)2)h=limh0(x+h)1x2x1(x+h)2h=limh0(x+h)2(1x2)x2(1(x+h)2)h((x+h)1x2+x1(x+h)2)Numerator=(x+h)2x2(x+h)2x2+x2(x+h)2Numerator=(x+h)2x2=2xh+h2=limh02x+h(x+h)1x2+x1(x+h)2=2xx1x2+x1x2=2x2x1x2=11x2 \begin{aligned} &\frac{d}{dx}arcsinx=\lim_{h\to0} \frac{arcsin(x+h)-arcsin(x)}{h}\\ & sin(a-b) = sinacosb-sinbcosa\\ & \arcsin {sin(a-b)} = \arcsin {(sinacosb-sinbcosa)}\\ & a-b = \arcsin {(sinacosb-sinbcosa)}\\ & a=arcsin(x+h), b=arcsin(x)\\ &arcsin(x+h)-arcsin(x) = arcsin(sin(arcsin(x+h))cos(arcsin(x))-sin(arcsin(x))cos(arcsin(x+h)))\\ &=arcsin((x+h)cos(arcsin(x))-xcos(arcsin(x+h)))\\ & (cos(x) = \sqrt {1-sin^2(x)}) \\ & \text{We know,} \lim_{x\to0} \frac{sin x}{x}=1, \lim _{x\to0} sin(x) = \lim_{x\to0} x\\ &So, \lim_{x\to0} sin^{-1}(x)=\lim_{x\to0}x &=arcsin( (x+h) \sqrt{1-x^2}-x\sqrt{1-(x+h)^2} )\\ &\frac{d}{dx}arcsinx=\lim_{h\to0} \frac{arcsin(x+h)-arcsin(x)}{h}\\ &=\lim_{h\to0} \frac{arcsin( (x+h) \sqrt{1-x^2}-x\sqrt{1-(x+h)^2} )}{h}\\ &=\lim_{h\to0} \frac{ (x+h) \sqrt{1-x^2}-x\sqrt{1-(x+h)^2} }{h} \\ &=\lim_{h\to0} \frac{ (x+h)^2(1-x^2)-x^2(1-(x+h)^2)} {h ((x+h) \sqrt{1-x^2}+x\sqrt{1-(x+h)^2} )} \\ &Numerator=(x+h)^2-x^2(x+h)^2-x^2+x^2(x+h)^2\\ &Numerator=(x+h)^2-x^2=2xh+h^2\\ &=\lim_{h\to0} \frac{ 2x+h} {(x+h) \sqrt{1-x^2}+x\sqrt{1-(x+h)^2} } \\ &=\frac{2x}{x\sqrt{1-x^2}+x\sqrt{1-x^2}}=\frac{2x}{2x\sqrt{1-x^2}}\\ &=\frac{1}{\sqrt{1-x^2}} \end{aligned}


98. ddxarctanx,def.\frac{d}{dx}arctanx, def.

Try like upper case, lim tan(x)/x = 1, atan(x)/x=1

ddxarctan(x)=limh0arctan(x+h)arctan(x)htan(ab)=tan(a)tan(b)1+tan(a)tan(b)ab=arctan(tan(a)tan(b)1+tan(a)tan(b))Numerator=arctan(x+h)arctan(x)N=arctan(tan(arctan(x+h))tan(arctan(x))1+tan(arctan(x+h))tan(arctan(x)))=arctan(x+hx1+(x+h)x)=artan(h1+x2+hx)So,ddxarctan(x)=limh0arctan(x+h)arctan(x)h=limh0artan(h1+x2+hx)h=limh011+x2+hx=11+x2 \begin{aligned} &\frac{d}{dx}arctan(x)=\lim_{h\to0} \frac{arctan(x+h)-arctan(x)}{h}\\ & tan(a-b)=\frac{tan(a)-tan(b)}{1+tan(a)tan(b)}\\ & a-b = arctan(\frac{tan(a)-tan(b)}{1+tan(a)tan(b)})\\ &Numerator=arctan(x+h)-arctan(x)\\ &N=arctan( \frac{tan(arctan(x+h))-tan(arctan(x))}{1+tan(arctan(x+h))tan(arctan(x))} )\\ &=arctan( \frac{x+h-x}{1+(x+h)x} )=artan(\frac{h}{1+x^2+hx})\\ &So, \\ &\frac{d}{dx}arctan(x)=\lim_{h\to0} \frac{arctan(x+h)-arctan(x)}{h}\\ &=\lim_{h\to0} \frac{artan(\frac{h}{1+x^2+hx})}{h}\\ &=\lim_{h\to0} \frac{1}{1+x^2+hx}=\frac{1}{1+x^2}\\ \end{aligned}


99. ddxf(x)g(x),def.\frac{d}{dx}f(x)g(x), def.

ddxf(x)g(x)=limh0f(x+h)g(x+h)f(x)g(x)h=limh0f(x+h)g(x+h)f(x)g(x)g(x+h)f(x)+g(x+h)f(x)h=limh0g(x+h)(f(x+h)f(x))+f(x)(g(x+h)g(x))h=limh0g(x+h)f(x+h)f(x)h+f(x)g(x+h)g(x)h=g(x)f(x)+f(x)g(x)=f(x)g(x)+f(x)g(x) \begin{aligned} &\frac{d}{dx}f(x)g(x)=\lim_{h\to0}\frac{f(x+h)g(x+h)-f(x)g(x)}{h}\\ &=\lim_{h\to0}\frac{f(x+h)g(x+h)-f(x)g(x)-g(x+h)f(x)+g(x+h)f(x)}{h}\\ &=\lim_{h\to0} \frac{g(x+h)(f(x+h)-f(x))+f(x)(g(x+h)-g(x))}{h}\\ &=\lim_{h\to0} g(x+h)\frac{f(x+h)-f(x)}{h}+f(x)\frac{g(x+h)-g(x)}{h}\\ &=g(x)f'(x)+f(x)g'(x)=f'(x)g(x)+f(x)g'(x) \end{aligned}


100. ddxf(x)g(x),def.\frac{d}{dx} \frac{f(x)}{g(x)}, def.

ddxf(x)g(x)=limh0f(x+h)g(x+h)f(x)g(x)h=f(x+h)g(x)f(x)g(x+h)g(x)g(x+h)h=f(x+h)g(x)f(x)g(x+h)g(x)f(x)+g(x)f(x)hg(x)g(x+h)=g(x)(f(x+h)f(x))f(x)(g(x+h)g(x))hg(x)g(x+h)=g(x)f(x)f(x)g(x)g(x)2 \begin{aligned} &\frac{d}{dx} \frac{f(x)}{g(x)}=\lim_{h\to0}\frac{ \frac{f(x+h)}{g(x+h)} - \frac{f(x)}{g(x)}}{h} =\frac{ \frac{f(x+h)g(x)-f(x)g(x+h)}{g(x)g(x+h)} }{h}\\ &=\frac{ f(x+h)g(x)-f(x)g(x+h)-g(x)f(x)+g(x)f(x)}{hg(x)g(x+h)}\\ &=\frac{g(x)(f(x+h)-f(x))-f(x)(g(x+h)-g(x))}{hg(x)g(x+h)}\\ &=\frac{g(x)f'(x)-f(x)g'(x)}{g(x)^2} \end{aligned}


101. ddxxxx\frac{d}{dx} x^{{x}^{x}}

First,ddxxxy=xx,lny=xlnx,(1/y)y=lnx+x(1/x)y=ylnx+y=xxlnx+xx \frac{d}{dx}x^x\\ y=x^x, lny=xlnx, (1/y)y'=lnx+x(1/x)\\ y'=ylnx+y=x^xlnx+x^x
Second,
ddxxxxy=xxxlny=xxln(x)1yy=(xxlnx+xx)ln(x)+xx1x=xx((lnx)2+ln(x)+1x)y=xxxxx((lnx)2+ln(x)+1x) \begin{aligned} &\frac{d}{dx} x^{x^{x}}\\ &y=x^{x^{x}} \\ &ln y = x^x ln(x) \\ &\frac{1}{y} y' = (x^xlnx+x^x)ln(x)+x^x\frac{1}{x}\\ &=x^x((lnx)^2+ln(x)+\frac{1}{x})\\ &y'=x^{x^x}x^x((lnx)^2+ln(x)+\frac{1}{x})\\ \end{aligned}


The END

Author: crazyj7@gmail.com

'Math' 카테고리의 다른 글

미적분학의 본질 #2  (0) 2020.08.27
미적분학의 본질 #1  (1) 2020.08.27
Derivative100 [81-90]  (0) 2019.12.12
derivative100 [71-80]  (0) 2019.11.27
derivative100 [61-70]  (0) 2019.11.19
반응형
derivative_br_81

81. ddxexsinhx\frac{d}{dx}e^x sinhx

ddxexsinhx=exsinhx+excoshx=ex(sinhx+coshx)=ex(2ex2)=e2x \begin{aligned} &\frac{d}{dx}e^x sinhx\\ &=e^xsinhx+e^xcoshx=e^x(sinhx+coshx)\\ &=e^x(\frac{2e^x}{2})=e^{2x} \end{aligned}


82. ddxsech(1x)\frac{d}{dx}sech(\frac{1}{x})

ddxsech(1x)sech(x)=1/cosh(x),D(sech(x))=sinh(x)/cosh2(x)=sech(x)tanh(x)ddxsech(1x)=sinh(1/x)/cosh2(1/x)(1/x2)=sinh(1/x)x2cosh2(1/x)=sech(1x)tanh(1x)x2 \begin{aligned} &\frac{d}{dx}sech(\frac{1}{x})\\ & sech (x)=1/cosh(x), D(sech(x))=-sinh(x)/cosh^2(x)\\ &=-sech(x)tanh(x)\\ &\frac{d}{dx}sech(\frac{1}{x})=-sinh(1/x)/cosh^2(1/x)(-1/x^2)\\ &=\frac{sinh(1/x)}{x^2cosh^2(1/x)}=\frac{sech(\frac{1}{x})tanh(\frac{1}{x})}{x^2}\\ \end{aligned}


83. ddxcosh(lnx))\frac{d}{dx}cosh(lnx))

ddxcosh(lnx)=sinh(lnx)x=elnxelnx2x=x(1/x)2x=x212x2 \begin{aligned} &\frac{d}{dx}cosh(lnx)=\frac{sinh(lnx)}{x}=\frac{e^{lnx}-e^{-lnx}}{2x}\\ &=\frac{x-(1/x)}{2x}=\frac{x^2-1}{2x^2}\\ \end{aligned}


84. ddxln(coshx)\frac{d}{dx}ln(coshx)

ddxln(coshx)=sinhxcoshx=tanh(x) \begin{aligned} &\frac{d}{dx}ln(coshx)=\frac{sinhx}{coshx}=tanh(x)\\ \end{aligned}


85. ddxsinhx1+coshx\frac{d}{dx}\frac{sinhx}{1+coshx}

ddxsinhx1+coshx=coshx(1+coshx)sinhxsinhx1+cosh2x+2cosh(x)=coshx+cosh2xsinh2x(1+coshx)2=1+coshx(1+coshx)2=11+coshx \begin{aligned} &\frac{d}{dx}\frac{sinhx}{1+coshx}=\frac{coshx(1+coshx)-sinhxsinhx}{1+cosh^2x+2cosh(x)}\\ &=\frac{coshx+cosh^2x-sinh^2x}{(1+coshx)^2}=\frac{1+coshx}{(1+coshx)^2}\\ &=\frac{1}{1+coshx} \end{aligned}


86. ddxarctanh(cosx)\frac{d}{dx}arctanh(cosx)

ddxarctanh(cosx)D(arctanh(x))=11x2y=arctanh(x),x=tanh(y),dx=sech2(y)dydy/dx=1/sech2(y)=cosh2(y)=1(1/cosh2(y))=1(cosh2(y)sinh2(y))/cosh2(y)=11tanh2(y)=11x2ddxarctanh(cosx)=sinx1cos2x=sin(x)sin2(x)=csc(x) \begin{aligned} &\frac{d}{dx}arctanh(cosx)\\ &D(arctanh(x)) = \frac{1}{1-x^2}\\ &y=arctanh(x), x=tanh(y), dx=sech^2(y)dy\\ &dy/dx = 1/sech^2(y)=cosh^2(y)=\frac{1}{(1/cosh^2(y))}\\ &=\frac{1}{( cosh^2(y)-sinh^2(y))/cosh^2(y)}=\frac{1}{1-tanh^2(y)}\\ &=\frac{1}{1-x^2}\\ &\frac{d}{dx}arctanh(cosx)=-\frac{sinx}{1-cos^2x}\\ &=-\frac{sin(x)}{sin^2(x)}=-csc(x)\\ \end{aligned}


87. ddx(x)(arctanhx)+ln((1x2))\frac{d}{dx}(x)(arctanhx)+ln(\sqrt{(1-x^2}))

ddx(x)(arctanhx)+ln(1x2)=arctanh(x)+x11x2+11x22x21x2=arctanh(x)+x1x2x1x2=arctanh(x) \begin{aligned} &\frac{d}{dx}(x)(arctanhx)+ln(\sqrt{1-x^2})\\ &=arctanh(x)+x\frac{1}{1-x^2}+\frac{1}{\sqrt{1-x^2}}\frac{-2x}{2\sqrt{1-x^2}}\\ &=arctanh(x)+\frac{x}{1-x^2}-\frac{x}{1-x^2}\\ &=arctanh(x) \end{aligned}


88. ddxarcsinh(tanx)\frac{d}{dx}arcsinh(tanx)

ddxarcsinh(tanx)=11+tan2xsec2x=sec2xsecx=sec(x) \begin{aligned} &\frac{d}{dx}arcsinh(tanx)\\ &=\frac{1}{\sqrt{1+tan^2x}}sec^2x=\frac{sec^2x}{sec x}\\ &=sec(x) & \end{aligned}


89. ddxarcsin(tanhx)\frac{d}{dx}arcsin(tanhx)

ddxarcsin(tanhx)=11tanh2xsech2x1tanh2x=cosh2xsinh2xcosh2x=sech2x=sech2xsech2x=sech(x) \begin{aligned} &\frac{d}{dx}arcsin(tanhx)\\ &=\frac{1}{\sqrt{1-tanh^2x}} sech^2x\\ &1-tanh^2x = \frac{cosh^2x-sinh^2x}{cosh^2x}=sech^2x\\ &=\frac{sech^2x}{\sqrt {sech^2x} }=sech(x) \end{aligned}


90. ddxarctanhx1x2\frac{d}{dx} \frac{arctanhx}{1-x^2}

ddxarctanhx1x2=11x2(1x2)arctanh(x)(2x)(1x2)2=1+2xarctanh(x)(1x2)2 \begin{aligned} &\frac{d}{dx} \frac{arctanhx}{1-x^2}\\ &=\frac{\frac{1}{1-x^2}(1-x^2)-arctanh(x)(-2x)}{(1-x^2)^2} \\ &=\frac{1+2x arctanh(x)}{(1-x^2)^2} \\ \end{aligned}


Author: crazyj7@gmail.com

'Math' 카테고리의 다른 글

미적분학의 본질 #1  (1) 2020.08.27
Derivative100 [91-100]  (0) 2019.12.12
derivative100 [71-80]  (0) 2019.11.27
derivative100 [61-70]  (0) 2019.11.19
derivatie100 [51-60]  (0) 2019.11.18

+ Recent posts