Многие «знают», что программирование на C/C++ позволяет получить программы, которые работают почти так же быстро, как программы, написанные на языке Assembler, а уж те, в свою очередь, быстры настолько, насколько это вообще возможно в теории.

На самом деле, конечно, это не совсем так (а в редких случаях — и совсем не так), но в целом программы на C/C++ действительно быстры, требуют немного памяти и запускаются мгновенно. Если их правильно написать.

Вот о том как правильно писать на C/C++ я и хотел бы немного поговорить. Сегодня я хочу обсудить вопрос о наборах строк. То есть о процедурах, позволяющих из числа получить строку, а из строки — число.

Где подобные списки встречаются? Ну, например, это могут быть списки токенов html, с которыми работает ваша программа. Или список команд, которые принимает ваш командный интерпретатор. Но, конечно, наиболее часто такие наборы возникают как списки всевозможных ошибок: strerror, gai_strerror, regerror и т.д. Думаю каждый программист встречался с подобной задачей хотя бы раз.

Хочу оговориться что дальнейшее описание впрямую применимо только к операционным системам, использующим формат ELF: Linux, MacOS, etc. В Windows или встраиваемых системах ситуация может быть слегка иной. Плюс я в этот раз ограничусь только прямой задачей (по числу получить строку) ибо она во-первых проще, а во-вторых многие решения обратной задачи содержат в себе прямую задачу как часть решения.

Поскольку число положительных отзывов превысило число отрицательных, продолжу выкладывание уроков. Те кто уже знаком с основами — можете или просто пропустить урок, или попробовать сделать задание 3 самым коротким способом :)

Для начала маленькое замечание.

Начиная с Python 2.3, всем, кто использует не-ASCII кодировку нужно добавлять указание о кодировке в самом начале программы. Для русского языка это будет в основном:

# -*- coding: cp1251 -*-

или использовать для хранения исходных текстов файлы utf-8 (что предпочтительней).

Изучив управление числами, пришла пора осваивать строки. Пайтон обладает весьма богатым набором возможностей в этой области.

Строки

Продолжаю своё начинание. Данная статья является логическим продолжением первой. Было приятно читать ваши комментарии. Я надеялся, что данный цикл статей окажется для кого-то полезным, но совершенно не предполагал, что заинтересовавшихся будет довольно большое количество. Это заставляет относится к делу серьёзнее и ответственнее.
Без лишних слов, сразу к делу.

По просьбам трудящихся выкладываю описание и доказательство алгоритма Укконена.

Описание задачи

Требуется построить суффиксное дерево для данной строки за разумное время. Суффиксное дерево — это бор, состоящий из всех суффиксов данной строки. Если в кратце, бор — подвешенное дерево с символами на ребрах, реализация структуры данных для хранения строк. Строки получаются прохождением из корня по рёбрам, записывая соответствующие им символы, до терминальной вершины.

Бор для произвольного набора строк строится за O (суммы длин этих строк). Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки. Таким образом, построение суффиксного дерева тривиальным алгоритмом работает за O(N²). И тут возникает резонный вопрос, можно ли построить суффиксное дерево быстрее?

На самом деле можно.

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

Здравствуйте, уважаемое сообщество! Думаю, многим знакома такая структура данных как суффиксное дерево. На Хабре уже было описание как его построить и зачем. Если вкратце, то оно нужно тогда, когда надо много раз искать какие-то произвольные образцы X_i в заранее заданном тексте A, а строится такое дерево мучительно с помощью алгоритма Укконена (есть и другие варианты, но они предполагают еще большее количество страданий). Общее наблюдение при работе с алгоритмами таково, что деревья — это, конечно, хорошо, но на практике их лучше избегать из за серьезных оверхэдов по памяти и не очень оптимального (с точки зрения эффективности оперирования данными компьютером) расположения. Кроме того, именно в таком дереве есть еще более существенная неприятность, а именно алфавитнозависимость структуры. Для решения этих проблем был придуман суффиксный массив. О том как его строить и как использовать и пойдет в этой статье.

Материал статьи предполагает знание понятий суффикса и префикса строки, а также знание того, как работает бинарный поиск. Надо также представлять, что такое стабильная сортировка и поразрядная сортировка, а также понимание, что имеется ввиду под стабильной сортировкой подсчетом. Для некоторых частей нам понадобится знание задачи о минимуме на отрезке — Range Minimum Query (RMQ). Ну, в общем, вас предупредили: никто не говорил, что будет просто.

