Changing every link on page, in fastest way possible

Question

I have created a script (mediawiki gadget), which iterates over every redlink in a rendered wiki-page (that is, over every href with class new, signifying an internal link to an article that does not exist), and checks if the title exists in a set of known pages. If it does, a few attributes are changed. The execution is extremely simple, but I need it to be as fast as possible.

The set of known pages contains nearly 20K strings, here omitted:

const rawPages=new Set([...])

$("#mw-content-text a.new").each(function() {
    var b=$(this),a=b.attr("title");
    !a||
    a.startsWith("קאַטעגאָריע:") ||
    a.startsWith("טעקע:") ||
    a.startsWith("שמועס:") ||
    a.startsWith("באניצער:") ||
    a.startsWith("המכלול:") ||
    a.startsWith("הילף:") ||
    a.startsWith("מעדיעװיקי:") ||
    a.startsWith("מוסטער:") ||
    a.startsWith("יחידה:") ||
    a.startsWith("דרעפט:") ||
    a.startsWith("טעמע:") ||
    (a=a.replace(" (בלאַט עקזיסטירט נאכנישט)", ""),
    rawPages.has(a)&&
    b.attr({
        "class": "raw",
        "title": a + " (רוי)",
        "href": "/"+encodeURIComponent("רוי")+":"+encodeURIComponent(a)
    }))});

At first, the script checks if the title begins with some prefixes, in which case we are not interested in modifying the link. But the rawPages set does not contain any such title anyway; would it be faster to check directly for membership, instead of trying to short-circuit with multiple startsWith calls?

Anything else I can do, to speed it up?

Thanks!

Answer 1

The easiest way to get a performance boost in your code is to not use jQuery:

const rawPages = new Set([...]);

const anchors = document.querySelectorAll("#mw-content-text a.new");
for (let i = 0; i < anchors.length; i++) {
    const a = anchors[i];
    const title = a.title;
    if (!rawPages.has(title)) {
        continue;
    }

    a.title = title + " (רוי)";
    a.classList.add("raw");
    // concatenation might be faster than this interpolation, test it.
    a.href = `/${encodeURIComponent("רוי"):${encodeURIComponent(title)}`;
}

I've also removed the startsWith calls as I'm not sure whether that will be saving computation on average.

Answer 2

You must match T titles against a dictionary of W words, and your current code runs in O(T × W) time.

For at least some of your thousands of strings (and for all eleven that appeared in your example) the spec is to find each title that .startsWith this single-word regex: ^(\w+):

So create a Set() lexicon containing all those words. Then for each title, use that regex to parse out the leading word (if any), and look it up in the the lexicon. If found, perform the .replace operation. That's O(1) constant time per title, total of O(T) time for the page.

If you need a leading phrase rather than leading word, use ^([ \w]+): or similar expression.