Какая самая быстрая настройка для вычисления больших наборов строковых данных?

Question

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

Настройка:

• 100 000 записей в базе данных, содержащей строки
• Я буду выполнять вычисления сходства строк, чтобы найтипримерные дубликаты
  • т.е. каждая строка против любой другой строки, поэтому ~ 5 миллиардов вычислений
• Я написал доказательство концепции в Ruby, используя SQLite3 в качестве базы данных, используя 1000 строк выборки
• Вся работа должна выполняться менее чем за несколько дней - чем быстрее, тем лучше, но с убывающей отдачей.Это однократный пропуск, поэтому мне не нужен суперкомпьютер, если настройка рабочего стола может сделать это в течение нескольких дней

Что я ищу:

• Если я создаю специальный ящик для запуска этого задания (и, возможно, будущих заданий аналогичного характера), на каком оборудовании мне следует сосредоточиться на оптимизации?Т.е. я должен потратить свой ограниченный бюджет на очень быстрый графический процессор?ЦПУ?Большие объемы оперативной памяти?Я не знаю Ruby на достаточно низком уровне, чтобы знать, где находятся узкие места для этого типа операций
• Я пропускаю лучший подход?Я не получу одобрения на какие-либо крупные покупки программного обеспечения или дорогостоящего оборудования, по крайней мере, пока не смогу доказать, что этот метод работает с этим прогоном.Но кто-нибудь может предложить более эффективный метод обнаружения неточных дубликатов?

Answer 1

Во-первых, в настоящее время 100 000 строк на самом деле не могут рассматриваться как большой набор данных, поэтому не стоит слишком беспокоиться об аппаратном обеспечении.Вот несколько советов из моей предыдущей работы (связанной с поиском и машинным переводом) и текущей, где я постоянно работаю с несколькими сотнями миллионов записей XML:

• Вам нужна оперативная память.Многое.
• Как сказал Сорен, вы хотите убедиться, что ваш алгоритм в порядке.
• Мудро выбирайте свою БД.Например, Postgres имеет превосходные строковые функции , и выполнение определенных операций непосредственно в БД может быть очень быстрым.Я сказал, что вы хотите много оперативной памяти?
• Ваша работа звучит так, что было бы довольно легко разбить ее на более мелкие подзадачи, которые можно решать параллельно.Если это действительно так, вы можете посмотреть на MapReduce .В предыдущей работе у нас были довольно хорошие рабочие станции (4 ядра, 8 ГБ ОЗУ), которые никогда не отключались, поэтому мы превратили некоторые из них в кластер Hadoop, который мог бы выполнять полезные функции.Так как машины были достаточно мощными для повседневного использования, пользователи даже не заметили.Обычно не так уж сложно превратить что-либо в задание MapReduce, и другим преимуществом будет то, что вы сможете сохранить настройку для подобных задач в будущем.
• Что касается бутылочных горлышек, характерных для Ruby, то самая большая из них в МРТ - это, как правило, сбор мусора, который благодаря своей природе "остановка мира" очень медленный.Когда мы регистрируем, это регулярно становится проблемой.Посмотрите, почему статья Полностью перевернутая корзина для получения подробной информации о Ruby GC.Если вы настроены на использование Ruby, возможно, вы захотите сравнить MRI с JRuby, исходя из моего опыта работы с последними и такими профилировщиками, как JVisualVM, я не удивлюсь, если бы JRuby справился лучше.

Answer 2

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

Если это одноразовая задача, вам действительно нужно просто запустить ее на Amazon - получить очень большую машину (4Core, 15 ГБ ОЗУ) на несколько часов и просто запустить ее там.

Answer 3

Ваш алгоритм сходства строк гораздо важнее, чем ваша аппаратная спецификация.

Ключевой вопрос для алгоритмов сходства строк: «когда вы ожидаете, что строка будет похожа?»Рассматриваете ли вы подстроки, орфографические ошибки, фонетику, опечатки.

Эта ссылка SO отлично обсуждает алгоритмы.100 000 записей - это действительно очень мало данных (в моем мире), но для простоты реализации, когда у вас есть хороший алгоритм, вы должны попытаться получить как можно больше оперативной памяти.Выполнение этого в Ruby также может оказаться не лучшим выбором с точки зрения производительности.