K中心算法

Question

我目前使用python來求解k中心算法。 當我運行我的代碼時，它的運行時間超過了限制時間（由我的老師提供），我不知道如何改進我的代碼，以便它可以通過有限的運行時間。 我的代碼如下：

import math 

# 1.Import group 
# 2.Find the most farthest point in this group. 
# 3.reassign the rest points between two center points 
# 4.Find the most farthest point from its center point, and make it the newest center point 
# 5.reassign points among all center points 
# 6.Repeat 4 and 5 step untill the answer fits the condition 

class point(): 
    def __init__(self,x,y,num,group=[]): 
     self.x = x 
     self.y = y 
     self.id = num 
     self.group = [] 

def range_cus(one,two): 
    return math.sqrt(math.pow((one.x-two.x),2)+math.pow((one.y-two.y),2)) 

def reassign(all_points,all_answer): 
    for i in range(len(all_answer)): 
     all_answer[i].group = [] 
    for i in range(len(all_points)): 
     if all_points[i] not in all_answer: 
     min_length = 0 
     for j in range(len(all_answer)): 
      current_length = range_cus(all_answer[j],all_points[i]) 
      if min_length == 0: 
       min_length = current_length 
       current_group = all_answer[j] 
      elif current_length < min_length: 
       min_length = current_length 
       current_group = all_answer[j] 
     current_group.group.append(all_points[i]) 

def search(all_answer,seek_points_number): 
    if seek_points_number == 0: 
     return 0 
    answer_range = 0 
    for j in range(len(all_answer)): 
     for i in range(len(all_answer[j].group)): 
      if range_cus(all_answer[j],all_answer[j].group[i])>answer_range: 
       answer_range = range_cus(all_answer[j].group[i],all_answer[j]) 
       answer_obj = all_answer[j].group[i] 
    seek_points_number -= 1 
    final_answer.append(answer_obj) 
    reassign(group,final_answer) 
    search(final_answer,seek_points_number) 

info = raw_input().split(',') 
info = [int(i) for i in info] 
group = [] 
final_answer = [] 
for i in range(info[0]): 
    x = raw_input().split(',') 
    group.append(point(float(x[0]),float(x[1]),i+1)) 

final_answer.append(group[info[2]-1]) 
group[info[2]-1].group = [point for point in group if point not in final_answer] 

search(final_answer,info[1]-1) 
print ",".join([str(answer.id) for answer in final_answer]) 

請幫我檢查一下應該在哪裏的功能進行修改，以節省一些運行時。

Example input: 

10,3,10 #The first number denotes the sets of data.The second denotes the number of answer I want to return.The third denotes the first center point's id.     
21.00,38.00 
26.00,28.00 
45.00,62.00 
31.00,51.00 
39.00,44.00 
42.00,39.00 
21.00,27.00 
28.00,29.00 
31.00,60.00 
27.00,54.00 

Example output 

10,7,6 

Answer 1

只需重寫range_cus函數即可至少節省一些時間。當你在嵌套循環中調用這個函數時，它應該是一個很好的攻擊點。嘗試將其替換爲

def range_cus(one,two): 
    return sqrt((one.x - two.x)**2 + (one.y - two.y)**2) 

並記得在程序的頂部執行from math import sqrt。在這個版本中，你擺脫了很多關於math對象的查找（math.）