This is all probably too nitpicky and you should try get others to review the PR as it stands.

Resampling by class for 1e6 classes seems a very unlikely use-case. You're right that `unique` unnecessarily creates a copy of the data.

How about changing the last line of `_collect_indices` to `labels, indices = zip(*sorted(iteritems(d)))` and return both the labels and the indices. Then convert `distribution` to an array with the corresponding labels.