toplogical sort

2016-11-09

아래 처럼 모든 unvisited node를 돌면서 topologicalSort를 불러주는 방법이 있는가 하면, 각 노드로 들어가는 edge를 수를 트래킹하면서(indegree map) 트래버스할 수 도 있다.

using incoming edge

1 2	1 -> 2 3 -> 2 -> 5

위와 같은 그래프가 있다고 치자.. 그럼 각노드의 incoming edge수를 세어보면 이렇게 된다.
1: 0
3: 0
2: 2
5: 1

incoming edge가 0라는 말은 아무 prerequisite이 없으니 이 노드부터 traverse할 수 있다는 얘기니까 1/3번 노드를 가장먼저 진행하고 1/3번을 제거하면 2의 incoming edge는 0가 된다. 그러니 2를 진행할 수 있고 2가 없어지면 5의 incoming edge가 0가 되어서 5도 없앨 수 있다. 이렇게 topological sort가 되는 것이다.

using dfs

boolean topologicalSort(int[][] map,int[] visited, int here, List<Integer> path ){
    if(visited[here] == 2) returnt true; // if visited return
    if (visited[here] == 1) return false; // detect cycle

    visited[here] = 1; // open

    for (int i = 0; i < map[here].length; i++){
        if(map[here][i]==1)
            topologicalSort(map, visited, i, path);
    }

    visited[here] = 2; // close
    path.add(here);
    return true;
}

detect cycle

cycle의 경우, directed graph는 visited의 state(1:open, 2:close)까지 봐야 하는 반면, undirectional graph의 경우는 visited의 여부만 보면 된다. 즉 visited에 node에 들어가면 바로 cycle이라고 판정하면 된다.

Problems

알고리즘 이해가 되었다면 아래 문제들 풀어보시길.

course schedule : 기본.
alien dictionary @leetcode : 코너 케이스가 많으니 정신 바짝 차리고.
sequence reconstruction @leetcode : 응용
https://leetcode.com/problems/parallel-courses/
https://leetcode.com/problems/parallel-courses-ii/

Reference

explanation @geeks

sliding window maximum/minimum

2016-11-08

Given array [A₀,A₁, - ,A_n ], sliding window of size k which is moving from the very left of the array to the very right. find max/min of each sliding window.

naive

O(NK) 로 가능.

using priority_queue

슬라이딩 윈도우의 값들을 TreeSet으로 오더를 유지해주면 O(Nlog(K)) 정도로 풀 수 있다. O(logK)는 추가 및 삭제에 걸리는 시간

linear

O(N)도 가능!

intuition:

윈도우 안의 값이 추가될때, 기존 최대보다 크다면 기존 것은 버리고 새로운 값이 최대가 된다. 그러므로 자연스럽게 내림차순 정렬이 된다!
값이 삭제될때, 최대값이 삭제되면 그 다음 값이 최대값이 된다.

구현 :

window안의 값을 deque로 관리하는데 head에는 최소 값, tail에는 최대값이 들어가게 관리.
whenever add a[i], while(a[i]>head) 이면 head 삭제. 윈도우의 값보다 작은 값들은 모두 버린다. 왜 그럴까? (버려지는 값들은 a[i]가 있는한 최대값이 될 수 없으므로).
그럼 sliding window가 범위를 벗어날때, 삭제는 어떻게 하면 될까? deque를 돌면서 지우면 될까? 그렇게 하면 O(N)을 만족할 수 없고, 우리는 tail값만 사용할 것이므로 tail이 현재 window에 있는지만 보면 된다. 따라서, 각 스텝마다 윈도우를 벗어나면 지우면 된다.

