Рубрика «строки» - 2

И ещё о сортировках

Рискну опять поднять эту тему. Начну со ссылки на статью Михаила Опанасенко (oms7), очень впечатляющую по объёмам проделанной работы, а также по количеству приведёных ссылок. Свой материал начал готовить, не зная об этой публикации, что впоследствии, после ознакомления привело к необходимости его существенной переработки. Для тех, кто уже прочитал эту статью, сообщаю, что в моём материале, исследуются более разнообразные по типам данные, в частности, строки и вещественные числа, используются библиотеки boost и bsd, а также затрагиваются некоторые другие отсутствующие в названной статье темы.
Читать полностью »

В ClickHouse постоянно возникают задачи, связанные с обработкой строк. Например, поиск, вычисление свойств UTF-8 строк или что-то более экзотическое, будь то поиск типа учёта регистра или поиск по сжатым данным.

Всё началось с того, что руководитель разработки ClickHouse Лёша Миловидов o6CuFl2Q пришёл к нам на факультет компьютерных наук в НИУ ВШЭ и предложил огромное количество тем для курсовых и дипломов. Когда я увидел «Умные алгоритмы обработки строк в ClickHouse» (я, человек, который увлекается разными алгоритмами, в том числе экспериментальными), сразу же настроил планов, как сделаю самый крутой диплом. Мою радость и выражение лица можно описать следующей картинкой:

Умные алгоритмы обработки строк в ClickHouse - 1

Читать полностью »

И сотворил Гвидо строки по образу C, по образу массивов символов сотворил их. И увидел Гвидо, что это хорошо. Или нет?

Представьте, что вы пишете совершенно идиоматичный код по обходу неких данных с вложенностью. Beautiful is better than ugly, simple is better than complex, так что вы останавливаетесь на следующем варианте кода:

from collections.abc import Iterable

def traverse(list_or_value, callback):
    if isinstance(list_or_value, Iterable):
        for item in list_or_value:
            traverse(item, callback)
    else:
        callback(list_or_value)

Вы пишите юнит-тест, и что бы вы думали? Он не работает, причём не просто не работает, а

>>> traverse({"status": "ok"}, print)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in traverse
  File "<stdin>", line 4, in traverse
  File "<stdin>", line 4, in traverse
  [Previous line repeated 989 more times]
  File "<stdin>", line 2, in traverse
  File "/usr/local/opt/python/libexec/bin/../../Frameworks/Python.framework/Versions/3.7/lib/python3.7/abc.py", line 139, in __instancecheck__
    return _abc_instancecheck(cls, instance)
RecursionError: maximum recursion depth exceeded in comparison

Как? Почему? В поисках ответа вы погрузитесь в удивительный мир коллекций бесконечной глубины.
Читать полностью »

Задача сравнения похожих строк встречается на практике довольно часто: лично я недавно столкнулся с ней при попытке импорта почтовых адресов из одной программы в другую.

Например, один адрес может выглядеть как «Тверская обл., Кашин г, Советская ул, 1, 5», а другой – как «Тверская область; город Кашин; улица Советская; дом 1; квартира 5». Похожи ли эти строки и насколько? Несомненно, похожи. И «невооруженным глазом» видна их структура: область – населенный пункт – улица – дом – квартира. Логично, что для адресов важно такое разбиение строк на группы; то есть сравнивать мы должны не «две каши» из сходных слов (где одна «каша» состоит из слов первой строки, а вторая – из слов второй), а именно осуществлять «погруппное» сравнение слов из первой строки со словами из второй. Просматривается и критерий разбиения на группы: в первой строке разделителем групп является «, », а во второй – «; ».
Читать полностью »

Гравюра М. Эшера &quot;Вавилонская башня&quot;

Гравюра М. Эшера «Вавилонская башня», 1928

Введение

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

Спустя четыре тысячи лет после Вавилонского столпотворения технологии предлагают нам несколько замечательных инструментов. Что же у нас есть?

Во-первых, сборная солянка — абстракция локали (locale). Локаль включает не только язык, но еще и письменность, календарь, правила форматирования чисел, денежных единиц, дат и пр.

Во-вторых, Юникод. Юникод — это не просто таблица кодирования символов. Это еще и различные формы одних и тех же букв, диакритические знаки, порядок сортировки символов, правила изменения регистра, алгоритмы нормализации строк, семейство кодировок UTF и многое другое.

Все это большое подспорье. Такие возможности, как правило, уже встроены в операционные системы и доступны в стандартных библиотеках. Программисты и пользователи во всех уголках планеты благополучно применяют одни и те же операционные системы, средства разработки, базы данных. Читать полностью »

При работе с естественным языком и лингвистическом анализе текстов нам часто приходится оперировать огромным количеством уникальных коротких строк. Счёт идёт на десятки и сотни миллионов — именно столько в языке существует, к примеру, осмысленных сочетаний из двух слов. Основной платформой для нас является Java и мы не понаслышке знаем о её прожорливости при работе с таким большим количеством мелких объектов.

Чтобы оценить масштаб бедствия, мы решили провести простой эксперимент — создать 100 миллионов пустых строк в Яве и посмотреть, сколько придётся заплатить за них оперативной памяти.Читать полностью »

Часто бывает, что мы соединяем 2 коллекции или группируем коллекцию при помощи LINQ to Objects. При этом происходит сравнение ключей, выбранных для группировки или связывания.
К счастью, стоимость этих операций равна O(n). Но в случае больших коллекций нам важна эффективность самого сравнения. Если в качестве ключей выбраны строки, то какая из реализаций сравнения будет использована по умолчанию, подходит ли эта реализация для ваших строк и можно ли, указав IEqualityComparer<string> явно, сделать эту операцию быстрее?

clients.Join(orders, 
                   c => c.Name, 
                   o => o.ClientName, 
                   (c, o) => CreateOrederDto(c, o));

Как же выбирается реализация компаратора, если пользователь не указал её явно?
Читать полностью »

От переводчика

КДПВ Это последняя статья из цикла про работу со строками и памятью в Rust от Herman Radtke, которую я перевожу. Мне она показалась наиболее полезной, и изначально я хотел начать перевод с неё, но потом мне показалось, что остальные статьи в серии тоже нужны, для создания контекста и введения в более простые, но очень важные, моменты языка, без которых эта статья теряет свою полезность.


Мы узнали как создать функцию, которая принимает String или &str (англ.) в качестве аргумента. Теперь я хочу показать вам как создать функцию, которая возвращает String или &str. Ещё я хочу обсудить, почему нам это может понадобиться.
Читать полностью »

КДПВ
Этот пост посвящается всем тем, кого смущает необходимость использовать to_string(), чтобы заставить программы компилироваться. И я надеюсь пролить немного света на вопрос о том, почему в Rust два строковых типа String и &str.
Читать полностью »

image
(здесь должна быть картинка со строками, наверное)

RCString– это мини-контейнер для хранения 0-терминированных С-строк.
Сегодня для меня маленький праздник, т.к. число строк в RCString.c стало 533, т.е. это побило мой рекорд с RArray в 491 строку. Теперь RCString.c самый длинный файл в foundation.
Далее лирика (и исходники конечно же) о том, что я хотел сделать, и что я сделал.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js