Mercurial > hg > GlobalNeighbors

comparison globalneighbors/distance.py @ 7:254195d0bac2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want
author Jeff Hammel <k0scist@gmail.com>
date Sun, 25 Jun 2017 09:13:48 -0700
parents 316e1d54ffd4
children e3d6919130ca
comparison
equal deleted inserted replaced
6:316e1d54ffd4 7:254195d0bac2
36 """ 36 """
37 insert `(i, new_distance)` into `distances` 37 insert `(i, new_distance)` into `distances`
38 keeping distances in order with maximum of size `k` 38 keeping distances in order with maximum of size `k`
39 """ 39 """
40 40
41 if len(distances) == k and new_distance >= distances[-1][-1]:
42 return
43
41 # TODO: Binary Search Tree 44 # TODO: Binary Search Tree
42 for _index, (geoid, old_distance) in enumerate(distances): 45 for _index, (geoid, old_distance) in enumerate(distances):
43 if new_distance < old_distance: 46 if new_distance < old_distance:
44 distances.insert(_index, (i, new_distance)) 47 distances.insert(_index, (i, new_distance))
45 if len(distances) == k+1: 48 if len(distances) == k+1:
46 distances.pop() 49 distances.pop()
47 break 50 break
48 else: 51 else:
49 distances.append((i, new_distance)) 52 distances.append((i, new_distance))
50 53
51 # def insert_distance(distances, i, new_distance, k): 54
52 # if not distances: 55 def insert_distance_bisect(distances, i, new_distance, k):
53 # distances.append((i, new_distance)) 56 if not distances:
54 # return 57 distances.append((i, new_distance))
55 # if new_distance >= distances[-1][-1]: 58 return
56 # if len(distances) < k: 59 if new_distance >= distances[-1][-1]:
57 # distances.append((i, new_distance)) 60 if len(distances) < k:
58 # return 61 distances.append((i, new_distance))
62 return
63 indices = [0, len(distances)]
64 while True:
65 midpoint = int((indices[-1] - indices[0])/2)
59 66
60 67
61 def calculate_distances(locations, r=Rearth): 68 def calculate_distances(locations, r=Rearth):
62 """ 69 """
63 WARNING! This is an N-squared approach 70 WARNING! This is an N-squared approach
122 new_distance = haversine(*args, r=Rearth) 129 new_distance = haversine(*args, r=Rearth)
123 130
124 # insert in order 131 # insert in order
125 for i in (id1, id2): 132 for i in (id1, id2):
126 distances = neighbors.setdefault(i, []) 133 distances = neighbors.setdefault(i, [])
127 if len(distances) == k and new_distance >= distances[-1][-1]:
128 continue
129 134
130 insert_distance(distances, i, new_distance, k) 135 insert_distance(distances, i, new_distance, k)
131 136
132 return neighbors 137 return neighbors
133 138