Самый быстрый способ анализа больших строк (многопоточный)

Я собираюсь начать проект, который будет брать блоки текста, анализировать в них много данных в какой-то объект, который затем можно сериализовать, хранить и собирать статистику/данные. Это должно быть как можно быстрее, так как у меня > 10 000 000 блоков текста, с которых мне нужно начать, и я буду получать 100 000 тысяч блоков в день.

Я запускаю это в системе с 12 ядрами xeon + гиперпотоками. У меня также есть доступ / немного знаю о программировании CUDA, но для строковых вещей я думаю, что это не подходит. Из каждой строки мне нужно разобрать много данных, и некоторые из них я знаю точные позиции, некоторые нет, и мне нужно использовать регулярное выражение/что-то умное.

Итак, рассмотрим что-то вроде этого:

object[] parseAll (string [] stringsToParse)
{
     parallel foreach 
          parse( string[n] )
}

object parse(string s)
{
     try to use exact positions / substring etc here instead of regex's
}

Итак, мои вопросы:

  • Насколько медленнее использование регулярных выражений для substr.
  • Будет ли .NET значительно медленнее, чем другие языки?
  • Какие оптимизации (если есть) я могу сделать, чтобы максимизировать параллелизм.
  • Что-то еще, что я не учел?

Спасибо за любую помощь! Извините, если это многословно.


string parsing c# regex parallel-processing
person Luke Belbina    schedule 06.11.2010    source источник
comment
Я предполагаю, что IO будет ограничивающим фактором. Настройте несколько простых тестовых случаев и профилируйте использование ресурсов и т. д.   -  person    schedule 06.11.2010
comment
На современном ПК объем, о котором вы говорили, — это мелочь для работы с хранилищем данных. Метод, который вы предлагаете, звучит, э-э, звучит. Подумайте также об использовании таких вещей, как IndexOf, когда вы знаете, что можете безопасно искать фиксированную строку. По возможности избегайте ToUpper/Lower, если функции сравнения поддерживают игнорирование регистра. Но сначала напишите для удобства чтения, а потом оптимизируйте.   -  person Will    schedule 06.11.2010

Ответы (4)


arrow_upward
5
arrow_downward

Насколько медленнее использование регулярных выражений для substr.
Если вы ищете точную строку, substr будет быстрее. Однако регулярные выражения очень оптимизированы. Они (или хотя бы части) скомпилированы в IL и можно даже хранить эти скомпилированные версии в отдельной сборке с помощью Regex.CompileToAssembly. См. http://msdn.microsoft.com/en-us/library/9ek5zak6.aspx для получения дополнительной информации.

Что вам действительно нужно сделать, так это выполнить измерения. Использование чего-то вроде Stopwatch — самый простой способ проверить, работает ли та или иная конструкция кода быстрее.

Какие оптимизации (если таковые имеются) можно выполнить, чтобы максимизировать параллелизм.
С помощью Task.Factory.StartNew вы можете планировать выполнение задач в пуле потоков. Вы также можете взглянуть на TPL (библиотека параллельных задач, частью которой является Task). Он имеет множество конструкций, которые помогают распараллелить работу и позволяют конструкциям вроде Parallel.ForEach() выполнять итерацию в нескольких потоках. См. http://msdn.microsoft.com/en-us/library/dd460717.aspx для получения дополнительной информации.

Что-то еще, что я не учёл?
Одной из вещей, которая может навредить вам при работе с таким объёмом данных, является управление памятью. Несколько вещей, которые следует учитывать:

  • Ограничьте выделение памяти: попробуйте повторно использовать одни и те же буферы для одного документа вместо того, чтобы копировать их, когда вам нужна только часть. Скажем, вам нужно работать с диапазоном символов, начиная с 1000 до 2000, не копируйте этот диапазон в новый буфер, а создайте свой код для работы только в этом диапазоне. Это усложнит ваш код, но сэкономит вам память;

  • StringBuilder — важный класс. Если вы еще не знаете об этом, посмотрите.

person Pieter van Ginkel    schedule 06.11.2010
comment
Полностью согласен. В частности, остерегайтесь части распределения памяти. При таком большом объеме можно пострадать от фрагментации памяти. Я предлагаю вам прочитать и понять это, если вы еще этого не сделали: simple-talk.com/dotnet/.net-framework/ - person Francesco De Vittori; 17.11.2010

