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

Question

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

Это может помочь u :-) http://bytes.com/topic/c/insights/660463-sizeof-empty-class-structure-1-a

Размер пустого класса или структуры равен 1

. Причина, по которой это происходит, сводится к правильной реализации стандарта, что говорит о том, что «ни один объект не должен иметь тот же адрес в памяти, как и любая другая переменная ".... Что является самым простым способом обеспечить это? Убедитесь, что все типы имеют ненулевой размер. Для этого компилятор добавляет фиктивный байт к структурам и классам, у которых нет элементов данных и нет виртуальных функций, поэтому они имеют размер 1, а не размер 0, и тогда у них гарантированно будет уникальный адрес памяти.
blockquote>

23

functional-programming haskell string

задан Rob Lachlan 23 February 2009 в 00:50

4 ответа

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

33

ответ дан porges 23 February 2009 в 00:50

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

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

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

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

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

6

ответ дан Curt J. Sampson 23 February 2009 в 00:50

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

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

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

7

ответ дан Paul Johnson 23 February 2009 в 10:50

1

That' s не литерал словаря, это должно быть NSDictionary *spec = @{(__bridge id)kSecClass: secItemClass}; – kevboh 26 April 2013 в 13:34

Другие вопросы по тегам:

functional-programming haskell string

Похожие вопросы:

That' s не литерал словаря, это должно быть NSDictionary *spec = @{(__bridge id)kSecClass: secItemClass}; — kevboh, 26 April 2013 в 13:34

score 30 · Accepted Answer

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

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

<час>

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

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

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

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