Лекция 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++) (Примечание: решение использует предыдущий метод для нахождения медианы).