Sorting two arrays at once in Python

If two arrays should be sorted with the same criteria, use zip.

>>> x1 = ['c', 'a', 'b']
>>> y1 = [3, 1, 2]
>>> z = zip(x1, y1)
>>> z.sort()
>>> z
[('a', 1), ('b', 2), ('c', 3)]
>>> # Because zip returns tuples, we need to convert them to lists.
>>> x2, y2 = map(lambda x: list(x), zip(*z))
>>> x2
['a', 'b', 'c']
>>> y2
[1, 2, 3]

Similar Posts:

Linux Kernel 3.9 에서의 SO_REUSEPORT

http://freeprogrammersblog.vhex.net/post/linux-39-introdued-new-way-of-writing-socket-servers/2
https://lwn.net/Articles/542629/

SO_REUSE_PORT를 사용해서 소켓을 만드는 프로세스를 여러개 띄우면 부모 process 역할은 커널이 알아서 한다. 이 때 어떤 child process가 요청을 처리할지도 공평하게 분배해서 workload의 분산이 잘 이루어짐.

이 방식이 정말 사용하기 쉬운게, 자식 프로세스는 필요하면 그냥 더 띄우기만 하면 되기 때문. 더구나 이건 pre-fork model이므로 접속이 있을때마다 자식 process를 띄우는 것에 비해 프로세스의 수나 서버에 걸리는 로드를 조정하기에 편리. 시간이 좀 지나면 이렇게 코딩하는게 기본 방식이 될지도.

Similar Posts:

HTTPS상의 압축에 따른 취약점 공격: CRIME과 BREACH

제가 SSL/TLS는 잘 몰라서 틀린점이 있을 수 있습니다. 그리고 편의를 위해 개략적으로만 설명합니다.

CRIME의 기본 아이디어는 다음과 같습니다..

(편의를 위해 공격자: attacker, 악의적인 사이트: evil.com, 피해자: victim, 공격대상 사이트: target.com 의 용어를 사용)

  1. TLS상에 주고받는 데이터를 해독할 수는 없지만 주고받는 데이터의 크기는 알 수 있다고 가정.
  2. attacker가 사용자가 대상 사이트에 전송하는 데이터에 임의의 값을 삽입할 수 있다고 가정. 이 단계는 의외로 쉽게 할 수 있는데, 예를들어 evil.com 에서 [img src=’target.com/xyz.png’]와 같은 HTML을 페이지에 넣고 victim이 evil.com을 방문하게 하면 됩니다.
  3. attacker는 target.com에 전송되는 victim의 cookie를 알고 싶어하는데, 이 cookie값이 abcde라고 하겠습니다.
  4. victim이 img src 태그를 보면 브라우저는 이미지 태그에 대한 요청을 target.com으로 보냅니다. 이 때, http request에는 xyz.png 라는 이미지 주소가 들어가겠죠. 그런데 이 주소와 #3에 설명한 cookie값은 한덩어리로 묶어서 압축됩니다. 즉 xyz.png와 abcde의 두개 문자열이 들어있는 http request는 한덩어리의 텍스트로 취급되어 압축됩니다. 그런데 attacker가 파일명을 ayz.png로 바꾸면 무슨일이 생길까요.. ayz.png와 abcde에는 ‘a’가 반복됩니다. 따라서 ayz.png, abcde를 압축한 결과의 바이트수는 xyz.png, abcde를 압축한 바이트 수보다 작습니다.
  5. 따라서 attacker는 img src의 주소를 계속 바꾸면서 http request의 바이트 크기가 최소가되는 지점을 찾아 cookie를 알아냅니다.

CRIME의 아이디어는 TLS상의 compression이 enable되어있는 경우가 드물기때문에 효과적이진 않았습니다.

BREACH는 http request가 아닌 http response에 초점을 맞춥니다. 공격자가 준 입력이 http의 response에 나타난다면 공격자는 입력을 바꿔가면서 http response의 크기를 재서 response에 있는 문자열을 예측해낼 수 있습니다. 예를들어 CSRF Token 탈취를 생각해 볼 수 있겠죠. http상의 gzip 압축은 자주 사용됩니다. 따라서 response를 사용한 공격 가능성은 더 많은 사람들에게 영향을 줍니다.

Similar Posts:

더 빠른 모바일 사이트를 위한 구글의 가이드라인

https://developers.google.com/speed/docs/insights/mobile

DNS Lookup, TCP Connection, HTTP Request/Response에 600ms 가 소요되므로 1초안에 페이지를 로딩하려면 400ms안에 (서버/클라이언트) 렌더링이 끝나야함.

특히 다음에 유의:
1) 서버측 렌더링은 200ms 안에 종료할 것.
2) 리다이렉트는 최소화할 것
3) TCP Slowstart로 인해 congestion window가 커지기 전까지 총 10개의 TCP Packet(14KB)를 주고 받으므로 이 안에 ATF(above the fold)의 렌더링을 끝낼 것.
4) ATF에서 javascript, CSS의 외부참조로 인한 지연이 없도록 전부 inline하거나 ATF 렌더링 뒤에 불리도록 지연시킬 것.
5) 브라우저 렌더링에 200ms는 소요됨을 고려할 것.
6) js 실행과 렌더링 최적화를 할 것.

Similar Posts:

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: