Курс по Elixir

Низове

от meddle

В тази публикация ще разгледаме низовете в Elixir. Тъй като низовете представляват двоични структури, ще е добре да прочетете първо за тях. Всички операции, свързани с binaries, които разгледахме, могат да бъдат приложени и върху стрингове.

Низовете в Elixir използват unicode. Това значи, че както казахме, представляват binary структури, които са поредица от unicode codepoint-и в utf8 енкодинг.

Какво е Unicode

Unicode е начин на представяне на символи. Свързан е донякъде с ASCII. При ASCII всяко от числата от 0 до 127 отговаря на определен символ. Тези числа, отговарящи на символи, наричаме codepoint-и. Ако решим да съхраняваме ASCII codepoint-ите в един байт, ще използваме само 7 бита, слагайки една 0 отпред.

При ASCII имаме codepoint-и само за букви на латиница, за цифри и за различни символи, които можем (или не) да намерим на клавиатурите си.

Къде е кирилицата? А гръцката азбука, от която се нуждаем толкова много, когато пишем математически формули? Къде е кси (ξ), както и да се пише наистина? На практика има различки енкодинги като CP-1252, които допълват с нещо основните 128 кодпойнта до 1 байт; те са много на брой, но с ограничени възможности.

Това, което unicode предлага, са codepoint-и за огромен набор от символи, включващи както кирилицата, така и гръцката азбука, също множество канджи (йероглифи) и символи, които могат да се обединят в йероглифи. Включва и странни неща като карти за игра, емотикони и алхимични символи…

На теория Unicode включва символи за всичко изразимо на който и да е човешки език. Теорията има изключения, но работи в огромен процент от случаите.

И Unicode е като ASCII, дефинира числа, съответстващи на символи – огромен брой codepoint-и. Разбира се, тези числа трябва да се съхраняват по някакъв начин. Тъй като се съхраняват на компютър, те ще се представят като поредици от нули и единици. Как точно се съхраняват зависи от енкодинга, който се ползва. Има много енкодинги, да речем, utf-32 използва по 4 байта за всеки codepoint, което не е оптимално. В Elixir низовете се пазят в unicode utf-8 енкодинг.

UTF-8

При UTF-8 даден codepoint може да се съхранява в от един до четири байта (на практика е възможно и в повече). Първите 128 кодпойнта съвпадат с ASCII codepoint-ите. Te се пазят в един байт, който започва с 0:

0XXXXXXX

Има специфики защо даден номер съответства на даден символ при тези първи 128 символа. Да речем, цифрите винаги имат префикс от 4 бита – 0011:

<< 0b0011_0000 >>
#=> "0"
<< 0b0011_0001 >>
#=> "1"
<< 0b0011_0010 >>
#=> "2"
<< 0b0011_0101 >>
#=> "5"
<< 0b0011_1001 >>
#=> "9"

Главните букви на латиница започват след 0b01000000, тоест имат префикс 010:

<< 0b010_00001 >>
#=> "A"
<< 0b010_11010 >>
#=> "Z"

Малките букви са след 0b01100000, което значи, че ако добавим 100000 (32) към главна буква, получаваме малка.

След като 128-е възможности за 1 байт се изчерпат, започват да се ползват по 2 байта:

110XXXXX 10XXXXXX

В този шаблон за двубайтови codepoint-и виждаме, че първият байт винаги започва с 110. Двете единици значат два байта. Байт, започващ с 10, е част от поредица от байтове. Тъй като в този порядък се пазят буквите от кирилицата, нека разгледаме какво представлява една от тях:

?Ъ
#=> 1066

Така с въпросителен знак пред символ можем да видим codepoint-а на символа. Нека да видим какво представлява 1066 в двоична бройна система:

Integer.to_string(1066, 2)
#=> "10000101010"

За целта ползваме Integer.to_string/2, която взима за втори аргумент база. Ще пробваме да вкараме числото 10000101010 в шаблона на utf8 за два байта:

(110)10000 -> Префиксваме със 110 и допълваме до байт с битовете от числото.
(10)101010 -> Префиксваме с 10 и допълваме до байт с битовете, които останаха.

От горното следва, че Ъ се пази като 11010000 10101010. Нека сложим тези два байта в binary:

<< 0b110_10000, 0b10_101010 >>
#=> "Ъ"

Така получаваме низа "Ъ".

Шаблонът за трибайтови codepoint-и е:

1110XXXX 10XXXXXX 10XXXXXX

А шаблонът за четирибайтовите:

11110XXX 10XXXXXX 10XXXXXX 10XXXXXX

