사실 아이들이 생긴 후로는 대부분의 순간이 그러하다.

그럼에도 불구하고 시간이 매우 흐르지 않는 순간이 있다.

치과와 수영장..

Graph Neural Network 관련 5 편

Random Walk Theory

Diffusion

#include <string>

#include <tr1/unordered_map>

#include <string.h>

#include <stdio.h>

#include <stdlib.h>     /* srand, rand */

#include <time.h>       /* time */

#include <omp.h>

#include <iostream>

#define ULLONG_MAX 18446744073709551615ULL

#define MAX_LMS 5

typedef unsigned long long uint64;

typedef unsigned int uint32;

typedef struct {

        uint32 lm_indice[MAX_LMS];

        int lms_N;

}lm_indice;

std::tr1::unordered_map<uint64, lm_indice> aa;

int main()

{

    srand (time(NULL));

/*

    lm_indice li1;

    lm_indice&nbsp;li2;

    li1.lms_N = 5;

    li2.lms_N = 5;

    li1.lm_indice[0] = 1004011520;

    li1.lm_indice[1] = 1456139563;

    li1.lm_indice[2] = 1564739221;

    li1.lm_indice[3] = 1527793660;

    li1.lm_indice[4] = 245277883;

    li2.lm_indice[0] = 2013966848;

    li2.lm_indice[1] = 168021018;

    li2.lm_indice[2] = 899633766;

    li2.lm_indice[3] = 1914500838;

    li2.lm_indice[4] = 358854042;

//  uint64 key1 = std::tr1::hash<std::string>()(std::string((char*)&li1));

    uint64 key1 = std::tr1::hash<std::string>()((char*)&li1);

//  uint64 key2 = std::tr1::hash<std::string>()(std::string((char*)&li2));

    uint64 key2 = std::tr1::hash<std::string>()((char*)&li2);

    printf("%llu %llu

", key1, key2);

    lm_indice li1_1;

    lm_indice li2_1;

    memcpy(&li1_1, (char*)&li1, sizeof(lm_indice));

    memcpy(&li2_1, (char*)&li2, sizeof(lm_indice));

    for(int i=0;i<MAX_LMS;i++)

        printf("%d %d

",li1_1.lm_indice[i], li2_1.lm_indice[i]);

    getchar();

*/

    int coll = 0;

    uint64 max_gap = 0;

    uint64 N = 10000000;

//  #pragma omp parallel for

    for(uint64 T = 0;T<N;T++){

        lm_indice li;

        for(int i=0;i<MAX_LMS;i++)

            li.lm_indice[i] = (uint32)rand();

        li.lms_N = MAX_LMS;

        char* a= (char*)&li;

        uint64 key = std::tr1::hash<std::string>()((char*)&li);

        bool inserted = false;

        uint64 gap = 0;

//      std::tr1::unordered_map<uint64, lm_indice>::iterator it = aa.find(key);

//      if(it != aa.end()) coll++;

//      aa[key] = li;

//      #pragma omp parallel for

        for(uint64 k = key, kk = key;;gap++){

            bool isDone = true;

            if(gap != ULLONG_MAX){

                std::tr1::unordered_map<uint64, lm_indice>::iterator it = aa.find(k);

                if(it == aa.end()){

                    inserted = true;

//                  #pragma omp critical

                    aa[k] = li;

                    break;

                }

                isDone = false;

                uint64 r30 = RAND_MAX*rand()+rand();

                uint64 s30 = RAND_MAX*rand()+rand();

                uint64 t4  = rand() & 0xf;

                k = (r30 << 34) + (s30 << 4) + t4;

                //k = (uint64)rand();

            }

            if(isDone) break;

        }

//      #pragma omp critical

//      {

            if(gap > max_gap) max_gap = gap;

            if(!inserted) coll++;

//      }

    }

    printf("%.2f, max_gap: %llu  

",(coll*100.0f/N),max_gap);

    return 0;

}

아마 hash collision 을 잘 하는 방법이 tree 나 별도의 DS 를 써서 해야하는 것 이겠지만... 일단 2000 번 이내에서 찾을 수 있으니 그냥 해본다고 치면

어쨌든 속도는 느릴 듯;

bi-directional 이 마음에 안들지만 어쩔수 없나;