Term의 분포

Heaps law
코퍼스내 unique term의 수는 (문서의 길이)^b 에 비례. b는 보통 0.4-0.6사이의 수

Zipf’s Law
어떤 term의 빈도는 term빈도에따라 term들을 나열했을때의 랭킹에 반비례

Similar Posts:

웹 분석과 데이터 마이닝을 위한 확률적 자료구조

Probabilistic Data Structures for Web Analytics and Data Mining

이런 훌륭한 글이 있군요. 위 글은 많은 양의 데이터에서 각 아이템의 출현횟수를 세거나 unique 아이템의 수가 몇개인지 세거나 하는 방법들입니다. 예를들어 integer가 엄청나게 많을때 각 값의 출현횟수 세기같은 경우죠.

간단하게 관심가는 것들, 기본적인 내용으로 정리해봅니다.

1. 입력에 몇개의 unique한 수가 있는지 세기(Cardinality Esitmation): Linear Counting
m 비트를 준비합니다. 주어진 입력을 0~(m-1) 사이로 해싱합니다. 그 다음 해당 비트의 값을 1로 셋팅. 결국 1로 셋팅된 비트의 수를 세면 이게 입력에 있는 unique한 숫자의 갯수가 되겠죠.

2. 입력에 몇개의 unique한 수가 있는지 세기(Cardinality Esitmation): Log Log Counting
전에 대량의 데이터에서 대략적으로 UNIQUE ITEM 의 수 세기에서 썼던 내용입니다. 다시 정리하자면, 주어진 입력을 해싱함. 해싱한 수들을 살펴보고 제일 앞자리에 최대 몇개의 0이 연속으로 나오는지 봅니다. 이 때 최대 r자리의 연속된 0을 봤다고 하면 2^r개의 unique item이 있구나 하고 보는 방법입니다.

이유는 간단하죠. 해시값의 제일 앞자리에 0이 나올려면 2개의 unique숫자를 봤어야합니다. 1개만 봤을때는 앞자리가 1일수 있으니까요. 마찬가지로 해시값 앞자리에 연속된 0이 2개, 즉 00이 나오려면 4개의 unique숫자를 봤어야합니다. 예를들어 3개만 봤다면 해시값 앞자리가 11, 10, 01이었을 수 있으까요.

사실 2^r은 너무 거친 추정이므로 여러개의 해시함수를 써서 평균을 내던가 하는 방법을 씁니다.

3. 각 입력의 출현횟수 세기: Count-Min Sketch
대량의 데이터에서 각 입력값이 몇번 나왔나 세는 방법입니다. 예를들어 integer로 구성된 데이터였다면 1은 몇개나왔나, 2는 몇개나왔나 등을 세는 것이죠.

방법은 이렇습니다. 0으로 초기화된 d행 w열의 행렬 m을 준비합니다. 그리고 해시 함수 d개를 준비합니다. 이들을 각각 h_1, h_2, …, h_d 라고 합시다. 이 해시는 각각 0~(w-1)까지의 숫자로 입력을 해싱해 줍니다. 처리할 대량의 데이터에대해 다음을 수행합니다.

for each of datum in input
  for i in 1..d
    m[i, h_i(datum)] += 1
  end for
end for

자 그러면 각 입력에대해 총 d개 셀을 1씩 추가시키는 것이죠.

이게 끝나고나서, 역으로 어떤 숫자 k의 출현횟수를 세고 싶다고 하면 다음과 같이 k의 출현횟수를 찾습니다.

cnt = INT_MAX
for i in 1..d
  cnt = min(cnt, m[i, h_i(k)])
end for

여기서 min이 필요한 이유는 이 방법이 본질적으로 hash collision이 있기 때문에 항상 count를 overestimate하기 때문입니다.