Както виждате, броят на единиците, с които започва началния байт, определя колко байта е общо codepoint-ът.

Можем да заключим, че има три типа байтове:

1. Единичен – започва с 0 и представлява първите 128 ASCII-compatible codepoint-и.
2. Байт-продължение – започва с 10 и следва други байтове в codepoint от повече от 1 байт.
3. Байт-начало – започва с 110, 1110, 11110, първи байт от серия байтове, представляващи codepoint.

Интересно е, че при буквите в кирилицата първият байт е винаги 208 (11010000). Главните започват от втори байт 144 (10010000), a малките от 176 (10110000). Разликата между главните и малките букви отново е 32 (100000).

Графеми и codepoint-и

Символите или графемите невинаги са точно един codepoint. Има графеми, които могат да се представят и от един codepoint, и от няколко. Такъв случай е например комбинация с диакритични знаци. Нека разгледаме следния код:

name = "Николай"
#=> "Николай"

String.codepoints(name)
#=> ["Н", "и", "к", "о", "л", "а", "й"]
String.graphemes(name)
#=> ["Н", "и", "к", "о", "л", "а", "й"]
String.graphemes(name) == String.codepoints(name)
#=> true

Започваме да използваме String модула. Той ни дава две функции за превръщането на низ в списък от графеми или codepoint-и, които връщат напълно еднакви списъци. Тогава защо имаме две функции? Кога ще са различни?

name = "Николаи\u0306"
#=> "Николай"

String.codepoints(name)
#=> ["Н", "и", "к", "о", "л", "а", "и", ̆"<не може да се представи>"]
String.graphemes(name)
#=> ["Н", "и", "к", "о", "л", "а", "й"]

Това пак е името ‘Николай’, но графемата ‘й’ е съставена от два codepoint-а – и и диакритичен знак.

name1 = "Николай"
#=> "Николай"
name2 = "Николаи\u0306"
#=> "Николай"

name1 == name2
#=> false
String.equivalent?(name1, name2)
#=> true

Такa написани, стрингове могат да се сравняват със String.equivalent?/2, ако ни интересуват само графемите в тях, a не как са представени.

Функции като String.reverse/1 работят правилно, защото ползват String.graphemes/1:

String.reverse(name2)
#=> "йалокиН"

# Аналогично:
String.graphemes(name2) |> Enum.reverse |> Enum.join("")
#=> "йалокиН"

Дължина на низ

Тъй като стринговете са binary, можем да използваме функциите от Kernel – Kernel.byte_size/1 и Kernel.bit_size/1. Те няма да ни върнат броя на графемите, но са бързи операции O(1). String.length/1 ще ни върне броя на графемите и за да го направи, трябва да мине през всички байтове, да ги групира в codepoint-и, а тях да групира в графеми. Това е линейна O(N) операция:

Kernel.bit_size("Николаи\u0306")
#=> 128
Kernel.byte_size("Николаи\u0306")
#=> 16

String.length("Николаи\u0306")
#=> 7

Поднизове

Има доста функции за взимане на подниз от низ. Ако искате кодът ви да бъде оптимален, когато работите с низове, съставени от първите 128 codepoint-а, използвайте binary pattern matching или binary функции за обхождане. Те са по-бързи и по този начин могат да се преизползват matching context-и.

Нека да видим как да вземем символ на дадена позиция:

String.at("Искам бира!", 6)
#=> "б"
String.at("Искам бира!", -1)
#=> "!"
String.at("Искам бира!", 12)
#=> nil

Както виждате, можем да използваме отрицателни индекси, за да започнем от края. Ако индексът е невалиден, получаваме атома nil. Ако искаме да вземем 6-ия символ с pattern matching, ще трябва да напишем нещо такова:

<< _::binary-size(11), x::utf8, _::binary >> = "Искам бира!"
#=> "Искам бира!"

x
#=> 1073
<< x::utf8 >>
#=> "б"

Знаем това по-горе, защото имаме 5 символа от по 2 байта и един – шпацията – от 1 байт, затова пропускаме първите 11 байта. Добре е да работим с binary pattern matching само когато сме сигурни какво съдържа стрингът.

Това също работи:

<< "Искам ", x::utf8, _::binary >> = "Искам бира!"
#=> "Искам бира!"

Други интересни функции:

String.next_codepoint("Николаи\u0306")
#=> {"Н", "иколай"}
String.next_codepoint("и\u0306")
#=> {"и", "<нещо което скапва hilighting-a на кода>"}

String.next_grapheme("и\u0306")
#=> {"й", ""}

