测试最少行数或标记数的最快方法

Question

我现在有两次发现自己想知道 Javascript 字符串是否有最小行数，但不想浪费地拆分字符串来找出答案。两次都对正则表达式进行了过多的试验，才意识到解决方案很简单。这个自我回答 post 是为了防止我（以及希望其他人）不得不重新解决这个问题。

更一般地说，我想有效地确定任何给定字符串是否至少具有指定数量的标记。我不需要确切地知道字符串有多少个标记。 token可以是一个字符，一个子串，一个匹配正则表达式的子串，或者一个分隔的单位，比如一个词或者一行。

Another SO question 探讨了拆分字符串或进行全局正则表达式匹配是否更快，以便计算字符串中的行数。据报道，拆分速度更快，至少在内存充足的情况下。我们这里的问题是，如果我们只需要知道标记的数量是否等于或超过最小值，我们是否可以在一般情况下比字符串拆分更快地对正则表达式进行测试？

以下是我在尝试匹配最少行数时犯的一些错误——在本例中至少为 42 行：

/(^[\n]*){42}/m.test(stringToTest)
/(\n[^\n]*|[^\n]*){42}/.test(stringToTest)
/(\n[^\n]*|[^\n]*(?!\n)){42}/.test(stringToTest)

这些表达式显然乐于不匹配 42 次。他们 return stringToTest = '' 正确。

Answer 1

解决方案是测试一系列 token/non-token 单元，而不是尝试测试分隔单元的正确计数或标记的正确计数。如果令牌是定界符并且您需要最少数量的定界单位，则需要 token/non-token 个单位的计数等于比所需的单位数少一。正如我们将看到的，此解决方案具有令人惊讶的性能。

最小行数

此函数检查最小行数，其中 \n 分隔行而不是严格结束它们，允许最后一行为空：

function hasMinLineCount(text, minLineCount) {
    if (minLineCount <= 1)
        return true; // always 1+ lines, though perhaps empty
    var r = new RegExp('([^\n]*\n){' + (minLineCount-1) + '}');
    return r.test(text);
}

或者，\n 可以假设为结束行，而不是纯粹地分隔它们，为非空的最后一行创建一个例外。例如，"apple\npear\n" 是两行，而 "apple\npear\ngrape" 是三行。以下函数以这种方式计算行数：

function hasMinLineCount(text, minLineCount) {
    var r = new RegExp('([^\n]*\n|[^\n]+$){' + minLineCount + '}');
    return r.test(text);
}

字符串定界符和标记

更一般地说，对于由字符串分隔符分隔的任何单元：

var _ = require('lodash');

function hasMinUnitCount(text, minUnitCount, unitDelim) {
    if (minUnitCount <= 1)
        return true; // always 1+ units, though perhaps empty
    var escDelim = _.escapeRegExp(unitDelim);
    var r = new RegExp('(.*?'+ escDelim +'){' + (minUnitCount-1) + '}');
    return r.test(text);
}

我们还可以测试是否存在最少数量的字符串标记：

var _ = require('lodash');

function hasMinTokenCount(text, minTokenCount, token) {
    var escToken = _.escapeRegExp(token);
    var r = new RegExp('(.*?'+ escToken +'){' + minTokenCount + '}');
    return r.test(text);
}

正则表达式分隔符和标记

我们可以通过允许单位定界符和标记包含正则表达式字符来进一步概括。只要确保定界符或标记可以明确地连续出现即可。示例正则表达式分隔符包括 "<br */>" 和 "[|,]"。这些是字符串，而不是 RegExp 对象。

function hasMinUnitCount(text, minUnitCount, unitDelimRegexStr) {
    if (minUnitCount <= 1)
        return true; // always 1+ units, though perhaps empty
    var r = new RegExp(
              '(.*?'+ unitDelimRegexStr +'){' + (minUnitCount-1) + '}');
    return r.test(text);
}