public int[] maxSlidingWindow(int[] nums, int k) {
       int N = nums.length;
       int R = N-k+1;
       if(R<=0) return new int[]{};
       int[] ret = new int[R];
       LinkedList<Integer> deque = new LinkedList<>(); //first:min, last:max

       for (int i = 0; i < N; i++) {
           int start = i-k+1;
           int end = i;

           while(!deque.isEmpty()&& deque.peekLast()<start)
               deque.removeLast();

           while(!deque.isEmpty() && nums[deque.peekFirst()] <= nums[end] )
               deque.removeFirst();
           deque.addFirst(end);

           if(start>=0)
               ret[start] = nums[deque.peekLast()];
       }
       return ret;
   }

Problems

이해가 되었다면 아래 문제들을 풀어보자.

Sliding Window Maximum @leetcode
응용 문제, Shortest subarray with sum at least K

Reference

History

2018.07.03 , 응용문제 추가

kadane algorithm, maximum sum subarray

2016-11-05

Kadane

find the max sum of contiguous subarray of given array.
-1, -2, 3, 4, -5, 6

위의 경우 {3,4,-5,6} = 8이 된다.

naive

start, end index를 정해서 for loop 2번 하면 구할 수 있음. O(n^2)

dp

dp[i] -> index i 에서 끝나는 subarray 중에서 쵀대값. 이라고 정의 하면

dp[i] = max(dp[i - 1] + a[i], a[i]). 증명은 a[i]가 음수,양수 나누어서 해보면 증명할 수 있음.

time complexity는 O(N)

int[] dp = new int[N];
dp[0]=a[0];
max_sum=a[0];
for(int i=1;i<N;i++){
	dp[i]=Math.max(dp[i-1]+a[i], a[i]);
	max_sum=Math.max(max_sum, dp[i]);
}

이때, memory optimization을 할 수 있다. dp[i]는 항상 dp[i-1]과 디펜던시가 있으니, 그 전단계를 가지고 있으면 O(N) 메모리를 O(1)으로 절약할 수 있다.

cur_max =a[0];
max_sum=a[0];
for(int i=1;i<N;i++){
	cur_max=Math.max(cur_max+a[i], a[i]);
	max_sum=Math.max(max_sum, dp[i]);
}

응용

위의 문제를 약간만 바꿔서 K보다 작으면서 가장 큰 값을 찾으라는 문제로 바뀌었다.

Given an array of integers A and an integer k, find a subarray that contains the largest sum, subject to a constraint that the sum is less than k?

intuition

안타깝게도 위의 제약조건이 들어가면 dp방식으로는 풀수 없다. 그리고 값을 비교해야 하기 때문에 sort가 필요하다. 그러면 O(longN)의 complexity가 붙겠지.

range sum은 보통 array의 처음부터 cumulative sum을 해서 cum[j]-cum[i] where i<j 을 해주면 구할 수 있다.

여기서 더 발전시키면, 왼쪽에서 부터 cum[j]를 TreeSet에 추가하기 전에, 트리에 이미있는 값들은 소트가 되어 있으므로 트리에 있는 값중 최적의 갑을 찾아낼 수 있다. 아래에서 cum[j],k는 상수 이므로 TreeSet의 값중에서 ceiling 를 찾으면 된다.

cum[j]-cum[i]<=k, where i cum[i]>=cum[j]-k

implementation

int maxSumLessThanK(int[] a, int k){
    int ret=Integer.MIN_VALUE;
    int sum=0;
    TreeSet<Integer> set = new TreeSet<>();
    set.add(0);
    for (int i = 0; i < N; i++){
        sum+=nums[i];
        int min = set.ceiling(sum-k);
        ret=Math.max(ret, min);        
        set.add(sum);
    }

    return ret;
}

Problems

알고리즘 이해가 되었다면 아래 문제들 풀어보시길.

Reference

explanation @geeks

(no title)

2016-11-02

BSP(Bulk Synchronous parallel) model
sequence of iterations, called superstep

running arm dockerimage on x86

2016-07-16

docker v1.12 버전 부터는 container에 qemu가 설치만 되어 있으면 Mac(x86)에서 arm docker image를 실행할 수 있다.

