그래프 관련 논문 모음 - 알아야 할 것

Graph Neural Network 관련 5 편

Random Walk Theory
Diffusion

파일명 :  GraphWithNN_20171105.7z

c++ tr1 hash - 컴퓨터

#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 (memory) vs bi-directional hash map (speed) - 컴퓨터

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

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