【架构师训练营】第五期作业

import hashlib
from collections import defaultdict
REMAINDER = 2 ** 32 - 1
class Node(object):
    def __init__(self, node_no, virtual_no):
        self.name = 'node-{}'.format(node_no)
        self.virtual_no = virtual_no
        self.virtual_name = self.name + '#' + str(self.virtual_no)
        self.hash_code = cal_hash(self.virtual_name)
def cal_hash(i):
    md5_str = hashlib.md5(i.encode(encoding='UTF-8')).hexdigest()
    return int(md5_str, 16) % REMAINDER  
def find_node(hash_code, nodes):
    i, j = 0, len(nodes)
    while i < j:
        mid = (i + j) // 2
        if nodes[mid].hash_code < hash_code:
            i = mid + 1
        else:
            j = mid
    node = nodes[0] if i == len(nodes) else nodes[i]
    return node
def gen_virtual_nodes(physical_node_cnt, virtual_node_cnt):
    virtual_nodes = [Node(i, j) for i in range(physical_node_cnt) for j in range(virtual_node_cnt)]
    virtual_nodes.sort(key=lambda v: v.hash_code)
    return virtual_nodes
def get_standard_deviation(physical_node_cnt, virtual_node_cnt, total_num=10 ** 6):
    virtual_nodes = gen_virtual_nodes(physical_node_cnt, virtual_node_cnt)
    node_item_cnt = defaultdict(int)
    for i in range(total_num):
        hash_code = cal_hash(str(i))
        insert_node = find_node(hash_code, virtual_nodes)
        node_item_cnt[insert_node.name] += 1
    average = total_num // physical_node_cnt
    s = 0
    for node_name in list(set([v.name for v in virtual_nodes])):
        s += ((node_item_cnt[node_name] - average) ** 2)
    return s ** 0.5
    
if __name__ == '__main__':
    for i in range(15):
        virtual_node = 2 ** i
        print("virtual node:%d && physical node:%d ====> %.3f"%(virtual_node, 10, get_standard_deviation(10, virtual_node)))