Recall our discussion of linear vs. binary searching of sorted arrays for a particular value.
Suppose we a set of nbin ascending-sorted histogram bins edges = range(nbin) and a given number x
whose histogram bin i we wish to find such that edges[i] <= x < edges[i + 1] assuming i < nbin - 1.
Write a function (e.g., in Python) with the following example Python interface that use linear searching method to find the correct histogram bin of x.
def getBinLinear(x, edges):
"""
Return the index of the element of `edges` such that the condition `edges[i] <= x < edges[i + 1]` holds.
If `x` is larger than all elements of `edges`, then the function returns `len(edges) - 1`.
If `x` is smaller than all elements of `edges`, then the function returns `- 1`.
"""
Recall that for sorted arrays, we can also use the binary search method to compute the corresponding bin of x.
Write a new function with the following example Python interface to use the binary searching method to find the histogram bin of x.
def getBinBinary(x, edges):
"""
Return the index of the element of `edges` such that the condition `edges[i] <= x < edges[i + 1]` holds.
If `x` is larger than all elements of `edges`, then the function returns `len(edges) - 1`.
If `x` is smaller than all elements of `edges`, then the function returns `- 1`.
"""
Which algorithm is faster for finding the bin of an arbitrary x value? When? Why?
Benchmark the two algorithms you have implemented for a range of incrementally-increasing edges array values and lengths.
Make a plot of the benchmark and justify your answer to the performance of the two algorithms based on your benchmark results.
Hint: To simplify the benchmark, you can fix the value of x in your benchmark to edges[-2] (the element before the last in edges).
Then, run the benchmarks for different values of nbin, for example, from 5 to 50,000 edges.
The specific suggested value of x roughly leads to the worst-case performance of the linear and binary searches.
This benchmark setting, therefore, gives you a rough idea of how fast the two methods are compared to each other.
Here is an example range of nbin values (in Python) with which you can test your algorithms,
for val in np.logspace(np.log2(5), np.log2(50000), 10, base = 2):
nbin = np.int(val)
edges = range(nbin)
x = edges[-2]
print("nbin = {}, x = {}".format(nbin, x))
nbin = 4, x = 2
nbin = 13, x = 11
nbin = 38, x = 36
nbin = 107, x = 105
nbin = 299, x = 297
nbin = 834, x = 832
nbin = 2320, x = 2318
nbin = 6457, x = 6455
nbin = 17969, x = 17967
nbin = 50000, x = 49998
