빅 데이터 처리 면접 문제 분석

**          **

                --   ，AVL ，   ，   ，      -  ，     ；

              ，         IT         ，           ；

                            ：

   ，        ，                 ，            ！

  ，                             ，         ！
   ，        ，   ，  ，       ，  ！

                         ，       ！
（           ，          ，    ！）

1）      100G   log file, log   IP  ,              IP  ？!

제목 분석: 우선, 우리 가 본 것 은 100 G 크기 의 로그 파일 입 니 다. 첫 번 째 는 일반 컴퓨터 의 메모리 가 놓 여 있 지 않다 는 것 을 생각해 야 합 니 다.분명히 100 부 로 잘라 서 이 100 개의 파일 을 100 크기 의 해시 표 로 삼 아야 합 니 다. 각각 1G 크기 만 있 으 면 메모 리 를 읽 고 처리 할 수 있 습 니 다. 메모리 에서 어떻게 처리 해 야 합 니까?아래 를 보다
그리고 문 제 를 살 펴 보 자. 가장 많이 나 온 IP 를 찾 아 라.
그러면 메모리 에서 어떻게 처리 하 는 근거 가 나 옵 니 다. 우 리 는 당연히 같은 IP 를 같은 파일 에 넣 어야 합 니 다. 발생 횟수 를 통계 해 야 하기 때 문 입 니 다.
어떻게 하면 이 100 개의 작은 파일 에 같은 IP 를 넣 을 수 있 습 니까?
해시 함수!우 리 는 해시 표를 배 울 때 키워드 key 가 해당 하 는 저장 위 치 를 매 핑 하 는 것 을 알 고 있 습 니 다. 그 중에서 문자열 에 해당 하 는 해시 함수 가 문자열 을 해당 하 는 key 로 바 꾸 면 IP 를 문자열 로 똑 같이 처리 하고 key 를 얻 은 다음 index = key% 100 에 따라 어떤 파일 이 존재 하 는 지 결정 합 니 다. 같은 IP 가 얻 은 key 는 똑 같 을 것 입 니 다.같은 파일 에 들 어 갔 습 니 다.

           key:
        size_t HashFunc1(const K& key)
        { 
        const char* str = key.c_str();
        unsigned int seed = 131;   
        unsigned int hash = 0;    
        while(*str)    
        {        
            hash = hash*seed + (*str++);    
        }    
        return(hash& 0x7FFFFFFF);
        };

위의 이 절차 들 이 야 말로 중점 (바로 하 쉬 가 나 누 는 과정) 이 고 아래 는 일반적인 과정 이다.이제 우 리 는 이 100 개의 파일 을 메모리 에 다시 읽 어야 합 니 다. 메모리 에 한 개의 파일 을 읽 을 때마다 우리 가 볼 일 은 이 파일 에서 가장 많은 횟수 가 발생 한 IP (빠 른 방법, key 를 이용 하면 IP, value 가 발생 한 횟수 를 나타 내 는 key value 의 구 조 를 나타 내 는 검색 트 리 를 통계 하면 됩 니 다) 를 MAX 로 기록 하고 두 번 째 파일 을 읽 습 니 다.새 파일 에서 가장 많은 횟수 가 발생 한 IP 를 통계 하여 MAX 와 비교 하고 MAX 보다 크 면 MAX 를 업데이트 하 며 상기 절 차 를 계속 합 니 다!이것 이 바로 기본 적 인 알고리즘 이다.이 문제 의 포 인 트 는 하 시 컷!

2）       ，    top K IP？      Linux      ？!

