MSLibrary. ПРОСТО: удаляем из строки ненужные символы, используя регулярные выражения, для iOS и не только…

[mwizard]

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

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

[MSLibrary]

Спасибо за комментарий, Алексей! Не совсем с вами согласен.

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

Что касается "ужасно ресурсоемкого процесса", то я нигде не видел реальной статистики, сравнивающей использование регулярных выражений или, как вы выразились, "фильтров по таблице". Общепринято считать, что парсинг регулярного выражения относительно ресурсоемкий процесс. И здесь ключевые слова — "общепринято" и "относительно". Обычно когда "общепринято" — никто ни за что не отвечает. А что касается "относительно", то при работе с небольшими строками, а в данном случае чаще всего речь идет о небольших строках (логины, пароли, адреса и тд), а не романах объема "Войны и мира", вообще говорить о производительности довольно странное занятие.

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

[mwizard]

Самое простое решение может быть не самым удачным только в двух случаях

В теории разницы между теорией и практикой нет — а на практике есть. Вся проблема в т.н. «дырявых абстракциях» — большинство вещей устроено намного сложнее, чем позволяет предположить их внешний интерфейс. Примеров множество — конкатенация строк в цикле без использования StringBuilder-а, побайтовое копирование памяти, работа с сетевыми ФС как с локальными, перемещение файлов между границами разделов, «заторы» в TCP, использование регулярок без кэша, и т.д.

Насчет «статистики» — простите, а какого вида статистику вы ожидаете? Внутри NSRegularExpression не магия происходит — посмотрите исходники, почитайте, как в принципе работают регулярные выражения, и какой оверхед имеет компиляция регулярного выражения (токенизация, разбор в AST, генерация байткода и его последующее выполнение). То, что у вас речь не идет о романах объема «Войны и мира», только усугубляет ситуацию, т.к. на маленьких строках компиляция регулярок займет больше времени, чем непосредственно обработка.

Любопытства ради, проведите тест по производительности, и скажите, на каких начальных данных ваш код окажется быстрее?

Сниппет

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

typedef uint32_t ucs4_t;

#define DEFAULT_CAPACITY  16
#define CAPACITY_MULTIPLIER  125

ucs4_t *strip(const ucs4_t *restrict string, const ucs4_t *restrict chars) {
    ucs4_t single_ch = *chars++;

    if (!single_ch) { // no filter chars
        size_t size;
        {
            const ucs4_t *string_top = string;

            while (*string_top++) { };

            size = sizeof(ucs4_t) * (string_top - string);
        }

        ucs4_t *restrict result;
        if (!(result = malloc(size))) {
            return NULL;
        }

        memcpy(result, string, size);

        return result;
    }

    size_t size = DEFAULT_CAPACITY;
    ucs4_t *result_base, *result_top, *result;
    ucs4_t *_result_base;
    ucs4_t ch;

    bool single_mode = !*chars;
    uint64_t *bitmap = NULL;

    if (!single_mode) {
        if (!(bitmap = calloc(1, 0x110000 / sizeof(*bitmap)))) {
            return NULL;
        }

        chars--;
        while ((ch = *chars++)) {
            bitmap[ch / 64] |= 1 << (ch % 64);
        }
    }

    if (!(result_base = result = malloc(size))) {
        goto fail;
    }
    result_top = result_base + size;

    while ((ch = *string++)) {
        if (single_mode) {
            if (ch == single_ch) {
                continue;
            }
        } else {
            if (bitmap[ch / 64] & (1 << (ch % 64))) {
                continue;
            }
        }

        *result++ = ch;

        if (result == result_top) {
            size_t offset = size;

            size = 1 + size * CAPACITY_MULTIPLIER / 100;

            if (!(_result_base = realloc(result_base, size))) {
                goto fail;
            }
            result_base = _result_base;

            result_top = result_base + size;
            result = result_base + offset;
        }
    }

    *result = 0;
    if (!(_result_base = realloc(result_base, sizeof(ucs4_t) * (result - result_base + 1)))) {
        goto fail;
    }
    result_base = _result_base;

    return result_base;

fail:
    free(bitmap);
    free(result_base);
    return NULL;
}

