Graphics Programming

문제: https://www.hackerrank.com/challenges/matrix-rotation 난이도 Hard이지만 코드포스로 따지면 Div2 B 정도 되는 문제다. m×n 배열을 바깥 테두리부터 한 층씩 잘라내어 각각 r번 돌리고 다시 합쳐서 출력하면 된다. 이 때 r이 너무 크니 r을 테두리 길이로 나눈 나머지 만큼만 돌린다. 절차형 언어면 그냥 배열을 직접 조작해서 풀었는데 하스켈이니 리스트와 배열을 왔다갔다 하면서 풀어야 한다. mutable array를 사용하면 하스켈을 쓰는 의미가 퇴색되니 쓰지 않는다. 먼저 입력을 받는다. 배열 원소가 최대 90000개여서 String으로 읽으면 I/O 하다 시간 초과가 날 것 같으니 ByteString으로 읽는다. import Control.Mon..

윈도우즈용 GHC와 cabal을 설치하고, cabal을 통해서 sqlite3 라이브러리를 설치하려고 다음 명령을 실행하면 cabal install HDBC-sqlite3 missing C library: sqlite3 가 포함된 오류 메시지가 뜨면서 설치가 실패할 것이다. c로 작성된 sqlite3 소스 코드가 필요하기 때문이다. 다음과 같은 절차를 밟아서 해결할 수 있다. 1. hdbc-sqlite3를 설치하려면 이러이러한 선행 라이브러리가 필요하다고 오류 메시지가 뜰 수 있다. 나의 경우 utf8-string 라이브러리와 hdbc 라이브러리를 설치하라고 떴다. 이것들은 그냥 cabal install utf8-string / cabal install hdbc 를 실행하면 설치된다. 2. sqlite3 ..

문제: https://www.hackerrank.com/challenges/range-minimum-query 숫자 n개가 주어지고, 일정 구간 내에서 최솟값을 찾는 쿼리 m개에 모두 답해야 한다. 각 숫자는 10^5를 넘지 않는다. n, m이 최대 10만이기 때문에 항상 구간 내의 모든 값을 확인해서 최솟값을 찾으면 시간복잡도가 O(nm)이여서 통과하지 못한다. 세그먼트 트리를 이용하면 트리 구축에 O(n), 쿼리 하나에 O(logn) 시간이 걸리므로 O(n) + O(mlogn) ⊆ O(mlogn)으로 테스트를 통과할 수 있다. 세그먼트 트리는 크게 세 가지 구현이 가능하다. 1. 트리 기반, 탑 다운 방식2. 트리 기반, 바텀 업 방식3. 배열 기반 이름에 트리가 들어가지만 세그먼트 트리는 배열로 구..

foldr의 정의는 다음과 같다. foldr :: (a -> b -> b) -> b -> [a] -> bfoldr f z [] = zfoldr f z (x:xs) = f x (foldr f z xs) 그리고 foldr의 fusion law는 다음과 같다. f . foldr g a = foldr h bif (1) f is strict (2) f a = b (3) f (g x y) = h x (f y) 증명은 수학적 귀납법을 이용한다. 기본 가정: (f . foldr g a) [] = foldr h b []foldr의 정의에 따라 양변을 각각 전개하면 (f . foldr g a) [] = f afoldr h b [] = b 조건 (2)에 의해 f a = b이므로 기본 가정 성립. 재귀 가정: f . fold..

하스켈 성능 튜닝 from 민석 이 교내 동아리 발표 자료. 하스켈로 알고리즘 문제 풀다가 겪은 일을 다룬 발표. 하스켈 성능 튜닝 2 from 민석 이 동아리 발표 이후 추가로 만든 자료

Johan Tibell의 ZuriHac 2015 발표: https://www.youtube.com/watch?v=_pDUq0nNjhI 그냥 동영상에 나오는 슬라이드 별로 요약한 것. 자세한 내용은 동영상 참조. ◎ 생성자의 헤더에 1워드, 필드에 1워드 소모 data Uno = Uno a -- 2워드 data Due = Due a b -- 3워드 예외: 필드 없는 생성자는 메모리 사용 X (Nothing, True 등) ◎ [1, 2] 의 메모리 표현 - 1박스 = 1워드 - 생성자마다 1워드의 오버헤드 (가비지 컬렉션 등에 이용) ◎ unboxed 타입 = 원시 기계 타입 - 관례에 의해 이름이 #로 끝난다 - 대부분 1워드를 소모 (예외: 32비트 기계에서 Double#) - unboxed 타입의 값..

원문: http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel/AFP08-notes.pdf 요약 형식으로 번역. 1. 서문 다양한 반-암시적(semi-implicit) 병렬화와 쓰레드 기반 명시적 병렬화 기법들, 소프트웨어 트랜잭션 메모리, 중첩 데이터 병렬화 등을 다룬다. 독자가 하스켈의 지연 함수형 프로그래밍에 익숙하다고 가정. 2. 동시성과 병렬화의 응용 동시성 병렬 프로그램을 작성하는 것은 순차적 프로그램을 작성하는 것보다 어렵다. 하지만 그럴 만한 가치가 있다. 수행능력. 멀티코어 프로세서로 수행능력을 향상할 수 있다. 지연시간 감추기. 싱글코어 프로세서에서도 동시성으로 느린 I/O 작업의 지연시간을 숨길 수 있다. 소프트웨어..

하스켈로 채팅 봇을 작성하다 문제가 하나 발생했다. wuss는 secure 웹소켓 클라이언트를 만들기 위한 라이브러리다. 웹소켓 클라이언트를 생성하는 함수는 runSecureClient다. runSecureClient :: HostName -> PortNumber -> String -> ClientApp a -> IO a ClientApp은 별칭 타입이다. type ClientApp a = Connection -> IO a 따라서 실제로는 다음과 같이 사용한다. main = do runSecureClient "some_host" 443 "some_path" app app conn = do -- input and output through websocket app은 Connection만을 인자로 받는다. ..