제목 분석: 본 문제 도 해시 절 분 을 진행 하 는데 이 과정 은 생략 하 겠 습 니 다.첫 번 째 문 제 는 가장 많은 것 만 찾 으 면 이 문 제 는 가장 많은 K 개 를 찾 아야 한다.사실 우 리 는 데이터 구 조 를 배 웠 다 면 top K 를 보면 정렬 을 생각해 야 한다. 그러면 문 제 는 간단 하 다. 물론 우 리 는 첫 번 째 파일 에서 모든 IP 가 나타 난 횟수 (방법 은 첫 번 째 문제 와 같다) 를 통계 해 야 한다. 만약 에 검색 트 리 라면 그 중의 K 개 (key value 구조) 결점 을 취하 여 최소 더 미 를 만들어 야 한다.
주의: 여 기 는 가장 작은 무 더 기 를 짓 는 것 입 니 다!!우 리 는 top K 를 보 자마자 무의식적으로 가장 큰 무 더 기 를 만 들 겠 다 고 대답 하고 싶 었 다. 그러면 계략 에 빠 졌 다.
왜 최소 더 미 를 만 듭 니까?
현재 이 더미 에 있 는 K 개의 IP 가 꼭 top K 가 아니 기 때문에 우 리 는 더미 에 삽입 해 야 합 니 다.그리고 쌓 인 크기 를 확보 해 야 합 니까? K 입 니까? 그리고 쌓 인 K 개의 노드 의 IP 입 니까? 아니면 현재 가장 많이 나타 난 K 개 입 니까? 그래서 우 리 는 쌓 인 노드 와 교환 해 야 합 니 다. 그러면 중점 은 어떤 노드 와 새로 삽 입 된 노드 로 교환 해 야 합 니까?가장 조건 에 부합 되 는 것 은 바로 지붕 요 소 를 쌓 는 것 입 니 다. 전 제 는 가장 작은 더미 입 니 다. 그러면 지붕 요 소 는 현재 K 개의 IP 가 나타 나 는 횟수 가 가장 적 습 니 다. 그리고 제 가 새로 온 이 IP 가 나타 난 횟수 가 쌓 인 것 보다 많 으 면 저 는 교환 할 수 있 습 니 다. 교환 한 후에 쌓 인 요 소 를 아래로 조정 하여 쌓 인 요소 가 가장 적 습 니 다!첫 번 째 노드 에 구 축 된 검색 트 리 를 비교 한 다음 에 두 번 째 파일 을 읽 고 검색 트 리 를 구축 하 며 발생 횟수 를 통계 하고 정상 요소 와 비교 하여 상기 과정 을 반복 합 니 다. 끝 날 때 까지!
마지막 에 쌓 인 K 개의 IP 가 top K 입 니 다.

3）  100    ，              !

제목 분석: 이 문 제 는 간단 하 다. 그러나 같은 문 제 를 보면 100 억 개의 정수, 약 35G 의 크기 이다. 그러나 정수 가 표시 할 수 있 는 최대 범 위 는 2 의 32 제곱 이다. 그러면 약 16G 의 크기 이다. 그러면 나머지 는 모두 중복 되 는 숫자 이다. 이 문 제 는 메모리 크기 를 규정 하지 않 았 지만 16G 는 너무 크다.어떻게 필요 한 메모 리 를 계속 줄 입 니까?
우 리 는 비트 맵 의 특성 을 이용 할 수 있 습 니 다. 비트 맵 은 보통 한 사람 이 하나의 key 를 표시 합 니 다. 여기 서 우 리 는 두 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트
마지막 으로 한 번 나 온 정 수 를 찾 으 면 됩 니 다!

4）      ，   100    ，    1G  ，          !

제목 분석: 또 100 억 개의 정수 이지 만 두 파일 의 교 집합 을 찾 아야 합 니 다. 이것 은 위의 비트 맵 을 사용 하 는 방법 으로 는 쉽 지 않 습 니 다. 하지만 우리 가 데이터 구조 로 처리 하지 못 하면 하 쉬 절 분 도 있 잖 아 요!
우 리 는 두 파일 을 각각 1000 개의 파일 로 나 누 었 다. 각 파일 의 크기 는 몇 십 메 가 의 모양 이다. 먼저 파일 A 분 의 1000 개의 파일 안의 정 수 를 해시 분 배 를 한다. 즉, 정수 모드 를 1000 으로 나 누 어 같은 파일 에 들 어가 게 하고 파일 B 분 의 1000 개의 파일 을 똑 같이 처리한다.그리고 각각 A 해시 가 잘 라 낸 첫 번 째 파일 과 B 해시 가 잘 라 낸 첫 번 째 파일 을 비교 하여 교 집합 을 찾 아 새 파일 에 저장 하고 2000 개의 파일 이 서로 비교 할 때 까지 순서대로 유추 합 니 다!

5）1     100  int，1G  ，             2      !

제목 분석: 3 번 과 유사 하 게 비트 맵 을 이용 하여 해답 을 구한다!11 은 두 번 넘 게 나 온 정 수 를 대표 합 니 다!

6）      ，   100  query，    1G  ，           ？             !