arrow_upward
1
arrow_downward

Я не знаю, какую обработку вы здесь выполняете, но если вы обрабатываете сотни тысяч строк в день, это кажется довольно небольшим числом. Предположим, что вы ежедневно обрабатываете 1 миллион новых строк и можете полностью загрузить 10 из этих 12 ядер Xeon. Это 100 000 строк на ядро ​​в день. В сутках 86 400 секунд, поэтому мы говорим о 0,864 секунды на строку. Это много синтаксического анализа.

Я повторю рекомендации, сделанные @Pieter, особенно там, где он предлагает провести измерения, чтобы увидеть, сколько времени потребуется для обработки. Лучше всего создать и запустить что-то, затем придумать, как сделать это быстрее, если нужно. Я думаю, вы будете удивлены тем, как часто вам не нужно делать какую-либо оптимизацию. (Я знаю, что это ересь для мастеров оптимизации, но процессорное время дешево, а время программиста дорого.)

Насколько медленнее использование регулярных выражений для substr?

Это полностью зависит от того, насколько сложны ваши регулярные выражения. Как сказал @Pieter, если вы ищете одну строку, String.Contains, вероятно, будет быстрее. Вы также можете рассмотреть возможность использования String.IndexOfAny, если вы ищете константные строки. Регулярные выражения не нужны, если только вы не ищете шаблоны, которые не могут быть представлены в виде строк-констант.

Будет ли .NET значительно медленнее, чем другие языки?

В приложениях, интенсивно использующих процессор, .NET может работать медленнее, чем собственные приложения. Иногда. Если да, то обычно она находится в диапазоне от 5 до 20 процентов, а чаще всего от 7 до 12 процентов. Это просто код, выполняемый изолированно. Вы должны учитывать и другие факторы, например, сколько времени у вас уходит на создание программы на другом языке и насколько сложно обмениваться данными между родным приложением и остальной частью вашей системы.

person Jim Mischel    schedule 06.11.2010
comment
Ваши расчеты предполагают идеальное распределение по времени. Во многих сценариях его нагрузка может быть вдвое или более в часы пик. (что по-прежнему может не занимать много времени на обработку, но нет причин заниматься математикой, когда у вас есть только 1/10 требуемой статистики для фактического решения проблемы/сообщения ему, нужно ли ему покупать больше серверов :). - person Merlyn Morgan-Graham; 06.11.2010
comment
@Merlyn: Да, я проигнорировал пики. Я также переоценил суточную нагрузку. Кроме того, не было никакого упоминания о том, что это должно быть в реальном времени. Я интерпретировал вопрос как то, как мне не отставать от нагрузки? и мой ответ отражает это. Да, в периоды пиковой нагрузки в очереди могут оставаться предметы. Но это почти всегда так, если только вы не проектируете систему для пиковых нагрузок, а это означает, что у вас простаивает оборудование в непиковое время. - person Jim Mischel; 08.11.2010
comment
Истинный. Все зависит от того, каковы его реальные потребности. Как можно быстрее показывает, что ему нужно хорошее время отклика или, по крайней мере, хорошее время обработки, но это также показывает, что он не знает, на что ему нужно обратить внимание, чтобы гарантировать какой-либо конкретный уровень обслуживания. Я думаю, что предоставление математики вместо данных, которые у него есть сейчас, может дать ему ложное чувство безопасности, что он должным образом изучил свои требования и будет им соответствовать. Кстати, я также думаю о сетевой службе. Его приложение может не отражать этого, и в этом случае могут подойти простые показатели производительности. - person Merlyn Morgan-Graham; 08.11.2010

arrow_upward
0
arrow_downward

Google недавно объявил о своем внутреннем языке обработки текста (который выглядит как подмножество Python/Perl, предназначенное для интенсивной параллельной обработки).

http://code.google.com/p/szl/ — Sawzall.

person kagali-san    schedule 06.11.2010

arrow_upward
0
arrow_downward

Если вы хотите быстро анализировать строки на C#, возможно, вам стоит взглянуть на новый проект NLib. . Он содержит расширения строк для облегчения быстрого поиска строк различными способами. Например, IndexOfAny(string[]) и IndexOfNotAny. Они также содержат перегрузки с аргументом StringComparison.

person drifter    schedule 16.11.2010