Быстро взвешенный случайный выбор из очень большого набора значений

Я сейчас работаю над проблемой, которая требует случайного выбора элемента из набора. Каждый из элементов имеет связанный с ним вес (вероятность выбора).

Моя проблема в том, что для наборов с небольшим количеством элементов, скажем, 5-10, сложность (время выполнения) решения, которое я использовал, является приемлемым, однако по мере увеличения количества элементов, скажем, для 1 КБ или 10 КБ и т. д., время выполнения становится неприемлемым.

Моя текущая стратегия:

1. Выбрать случайное значение X с range [0,1)
2. Итерируйте элементы, суммируя их веса, пока сумма не превысит X
3. Элемент, из-за которого сумма превысила X, выбирается и возвращается

Для больших наборов и большого количества выборок это процесс начинает проявлять квадратичное поведение, короче говоря, есть ли более быстрый способ? Возможно, лучший алгоритм?