You are here

연산 시간이 너무 길게 나오는데...

아래 과정을 구현한 소스인데 연산 시간이 너무 길게 나와서 줄이는 방법을 알고 싶습니다.

참고로 좌표 리스트가 수만개 까지 될수 있습니다.
첨부 파일의 리스트는 2128개입니다.

Step 0: 시작 리스트 중에서 임의로 하나의 좌표를 선택하여 그 좌표를 C1 이라고 한다. (최초 C1은 {0 0}으로 지정)
Step 1: C1과 나머지 좌표와의 거리를 계산하여 가장 가까운 좌표를 C2라 하고 최종 리스트에 추가한다.
Step 2: C2를 C1에 대입하고 시작 리스트에서 C2 삭제 후 시작 리스트가 없어질때까지 Step 1 반복

proc shortest_dist {org list} {
    global widget env script
    set _loc_list1 $org
    set _distance_min 1.0e30
    set no [llength $list]
    for { set i 0} {$i < $no} {incr i} {
        set _loc_list2 [lindex $list $i]
        set x1 [lindex $_loc_list1 0]
        set y1 [lindex $_loc_list1 1]
        set x2 [lindex $_loc_list2 0]
        set y2 [lindex $_loc_list2 1]
   
        set _distance [expr {hypot([expr {abs([expr $x2 - $x1])}],[expr {abs([expr $y2 - $y1])}])}]
        if {$_distance < $_distance_min} {
            set _distance_min $_distance
            set _distance_min_idx $i
        }
        update
    }
    set script(shortest_dist) $_distance_min
    return $_distance_min_idx
}
source [file join [pwd] sample_list.tcl]
set list_no [llength $list]
set _list ""
set _org "0 0"
set _distance_t 0
set list2 $list
set start_time [clock clicks -milliseconds]
for { set j 0} {$j < $list_no} {incr j} {
    set _loc_list1 $_org
    set _index [shortest_dist $_org $list2]
    set _org [lindex $list $_index]
    set list2 [lreplace $list2 $_index $_index]
    set _distance_t [expr $script(shortest_dist) + $_distance_t]
    lappend _list $_org
    update
}
set end_time [clock clicks -milliseconds]
set elapsed_time [format %.3f [expr ($end_time - $start_time) / 1000.0]]
puts "List Qty. : $list_no  Elapsed Time : $elapsed_time sec"