Mercurial > hg > GlobalNeighbors

comparison globalneighbors/distance.py @ 5:7e27e874655b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
test a larger grid + move distance insertion to its own function
author Jeff Hammel <k0scist@gmail.com>
date Sat, 24 Jun 2017 15:16:10 -0700
parents 49aae0c0293b
children 316e1d54ffd4
comparison
equal deleted inserted replaced
4:8e130b7bfed9 5:7e27e874655b
28 )) 28 ))
29 29
30 30
31 def deg_to_rad(degrees): 31 def deg_to_rad(degrees):
32 return degrees*DEGREESTORADIANS 32 return degrees*DEGREESTORADIANS
33
34
35 def insert_distance(distances, i, new_distance, k):
36 """
37 insert `(i, new_distance)` into `distances`
38 keeping distances in order with maximum of size `k`
39 """
40
41 # TODO: Binary Search Tree
42 for _index, (geoid, old_distance) in enumerate(distances):
43 if new_distance < old_distance:
44 distances.insert(_index, (i, new_distance))
45 if len(distances) == k+1:
46 distances.pop()
47 break
48 else:
49 distances.append((i, new_distance))
33 50
34 51
35 def calculate_distances(locations, r=Rearth): 52 def calculate_distances(locations, r=Rearth):
36 """ 53 """
37 WARNING! This is an N-squared approach 54 WARNING! This is an N-squared approach
99 for i in (id1, id2): 116 for i in (id1, id2):
100 distances = neighbors.setdefault(i, []) 117 distances = neighbors.setdefault(i, [])
101 if len(distances) == k and new_distance >= distances[-1][-1]: 118 if len(distances) == k and new_distance >= distances[-1][-1]:
102 continue 119 continue
103 120
104 # TODO: Binary Search Tree 121 insert_distance(distances, i, new_distance, k)
105 for _index, (geoid, old_distance) in enumerate(distances):
106 if new_distance < old_distance:
107 distances.insert(_index, (i, new_distance))
108 if len(distances) == k+1:
109 distances.pop()
110 break
111 else:
112 distances.append((i, new_distance))
113 122
114 return neighbors 123 return neighbors
115 124
116 125
117 def main(args=sys.argv[1:]): 126 def main(args=sys.argv[1:]):
141 neighbors = calculate_neighbors(city_locations, 150 neighbors = calculate_neighbors(city_locations,
142 k=options.k, 151 k=options.k,
143 output=options.output_counter) 152 output=options.output_counter)
144 153
145 # output 154 # output
146 options.output.write(json.dumps(neighbors, indent=2)) 155 options.output.write(json.dumps(neighbors))
147 156
148 if __name__ == '__main__': 157 if __name__ == '__main__':
149 main() 158 main()