Bytestring: тот же String, но быстрее

Список – полезная и удобная структура данных. Мы использовали списки почти что везде. Существует очень много функций, рабо- тающих со списками, и ленивость языка Haskell позволяет нам заменить циклы типа for и while из других языков программиро- вания на фильтрацию и отображение списков, потому что вычис- ление произойдёт только тогда, когда оно действительно понадо- бится. Вот почему такие вещи, как бесконечные списки (и даже

 

бесконечные списки бесконечных списков!) для нас не проблема. По той же причине списки могут быть использованы в качестве потоков, читаем ли мы со стандартного ввода или из файла. Мы можем открыть файл и считать его как строку, но на самом деле обращение к файлу будет происходить только по мере необходи- мости.

Тем не менее обработка файлов как строк имеет один недоста- ток: она может оказаться медленной. Как вы знаете, тип String – это просто синоним для типа [Char]. У символов нет фиксированного размера, так как для представле-

ния, скажем, символа в кодировке Unicode может потребоваться не- сколько байтов. Более того, спи- сок – ленивая структура. Если у вас есть, например, список [1,2,3,4], он будет вычислен только тогда, когда это необходимо. На самом деле список, в некотором смыс- ле, – это обещание списка. Вспом- ним, что[1,2,3,4]– этовсеголишь синтаксический сахар для записи 1:2:3:4:[]. Когда мы принудитель- но выполняем вычисление перво- го элемента списка (например, выводим его на экран), остаток списка 2:3:4:[] также представля-

ет собой «обещание списка», и т. д. Список всего лишь обещает, что следующий элемент будет вычислен, как только он действительно понадобится, причём вместе с элементом будет создано обещание следующего элемента. Не нужно прилагать больших умственных усилий, чтобы понять, что обработка простого списка чисел как серии обещаний – не самая эффективная вещь на свете!

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

 

Строгие и ленивые

Байтовые строки бывают двух видов: строгие и ленивые. Строгие бай- товые строки объявлены в модуле Data.ByteString, и они полностью не ленивые. Не используется никаких «обещаний», строгая строка байтов представляет собой последовательность байтов в массиве. Подобная строка не может быть бесконечной. Если вы вычисляете первый байт из строгой строки, вы должны вычислить её целиком. Положительный момент – меньше накладных расходов, поскольку не используются «обещания». Отрицательный момент – такие стро- ки заполнят память быстрее, так как они считываются целиком. Второй вид байтовых строк определён в модуле Data.ByteString.

Lazy. Они ленивы – но не настолько, как списки. Как мы говорили ранее, в списке столько же «обещаний», сколько элементов. Вот по- чему это может сделать его медленным для некоторых целей. Лени- вые строки байтов применяют другой подход: они хранятся блока- ми размером 64 Кб. Если вы вычисляете байт в ленивой байтовой строке (печатая или другим способом), то будут вычислены первые 64 Кб. После этого будет возращено обещание вычислить осталь- ные блоки. Ленивые байтовые строки похожи на список строгих байтовых строк размером 64 Кб. При обработке файла ленивыми байтовыми строками файл будет считываться блок за блоком. Это удобно, потому что не вызывает резкого увеличения потребления памяти, и 64 Кб, вероятно, влезет в L2 – кэш вашего процессора. Если вы посмотрите документацию на модуль Data.ByteString.

Lazy, то увидите множество функций с такими же именами, как и в модуле Data.List, только в сигнатурах функций будет указан тип ByteString вместо [a] и Word8 вместо a. Функции в этом модуле работают со значениями типа ByteString так же, как одноимённые функции – со списками. Поскольку имена совпадают, нам придёт- ся сделать уточнённый импорт в скрипте и затем загрузить этот скрипт в интерпретатор GHCi для того, чтобы поэкспериментиро- вать с типом ByteString.

import qualified Data.ByteString.Lazy as B import qualified Data.ByteString as S

Модуль B содержит ленивые строки байтов и функции, мо- дуль S – строгие. Главным образом мы будем использовать ленивую версию.

 

Функция pack имеет сигнатуру pack:: [Word8] –> ByteString. Это означает, что она принимает список байтов типа Word8 и возвра- щает значение типа ByteString. Можно думать, будто функция при- нимает ленивый список и делает его менее ленивым, так что он ленив только блоками по 64 Кб.

Что за тип Word8? Он похож на Int, но имеет значительно меньший диапазон, а именно 0 – 255. Тип представляет собой восьмибитовое число. Так же как и Int, он имеет экземпляр класса Num. Например, мы знаем, что число 5 полиморфно, а значит, оно может вести себя как любой числовой тип. В том числе – принимать тип Word8.

ghci> B.pack [99,97,110]

Chunk "can" Empty ghci> B.pack [98..120]

Chunk "bcdefghijklmnopqrstuvwx" Empty

Как можно видеть, Word8 не доставляет много хлопот, поскольку система типов определяет, что числа должны быть преобразованы к нему. Если вы попытаетесь использовать большое число, напри- мер 336, в качестве значения типа Word8, число будет взято по моду- лю 256, то есть сохранится 80.

Мы упаковали всего несколько значений в тип ByteString; они уместились в один блок. Значение Empty – это нечто вроде [] для списков.

Если нужно просмотреть байтовую строку байт за байтом, её нужно распаковать. Функция unpack обратна функции pack. Она принимает строку байтов и возвращает список байтов. Вот при- мер:

ghci> let by = B.pack [98,111,114,116] ghci> by

Chunk "bort" Empty ghci> B.unpack by [98,111,114,116]

Вы также можете преобразовывать байтовые строки из стро- гих в ленивые и наоборот. Функция fromChunks принимает список строгих строк и преобразует их в ленивую строку. Соответственно, функция toChunks принимает ленивую строку байтов и преобразует её в список строгих строк.

 

ghci> B.fromChunks [S.pack [40,41,42], S.pack [43,44,45], S.pack [46,47,48]] Chunk "()*" (Chunk "+,–" (Chunk "./0" Empty))

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

Аналог конструктора: для строк байтов называется cons. Он принимает байт и строку байтов и помещает байт в начало строки.

ghci> B.cons 85 $ B.pack [80,81,82,84] Chunk "U" (Chunk "PQRT" Empty)

Модули для работы со строками байтов содержат большое коли- чество функций, аналогичных функциям в модуле Data.List, включая следующие (но не ограничиваясь ими): head, tail, init, null, length, map, reverse, foldl, foldr, concat, takeWhile, filter и др.

Есть и функции, имя которых совпадает с именем функций из модуля System.IO, и работают они аналогично, только строки за- менены значениями типа ByteString. Например, функция readFile в модуле System.IO имеет тип

readFile:: FilePath –> IO String

а функция readFile из модулей для строк байтов имеет тип

readFile:: FilePath –> IO ByteString

ПРИМЕЧАНИЕ. Обратите внимание, что если вы используете строгие строки и выполняете чтение файла, он будет считан в па- мять целиком! При использовании ленивых байтовых строк файл будет читаться аккуратными порциями.