Эффективная реализация строк в Haskell

В настоящее время я преподаю себе Haskell, и мне интересно, какие лучшие практики при работе со строками в Haskell.

Строковая реализация по умолчанию в Haskell представляет собой список Char. Это неэффективно для ввода-вывода файлов, в соответствии с Real World Haskell, поскольку каждый символ выделен отдельно (я предполагаю, что это означает, что строка в основном связанный список в Haskell, но я не уверен.)

Но если стандартная реализация строки неэффективна для файлового ввода/вывода, также ли она неэффективна для работы со строками в памяти? Почему или почему нет? C использует массив char для представления String, и я предположил, что это будет по умолчанию способ делать вещи на большинстве языков.

Как я вижу, реализация списка String будет занимать больше памяти, так как каждому персонажу потребуются дополнительные накладные расходы, а также больше времени для повторения, поскольку для последующего Char потребуется разыменование указателя. Но мне до сих пор нравилось играть с Haskell, поэтому я хочу поверить, что реализация по умолчанию эффективна.

Ответ 1

Лучшие практики для работы с строками в Haskell в основном: используйте Data.ByteString/Data.ByteString.Lazy.

http://hackage.haskell.org/packages/archive/bytestring/latest/doc/html/

Насколько эффективна реализация строки по умолчанию в Haskell, это не так. Каждый Char представляет кодировку Unicode, что означает, что ей требуется не менее 21 бит на Char.

Так как a String является просто [Char], то есть связанным списком Char, это означает, что String имеет плохую локальность ссылки и снова означает, что String достаточно велики в памяти, при минимум N * (21bits + Mbits), где N - длина строки, а M - размер указателя (32, 64, что у вас), и в отличие от многих других мест, где Haskell использует списки, в которых другие языки могут использовать разные структуры (я мышление конкретно о потоке управления здесь), String гораздо реже могут быть оптимизированы для циклов и т.д. компилятором.

И хотя a Char соответствует кодовому центру, отчет Haskell 98 ничего не указывает на кодировку, используемую при выполнении ввода файла IO, даже не по умолчанию, а гораздо меньше способ изменить его. На практике GHC предоставляет расширения, например, бинарный IO, но вы все равно уходите от резервирования.

Даже при таких операциях, как добавление к фронту строки, маловероятно, что String будет бить ByteString на практике.

Ответ 2

Помимо String/ByteString, теперь есть библиотека Text, которая сочетает в себе лучшее из обоих миров - она работает с Unicode, будучи ByteString основанный на внутреннем уровне, поэтому вы получаете быстрые, правильные строки.

Ответ 3

Ответ немного сложнее, чем просто "использовать ленивые байты".

Строки байтов хранят только 8 бит на каждое значение, тогда как строка содержит реальные символы Юникода. Поэтому, если вы хотите работать с Unicode, вам нужно постоянно конвертировать в UTF-8 или UTF-16, что является более дорогостоящим, чем просто использование строк. Не делайте ошибку, предполагая, что вашей программе будет нужен только ASCII. Если только его код не выбрасывается, то в один прекрасный день кому-то нужно будет ввести символ евро (U + 20AC) или акцентированные символы, и ваша хорошая быстрая реализация bytestring будет безвозвратно нарушена.
Байт-строки делают некоторые вещи, например, добавление к началу строки, более дорогим.

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

Ответ 4

Основной ответ, используемый ByteString, правильный. Тем не менее, все три ответа до моего имеют неточности.

Относительно UTF-8: будет ли это проблемой или нет, полностью зависит от того, какую обработку вы выполняете со своими строками. Если вы просто рассматриваете их как единичные фрагменты данных (включая операции, такие как конкатенация, хотя и не разделение), или выполняете определенные операции с ограниченным байтом (например, находите длину строки в байтах, а не длину в символы), у вас не будет проблем. Если вы используете I18N, есть и другие проблемы, которые просто используют String, а не ByteString начнут исправлять лишь некоторые из проблем, с которыми вы столкнетесь.

Превращение одиночных байтов в начало ByteString, вероятно, дороже, чем для String. Однако, если вы делаете много этого, возможно, вы сможете найти способы решения вашей конкретной проблемы, которые дешевле.

Но конечный результат был бы для плаката оригинального вопроса: да, строки в Haskell неэффективны, хотя и весьма удобны. Если вы беспокоитесь об эффективности, используйте ByteStrings и рассматривайте их как массивы Char8 или Word8, в зависимости от вашей цели (ASCII/ISO-8859-1 или Unicode какого-либо типа или просто произвольные двоичные данные). Как правило, используйте Lazy ByteStrings (где добавление к началу строки на самом деле очень быстрая операция), если вы не знаете, почему вам нужны не-ленивые (которые обычно завершаются в оценке аспектов производительности ленивой оценки).

Для чего это стоит, я полностью создаю автоматизированную торговую систему в Haskell, и одна из вещей, которую нам нужно сделать, - очень быстро разобрать подачу рыночных данных, которую мы получаем по сетевому соединению. Я могу обрабатывать чтение и разбор 300 сообщений в секунду с пренебрежимым количеством CPU; что касается обработки этих данных, GHC-скомпилированный Haskell выполняет достаточно близко к C, что он нигде не входит в мой список заметных проблем.