4. Range Query: 다수의 Count-Min Sketch 사용
Count-Min Sketch로 어떤 수 k가 몇회나왔는가는 잘 셀수 있게 되었습니다. 이번엔 range query로 1, 2, 3, .., k 까지의 수가 몇번 나왔나? 혹은 500, 501, …, k까지의 수가 몇회나왔나? 와 같은 질문이 주어졌을때 답하는 방법입니다.

이는 Count-Min Sketch만으로는 부족합니다. 각 숫자의 출현횟수를 매번 구하기가 어려울 수 있으니까요. 이를 위해 Count-Min Sketch를 여러개 쓸 수 있습니다. 예를들어 일단 기본적인 Count-Min Sketch를 만듭니다. 그다음은 1, 2를 하나의 수로 3,4를 하나의 수로, … 과 같이 연속된 2개씩의 숫자들을 카운트를 세는 Count-Min Sketch를 만듭니다. 거기에더해 1~4, 5~8, … 과 같이 연속된 4개의 숫자를 묶어서 세는 Count-Min Sketch를 만듭니다. 이런식으로 계속해서 2배씩 키워나가는 Count-Min Sketch를 많이 만듭니다.

이걸로 range query를 어떻게 처리할지 벌써 감이 오시죠?

예를들어 1, 2, 3, …, 10 의 총 발생횟수는 1~8, 9~10 의 2개의 Count-Min Sketch로 답합니다. 또 다른 예로 1~6의 발생횟수는 1~4, 1~2의 2개로 답하면 되겠죠.

5. 집합에 속해있는지. Bloom Filter.
아주 많은 숫자들의 집합이 있습니다. 어떤 입력이 주어졌을때 그 수가 집합의 원소인지 빠르게 답하는 방법이 바로 bloom filter입니다. 방법은 이렇습니다.

m 비트를 만들고 각 자리를 0으로 초기화합니다. 그리고 n 개 해시 함수 h_1, h_2, …, h_n을 만들어놓습니다. 그 다음 집합에 속해있는 데이터에 대해서 다음을 수행합니다.

for each of datum in input
  for i in 1..n
    m[h_i(datum)] = 1
  end for
end for

결국 각 데이터에 대해 n개의 해시함수를 적용해서 각 자리를 1로 셋팅하는 것이죠. 다 준비가 되면 각 입력에 대해 다음을 수행하면 그 입력이 집합에 속하는지 알 수 있습니다.

is_member = true
for i in 1..n
  is_member = is_member && m[h_i(input)]
  if !is_member
    return false
  end if
end for
return true

물론 hash collision이 있기에 이 방법은 false positive가 있습니다.

앞서의 방법들 모두 오차가 있습니다. 그 오차의 한계를 관리하기위해 m, n, d, w 등의 파라미터를 잘 정해주어야 합니다.

Similar Posts:

OSX에서 Latex 설치하기

http://curriq.com/course/73

ktug 링크가 죽어있는 것 같아서 정리된 내용을 찾아 올려둡니다.

Similar Posts:

대량의 데이터에서 대략적으로 unique item 의 수 세기

http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation

HyperLogLog 라고 하는 알고리즘. 셋이 주어지면 아이템들의 해시값을 구한 뒤 해시값의 맨 앞에서 연속적으로 나타난 0의 최대 갯수를 세고, 이로부터 전체 unique 데이터 갯수를 알아냅니다.

예를들어 해시함수의 출력이 m자리 이진수라고 해보죠. n개 수를 해싱했더니 나온 n개 해시값들중에서 연속된 0이 가장 길게 나온경우는 세자리였다고 해보겠습니다. 연속적으로 0이 3자리 나오는건 약 2^3개의 엘리먼트를 볼때마다이므로 unique item 수를 약 8로 추정합니다. 이 알고리즘의 나머지 부분은 이 정확도를 더 개선시키기위해 더 많은 해시함수를 작용하는 등의 최적화입니다.

정확도는 1 billion 갯수에대해 약 2% 정도의 오차가 있는 정도로 준수하다고 합니다.

