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

Question

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

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

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

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

Answer 1

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

Answer 2

Рекомендации по эффективной работе со строками в Haskell в основном: Используйте Data.ByteString / Data.ByteString.Lazy.

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

---

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

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

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

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

Answer 3

Ответ немного сложнее, чем просто «использовать ленивые строки».

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

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

Answer 4

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

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

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

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

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