Search with wildcards (v4)

Revision 4 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
With trie algorithm
class TrieNode {
  constructor() {
    this.wordEnd = false
    this.children = {}
  }
}

class Search {
    constructor(words) {
        this.root = new TrieNode()

        for (let word of words) {
            let node = this.root

            for (let i = 0; i < word.length; i++) {
                const key = word[i]
                if (!node.children[key]) {
                    node.children[key] = new TrieNode()
                }

                node = node.children[key]
            }

            node.wordEnd = true
        }
    }

    search(word, index = 0, baseNode = null) {
        const node = baseNode ?? this.root

        if (index >= word.length) return node.wordEnd
        
        const key = word[index]
        if (key === '*') {
            for (let child of Object.values(node.children)) {
                if (this.search(word, index + 1, child)) {
                    return true
                }
            }

            return false
        }
        
        if (!node.children[key]) return false

        return this.search(word, index + 1, node.children[key])
    }
}

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

  SEARCHES.forEach(search => {
    console.log(`Search: "${search}"`);
    const result = searcher.search(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.