Flajolet Martine Algorirhm이라고 해시값의 끝에 몇개의 연속된 0이 나오는지 세서 그 0의 수가 R이면 2^R로 unique item수를 측정할수도 있습니다.

해시값에 영향을 많이 받기때문에 다수의 해시함수를 구하고, 이들을 그룹으로 묶어 각 그룹내에서 측정한 값의 평균을 내놓고, 그 평균들의 median을 구하기도 합니다. (자세한건 mining massive datasets라는 책 참고하세요)

물론 이외에도 bloom filter등을 쓰는 방법도 있겠습니다. 아이템이 주어지면 bloom filter를 사용해 이미 셋에 있는지보고 이미 있다면 패스. 없다면 필터에 추가. 이를 반복하면 됩니다.

Similar Posts:

C++에서 const Klass&반환값 형태의 단점들.

논의하고 싶은 상황은 예를들면 아래와 같은 경우입니다.

class Foo {
public:
 const Klass& foo() {
    return ...;
 }
};

foo()는 Klass을 반환해야할까요 아니면 const Klass&을 반환해야할까요? const Klass& 형태의 리턴을 원하는 까닭은 당연하게도 퍼포먼스입니다. 그러나 Klass을 반환해야하는 이유는 더 많습니다.

const reference가 아니라 value를 반환해야하는 이유

  • 만약 foo()의 구현이 내부에서 복잡한 연산을 한다음 Klass를 리턴하는 것이라면 Klass 복사하는 것을 없애는 것이 전체 실행시간에 큰 영향이 없습니다. 특히 Klass가 string같은 단순 문자열 복사라면 더 그렇습니다. 퍼포먼스 튜닝은 1) 성능 목표 결정, 2) 컴포넌트별 퍼포먼스 측정, 3) 최적화의 3단계로 이루어져야지 이처럼 단순히 복사 생성자 하나만 무작정 잡고 보는 것은 아래에 또다시 설명할 이유들로 인해 premature optimization이 되고 맙니다.
  • 만약 foo()가 멤버 변수를 리턴하는 함수라면 Foo 클래스 인스턴스가 메모리에서 없어진 후에 그 반환값을 사용할 수 없습니다. 예를 들어 다음 경우.
    #include <iostream>
    
    using namespace std;
    
    class Foo {
     public:
      Foo(): val_("hi") {
      }
      string val_;
      const string& GetVal() const {
        return val_;
      }
    };
    
    int main() {
      Foo* foo = new Foo;
      const string& val = foo->GetVal();
      delete foo;
      cout << val << endl;  // dangling reference!
      return 0;
    }
    

    val 은 dangling reference입니다. 모든 코드가 간단하면야 이런 뻔한 실수를 하겠습니까만, 코드가 길어지면 모르는 일이죠.

  • 내부의 구현을 반환하는 것은 어쨌거나 내부의 구현을 노출합니다! 단순히 추상적 아름다움을 깰뿐만 아니라 심지어 Security에 문제가 됩니다. 예를들어 다음과 같은 Bar, Foo클래스를 사용자에게 제공했다고 가정해보겠습니다.
    #include<iostream>
    
    using namespace std;
    
    class Bar {
     public:
      Bar(int v) {
        val_ = v;
      }
      int GetVal() const {
        return val_;
      }
      void SetVal(int v) {
        val_ = v;
      }
     private:
      int val_;
    };
    
    class Foo {
     public:
      Foo(): bar_(1) {
      }
      const Bar& GetBar() const {
        return bar_;
      }
     private:
      Bar bar_;
    };
    

    이 클래스를 제공하는 자는 이 클래스를 가져다 쓰는 클라이언트가 Foo를 만들고 GetBar()로 Bar를 얻을땐 항상 Bar내의 val_ 값이 1이기를 기대하겠지만, 다음과 같이 그 기대는 쉽게 깨집니다.

    int main() {
      Foo* foo = new Foo;
      Bar& bar = const_cast<Bar&>(foo->GetBar());
      cout << bar.GetVal() << endl;  // 1
      cout << foo->GetBar().GetVal() << endl;  // 1
      bar.SetVal(2);  
      cout << bar.GetVal() << endl;  // 2
      cout << foo->GetBar().GetVal() << endl;  // 2
      return 0;
    }
    

    이 예에서 보듯이 클라이언트가 손쉽게 Foo내 bar에 대한 레퍼런스를 획득했습니다.

  • const string&을 반환하는 라이브러리를 만들어도 사용자가 순순히 최적화에 응해주지 않습니다.
    #include <iostream>
    
    using namespace std;
    
    class Foo {
     public:
      Foo(): val_("hi") {
      }
      string val_;
      const string& GetVal() const {
        return val_;
      }
    };
    
    int main() {
      Foo* foo = new Foo;
      string val = foo->GetVal();  // const string&가 아니라도 아무 문제 없이 컴파일.
      cout << val << endl;
      return 0;
    }
    

    이렇게 되면 피했다고 생각하는 문자열 복사가 일어나고 맙니다.

  • 만약 어느날 갑자기 Foo가 멀티 쓰레딩으로 전환된다면 생각지도 못한 버그들이 생겨납니다.
    #include <iostream>
    
    using namespace std;
    
    class Foo {
     public:
      Foo(): val_("hi") {
      }
      string val_;
      const string& GetVal() const {
        return val_;
      }
      void SetVal(const string& v) {
        val_ = v;
      }
    };
    
    ...
    
    Foo* foo = new Foo;
    ... Thread1과 Thread2를 시작시킴 ...
    
    // Thread 1이 실행됨
    const string& val = foo->GetVal(); <- 이 시점에 Thread1은 val == "hi"를 기대
    
    // Thread 2 가 들어오고 다음 라인을 실행
    foo->SetVal("hello");
    
    // Thread 1이 다시 살아나서 다음 라인을 실행
    cout << val << endl;  <- 예상과 달리 hello가 출력!
    

    Thread1이 GetVal()가 순수한 getter라고 생각했다면 Thread1입장에선 정말로 황당한 일이 될 뿐입니다.

  • 어떤 경우엔 const Klass&가 Klass를 바로 리턴하는것 대비 이득이 없을수 있습니다. 예를들어 다음코드는 return 문에서 1개의 temporary object를 생성하고 이것을 그대로 caller쪽의 f에 가져다 줍니다.
    const Foo& computeFoo() {
      .. 작업 ..
      return Foo(...);
    }
    
    ...
    
    const Foo& f = computeFoo();
    

    그런데 그냥 string을 리턴하더라도 똑같은 최적화가 RVO, NRVO에서 이미 이루어집니다. 물론 이것이 만병통치약으로 적용되는 것은 아닙니다만 최소한 위와 같은 포멧에서는 적용되는 것으로 알고 있습니다.

