Низове

Публикувано сряда, 22 март 2017, 14:47

В тази статия ще разгледаме низовете в Elixir. Тъй като низовете представляват binary структури, ще е добре да прочетете статията Binaries преди тази. Всички операции свързани с 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:

iex> << 0b00110000 >>
"0"
iex> << 0b00110001 >>
"1"
iex> << 0b00110010 >>
"2"
iex> << 0b00110101 >>
"5"
iex> << 0b00111001 >>
"9"

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

iex> << 0b01000001 >>
"A"
iex> << 0b01011010 >>
"Z"

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

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

110XXXXX 10XXXXXX

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

iex> ?Ъ
1066

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

iex> Integer.to_string(1066, 2)
"10000101010"

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

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

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

iex> << 0b11010000, 0b10101010 >>
"Ъ"

И получихме низа - "Ъ".

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

1110XXXX 10XXXXXX 10XXXXXX

А шаблонът за 4-байтовите:

11110XXX 10XXXXXX 10XXXXXX 10XXXXXX

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

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

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

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

Графеми и codepoint-и

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

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

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

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

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

iex> name1 = "Николай"
"Николай"
iex> name2 = "Николаи\u0306"
"Николай"
iex> name1 == name2
false
iex> String.equivalent?(name1, name2)
true

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

Също е добре да знаем че функции като String.reverse/1, работят правилно, защото ползват String.graphemes/1:

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

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

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

iex> Kernel.bit_size "Николаи\u0306"
128
iex> Kernel.byte_size "Николаи\u0306"
16
iex> String.length "Николаи\u0306"
7

Всичко изглежда да работи правилно.

Под-низове

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

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

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

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

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

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

Между другото, това също работи:

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

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

iex> String.next_codepoint("Николаи\u0306")
{"Н", "иколай"}
iex> String.next_codepoint("и\u0306")
{"и", "<нещо което скапва hilighting-a на кода>"}
iex> String.next_grapheme("и\u0306")
{"й", ""}
iex> String.next_grapheme_size("и\u0306")
{4, ""}
iex> 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 = """
  Ще строим завод,
  огромен завод,
  със яки
        бетонни стени!
  Мъже и жени,
  народ,
  ще строим завод
  за живота!
"""

iex> large_factory = String.slice(poem, 18..30)
"огромен завод"
iex> 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, ако не е продължаваме - накрая върщаме n. Решението работи. Но за големи низове се усеща забавяне. Ние го тествахме с низ с дължина 2_299_688:

iex> :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

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

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

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

Разбира се можем да имплементираме същото това поведение с binary patternt 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 модула има още доста различни функции, които можете да прегледате тук. В следващите статии от серията ‘Модули и структури от данни’ ще разгледаме други конструкции в езика - протоколи, речници, списъци и потоци.