// Пример вызова: ucs4_t *result = strip(U"zqHeqllzo, __qwzor_lzd!q_q", U"zq_");

Пользоваться моим кодом в результате не сложнее, чем вашим — прошу лишь извинить, что я не знаю ObjC и поэтому не могу привести NSString к массиву codepoint-ов самостоятельно.

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

А потом люди удивляются — как так выходит, что современные компы тупят, как в старые-добрые времена? Ну, зато программист время сэкономил. Ваш подход учит неопытных программистов плохому, и это грустно.

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

[MSLibrary]

Алексей, цель этой маленькой статьи — показать как ПРОСТО реалзовать удаление лишних символов из строки с помощью регулярных выражений. Это все. Цели показать ВСЕ варианты решения этой задачи мы не ставили, поскольку СЛОЖНО не всегда хорошо. Если бы статья описывала реализацию с использованием циклов, обязательно появился бы комментарий, что это не здорово, потому, что… и так далее. С вашими рассуждениями никто не спорит они имеют право на жизнь, так же как и многие другие. Если написать решение этой задачи в машинном коде, то, скорее всего, работать будет еще быстрее, но сам код разрастется до чудовищный размеров, несопоставимых с решаемой задачей.

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

Что касается библиотеки, то все действительно, решается одним вызовом. НО цель статьи не показать как пользоваться библиотекой, а совсем другая — как использовать регулярные выражения для удаления лишних символов. Эта задача решена.

[MSLibrary]

Алексей, небольшое дополнение. Было бы здорово, если бы вы написали небольшую статью с примером оптимальной с вашей точки зрения реализации. От этой статьи было бы больше пользы, чем от в общем-то пустых словопрений кто быстрее, кто экономичнее и тд. Спасибо.

[mwizard]

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

Писать статью для тривиального решения? Зачем? Максимальное значение кодепоинта юникода — 0x10FFFF, значит, битовая карта из 0x110000 бит покроет весь диапазон, а для хранения этой карты достаточно 17408 значений по 64 бита каждое. Проходимся по списку фильтруемых символов, заносим их в битовую карту. Проходим по строке, и если знак отсутствует в битовой карте, то дописываем его в конец результирующей строки. Если место в результирующей строке закончилось, то увеличиваем ее в 1.25 раз, а в конце отрезаем хвост по фактической длине, включая терминатор. Мое решение еще включает два частных случая — когда в списке фильтров нет ни одного символа вообще (строка просто копируется), и когда там один символ (можно обойтись без битовой карты). В принципе, можно еще было бы сократить потребление памяти, если сначала выделять битовую карту на 2⁸ бит, и увеличивать ее до 2¹⁶ бит при использовании соответствующих символов, и только затем поднимать до 2²¹ при выходе за пределы BMP.

К чему очередная мусорная статья "Как я писал Hello world", если подобное реализует любой начинающий программист?

[Krypt]

Зачем?
Быстрее и читабельнее пройтись циклом по символам строки.

[MSLibrary]

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

[Valle]

В этом случае это точно будет быстрее. Можете померять. И простой цикл, который оставляет только цифры будет для многих читабельней смайлика [:^digit:]

[Krypt]

Имхо, регекспы — переоцененный инструмент. Да, он неплохо решает определённый подкласс задач: например, поиск email в тексте, вычленение телефона номера из форматированной строки, etc. Но для него так же есть как слишком простые (поиск символов в подстроке), так и слишком сложные (парсинг файлов) задачи.

Конкретно тут в голову приходят несколько реализаций, которые будут не длиннее по коду и уж точно будут работать быстрее. Доберусь до чего-нибудь с xcode — скину пример.

[MSLibrary]

Спасибо, будет ждать...