예외적으로 const reference반환이 가능한 경우
이렇게 놓고 볼때, 어떤 경우에 const Klass&를 사용할 것인가에 대한 답은 다음의 경우에 한정됩니다.

  1. Caller측 코드도 내가 다 보고 있어서 반환값을 const reference로 받는 것이 보장되고, Caller가 그 반환값을 Callee가 파괴되기전에 사용 완료하는 것이 보장되며,
  2. 성능이 매우 중요한 상황인데 Klass복사가 너무 비싸거나 값싸더라도 그 복사가 너무 자주 일어나고,
  3. 성능 목표상 이러한 수정이 확실히 필요한 경우일때.

그러나 실제로는 이런 중대한 일이 벌어지는 것을 알려주는 코딩 포멧은 const Klass& 보다는 다음과 같은 형태입니다.

// 너무 암시적이고 client가 손쉽게 무시가능함.
// 순진하게 아무것도 모르고 BigData bd = foo(); 라고 호출해버릴 수 있음.
const BigData& foo() { 
  ...
  return big_data;
}

// 도저히 모르고 지나칠 수 없는 인터페이스.
void foo(BigData** big_data) {  
  ...
  **big_data = ...;
}

두번째 형태의 포멧을 보면 foo()의 클라이언트 입장에서는 뭔가 심상치 않은 일이 벌어짐을 직감하게 됩니다. 무슨일인가 들여다보게되고, foo 함수의 설명도 읽고, 제대로 데이터를 갖다 쓰게 됩니다.