String.next_grapheme_size("и\u0306")
#=> {4, ""}
String.next_grapheme_size("\u0306")
#=> {2, ""}

Горните функции връщат наредени двойки. String.next_codepoint/1 връща tuple с първи елемент – първия codepoint на низа,и с втори елемент – остатъка. Ако низът е празен, резултатът ще е атомът nil. String.next_grapheme/1 се справя по-добре с комбинирани codepoint-и, но иначе има подобно поведение. Просто работи с графеми. Третата функция от примера – String.next_grapheme_size/1 – е по-интересна, защото връща големината на следващата графема в байтове. Тъй като й е съставено от два codepoint-a от по два байта – имаме 4 байта. Само по себе си ‘краткото’ е 2 байта.

Има две функции за взимане на парче от низ – String.slice/2 и String.slice/3:

poem = """
  Ще строим завод,
  огромен завод,
  със яки
        бетонни стени!
  Мъже и жени,
  народ,
  ще строим завод
  за живота!
"""

large_factory = String.slice(poem, 18..30)
#=> "огромен завод"
String.slice(poem, 18, 13)
#=> "огромен завод"

Едната взима отрязък по range от индекс до индекс, а другата – от индекс с дължина.

Обхождане на низове

Нека обходим низ и преброим срещането на буквата ‘a’ в него.

defmodule ACounter do
  def count_it_with_slice(str) do
    count_with_slice(str, 0)
  end

  defp count_with_slice("", n), do: n
  defp count_with_slice(str, n) do
    the_next_n = next_n(String.starts_with?(str, "a"), n)
    count_with_slice(String.slice(str, 1..-1), the_next_n)
  end

  defp next_n(true, n), do: n + 1
  defp next_n(false, n), do: n
end

Използваме String.starts_with?/2 за проверка на текущия първи символ в низа. Ако е "a", увеличаваме n. Ако не е "a", продължаваме. Накрая връщаме n. Решението работи, но за големи низове се усеща забавяне. Ние го тествахме с низ с дължина 3_000_000+:

:timer.tc(ACounter, :count_it_with_slice, [str])
#=> {3176592, 589251}

Това е около 3.18 секунди, което за едно просто обхождане на низ е доста бавно, даже за низ с такава дължина. Тук забавянето се получава от това, че на всяка итерация String.slice/2 създава ново sub-binary, a за него се създава нов match context, когато използваме String.starts_with?/2. Ще е по-добре, ако в възможно match context-а да бъде преизползван.

Вътрешно String.next_grapheme/1 ползва binary_part (:binary.part), която е достатъчно умна функция, за да запазва match context-a и да отлага създаването на sub-binaries. Нека да пробваме имплементация с тази функция:

defmodule ACounter do
  def count_it_with_next_grapheme(str) do
    count_with_next_grapheme(str, 0)
  end

  defp count_with_next_grapheme("", n), do: n
  defp count_with_next_grapheme(str, n) do
    {next_grapheme, rest} = String.next_grapheme(str)
    count_with_next_grapheme(rest, next_n(next_grapheme == "a", n))
  end

  defp next_n(true, n), do: n + 1
  defp next_n(false, n), do: n
end

Да видим сега:

:timer.tc(ACounter, :count_it_with_next_grapheme, [str])
#=> {792885, 589251}

Същият резултат, но сега за 0.8 секунди. Около 4 пъти по-бърза имплементация! Ако сме сигурни, че няма да имаме обединени codepoint-и, можем да заменим next_grapheme с next_codepoint. В този случай ще получим леко по-бързо поведение – около 0.5 секунди.

Можем да имплементираме същото това поведение с binary pattern matching:

defmodule ACounter do
  def count_it_with_match(str) do
    count_with_match(str, 0)
  end

  defp count_with_match("", n), do: n

  defp count_with_match(<< c::utf8, rest::binary >>, n) when c == ?a do
    count_with_match(rest, n + 1)
  end

  defp count_with_match(<< _::utf8, rest::binary >>, n) do
    count_with_match(rest, n)
  end
end

Тази имплементация със същия низ отнема около 0.1 секунди.

Изводът от горните няколко примера е, че както винаги, ако можем да ползваме pattern matching, задължително трябва да се възползваме от това. Сравнението, както и разделянето на низа със съпоставяне са много бързи.

Тази и миналата публикации наблегнаха на това как са имплементирани низовете в Elixir. Показахме ви уловки, които можете да избегнете, както и различни операции. В String модула има още доста функции, които можете да разгледате тук.

Ще се върнем на представянето на низове в паметта още веднъж, когато говорим за работа с процеси и уловки при garbage collection-а на процесите и на общата binary памет.