Почему список кумулятивных сумм частот необходим для реализации генератора случайных слов?

Question

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

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

1. Создать гистограмму, показывающую {word: frequency},
2. Использовать keys способ получить список слов в книге.
3. Создайте список, который содержит совокупную сумму частот слов, так что последний элемент в этом списке - это общее количество слов в книге, n,
4. Выберите случайное число от 1 до n,
5. Используйте поиск пополам, чтобы найти индекс, где случайное число будет вставлено в накопленную сумму.
6. Используйте индекс, чтобы найти соответствующее слово в списке слов.

Мой вопрос таков: что не так со следующим решением?

1. Превратить роман в список t слов, точно так же, как они появляются в романе, без устранения повторяющихся случаев или перемешивания.
2. Генерация случайного целого числа от 0 до n, где n = len(t) – 1,
3. Используйте это случайное целое число в качестве индекса, чтобы получить случайное слово из t,

Благодарю.

Answer 1

Ваш подход (также) правильный, но он использует пространство, пропорциональное размеру входного текста. Подход, предложенный в книге, использует пространство, пропорциональное только количеству отдельных слов во входном тексте, которое обычно намного меньше. (Подумайте о том, как часто такие слова, как "the", появляются в английском тексте.)