<<Метапрограммирование на Ruby
Лекция 3. Задача вычисления 10 самых частых слов
Метод inject позволяет не только суммировать и умножать элементы, но и
- вычислять минимум
- вычислять среднее арифметическое
- вообще любые однопроходные алгоритмы
- хештаблицу частот
- ...
Вычисление среднего арифметического
a = [1,2,3,4]
a.inject([0.0, 0]) {|p, elem|
# вычисляем пару [среднее_значение, число_элементов]
sr,count = p
sum = sr * count + elem
count += 1
sr = sum / count
[sr, count]
}
Вычисление самых частых 10 слов длины 5 символов или больше
IO.read("a.txt").scan(/[a-zA-Zа-яА-Я]+/).select{|w| w.length >= 5}.inject(Hash.new(0)){|f,word|
f[word] += 1
f
}.to_a.sort_by{|word,freq| -freq}[0...10].each do |word, freq|
puts "#{word}: #{freq}"
end
Вместо scan можно использовать split
IO.read("a.txt").split(/[\s,.:?!$]+/) ....
- scan получает в аргументе регулярное выражение того, что мы ищем и возвращает в качестве результата массив найденных подстрок, удовлетворяющих шаблону
- split получает в аргументе регулярное выражение промежутков того, что мы хотим отбросить, и возвращает массив кусочков, на которые разбилась строка
Отбор по длине можно выполнить прямо в регулярном выражении:
IO.read("a.txt").scan(/[a-zA-Zа-яА-Я]{5,}/).inject(Hash.new(0)){|f,word|
f[word] += 1
f
}.to_a.sort_by{|word,freq| -freq}[0...10].each do |word, freq|
puts "#{word}: #{freq}"
end
Задачи для самостоятельного решения:
- Оцените время работы представленного кода
- Напишите метод Array#nth_element(n), находящий n-й по порядку элемент в массиве, а также функцую Array#partition!(n), которая переставляет эелементы массива так, что справа от n-го элемента находятся элементы меньше или равные, а справа больше или равные элементу. Обе функции должны выполняться за линейное время.
- Напишите решение работающее за время порядка O(N) (Примеры на языке C и C++) (Примечание: решение использует предыдущий метод для нахождения медианы).