Hi hail team,
If I have a number and a list of numbers, is there a fast way to find the closest value in the list to the input number? For example, if I have the number 5 and the list [1, 7, 10, 15], I’d like to be able to quickly pull 7 from the list.
python’s min can do this, but I can’t seem to implement the same functionality with hl.min(). Is there a workaround, or am I missing something?
Thanks!
Hey @ch-kr !
You’re looking for binary_search:
ls = hl.array([1, 7, 10, 15])
x = hl.binary_search(ls, 7)
result = hl.or_missing(x != -1, ls[x])
result.show()
I wasn’t aware you could finagle min to do this, how do you invoke it?
ah neat, do you do this?
min([1, 7, 10, 15], key=lambda x: abs(x - 3))
I should note, my solution only works for sorted lists.
This is the best I’ve got in Hail:
In [6]: def find_nearest(ls, x):
...: def return_closest(l, r):
...: return hl.if_else(hl.abs(l - x) < hl.abs(r - x), l, r)
...: return hl.fold(return_closest, ls[0], ls[1:])
In [7]: find_nearest(ls, 5)
Out[7]: <Int32Expression of type int32>
In [8]: find_nearest(ls, 5).show()
+--------+
| <expr> |
+--------+
| int32 |
+--------+
| 7 |
+--------+
In [9]: find_nearest(ls, 8).show()
+--------+
| <expr> |
+--------+
| int32 |
+--------+
| 7 |
+--------+
In [10]: find_nearest(ls, 3).show()
+--------+
| <expr> |
+--------+
| int32 |
+--------+
| 1 |
+--------+
In [11]: find_nearest(ls, 4).show()
+--------+
| <expr> |
+--------+
| int32 |
+--------+
| 7 |
+--------+
hl.binary_search would return the index of the closest larger number in a sorted list. In the example, it works for input 5 (returns 7). But it doesn’t work for input 2 (also returns 7).
Another option would be to sort the list using a key and take the first element.
hl.sorted(ls, lambda n: hl.abs(n - input))[0]
@danking’s find_nearest function would be more efficient than sorting though.
I think binary search followed by checking the idx and idx - 1 would work, maybe?
thank you all!!