Front-end_dev
동적해싱의 구체적인 구현방법에 대해서 설명. 동적해싱은 인덱스를 2진수료표현한다. 따라서 들어오는 키값을 hash함수에 넣고 돌린값을 2진수로 convert해야하며 2진수를 토대로 들어갈 인덱스를 결정하며 실제 인덱스에 mapping할때는 다시10진수로 convert하는 작업이 필요하다.단, 그냥 변환하는것이 아니다. 현재 depth를 기준으로 변환해야한다.예를들어, 11이라는 값이 들어왔을때, 11은 2진수로 1011로 표현되며 현재 depth가 2라고 가정했을경우에 가장끝자리서부터 2개만 파싱해야한다.따라서 11로 변환되야하며, depth가 4라면 1011로 변환된다. Operation : transformToBinary(decimal) ::= 10진수를 2진수로 변환한다extract(binary) ..
위너트리 같은경우는 몇없는 external sorting중 한개이다.external sorting은 모든데이터를 전부 메모리에올려서 정렬하는 방식이아닌, 한개 혹은 일부만 올려서 정렬하고 다시 몇개만올려서 정렬하는(반복...) 방식이다. 위너트리의 동작방식은 각각의 run에서 1개씩 올려서 서로 경쟁을펼쳐(누가더 작나 혹은 누가더크나) 1인자가 나올떄까지 경쟁을하며 1인자가나올때마다 정렬이 되는방식이다. 물론 각각의 run들은 사전에 정렬이되어있어야한다. * 오름차순정렬을 min-winner tree라고하고 , 내림차순정렬을 max-winner tree라고함. 경쟁을할떄 중복된데이터가 있을경우에??먼저, 한개의 데이터가 뽑히고나서, 다음경쟁에서 중복된데이터가 뽑힐것이다. 그렇다면 한개의 데이터가뽑혔을때,..
밑의 그림은 무방향그래프이다. 하지만 멀티리스트에서는 무방향그래프로 구성을하지않고도 서로서로가 누구누구에게 연결되있는지 알고있는 그래프이다.예를들어,6->44->54->35->15->22->32->1 총 7개의 간선으로만 연결했을경우에 1에서는 5와 2가 달려있지않고, 3에는 4와 2가 달려있지않게된다...하지만 멀티리스트를 구현할경우 내가직접적으로 달고있지않고, 상대방이 나를달고있으면 내가 누구랑 연결되있는지 알아내는 알고리즘이다. 멀티리스트를 이용하면 15개의 간선으로도 밑의 그래프를 형성할수있다.