[wrsh07]

I'm somewhat curious about the initial problem:

> Consider the following real problem, one of the steps in scikit-learn’s gradient histogram boosting algorithm:

> You have a large array of floating point numbers.

> You want to assign them to the integer range 0-254, spread out evenly.

Naively I would consider sorting the initial array and then using something like `batched` from itertools to chunk them into the 255 buckets - binary search will give you a bunch of random accesses, and sorting can be cache-oblivious (eg efficient for arbitrary data sizes)

But I'm somewhat concerned I don't fully understand the underlying problem being solved with this step, so I might be misunderstanding the intended result

[itamarst]

The bucket boundaries are often chosen from a random sample of the data, if the input data is very large. Sorting is O(nlogn), but using binary search per value to assign a bucket is O(n), plus the cost of creating the buckets on a sample. So once you hit a large enough number of values this scales better.

Binary search does give random access but in this case there's only up to 255 buckets typically, so it's random access on cached memory.

[wrsh07]

Can you say more about what happens for bucket assignment? Eg is it appending to a file or writing to a 2d array?

Agreed on linear vs n log n, ofc, and streaming considerations might also be relevant