Search with wildcards (v2)

Revision 2 of this benchmark created on

Setup

// 1k words generated similarly
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",
  "achira", "baklava", "coconut", "dumpling", "enchilada", "fondue", "guava", "haricot",
  "island", "jasmine", "kebab", "lychee", "marzipan", "nectar", "omelette", "paella",
  "quesadilla", "radicchio", "saffron", "tarragon", "uglifruit", "vodka", "wasabi", "xoconostle",
  "yogurt", "ziti", "arugula", "biscuit", "cabbage", "danish", "endive", "fudge", "gorgonzola",
  "halva", "icecream", "jalapeno", "kaleidoscope", "lobster", "meringue", "nori", "okra",
  "parfait", "queso", "risotto", "sorbet", "turmeric", "ugric", "venison", "wiener", "xylophone",
  "yucca", "zabaglione", "angelica", "brioche", "chimichanga", "daikon", "espresso", "focaccia", 
  "ginger", "hoisin", "imarti", "jalebi", "knish", "lasagna", "macaron", "nougat", "okra",
  "pita", "quahog", "rigatoni", "spinach", "tilapia", "udon", "vichyssoise", "wakame", 
  "xylitol", "yuba", "zucchini", "asiago", "blackbean", "chickpea", "dumpling", "empanada",
  "feta", "gnocchi", "haloumi", "iceberg", "jaggery", "kumara", "limoncello", "macadamia", 
  "noodle", "orzo", "parsnip", "quinoa", "ravioli", "scallop", "taro", "udon", "vinaigrette", 
  "wonton", "ximenia", "yokan", "zatar", "anchovy", "bratwurst", "croissant", "dahl", "eel", 
  "falafel", "gouda", "honey", "idli", "jalapeno", "kimchi", "lamb", "masala", "naan", "okra", 
  "palm", "quark", "rosemary", "shallot", "thyme", "upland", "vinaigrette", "wheatgrass", 
  "ximenia", "yolk", "zaatar", "amaranth", "baguette", "cassava", "duck", "eggplant", "flounder", 
  "grits", "hummus", "iceberg", "jackfruit", "kohlrabi", "lentil", "mandarin", "noodle", 
  "onion", "pork", "quahog", "rutabaga", "schnitzel", "turmeric", "uni", "vinegar", "wakame", 
  "xigua", "yam", "zucchini", "alfalfa", "beetroot", "celeriac", "donut", "endive", "flaxseed", 
  "ghee", "haddock", "ilama", "jerky", "kefir", "lobster", "mungbean", "nopal", "oregano", 
  "pancetta", "quince", "ramen", "samosa", "tofu", "udon", "vermouth", "walnut", "ximenia", 
  "yogurt", "zabaglione", "almond", "bokchoy", "calamari", "dandelion", "edamame", "foiegras", 
  "ginger", "horseradish", "irishmoss", "jicama", "kohlrabi", "lychee", "mozzarella", "nectarine", 
  "onion", "pomegranate", "quiche", "radish", "shiitake", "tomato", "upland", "venison", "watercress", 
  "xylitol", "yarrow", "ziti", "anchovy", "broccoli", "capers", "dumpling", "endive", "fennel", 
  "garlic", "herbs", "indianfig", "jalapeno", "kale", "lettuce", "mustard", "nachos", "olive", 
  "pasta", "quail", "rice", "spinach", "turnip", "udon", "vanillabean", "watermelon", "xylophone", 
  "yuca", "zebra", "avocado", "bamboo", "carrot", "dates", "endive", "fennel", "grape", "horseradish", 
  "island", "jalapeno", "kale", "lemon", "mango", "nectar", "olive", "papaya", "quinoa", "rhubarb", 
  "spinach", "tomato", "ugni", "vodka", "watermelon", "ximenia", "yam", "zebra"
];

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"
  "c*rry",       // Should match "cherry"
  "w*termelon",  // Should match "watermelon"
  "ki*wi",       // Should match "kiwi"
  "e*berry",     // Should match "elderberry" or "blueberry"
  "ch*ch",       // Should match "chickpea" or "cabbage"
];

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

Revisions

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