Не так давно на работе встала передо мной задача написать прогу в среде C++ Builder, и был в ней момент, когда нужно парсить командную строку. К задаче прилагалось так же волшебное «можешь юзать все исходники, которые есть. Лежат они тут: ...». Первым делом полез, конечно, по адресу… и нашел там жутко ветвящуюся структуру кода, в которой попытался разобраться и решил, что подгонять ее под себя – ад. Поэтому пришло мне в голову написать что-то подобное Qt-шной системе сигналов и слотов, только для C++ Builder’а и аргументов командной строки.
Итак, начнем. Идея такова: анализ командной строки сводится к проверке, есть ли в аргументе спецсимвол (в моем случае – это «-» – был взять стандарт Linux). В зависимости от этого аргумент читается как имя параметра или его значение. Для вызова функций обработки используется ассоциативный массив, т.е. массив в котором в качестве ключей будут имена доступных параметров, а значений – адреса функций обработки конкретного параметра. Вот, в общем-то, и все. Приступим к реализации?

Получилось так, что мне довелось оптимизировать код кластерной задачи, которая входила в состав Большого Кластерного Алгоритма и занималась весьма простой вещью: входной поток из n полей нужно было в зависимости от содержимого полей переразложить в выходной поток из m полей и почти успокоиться. Почти — потому что внутри полей были строчки произвольного вида, которые нужно было «очистить» — провести простейшую, казалось бы, операцию удаления всех управляющих символов из строки.

Оказалось, что эта операция совсем не такая «простейшая», как кажется, особенно если рассматривать её в современных языках с виртуальной машиной. Чуть ниже я покажу, как можно заменить решение в одну строчку на решение в пару десятков строчек, увеличив производительность алгоритма в ~10 раз. Сразу оговорюсь, что примеры будут относится к Java, но аналогичные рассуждения будут справедливы и для большинства других языков и виртуальных машин — в первую очередь, для .NET-based.

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

Здравствуй, хабр. Сегодня я напишу, как можно использовать полиномиальные хеши (далее просто хеши) при решении различных алгоритмических задач.

Введение

Начнем с определения. Пусть у нас есть строка s_0..n-1. Полиномиальным хешем этой строки называется число h = hash(s_0..n-1) = s₀ + ps₁ + p²s₂ +… + p^n-1s_n-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а s_i — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).

Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство.

Здравствуй, Хабр.
Большинство из нас так или иначе работает со строками. Этого не избежать — если ты пишешь код, ты обречен каждый день складывать строки, разбивать их на составные части и обращаться к отдельным символам по индексу. Мы давно привыкли что строки — это массивы символов фиксированной длины, а это влечет за собой соответствующие ограничения в работе с ними.
Так, мы не можем быстро объединить две строки — для этого нам потребуется сначала выделить необходимое количество памяти, а потом скопировать туда данные из конкатенируемых строк. Очевидно, что такая операция имеет сложность порядка О(n), где n — суммарная длина строк.
Именно поэтому код

string s = "";
for (int i = 0; i < 100000; i++) s += "a";

работает так медленно.

Хочешь выполнять конкатенацию гигантских строк быстро? Не нравится, что строка требует для хранения непрерывную область памяти? Надоело использовать буферы для построения строк?

Нередко случается, что какие-то данные программа загружает в память и оставляет их там надолго (а то и до конца работы) в неизменном виде. При этом используются структуры данных, оптимизированные как для чтения, так и для записи. Например, вы вычитываете из базы Ensembl список идентификаторов всех генов человека (включая всякие микроРНК и т. д. — всего чуть больше 50000). Если их прочитать в стандартный ArrayList, то на 32-битной HotSpot вы потратите чуть больше 4 мегабайт. Можно ли сэкономить память, зная, что коллекция больше не будет меняться?

Многие C++ программисты, пишущие под Windows часто путаются над этими странными идентификаторами как TCHAR, LPCTSTR. В этой статье я попытаюсь наилучшим способом расставить все точки над И. И рассеять туман сомнений.

В свое время я потратил много времени копаясь в исходниках и не понимал что значат эти загадочные TCHAR, WCHAR, LPSTR, LPWSTR,LPCTSTR.
Недавно нашел очень грамотную статью и представляю ее качественный перевод.
Статья рекомендуется тем кто бессонными ночами копошиться в кодах С++.

