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

Question

Я должен исключить 1M записей (скажем, запись является номером телефона) для потока кода.

В настоящее время я думаю сохранить все эти записи в массиве и проверить в этом массиве, является ли текущая запись startWith(regex) любым из сохраненных значений в массиве.

Сложность времени для этого метода составляет O (n). Могу ли я сделать это более эффективным способом?

Answer 1

Сложность

Ваша задача звучит так, как будто это не менее O (N), где N - количество записей, которые вы должны обработать.Если вы отфильтровываете N из M общих записей (например, 1M записей из 1B общего количества, то это будет O (M), если M записей уже не проиндексированы или не сохранены в соответствующей структуре данных (например, trie *)1004 *).

Время настенных часов

Хорошая новость заключается в том, что обработка 1M записей с использованием строковых операций должна занимать относительно небольшое время настенных часов (в худшем случае, секунд).

IРекомендуется извлекать записи по 10 КБ и анализировать их время, чтобы получить приблизительную оценку общей стоимости обработки.

Предостережения

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

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