Сложность замены Regex
Я использовал NodeJS для загрузки файла, но забыл передать auth.
Сначала я использовал:
function downloadFiles() {
const service = google.drive('v3');
const dest = fs.createWriteStream('/tmp/foo.csv');
const fileId = '12345_ID_GOES_HERE';
service.files.export({
fileId: fileId,
mimeType: 'text/csv'
});
}
после этого, я добавил auth аргумент функции и передал его также методу export:
function downloadFiles(auth) {
const service = google.drive('v3');
const dest = fs.createWriteStream('/tmp/foo.csv');
const fileId = '12345_ID_GOES_HERE';
service.files.export({
auth: auth,
fileId: fileId,
mimeType: 'text/csv'
})
}
Я получаю auth, создавая экземпляр google-auth-library
7 ответов
От чисто теоретической позиции:
Реализация, с которой я знаком, должна была бы создать Детерминированный конечный автомат для распознавания regex. Это сделано в O (2^m), m быть размером regex, с помощью стандартного алгоритма. После того как это создается, выполнение строки через него линейно в длине строки - O (n), n являющийся длиной строки. Замена на соответствии, найденном в строке, должна быть постоянным временем.
Таким образом в целом, я предполагаю O (2^m + n).
Зависит от того, что вы определяете с помощью регулярных выражений. Если вы разрешите операторы конкатенации, альтернативы и Kleene-star, время может фактически быть O (m * n + m) , где m является размером регулярного выражения и n - длина строки. Вы делаете это путем создания NFA (который является линейным в m ), а затем моделируете его, поддерживая набор состояний, в котором вы находитесь, и обновляя его (в O (m) ) для каждой буквы ввода.
Вещи, которые затрудняют синтаксический анализ регулярных выражений:
- круглые скобки и обратные ссылки: захват по-прежнему в порядке с вышеупомянутым алгоритмом, хотя это усложнило бы его, поэтому оно может быть неосуществимым. Обратные ссылки увеличивают силу распознавания регулярного выражения, и его сложность хорошо
- позитивный прогноз: это просто еще одно название для пересечения, которое повышает сложность вышеупомянутого алгоритма до
O (m ^ 2 + n) - отрицательный прогноз: катастрофа для создания автомата (
O (2 ^ m) ), возможно, PSPACE-полная). Но все же должна быть возможность справиться с динамическим алгоритмом примерно так:O (n ^ 2 * m)
Обратите внимание, что в конкретной реализации все может стать лучше или хуже. Как правило, простые функции должны быть достаточно быстрыми, а однозначные (например, не такие как a * a * ) регулярные выражения лучше.
O (n ^ 2 * m)
Обратите внимание, что в конкретной реализации все может стать лучше или хуже. Как правило, простые функции должны быть достаточно быстрыми, а однозначные (например, не такие как a * a * ) регулярные выражения лучше.
O (n ^ 2 * m)
Обратите внимание, что в конкретной реализации все может стать лучше или хуже. Как правило, простые функции должны быть достаточно быстрыми, а однозначные (например, не такие как a * a * ) регулярные выражения лучше.
Копаться в ответе theprise, для конструкции автомата, O (2^m) - худший случай, хотя это действительно зависит от формы регулярного выражения (для очень простого, который распознает слово, это находится в O (m), с помощью, например, Knuth-Morris-Pratt алгоритм).
Зависит от реализации. Какой язык/библиотека/класс? Может быть лучший случай, но это было бы очень характерно для количества функций в реализации.
Можно обменять пространство на скорость путем создания недетерминированного конечного автомата вместо DFA. Это может быть пересечено в линейное время. Конечно, в худшем случае этому мог быть нужен O (2^m) пространство. Я ожидал бы, что компромисс будет стоить того.
Другая теоретическая информация, которая может представлять интерес.
Для ясности предположим стандартное определение регулярного выражения
http://en.wikipedia.org/wiki/Regular_language
из теории формального языка. Практически это означает, что единственное здание материалом являются символы алфавита, операторы конкатенации, чередования и Замыкание Клини вместе с единичной и нулевой константами (которые появляются для теоретико-групповые соображения). Как правило, лучше не перегружать этот термин несмотря на повседневную практику языков сценариев, которая приводит к неоднозначности.
Существует конструкция NFA, которая решает проблему согласования для регулярных выражение r и входной текст t во времени O (| r | | t |) и пространстве O (| r |), где | - | - функция длины. Этот алгоритм был дополнительно улучшен Майерсом
http://doi.acm.org/10.1145/128749.128755
до временной и пространственной сложности O (| r | | t | / log | t |) с использованием узла автомата листинги и парадигма четырех россиян. Эта парадигма, кажется, названа в честь четырех русских парней, написавших новаторскую статью, которая онлайн. Однако эта парадигма проиллюстрирована в этих вычислительных биологиях. конспекты лекций
http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf
Я считаю забавным называть парадигму числом и национальность авторов вместо их фамилий.
Проблема сопоставления регулярных выражений с добавленными обратными ссылками: NP-полная, что было доказано Ахо
http://portal.acm.org/citation.cfm?id=114877
путем редукции из проблемы вершинного покрытия, которая является классической NP-полной проблемой.
Для детерминированного сопоставления регулярных выражений с обратными ссылками мы могли использовать обратное отслеживание (в отличие от движка регулярных выражений Perl), чтобы отслеживать возможные подслова входного текста t, которые могут быть присвоены переменным в р. Есть только O (| t | ^ 2) подслов, которые могут быть присвоены любой переменной в г. Если в r есть n переменных, то существует O (| t | ^ 2n) возможных задания. Как только присвоение подстрок переменным зафиксировано, проблема сводится к простому сопоставлению регулярных выражений. Следовательно сложность наихудшего случая сопоставления регулярных выражений с обратными ссылками O (| t | ^ 2n).
Обратите внимание, однако, что регулярные выражения с обратными ссылками еще не полнофункциональное регулярное выражение.
Возьмем, например, символ "безразлично", кроме любого другого операторы. Существует несколько полиномиальных алгоритмов, определяющих, является ли набор Шаблоны соответствуют входному тексту. Например, Кучеров и Русинович
http://dx.doi.org/10.1007/3-540-60044-2_46
определяют шаблон как слово w_1 @ w _2 @ ... @w_n, где каждый w_i - это слово (не регулярное выражение), а «@» - это символ переменной длины «безразлично», не содержащийся ни в одном из w_i. Они выводят алгоритм O ((| t | + | P |) log | P |) для сопоставления набора шаблонов P с входным текстом t, где | t | - длина текста, а | P | - длина всех слов в P.
Было бы интересно узнать, как сочетаются эти меры сложности и какие является мерой сложности задачи сопоставления для регулярных выражений с обратные ссылки, «все равно» и другие интересные особенности практического регулярные выражения.
Увы, я не сказал ни слова о Python ... :)
Если вы после сопоставления и подстановки, это подразумевает группировку и обратные ссылки.
Вот пример Perl, в котором группировка и обратные ссылки могут использоваться для решения полной проблемы NP: http://perl.plover.com/NPC/NPC-3SAT.html
Это (вместе с некоторыми другими теоретическими лакомыми кусочками) означает, что использование регулярных выражений для сопоставления и подстановки является NP-полным.
Обратите внимание, что это отличается от формального определения регулярного выражения - которое не имеет понятия группировки - и соответствует за полиномиальное время, как описано в других ответах.