Reference:
1. pros and cons of returning const ref to string instead of string by value
2. http://en.wikipedia.org/wiki/Return_value_optimization
3. http://stackoverflow.com/questions/134731/returning-a-const-reference-to-an-object-instead-of-a-copy
4. http://www.parashift.com/c++-faq-lite/return-by-value-optimization.html

Similar Posts:

MySQL on OSX

After installing mysql51 and mysql51-server using macports, we need to make it secure by running /local/lib/mysql51/bin/mysql_secure_installation. But before that, as default installation does not set root password, root password should be set first:

$ mysql -uroot
mysql> use mysql;
mysql> update user set password=password('your_password') where user='root';
mysql> flush privileges;

And then run mysql_secure_installation.

Here’s how to start and stop mysql:

alias mysqlstart='sudo /opt/local/lib/mysql51/bin/mysqld_safe'
alias mysqlstop='sudo /opt/local/share/mysql51/mysql/mysql.server stop'

‘mysqlstop’ needs you to enter mysql root’s password. If that’s annoying, unset root password:

mysql> update user set password='' where user='root';
mysql> flush privileges;

Read the output of ‘mysqlstart’ to find log file location. In the log, there’s socket file location. To change it, modify /opt/local/etc/mysql51/my.cnf:

# Use default MacPorts settings
!include /opt/local/etc/mysql51/macports-default.cnf

[mysqld]
socket=/tmp/mysql.sock

[client]
socket=/tmp/mysql.sock

Similar Posts:

Topic Sensitive Pagerank

Topic sensitive pagerank is a way of getting pageranks per topic instead of using just one pagerank for all
pages.

In the book Mining of Massive Datasets, biased random walk algorithm is introduced. In the algorithm, we let the random surfer jumps to the page with the specific topic when it wants to teleport. That way, we bias the surfer to give higher pageranks to pages with specific topic.

Similar Posts:

전통적인 process viewer top 의 대체품 htop

요즘 늘어난 cpu 코어를 충분히 활용해보고자 멀티 프로세스, 멀티 쓰레드로 애플리케이션을 종종 돌리고 있습니다. 그런데 top 은 이럴때 시스템 전반의 상황을 쉽게 보기가 어렵더군요. 그래서 찾아보니 htop이란게 있네요.

http://htop.sourceforge.net/에서 더 많은 스크린샷을 볼 수 있고, OSX라면 macports로 설치가능합니다. 안해봤지만 리눅스에서도 yum이나 apt-get으로도 쉽게 설치가능할 것입니다.

장점은 기본 동작이 코어별로 cpu load를 보여주는 것이고, top보다는 기본으로 보여주는 필드수가 적은데 개인적으로는 제가 이해하고 또 궁금해하는 필드가 기본으로 잘 나와서 (저는 CPU%, MEM%, VIRT, RES 정도만 있으면 ok) 만족하고 쓰고 있습니다. 무려 풀다운메뉴(아.. 2012년에 풀다운 메뉴를 보고 감격하다니요)로 이외에 필요한 필드도 추가로 설정할 수 있습니다.

Similar Posts:

My .tmux.conf

