ワークロード特性評価／クラスタリング：ミニマム・スパニング・ツリー (Minimum spanning tree; MST clustering for workload benchmarking)

mst.py

import math

src_data = ((14,2735,"TKB"),
        (13,253,"MAC"),
        (8,27,"COBOL"),
        (6,27,"BASIC"),
        (6,12,"Pascal"),
        (4,91,"EDT"),
        (1,33,"SOS"))

test_data = ((2,4,"A"),
        (3,5,"B"),
        (1,6,"C"),
        (4,3,"D"),
        (5,2,"E"))

def dist_matrix(data):
    n = len(data)
    dist = [[float("inf") for x in range(n)] for x in range(n)] 
    for i,d in enumerate(data):
        for j in range(i+1,n): 
            xdis = data[i][0] - data[j][0]
            ydis = data[i][1] - data[j][1]
            #dist[i][j] = (i,j,math.sqrt(xdis*xdis + ydis*ydis),xdis/2,ydis/2,data[i],data[j])
            dist[i][j] = math.sqrt(xdis*xdis + ydis*ydis)
    print_matrix(dist)
    return dist

def print_matrix(data):
    for i,a in enumerate(data):
        for j,b in enumerate(data[i]):
            print("{0} ".format(b),end='')
        print("")

def find_cluster2(data):
    dist = dist_matrix(data)
    n = len(dist)
    min_dist = float('inf')
    min_pair = None
    # find minimum pair
    for i in range(0,n):
        for j in range(0,n):
            if dist[i][j] < min_dist:
                min_dist = dist[i][j]
                min_pair = (i,j)
    print(min_pair)
    clustered = []
    for i,d in enumerate(data):
        if i == min_pair[0] or i == min_pair[1]:
            continue
        clustered.append(d)
    clustered.append((
            (data[min_pair[0]][0] + data[min_pair[1]][0]) / 2,
            (data[min_pair[0]][1] + data[min_pair[1]][1]) / 2,
            data[min_pair[0]],data[min_pair[1]],))

    print_matrix(clustered)
    return clustered 

def gen_mst(clustered):
    while True:
        clustered = find_cluster2(clustered)
        print("")
        if len(clustered) <= 2:
            break


gen_mst(test_data)
print("")
gen_mst(src_data)