좋구나.
이전에는 qemu-arm-static trick을 사용했어야 했다. https://resin.io/blog/building-arm-containers-on-any-x86-machine-even-dockerhub/ 참고.
https://docs.docker.com/docker-for-mac/multi-arch/

Hadoop cluster docker for ARM

2016-06-28

ARM architecture에 hadoop cluster docker image를 만들어 보았다.

docker hub의 armv7/armhf-ubuntu_core:15.10 이미지를 기반으로 Dockerize를 시도.

크게 3개의 이미지를 만들 것

hadoop-base
hadoop-slave
hadoop-master

hadoop-base image

hadoop-base 에서는 slave와 master에서 공통적으로 사용할 것들을 설정

install java, openssh server
qemu-arm-static. 이것은 아래에서 설명
passwordless ssh
install hadoop

qemu-arm-static

qemu를 사용해서 x86 머신에서 docker를 빌드/테스트 하는 이유는 아래 2가지 이유 때문.

arm device가 잘 없다는 것. raspberry pi 정도?
arm device는 대게 x86 desktop 보다 느리니까

그래서 구글링 하다가 qemu를 이용해서 하는 방법을 찾아서 따라해 보니 잘 동작한다. 원리는 모든 커맨드 바로 앞에 qemu-arm-static을 붙여서 arm instruction을 x86으로 변환해 주는 것 되겠다.

install packages

java, ssh server, vim 등을 설치해 준다.

1	RUN apt-get update && apt-get install -y openjdk-7-jdk openssh-server openssh-client rsync vim

passwordless ssh

hadoop cluster를 구성하려면 cluster간 passwordless ssh가 구성이 되어야 한다. 그것을 위해서

# sshd setting
RUN ssh-keygen -t rsa -f /root/.ssh/id_rsa -P ''
RUN cat /root/.ssh/id_rsa.pub >> /root/.ssh/authorized_keys
ADD config /root/.ssh/
RUN chmod 600 /root/.ssh/config
#RUN chown root:root /root/.ssh/config
RUN echo 'root:sheepdog' | chpasswd
RUN sed -i 's/PermitRootLogin without-password/PermitRootLogin yes/' /etc/ssh/sshd_config
RUN echo "UsePAM no" >> /etc/ssh/sshd_config
RUN echo "Port 2122" >> /etc/ssh/sshd_config

reference

my hadoop arm multinode project @github
hadoop multinode : serf를 이용해서 host name resolution을 하는듯. 설정을 하려면 slave의 host name 혹은 ip를 알아야 하는데 이것 설정도 꽤 귀찮은 일. serf!

revision history

2016-6-28 draft

django

2016-04-15

Spring, Django, Ruby on Rails 등등 수많은 웹 프레임워크가 있다. 이 중 내가 이번에 선택한 것은 django이다. 그 이유는

admin 이 그냥 생기고(model을 정의만 하면…)
python 에 비교적 익숙하고
community가 발달되어서 3rd party app(django에서의 앱은 하나의 동자적인 기능을 하는 모듈이라고 보면 된다)이 많이 있다. Oauth2 authentication이라든가, markdown editor라든지…

MVC에서, M은 Model, V는 View(Template) C는 urls.py가 담당하게 된다.

Model

class Problem(models.Model):
    problem = models.CharField(max_length=200)
    pub_date = modesl.DateTimeField('date published')

    def __unicode__(self):
        return self.problem

# create new isntance & save to DB
new_instance = Problem(problem='which one is better?')
new_instance.save()

Controller

urls.py를 request url을 regex로 각 뷰로 dispatch한다.

urlpatterns = [
    url(r'^$', views.IndexView.as_view(), name='index'),
    url(r'^(?P<pk>[0-9]+)/$', views.DetailView.as_view(), name='detail'),
    url(r'^(?P<pk>[0-9]+)/results/$', views.ResultsView.as_view(), name='results'),
    url(r'^(?P<question_id>[0-9]+)/vote/$', views.vote, name='vote'),
    ]

View(Template)