# Use c-a instad of c-b
set-option -g prefix C-a
unbind-key C-b
bind-key C-a send-prefix
set-window-option -g mode-keys vi
set -g terminal-overrides 'xterm*:smcup@:rmcup@'
# Mouse should work.
set -g mode-mouse on
set -g mouse-select-pane on
set -g mouse-resize-pane on

# Use c-| for vertical split and c-'-' for horizontal split.
unbind %
bind | split-window -h
bind - split-window -v

# Use h, j, k, and l for panel select
bind h select-pane -L
bind j select-pane -D
bind k select-pane -U
bind l select-pane -R

어쩌다보니 screen대신 이걸 쓰게 되었네요.

Similar Posts:

Fork Join Framework in Java7

Java7 introduced interesting framework called fork join. It’s a mapreduce like lightweight parallel programming library.

The basic idea is to split the work into multiple small parts. Process them, and merge the results into final return value.

I’ve written a sample code that computes sum of integers in ArrayList:

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;


// Use RecursiveTask for task that returns value. Use RecursiveAction, otherwise.
public class SumTask extends RecursiveTask<BigDecimal>{
  
  private static final long serialVersionUID = -5398793510775248257L;
  private ArrayList<Integer> data;
  private int start;
  private int end;

  public SumTask(ArrayList<Integer> data, int start, int end) {
    super();
    this.data = data;
    this.start = start;
    this.end = end;
  }
  
  private static boolean isCheapComputation(int start, int end) {
    return (end - start) < 10000;
  }
  
  @Override
  protected BigDecimal compute() {
    // If the task is small, do it in a single thread.
    if (isCheapComputation(start, end)) {
      BigDecimal result = BigDecimal.ZERO;
      for (int i = start; i < end; ++i) {
        result = result.add(BigDecimal.valueOf(data.get(i)));
      }
      return result;
    }
    // If the task is big, split it into multiple subtasks. They can be subdivided recursively.
    final int mid = start + (end - start) / 2;
    ForkJoinTask<BigDecimal> t1 = new SumTask(data, start, mid);
    ForkJoinTask<BigDecimal> t2 = new SumTask(data, mid + 1, end);
    invokeAll(t1, t2);  // Fork t1 and t2, then wait until both of them finish.
    return t1.join().add(t2.join());
  }
  
  public static void main(String[] args) {
    Random r = new Random();
    ArrayList<Integer> data = new ArrayList<>();
    for (int i = 0; i < 10000000; i++) {
      data.add(r.nextInt());
    }
    ForkJoinPool pool = new ForkJoinPool();
    SumTask sumTask = new SumTask(data, 0, data.size());
    // Call pool.compute() and wait until completion.
    pool.invoke(sumTask);
    System.out.println(sumTask.join());
  }
}

Fork-Join framework is interesting in some ways:
1) It removed tedious (or sometimes error prone) boilerplate that was necessary for thread join and condition variable. Now, I can just fork and join.
2) Work stealing. As described by A Java Fork/Join Framework, Doug Lea, a thread can steal other thread’s task as a way of smart workload balancing.

Another interesting tutorial is Fork and Join: Java Can Excel at Painless Parallel Programming Too! though it lacks in-depth discussion/comparisons between Java 5/6’s executor service based approach VS Fork/Join framework.

And here’s critiques on F/J framework: A Java™ Fork-Join Calamity. I myself found the library is pretty much limited, say, for IO. (Read API doc carefully before you start using the library. It noted some limitations in the comments.)

Sadly, ParallelArray was not included in Java7. If it had, we could have written like the below for multiprocessor parallel programming:

// Taken from http://www.ibm.com/developerworks/java/library/j-jtp03048/index.html
ParallelArray<Student> students = new ParallelArray<Student>(fjPool, data);
double bestGpa = students.withFilter(isSenior)
                         .withMapping(selectGpa)
                         .max();

Anyway, I think F/J is a good move (as long as it won’t get too complex in the next version of Java). And F/J framework is good enough for no-so-serious parallel tasks.

Similar Posts: