Search with wildcards (v3)

Revision 3 of this benchmark created on

Setup

const WORDS = [
  "apple", "banana", "cherry", "date", "elderberry", "fig", "grape", "honeydew",
  "kiwi", "lemon", "mango", "nectarine", "orange", "papaya", "quince", "raspberry",
  "strawberry", "tangerine", "ugli", "vanilla", "watermelon", "xigua", "yellowfruit", "zucchini",
  "apricot", "blueberry", "cantaloupe", "dragonfruit", "eggplant", "feijoa", "gooseberry",
  "huckleberry", "imbe", "jackfruit", "kumquat", "lime", "mulberry", "nectar", "olive",
  "peach", "pear", "plum", "pomegranate", "quandong", "rhubarb", "soursop", "tamarind", 
  "ugni", "voavanga", "watercress", "ximenia", "yam", "ziziphus", "avocado", "blackberry", 
  "cranberry", "durian", "elderflower", "figtree", "grapefruit", "hawthorn", "indianfig", 
  "jambul", "kiwifruit", "loganberry", "medlar", "nutmeg", "okra", "pineapple", "quava", 
  "redcurrant", "salak", "tangelo", "ugu", "vanillabean", "wolfberry", "yuzu", "zebrafish", 
  "almond", "butternut", "cucumber", "dewberry", "endive", "fennel", "ginkgo", "horseradish", 
  "ivy", "jicama", "kale", "lettuce", "mushroom", "nopale", "onion", "potato", "quinoa", 
  "radish", "spinach", "turnip", "ugliapple", "violet", "wheat", "yarrow", "zest"
];

const SEARCHES = [
  "b*nana",   // Should match "banana"
  "gr*e",     // Should match "grape"
  "*berry",   // Should match "blueberry", "raspberry", "strawberry", etc.
  "ap*e",     // Should match "apple"
  "*fruit",   // Should match "dragonfruit", "jackfruit", "grapefruit"
];

Test runner

Ready to run.

Testing in
TestOps/sec
Simple with Regex
const searchWord = (words, search) => {
    const dict = new Set(words)
    if(!search.includes('*')) {
        return dict.has(search)
    }

    const regex = new RegExp(`^${search.replace(/\*/g, '.')}$`)
    let result;
    for(let word of dict) {
        if(result) break;
        if(word.length !== search.length) {
            continue;
        }

        result = regex.test(search)
    }

    return result;
}

// Performance test
const runPerfTest = () => {
  console.time("Performance Test");

  SEARCHES.forEach(search => {
    console.log(`Search: "${search}"`);
    const result = searchWord(WORDS, search);
    console.log(`Result: ${result}`);
  });

  console.timeEnd("Performance Test");
};

runPerfTest();
ready
With Indexes and Loops
const searchWord = (words, search) => {
    const dict = new Set(words);

    // No wildcard, direct match
    if (!search.includes('*')) {
        return dict.has(search);
    }

    // Split the search string by '*'
    const parts = search.split('*').filter(Boolean); // Remove empty strings

    for (let word of dict) {
        let currentIndex = 0;
        let isMatch = true;

        // Check if word can contain all parts in the correct order
        for (let part of parts) {
            const index = word.indexOf(part, currentIndex);

            // If part is not found or is out of order, skip the word
            if (index === -1) {
                isMatch = false;
                break;
            }

            // Move currentIndex to the end of the found part
            currentIndex = index + part.length;
        }

        if (isMatch) {
            return true; // Early exit if match is found
        }
    }

    return false; // No match found
};

// Performance test
const runPerfTest = () => {
  console.time("Performance Test");

  SEARCHES.forEach(search => {
    console.log(`Search: "${search}"`);
    const result = searchWord(WORDS, search);
    console.log(`Result: ${result}`);
  });

  console.timeEnd("Performance Test");
};

runPerfTest();
ready
Without substrings
const searchWord = (words, search) => {
    const dict = new Set(words);

    // No wildcard, direct match
    if (!search.includes('*')) {
        return dict.has(search);
    }

    for (let word of dict) {
    	if (word.length !== search.length) continue;
    	
        let counter = 0;
        for (let i = 0; i < words.length; i++) {
            if (search[i] === '*') {
            	counter++;
            	continue;
            }
            
            if (search[i] !== word[i]) {
            	break
            }
            
            counter++;
        }
        
        if (counter === word.length) {
        	return true;
        }
    }

    return false; // No match found
};

// Performance test
const runPerfTest = () => {
  console.time("Performance Test");

  SEARCHES.forEach(search => {
    console.log(`Search: "${search}"`);
    const result = searchWord(WORDS, search);
    console.log(`Result: ${result}`);
  });

  console.timeEnd("Performance Test");
};

runPerfTest();
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.