우리가 서버로 사용하는 것은 Django이고 실제로 웹사이트의 사용자가 보게 되는 것은 html이다. 그러면 django object를 html로 변환하는 과정이 필요하게 마련인데, 이것을 해주는 것이 template 되겠다.

object는 handle bar형식으로 표현이 되고, 그 외의 것은 {% tag %} 로 표현이 된다. 아래의 예제에서 extends, block, for, endfor, endblock 등이 되겠다.

신선했던 것은 template도 상속관계를 가질수 있다는 것. 그래서 전체적인 구조(block)는 base.html에서 잡아두고, override 하고 싶은 부분만 extends해서 커스터마이징 할 수 있다. 실제로도 아주 편한 피쳐임.

{% raw %}
{% extends "base_generic.html" %}

{% block title %}{{ section.title }}{% endblock %}

{% block content %}
<h1>{{ section.title }}</h1>

{% for story in story_list %}
<h2>
  <a href="{{ story.get_absolute_url }}">
    {{ story.headline|upper }}
  </a>
</h2>
<p>{{ story.tease|truncatewords:"100" }}</p>
{% endfor %}
{% endblock %}
{% endraw %}

revision history

2016-4-15 draft
2016-5-10 controller, view 업데이트

docker

2016-03-03

최근에 docker를 사용해볼 기회가 있어서 몇가지 컨셉 도움이 되는 것들을 정리해 보기로 한다. docker이전엔 virtual machine(VM)이 있었고 이것으로 많이 사용했지만 VM의 문제는 무겁다는 것. 그래서 light하게 에뮬레이션 할 수 있게 docker가 나오기 시작함. 개발환경/서버환경 설정등으로 사용하면 좋은 use case가 됨.

image vs container

처음 헷갈린 것은 image와 container의 관계. image는 read-only이고 container는 image를 기반으로 실행되고 있는 것을 의미함. class와 instance의 관계라고 하면 적당한 비유가 될 것 같다.

name	image	conatiner
list	docker images	docker ps

build

docker image 를 빌드하려면 Dockerfile을 작성하면 되는데, 이 파일은 일련의 명령들을 순차적으로 실행해서 내가 원하는 이미지를 만드는 형식이다.

1
2
3

# build using current directory's Dockerfile
docker build .
docker build -t myimage:latest . # set tag as myimage:latest

run

docker run

-p host_port:container_port : port forwarding
-v host_volume:container_volumen : volume mapping
-it : open tty interactive shell
–net=host : host network을 그대로 사용하게 함. 즉, expose된 모든 port들은 외부에서 접근가능하게 됨. default는 port forwarding을 해줘야만 접근이 가능함.
-e : env va를 다커로 넘겨주는 명령. 환경변수가 많을 경우 --env-file env.list 옵션을 사용할 수 있음.

# run nginx docker image with 8000 port
docker run -it -p 8000:80 nginx
docker run -d -e POSTGRES_ENV_POSTGRES_PASSWORD='foo' nginx
docker run --env-file ./env.list ubuntu bash

exec

docker exec -it nginx bash

run과 기본적으로 같지만, 이미 실행되어 있는 container에서 실행하는 명령이다. 즉, 이미 실행되어 있는 웹서버의 bash shell로 들어가서 뭔가 확인해야 할것이 있다면 아래처럼 명령을 실행하면 된다.

delete images

간혹 여러개 이미지를 지워야 할 일이 있는데 아래 커멘드로 한방에 훅. 그러나 다른 것 지우지 않게 조심해야 함.

1	docker images \| grep 810001cb03af \| awk '{print $3}' \| xargs docker rmi

push images

만들어진 docker image를 docker hub에 push하면 나중에 재사용할 수 있기 때문에 빌드 시간을 줄 일 수 있다. 그 전에 중요한 것은 image의 이름이 <dockerhub_id>/<image_name>의 형식으로 되어 있어야 한다.

$ docker images
REPOSITORY           TAG          IMAGE ID            CREATED             VIRTUAL SIZE
docker-whale         latest       7d9495d03763        38 minutes ago      273.7 MB
# change docker tag
docker tag 7d9495d03763 nberserk/docker-whale:latest
#login to docker hub
docker login --username=yourhubusername --email=youremail@company.com
# push image
docker push nberserk/docker-whale

Dockerfile

add

1
2
3

# local 의 dev directory를 container의 /code/dev 로 recursive copy를 하고 싶다면 아래처럼.
# 만약 `add dev /code` 로 주면 dev dir의 파일을 /code로 카피한다. 왜 이렇게 헷갈리게 동작을 정의 했을까..
add dev /code/dev

copy

1 2	COPY dist/. /usr/share/nginx/html/ # copy files under dist folder COPY dist /usr/share/nginx/html/ # copy dist directory to html folder

위의 예 처럼 폴더안에 든 파일만 카피를 하고 싶다면 <folder>/. 이런식으로 기술해 주면 된다.

CMD vs ENTRYPOINT

ENTRYPOINT는 디폴트로 실행하는 포인트이고 디폴트는 sh -c 이다. CMD는 이 ENTRYPOINT의 parameter가 된다. 자세한 것은 여기를 참고.

ENTRYPOINT를 내가 만든 shell로 대체해서 커스텀화 할 수 있다. docker-entrypoint.sh로 돌리고 CMD로 디폴트로 실행될 파람을 받고 등등..

#!/bin/bash -e
/usr/local/bin/uwsgi --ini /django/deploy/uwsgi.ini &
./manage.py migrate
exec "$@"

위는 django server를 띄우고, 또 optional하게 들어오는 커맨드를 실행하는 스크립트이다. 이런식으로 사용하면 된다.

Docker-machine에 insecure registry 영구적으로 추가하기

private docker registry 설정시, Ubuntu의 경우는 /etc/default/docker 에 아래처럼 추가해주면 되고

DOCKER_OPTS=”–insecure-registry <your_registry_ip>:5000”

맥의 경우는, docker-machine ssh 로 들어가서 /var/lib/boot2docker/profile 에 아래처럼 추가하면 된다.

EXTRA_ARGS=”–insecure-registry <your_registry_ip>:5000”

그런데 맥이나 윈도우의 경우는 docker-machine이 reboot될때마다 셋팅이 없어지기 때문에 아래의 커맨드로 vm을 생성하면 영구적인 변경을 줄 수 있다.

docker-machine create –driver virtualbox –engine-insecure-registry 10.240.70.80:5000 registry

vm을 이미 만든 경우라면, ~/.docker/machine/machines/default/config.json의 HostOptions>EngineOptions>InsecureRegistry에 직접 추가해주면 된다. 아래 예 참조. docker 버전은 1.10.0

"HostOptions": {
        "Driver": "",
        "Memory": 0,
        "Disk": 0,
        "EngineOptions": {
            "ArbitraryFlags": [],
            "Dns": null,
            "GraphDir": "",
            "Env": [],
            "Ipv6": false,
            "InsecureRegistry": [
                "10.240.70.80:5000"
            ],
            "Labels": [],
            "LogLevel": "",
            "StorageDriver": "",
            "SelinuxEnabled": false,
            "TlsVerify": true,
            "RegistryMirror": [],
            "InstallURL": "https://get.docker.com"
        },

revision history

2016-3-24 draft
2016-5-20 insecure registry 추가
2016-5-31 –net=host 추가

docker로 django개발 환경 만들기

2016-02-23

docker 공홈에 있는 django + postgres 의 예제를 django + mysql로 바꾸어서 해보았다.

mysql

docker repository mysql로 검색을 해보면 여러가지가 나오는데 mysql:5.7로 해보자.
아래처럼 실행하면 3306 포트로 mysql 데몬이 뜬다.
docker run -e MYSQL_ROOT_PASSWORD=root mysql:5.7

django

Dockerfile은 아래처럼.

FROM python:2.7
ENV PYTHONUNBUFFERED 1
RUN mkdir /code
WORKDIR /code
ADD requirements.txt /code/
RUN pip install -r requirements.txt
ADD . /code/

requirements.txt는 아래처럼 작성한다.

1
2
3

Django
psycopg2
MySQL-python

이렇게 하면 python:2.7 docker image에 pip로 requirements.txt에 있는 패키지를 설치해서 django ready상태가 되고 호스트의 WORKDIR을 /code로 마운트해서 장고 앱을 실행할 수 있는 상태로 만든다.
그 후 아래 명령을 실행하면 장고가 프로젝트 템플릿을 만들어 준다. MyApp 하위에

docker-compose run web django-admin.py startproject MyApp .

그후 mysql을 연결하는 작업을 해야 하는데 MyApp/settings.py 파일의 DATABASES 부분을 아래처럼 수정.

DATABASES = {
    'default': {
        'ENGINE': 'django.db.backends.mysql',
        'NAME': 'django',
        'USER': 'django',
        'PASSWORD': 'django',
        'HOST': 'db',
        'PORT': 3306,
    }
}

docker-compose

위에서 mysql container와 django container는 준비가 되었다. 매번 이렇게 2번의 명령으로 컨테이너를 실행하면 번거러울수 있다. 컨테이너가 더 많아질수록 그렇게 될텐데.. 이런 경우를 위해서 docker-compose라는 cli를 제공하고 있다.

아래처럼 docker-compose.yml을 작성하고

db:
    image: mysql:5.7
    environment:
    - MYSQL_ROOT_PASSWORD=root
    - MYSQL_DATABASE=django
    - MYSQL_USER=django
    - MYSQL_PASSWORD=django
web:
    build: .
    command: python manage.py runserver 0.0.0.0:8000
    volumes:
        - .:/code
    ports:
        - "8000:8000"
    links:
        - db

docker-compose up 명령을 내리면 두개의 docker 컨테이너를 동시에 실행할 수 있다.

잘 동작하는지 확인하려면 http://localhost:8000 포트로 접속해보면 된다. 맥이나 윈도우즈의 경우는 docker-machine ip 명령으로 나오는 ip의 8000 로트로 접속해보면 장고 초기화면이 나온다. 나의 경우는 http://192.168.99.100:8000/ 이었다.

revision history

2016/2/23 draft

merge sequence file in spark

2016-01-08

merging sequence files

spark로 파일을 저장하면 sequence 파일로 저장이 되는데, 이 파일을 합쳐서 하나의 파일로 만들고 싶을때 아래 scala function을 사용하면 된다.

def merge(srcPath: String, dstPath: String): Unit =  {
    import org.apache.hadoop.fs.{FileSystem, FileUtil, Path}
    import org.apache.hadoop.hdfs.HdfsConfiguration
    import org.apache.hadoop.conf.Configuration
    import java.net.URI

    val config = new Configuration()
    //config.set("fs.s3.impl", "org.apache.hadoop.fs.s3.S3FileSystem")
    val fs = FileSystem.get( URI.create(srcPath), config)
    FileUtil.copyMerge(fs, new Path(srcPath), fs, new Path(dstPath), false, config, null)
  }

revision history

2016/1/11 initial draft

Inertia

using incoming edge

using dfs

detect cycle

Problems

Reference

naive

using priority_queue

linear

Problems

Reference

History

Kadane

naive

dp

응용

intuition

implementation

Problems

Reference

hadoop-base image

qemu-arm-static

install packages

passwordless ssh

reference

revision history

Model

Controller

View(Template)

revision history

image vs container

build

run

exec

delete images

push images

Dockerfile

add

copy

CMD vs ENTRYPOINT

Docker-machine에 insecure registry 영구적으로 추가하기

revision history

mysql

django

docker-compose

revision history

merging sequence files

revision history

About

Categories

Tags

Tag Cloud

Archives

Recents