문제 분석: 먼저 문 제 를 보면 네 번 째 문제 와 비슷 하지만 서로 다른 것 은 유사 알고리즘 과 정확 한 알고리즘 이다.정확 한 알고리즘 은 바로 네 번 째 문제 의 해법 이다.
유사 알고리즘: 부 릉 필 터 는 해시 알고리즘 과 비트 맵 을 이용 하여 이 루어 집 니 다.먼저 A 와 B 파일 에 대해 해시 절 분 된 다음 에 A 파일 의 첫 번 째 절 분 된 파일 을 취하 여 부 릉 필 터 를 삽입 한 다음 에 B 파일 의 첫 번 째 절 분 된 파일 을 취하 여 부 릉 필 터 를 찾 습 니 다. 즉, 존재 여 부 를 판단 합 니 다!주의해 야 할 것 은 오심 을 줄 이기 위해 서 입 니 다. 우 리 는 보통 여러 개의 해시 함수 로 여러 개의 대응 위 치 를 생 성 합 니 다. 즉, 하나의 문자열 이 여러 비트 에 대응 하 는 것 입 니 다.왜 부 릉 필 터 는 유사 알고리즘 입 니까? 존재 하지 않 는 것 이 확실 하지 않 기 때 문 입 니 다. 존재 하 는 것 이 확실 하지 않 습 니 다. 즉, 하나의 문자열 이 5 자리 에 대응 하 는 것 입 니 다. 만약 에 한 자리 가 0 이 라면 이 문자열 은 존재 하지 않 을 것 입 니 다. 만약 에 한 문자열 이 대응 하 는 5 자리 가 모두 1 이 라면 이 문자열 은 반드시 존재 하지 않 습 니 다.이 다섯 자리 가 다른 문자열 의 대응 위치 가 1 일 수도 있 기 때 문 입 니 다!
대략 실현 코드 는 다음 과 같 습 니 다. 코드 는 핵심 알고리즘 부분 일 뿐 입 니 다.

   template
class BloomFilter
{
    size_t HashFunc1(const K& key)
    { 
        const char* str = key.c_str();
        unsigned int seed = 131;   
        unsigned int hash = 0;    
        while(*str)    
        {        
            hash = hash*seed + (*str++);    
        }    
        return(hash& 0x7FFFFFFF);
    };

    size_t HashFunc2(const K& key)  
    {  
        const char* str = key.c_str();
        register size_t hash = 0;  
        while (size_t ch = (size_t)*str++)  
        {  
            hash = 65599 * hash + ch;         
            //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  
        }  
        return hash;  
}  


size_t HashFunc3(const K& key)  
{  
    const char* str = key.c_str();
    register size_t hash = 0;  
    size_t magic = 63689;     
    while (size_t ch = (size_t)*str++)  
    {  
        hash = hash * magic + ch;  
        magic *= 378551;  
    }  
    return hash;  
}  


size_t HashFunc4(const K& key)  
{  
    const char* str = key.c_str();
    register size_t hash = 0;  
    size_t ch;  
    for (long i = 0; ch = (size_t)*str++; i++)  
    {  
        if ((i & 1) == 0)  
        {  
            hash ^= ((hash << 7) ^ ch ^ (hash >> 3));  
        }  
        else  
        {  
            hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));  
        }  
    }  
    return hash;  
}  


size_t HashFunc5(const K& key)  
{  
    const char* str = key.c_str();
    if(!*str)      
        return 0;  
    register size_t hash = 1315423911;  
    while (size_t ch = (size_t)*str++)  
    {  
        hash ^= ((hash << 5) + ch + (hash >> 2));  
    }  
    return hash;  
}  

public:
    BloomFilter(const size_t size)
        :_size(size)
        ,_bitmap(size)
    {}

    void Set(const K& key)
    {
        size_t hash1 = HashFunc1(key);
        _bitmap.Set(hash1%_size);
        size_t hash2 = HashFunc1(key);
        _bitmap.Set(hash2%_size);
        size_t hash3 = HashFunc1(key);
        _bitmap.Set(hash3%_size);
        size_t hash4 = HashFunc1(key);
        _bitmap.Set(hash4%_size);
        size_t hash5 = HashFunc1(key);
        _bitmap.Set(hash5%_size);
    }

    void ReSet()
    {}

    bool Test(const K& key)
    {
        size_t hash1 = HashFunc1(key);
        if(!_bitmap.Test(hash1%_size))
            return false;
        size_t hash2 = HashFunc1(key);
        if(!_bitmap.Test(hash2%_size))
            return false;
        size_t hash3 = HashFunc1(key);
        if(!_bitmap.Test(hash3%_size))
            return false;
        size_t hash4 = HashFunc1(key);
        if(!_bitmap.Test(hash4%_size))
            return false;
        size_t hash5 = HashFunc1(key);
        if(!_bitmap.Test(hash5%_size))
            return false;

        return true;
    }

private:
    BitMap _bitmap;
    size_t _size;
};


int main()
{
    BloomFilter<> bloom(32);
    bloom.Set("aaaaaaaaaa");
    bloom.Set("bbbbbbbbbb");
    bloom.Set("cccccccccc");
    bloom.Set("dddddddddd");

    cout<"aaaaaaaaaa")<"aaaaa")<"bbbbbbbbbb")<"bbbbb")<"dddddddddd")<"dddd")<"pause");
    return 0;
}

7）    BloomFilter            ？!