Вам интересно ??
Прошу под кат!!!

От переводчика: Джон Скит написал несколько статей о строках, и данная статья является первой, которую я решил перевести. Дальше планирую перевести статью о конкатенации строк, а потом — о Юникоде в .NET.

Тип System.String (в C# имеющий алиас string) является одним из наиболее часто используемых и важных типов в .NET, и вместе с тем одним из самых недопонимаемых. Эта статья описывает основы данного типа и развенчивает сложившиеся вокруг него мифы и непонимания.

Строковый тип данных является одним из самых важных в любом языке программировании. Вряд ли можно написать полезную программу не задействовав этот тип данных. При этом многие разработчики не знают некоторых нюансов связанных с этим типом. Поэтому давайте рассмотрим кое-какие особенности этого типа в .NET.

Итак, начнем с представления строк в памяти

В.NET строки располагаются согласно правилу BSTR (Basic string or binary string). Данный способ представления строковых данных используется в COM (слово basic от языка программирования VisualBasic, в котором он первоначально использовался). Как известно в C/C++ для представления строк используется PWSZ, что расшифровывается как Pointer to Wide-character String, Zero-terminated. При таком расположении в памяти в конце строки находится null-терминированный символ, по которому мы можем определить конец строки. Длина строки в PWSZ ограничена лишь объемом свободной памяти.

Вступление

Моя прошлая статья была посвящена особенностям строкового типа данных String в .NET. Эта статья продолжает традицию, однако на этот раз мы рассмотрим класс StringBuilder.

Как известно, строки в .NET являются неизменяемыми (не используя unsafe), а поэтому проводить с ними операцию конкатенации в больших количествах не самая лучшая идея. Это значит, что следующий код имеет весьма серьезные проблемы с нагрузкой на память:

string s = string.Empty;
for (int i = 0; i < 100; i++)
 {
    s += "T";
 }

Представим, что нам нужно что-нибудь сделать со строками в .net. Что-то не очень сложное, но и не совсем простое. Например, для правильного форматирования, расставить пробелы после запятых в тексте. Что же предлагает .net из коробки?
Что-то такое:

string str = "...";
str.Replace(",", ", ");

Постойте, но мы же хотели расставлять пробелы, а не заменять запятые!..

Постановка задачи

Совершенно случайно я превратился из питониста в JS-разработчика, и на мою хрупкую детскую психику обрушился непосильный груз вещей, которых в JS нет. Например, нет удобного форматирования строк. На питоне можно написать:

'hello, %(thing)s' % {'thing': 'world'}

Или вот так:

'hello, {thing}'.format(**{'thing': 'world'})

От переводчика. На Хабре уже неоднократно публиковались статьи как по Юникоду, так и по строкам в .NET. Однако статьи о Юникоде применительно к .NET ещё не было, поэтому я решил перевести статью общепризнанного гуру .NET Джона Скита. Она закрывает обещанный мною цикл из трёх статей-переводов Дж. Скита, посвящённых строкам в .NET. Как всегда, буду рад замечаниям и исправлениям.

Введение

Тема данной статьи довольно обширна, и не ждите от неё детального и глубокого разбора всех нюансов. Если вы полагаете, что достаточно хорошо разбираетесь в Юникоде, кодировках и т.д., эта статья может быть для вас почти или даже полностью бесполезной. Тем не менее, довольно много людей не понимают, чем различаются двоичные и текстовые данные (binary и text), или что такое кодировка символов. Именно для таких людей и написана данная статья. Несмотря на, в общем-то, поверхностное описание, в ней затрагиваются некоторые сложные моменты, однако это сделано скорее для того, чтобы читатель имел представление об их существовании, нежели чтобы дать детальные разъяснения и руководства к действию.

Вступление

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

Начальное описание

Алгоритм Ахо-Корасик реализует эффективный поиск всех вхождений всех строк-образцов в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем формально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — найти все возможные вхождения строк pattern[i] в s.

Суть алгоритма заключена в использование структуры данных — бора и построения по нему конечного детерминированного автомата. Важно помнить, что задача поиска подстроки в строки тривиально реализуется за квадратичное время, поэтому для эффективной работы важно, чтоб все части Ахо-Корасика ассимптотически не превосходили линию относительно длинны строк. Мы вернемся к оценке сложности в конце, а пока поближе посмотрим на составляющие алгоритма.