Nano Hash - криптовалюты, майнинг, программирование

Печать n наиболее часто встречающихся слов в файле (строке)

Цель:

Напишите функцию, которая принимает два параметра: (1) строку, представляющую текстовый документ, и (2) целое число, указывающее количество возвращаемых элементов. Реализуйте функцию таким образом, чтобы она возвращала список строк, упорядоченных по частоте слов, начиная с наиболее часто встречающегося слова. Используйте свое лучшее суждение, чтобы решить, как слова разделены. Ваше решение должно выполняться за время O(n), где n — количество символов в документе.

Я думал, что в худшем случае на вход функции может поступить общее количество слов в документе, что сведет проблему к сортировке слов по их частоте. Это натолкнуло меня на мысль, что нижняя граница временной сложности будет равна O (n log n), если я буду использовать метод сравнительной сортировки. Итак, я подумал, что лучшим подходом было бы реализовать сортировку подсчетом. Вот мой код.

Я хотел бы, чтобы вы сказали мне, верен ли мой анализ, я аннотировал код своим представлением о временной сложности, но он определенно может быть неверным. Какова фактическая временная и пространственная сложность этого кода? Также я хотел бы услышать, действительно ли это хороший подход, есть ли какие-либо альтернативные подходы, которые можно было бы использовать на практике.

### n is number of characters in string, k is number of words ###
def word_frequencies(string, n)
  words = string.split(/\s/)  # O(n)
  max = 0
  min = Float::INFINITY
  frequencies = words.inject(Hash.new(0)) do |hash,word|  # O(k)
    occurrences = hash[word] += 1                     # O(1)
    max = occurrences if occurrences > max            # O(1)
    min = occurrences if occurrences < min            # O(1)
    hash;                                             # O(1)  
  end

  ### perform a counting sort ###
  sorted = Array.new(max + words.length)

  delta = 0

  frequencies.each do |word, frequency|   #O(k)
    p word + "--" + frequency.to_s
    index = frequency
    if sorted[index]
      sorted[index] = sorted[index].push(word)  # ??? I think O(1).
    else
      sorted[index] = [word]                    # O(1)
    end
  end

  return sorted.compact.flatten[-n..-1].reverse   
  ### Compact is O(k).  Flatten is O(k).  Reverse is O(k). So O(3k)
end

### Total --- O(n + 5k) = O(n).  Correct? 
### And the space complexity is O(n) for the hash + O(2k) for the sorted array.  
### So total O(n).


text = "hi hello hi my name is what what hi hello hi this is a test test test test hi hi hi what hello these are some words these these"

p word_frequencies(text, 4)
ruby sorting algorithm big-o
12.11.2013

Ответы:


1

Два пути:

def word_counter(string, max)
  string.split(/\s+/)
        .group_by{|x|x}
        .map{|x,y|[x,y.size]} 
        .sort_by{|_,size| size} # Have to sort =/
        .last(max)
end

def word_counter(string, max)

  # Create a Hash and a List to store values in.
  word_counter, max_storage = Hash.new(0), []

  #Split the string an and add each word to the hash:
  string.split(/\s+/).each{|word| word_counter[word] += 1}

  # Take each word and add it to the list (so that the list_index = word_count)
  # I also add the count, but that is not really needed
  word_counter.each{|key, val| max_storage[val] = [*max_storage[val]] << [key, val]}

  # Higher count will always be at the end, remove nils and get the last "max" elements.
  max_storage.compact.flatten(1).last(max)

end
12.11.2013

2

Одна идея следующая:

  1. Вы уже строите хеш-карту, которая дает частоту данного слова.
  2. Теперь выполните итерацию по этой хеш-карте и создайте обратный «хеш-набор». Это набор слов для данной частоты.
  3. Найдите максимальную частоту и выведите набор слов для этой частоты.
  4. Уменьшите его и проверьте наличие слов в хеш-наборе.
  5. Продолжайте делать это до необходимого количества слов.

Порядок этого алгоритма должен быть O(f), где f — максимальная частота любого слова. Максимальная частота любого слова должна быть не более n, где n — требуемое количество символов.

12.11.2013
  • @ordinary IMO сложность должна быть O (f), где f - максимальная частота для любого слова. Тогда максимально возможное значение этой частоты равно n, где n — количество символов в тексте. Это произойдет, если все n символов являются одними и теми же словами из одного символа. 12.11.2013

    • 3

    Пример, быстрый способ :)

    #assuming you read from the file and get it to a string called str

h = {}
arr = str.split("\n")
arr.each do |i|
  i.split(" ").each do |w|
    if h.has_key[w]
      h[w] += 1
    else
      h[w] = 1
    end
  end
end
Hash[h.sort_by{|k, v| v}.reverse]

    Это работает, но может быть улучшено.

    12.11.2013
  • спасибо, но вы читали вопрос. это очевидный ответ, но, как я уже говорил, мне нужно сделать это за время O (n). сортировка всего массива в лучшем случае O (n log n) 12.11.2013
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..