알고리즘 분석: 부 릉 필터 의 키 하나 가 여러 비트 에 대응 하기 때문에 삭제 하려 면 번 거 로 울 수 있 습 니 다. 단순히 대응 하 는 위 치 를 0 으로 설정 할 수 없습니다. 다른 키 가 이 비트 에 대응 할 수 있 기 때문에 각 비트 에 대해 인용 수 를 계산 하여 삭제 작업 을 해 야 합 니 다. 그러면 다음 문 제 를 도입 합 니 다.

8）    BloomFilter         ？!

제목 분석: 지난 문제 의 확장 으로서 우 리 는 인용 계수 가 어떻게 실현 되 어야 하 는 지 를 고려 해 야 한다. 모든 대응 하 는 위치 에 하나의 계수 가 필요 하기 때문에 모든 사람 이 적어도 int 가 필요 하 다. 그러면 우 리 는 비트 맵 을 포기 해 야 한다. 즉, 최소 의 공간 소 모 를 포기 하고 우 리 는 하나의 배열 처럼 실현 해 야 한다.다만 배열 의 내용 은 인용 계수 에 저 장 됩 니 다.
대략 실현 코드 는 다음 과 같다.

template
class BloomFilter
{
    size_t HashFunc1(const K& key)
    { 
        const char* str = key.c_str();
        unsigned int seed = 131;   
        unsigned int hash = 0;    
        while(*str)    
        {        
            hash = hash*seed + (*str++);    
        }    
        return(hash& 0x7FFFFFFF);
    };

    size_t HashFunc2(const K& key)  
    {  
        const char* str = key.c_str();
        register size_t hash = 0;  
        while (size_t ch = (size_t)*str++)  
        {  
            hash = 65599 * hash + ch;         
            //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  
        }  
        return hash;  
}  


size_t HashFunc3(const K& key)  
{  
    const char* str = key.c_str();
    register size_t hash = 0;  
    size_t magic = 63689;     
    while (size_t ch = (size_t)*str++)  
    {  
        hash = hash * magic + ch;  
        magic *= 378551;  
    }  
    return hash;  
}  


size_t HashFunc4(const K& key)  
{  
    const char* str = key.c_str();
    register size_t hash = 0;  
    size_t ch;  
    for (long i = 0; ch = (size_t)*str++; i++)  
    {  
        if ((i & 1) == 0)  
        {  
            hash ^= ((hash << 7) ^ ch ^ (hash >> 3));  
        }  
        else  
        {  
            hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));  
        }  
    }  
    return hash;  
}  


size_t HashFunc5(const K& key)  
{  
    const char* str = key.c_str();
    if(!*str)      
        return 0;  
    register size_t hash = 1315423911;  
    while (size_t ch = (size_t)*str++)  
    {  
        hash ^= ((hash << 5) + ch + (hash >> 2));  
    }  
    return hash;  
}  

public:
    BloomFilter(const size_t size)
    {
        _map.resize(size);
        for(size_t i = 0; i<_map.size _map="" class="hljs-number">0;
    }

    void Set(const K& key)
    {
        size_t hash1 = HashFunc1(key);
        size_t hash2 = HashFunc2(key);
        size_t hash3 = HashFunc3(key);
        size_t hash4 = HashFunc4(key);
        size_t hash5 = HashFunc5(key);

        _map[hash1%_map.size()]++;
        _map[hash2%_map.size()]++;
        _map[hash3%_map.size()]++;
        _map[hash4%_map.size()]++;
        _map[hash5%_map.size()]++;
    }

    bool ReSet(const K& key)
    {
        size_t hash1 = HashFunc1(key);
        if(_map[hash1%_map.size()]==0)
            return false;
        size_t hash2 = HashFunc2(key);
        if(_map[hash2%_map.size()]==0)
            return false;
        size_t hash3 = HashFunc3(key);
        if(_map[hash3%_map.size()]==0)
            return false;
        size_t hash4 = HashFunc4(key);
        if(_map[hash4%_map.size()]==0)
            return false;
        size_t hash5 = HashFunc5(key);
        if(_map[hash5%_map.size()]==0)
            return false;


        _map[hash1%_map.size()]--;
        _map[hash2%_map.size()]--;
        _map[hash3%_map.size()]--;
        _map[hash4%_map.size()]--;
        _map[hash5%_map.size()]--;

        return true;
    }

    bool Test(const K& key)
    {
        size_t hash1 = HashFunc1(key);
        if(_map[hash1%_map.size()] == 0)
            return false;
        size_t hash2 = HashFunc2(key);
        if(_map[hash2%_map.size()] == 0)
            return false;
        size_t hash3 = HashFunc3(key);
        if(_map[hash3%_map.size()] == 0)
            return false;
        size_t hash4 = HashFunc4(key);
        if(_map[hash4%_map.size()] == 0)
            return false;
        size_t hash5 = HashFunc5(key);
        if(_map[hash5%_map.size()] == 0)
            return false;

        return true;
    }

private:
    vector _map;
};

“`