算法 - 关于Python嵌套循环代码优化

问题描述

问 题

用Python实现K-means算法时候，要计算随机两个数之间的欧氏距离，数据量为5000行，但计算的时间却有500多秒，不知道有什么能优化，求指教，代码如下
循环

for i in range(len(data)):    # 计算任意两点距离和
    for j in range(i+1, len(data)):
        random_sum += ed_relate(data[i][2:], data[j][2:])

ed_relate

def ed_relate(dataX, dataY):
    '''
    :param dataX:第一行
    :param dataY: 第二行
    :return: 之间的相似度
    '''
    sum = 0
    if len(dataX) == len(dataY):
        for a in range(0, len(dataX)):
            sum += (float(dataX[a])-float(dataY[a])) ** 2
        relate = math.sqrt(sum)
        return relate
    else:
        print 'len is not equal'
        return 0

数据data

[['3', '0010000000000', '1', '1', '4', '2', '2', '2', '2', '2', '2', '2', '3', '3', '3', '4', '4', '3', '3', '3', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2']
['3', '0000000000010', '1', '0', '4', '2', '1', '3', '3', '2', '3', '5', '3', '2', '2', '3', '4', '2', '2', '4', '1', '1', '1', '1', '3', '2', '3', '2', '2', '3', '2', '2', '3']
['3', '0010000000000', '1', '3', '2', '3', '3', '3', '3', '2', '3', '2', '2', '2', '3', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '3', '3', '3', '2', '2', '2', '3']
['2', '1000000000000', '2', '1', '3', '4', '2', '2', '2', '2', '3', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '3', '2', '2', '3', '3', '2', '2', '2', '2', '3', '2', '2']
['2', '1000000000000', '1', '1', '5', '3', '3', '3', '3', '3', '3', '3', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '3', '3', '3', '3']
['3', '0000000100000', '1', '0', '5', '2', '2', '2', '2', '3', '2', '2', '2', '3', '2', '2', '2', '2', '2', '2', '2', '3', '2', '2', '2', '3', '2', '2', '2', '2', '3', '3', '2']
['3', '0000000100000', '1', '0', '4', '2', '3', '3', '3', '2', '2', '2', '2', '2', '2', '1', '1', '2', '2', '2', '2', '4', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2']
['3', '0010000000000', '2', '1', '3', '4', '2', '2', '3', '2', '2', '2', '2', '2', '3', '2', '2', '2', '3', '2', '2', '2', '3', '2', '2', '2', '3', '2', '2', '3', '2', '2', '3']
['3', '0000010000000', '1', '1', '3', '2', '2', '2', '3', '2', '2', '2', '2', '2', '3', '2', '2', '3', '2', '4', '2', '2', '3', '2', '2', '2', '2', '2', '2', '2', '2', '3', '2']
['3', '0010000000000', '3', '1', '4', '3', '3', '3', '4', '3', '3', '2', '3', '3', '2', '1', '1', '1', '4', '4', '4', '4', '4', '4', '3', '1', '1', '1', '1', '1', '1', '1', '1']
['1', '0100000000000', '3', '4', '1', '2', '3', '4', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '4', '2', '3', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2']
['2', '0000000000100', '1', '2', '3', '4', '3', '2', '3', '1', '2', '2', '2', '2', '2', '2', '2', '4', '2', '2', '2', '3', '3', '2', '3', '2', '2', '2', '2', '2', '2', '2', '2']
['3', '0000000000010', '1', '3', '3', '2', '2', '3', '2', '3', '3', '3', '3', '3', '2', '3', '3', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2']
['1', '0100000000000', '1', '1', '3', '2', '3', '3', '3', '2', '3', '3', '3', '3', '3', '3', '2', '1', '1', '3', '2', '2', '3', '1', '1', '1', '1', '1', '2', '3', '3', '1', '2']
['1', '0100000000000', '1', '2', '4', '3', '3', '3', '3', '3', '3', '3', '3', '3', '3', '3', '3', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2']
['3', '0000000100000', '1', '1', '3', '3', '3', '2', '4', '4', '4', '4', '4', '2', '2', '1', '1', '3', '3', '4', '3', '4', '3', '1', '2', '1', '1', '1', '2', '2', '1', '1', '1']
['3', '0010000000000', '1', '2', '3', '3', '3', '2', '2', '2', '2', '3', '2', '2', '2', '2', '3', '2', '2', '3', '3', '3', '2', '2', '2', '2', '3', '3', '3', '2', '2', '2', '2']
['3', '0000010000000', '1', '1', '5', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2']
['3', '0000010000000', '1', '1', '5', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2']
['3', '0000000100000', '1', '4', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2']]
只给出了前20行

解决方案

已经找到解决的办法，问题出在计算欧氏距离的两个 float
sum += (float(dataX[a])-float(dataY[a])) ** 2
先将data全转成 int
data = [[int(x) for x in row] for row in data]
在计算，速度提升了10倍

这篇关于算法 - 关于Python嵌套循环代码优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！