Как быстро подсчитать вхождения строки в строку с помощью Ruby

Question

У меня есть текстовый файл размером 300 МБ, я хочу подсчитать вхождения каждой 10000 подстрок в файле. Я хочу знать, как сделать это быстро.

Теперь я использую следующий код:

content = IO.read("path/to/mytextfile")
Word.each do |w|
  w.occurrence = content.scan(w.name).size
  w.save
end

Word - это класс ActiveRecord.

Мне потребовался почти 1 день, чтобы закончить отсчет. Есть ли способ сделать это быстрее? Спасибо.

Edit1: Еще раз спасибо Я бегу рельсами 2.3.9. Таблица name слов содержит то, что я ищу, и содержит только уникальные значения. Вместо использования Word.each я использую пакетную загрузку (1000 строк за раз). Это должно помочь.

Я переписал весь код с идеей от bpaulon. Теперь потребовалось всего несколько часов, чтобы закончить отсчет.

Я профилировал код новой версии, теперь самые большие методы определения затрат времени - это кодирование с использованием utf8, поддерживающее код усечения строки

def truncate(n)
  self.slice(/\A.{0,#{n}}/m)
end

и код подсчета символов

def utf8_length
  self.unpack('U*').size
end

Есть ли другие более быстрые способы их замены?

Answer 1

Использование scan создает массив, считает его размер, а затем выбрасывает. Если у вас много вхождений подстроки в большой файл, вы временно создадите большой массив, потенциально сжигающий процессорное время с управлением памятью, но он все равно должен работать довольно быстро, даже с 300 МБ.

Поскольку Word является классом ActiveRecord, он зависит от схемы и любых индексов в вашей базе данных, а также от любых проблем, которые могут возникнуть на сервере базы данных. Если база данных не оптимизирована или реагирует медленно, или запрос, используемый для извлечения данных, неэффективен, то итерация будет медленной. Возможно, вам будет гораздо проще захватить группы Word, чтобы они были в ОЗУ, а затем выполнить итерации по ним.

И, если база данных и ваш код работают на одном и том же компьютере, вы можете страдать от ограничений ресурсов, таких как наличие только одного диска, недостаточно ОЗУ и т. Д.

Трудно сказать, не зная больше о вашей среде и оборудовании.

---

РЕДАКТИРОВАТЬ:

Я могу сначала захватить подстроки в массив / хэш, затем добавить результаты подсчета в массив или хэш и записать результаты обратно в базу данных после того, как все подсчеты выполнены. Вы думаете, это будет быстрее, верно?

Нет, я сомневаюсь, что это очень поможет, и, не зная, в чем заключается проблема, все, что вы можете сделать, это усугубить проблему, потому что вам придется загрузить 10 000 записей в виде объектов из базы данных, а затем создать 10 000 элементов хеш или массив, который также будет в памяти вместе с записями в БД, затем запишите их.

В настоящее время Ruby будет использовать только одно ядро, но вы можете набрать скорость, используя Ruby 1.9+. Я бы порекомендовал установить RVM и позволить ему управлять вашим Ruby. Обязательно прочитайте инструкции на этой странице, затем запустите rvm notes и следуйте этим указаниям.

Какова ваша модель Word и как выглядят базовая схема и индексы? База данных находится на той же машине?

---

РЕДАКТИРОВАТЬ: При просмотре схемы таблицы у вас нет индексов, кроме id, который действительно не сильно поможет при обычном поиске. Я бы порекомендовал представить вашу схему на сайте-партнере Stack Overflow https://dba.stackexchange.com/ и объяснить, что вы хотите сделать. Как минимум, я бы добавил ключ к текстовым полям, чтобы избежать полных сканирований таблиц для любых выполненных вами поисков.

Что может помочь больше, это прочитать: Извлечение нескольких объектов в пакетах из «Интерфейса запросов Active Record».

Кроме того, посмотрите на SQL, генерируемый при работе Word.each. Это что-то вроде "select * from word"? Если это так, Rails набирает 10000 записей, чтобы перебирать их одну за другой. Если это что-то вроде "select * from word where id=1", то для каждой записи у вас есть чтение базы данных, за которым следует запись при обновлении счетчика. Это тот сценарий, который поможет исправить ссылка «Извлечение нескольких объектов в пакетах».

Кроме того, я предполагаю, что content - это текст, который вы ищете, но я не могу сказать точно. Возможно ли, что у вас есть дублированные текстовые значения, заставляющие вас выполнять сканирование более одного раза для одного и того же текста? Если это так, выберите ваши записи, используя условие unique в этом поле, а затем обновите счетчик для всех совпадающих записей за один раз.

Профилировали ли вы свой код, чтобы увидеть, может ли сам Ruby помочь вам определить проблему? Немного измените ваш код для обработки 100 или 1000 записей. Запустите приложение с флагом -r profile. При выходе из приложения профилировщик выведет таблицу с указанием времени, потраченного на это.

Какую версию Rails вы используете?

Answer 2

Я думаю, что вы могли бы подойти к этой проблеме по-другому

Вам не нужно много раз сканировать файл, вы можете создать БД, как в mongo или mysql , и для каждого найденного слова вы выбираете БД для этого, а затем добавляет в некоторые "счетчик" поле.

Вы можете спросить меня: «Но тогда мне придется много сканировать базу данных, и это может занять гораздо больше». Ну, конечно, вы не спросите этого, но это не займет больше времени, потому что базы данных сосредоточены на IO, кроме того, вы всегда можете проиндексировать его .

---

РЕДАКТИРОВАТЬ: Нет никакого способа разграничить вообще ?? Предположим, что там, где у вас есть строка Word.name, вы действительно держите (не простое) регулярное выражение. Может ли регулярное выражение содержать \ n? Хорошо, если регулярное выражение может содержать любое значение, вы должны оценить максимальный размер строки, которую регулярное выражение может извлечь, удвоить и отсканировать файл по этому количеству символов, но переместив курсор на это число.

Допустим, ваша оценка максимального значения, которое может извлечь ваше регулярное выражение, равна 20 символам, а в вашем файле от 0 до 30000 символов. Вы передаете каждому имеющемуся регулярному выражению от 0 до 40 символов, затем снова от 20 до 60, от 40 до 80 и т. Д.

Вы также должны удерживать положение, которое вы нашли, для вашего меньшего регулярного выражения, чтобы оно не повторялось.

Наконец, это решение, похоже, не стоит усилий, ваша проблема может иметь лучшее решение, основанное на том, что это регулярные выражения, но это будет быстрее, чем запуск сканирования Word.count, умноженный на вашу строку 300 МБ.

Answer 3

Вы можете загрузить всю таблицу «Word» в Trie , а затем выполнить обратное отслеживание, поскольку вы сказали, что в тексте нет разделителей.

То есть для каждого символа втекст, иди вниз три слов.Если вы нажмете слово, увеличьте его количество.«Переход вниз по дереву» включает три случая:

1. У этого персонажа нет узла.(Если вы находитесь в середине поиска, вставьте стек отслеживания назад)
2. У этого персонажа есть узел.(Но это не Слово)
3. У этого персонажа есть узел.(Это слово - инкрементное и «грязное»)

Обратное отслеживание - это просто отслеживание мест, куда вы хотите попасть после того, как вы исчерпали этот «поиск» Trie, то есть когда вызакончились узлы для посещения.Вероятно, это будет каждый посещаемый вами символ, являющийся корнем Trie.

После того, как вы это сделаете, вы сможете посетить все измененные вами узлы и просто обновить записи, которые они представляют.

Это займет некоторое время для реализации, но, безусловно, будет быстрее, чем каждый & сканирования.