function hasMinTokenCount(text, minTokenCount, tokenRegexStr) {
    var r = new RegExp('(.*?'+ tokenRegexStr +'){' + minTokenCount + '}');
    return r.test(text);
}

计算成本

通用函数起作用是因为它们的正则表达式对字符进行非贪婪匹配（注意 .*?）直到下一个分隔符或标记。这是一个计算成本高昂的前瞻和回溯过程，因此相对于上面 hasMinLineCount() 中发现的更多硬编码表达式，这些表达式的性能会受到影响。

让我们重新审视最初的问题，即我们是否可以通过正则表达式测试胜过拆分字符串。回想一下，我们唯一的 objective 是为了测试最少的行数。我用benchmark.js来测试，我假设我们知道需要多行。这是代码：

var Benchmark = require('benchmark');
var suite = new Benchmark.Suite;

var line = "Go faster faster faster!\n";
var text = line.repeat(100);
var MIN_LINE_COUNT = 50;
var preBuiltBackingRegex = new RegExp('(.*?\n){'+ MIN_LINE_COUNT +'}');
var preBuiltNoBackRegex = new RegExp('([^\n]*\n){'+ MIN_LINE_COUNT +'}');

suite.add('split string', function() {
    if (text.split("\n").length >= MIN_LINE_COUNT)
        'has minimum lines';
})
.add('backtracking on-the-fly regex', function() {
    if (new RegExp('(.*?\n){'+ MIN_LINE_COUNT +'}').test(text))
        'has minimum lines';
})
.add('backtracking pre-built regex', function() {
    if (preBuiltBackingRegex.test(text))
        'has minimum lines';
})
.add('no-backtrack on-the-fly regex', function() {
    if (new RegExp('([^\n]*\n){'+ MIN_LINE_COUNT +'}').test(text))
        'has minimum lines';
})
.add('no-backtrack pre-built regex', function() {
    if (preBuiltNoBackRegex.test(text))
        'has minimum lines';
})
.on('cycle', function(event) {
    console.log(String(event.target));
})
.on('complete', function() {
    console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.run({ 'async': true });

这是三个运行的结果：

split string x 263,260 ops/sec ±0.68% (85 runs sampled)
backtracking on-the-fly regex x 492,671 ops/sec ±1.01% (82 runs sampled)
backtracking pre-built regex x 607,033 ops/sec ±0.72% (87 runs sampled)
no-backtrack on-the-fly regex x 581,681 ops/sec ±0.77% (84 runs sampled)
no-backtrack pre-built regex x 723,075 ops/sec ±0.72% (89 runs sampled)
Fastest is no-backtrack pre-built regex

split string x 260,962 ops/sec ±0.82% (85 runs sampled)
backtracking on-the-fly regex x 502,410 ops/sec ±0.79% (84 runs sampled)
backtracking pre-built regex x 606,220 ops/sec ±0.67% (88 runs sampled)
no-backtrack on-the-fly regex x 578,193 ops/sec ±0.83% (86 runs sampled)
no-backtrack pre-built regex x 741,864 ops/sec ±0.68% (84 runs sampled)
Fastest is no-backtrack pre-built regex

split string x 262,266 ops/sec ±0.76% (87 runs sampled)
backtracking on-the-fly regex x 495,697 ops/sec ±0.82% (87 runs sampled)
backtracking pre-built regex x 608,178 ops/sec ±0.72% (88 runs sampled)
no-backtrack on-the-fly regex x 574,640 ops/sec ±0.92% (87 runs sampled)
no-backtrack pre-built regex x 739,629 ops/sec ±0.72% (86 runs sampled)
Fastest is no-backtrack pre-built regex

所有正则表达式测试显然比拆分字符串以检查行数更快，即使是回溯测试也是如此。我想我会做正则表达式测试。

测试最少行数或标记数的最快方法

Fastest way to test for a minimum number of lines or tokens

javascript

regex

string

lines

count

最小行数

字符串定界符和标记

正则表达式分隔符和标记

计算成本