Performance of Set-Based Word Existence Check

Note#68

notes
Published

2023-04-12

When checking for the existence of a word in a file, using a set-based approach is more efficient than a classic word-by-word check, especially when querying for multiple words. However, this approach may not be optimal for very large files or when memory is a concern.

Set-Based Approach

Sets use hashing, allowing for fast membership testing. Storing words in a set and then checking for a word’s existence has an average time complexity of O(1). This means the search time remains constant, regardless of the size of the set.

Code Example

_word_sets_cache = {}

def word_exists(word, file_path):
    if file_path not in _word_sets_cache:
        with open(file_path, encoding="UTF-8") as file:
            words_set = set(file.read().split())
        _word_sets_cache[file_path] = words_set
    else:
        words_set = _word_sets_cache[file_path]
    return word in words_set

Word by Word Check

A classic word by word check involves iterating through the file and comparing each word individually. This results in a linear time complexity of O(n), where ‘n’ is the number of words in the file. In this case, the search time increases linearly with the size of the file.

Code Example

def word_exists(word, file_path):
    with open(file_path, encoding="UTF-8") as file:
        for line in file:
            for curr_word in line.split():
                if curr_word == word:
                    return True
    return False

Performance Comparison

Although creating the set has an initial time complexity of O(n) while reading the file, subsequent word existence checks have an average time complexity of O(1). This makes the set-based approach more efficient than the word by word check when querying multiple words against the file.

Reminder

Note that while caching the set of words in memory can improve performance for small to medium-sized files, it may not be optimal for very large files, since reading the entire file into memory can consume a lot of resources. Therefore, it’s important to consider the size of the files that will be processed by the word_exists() function, and adjust the caching strategy accordingly.

The Bloom Filter

A Bloom filter may be a good alternative to the set-based approach for checking the existence of elements in very large files or sets. By using hashing and a bit array, a Bloom filter can achieve fast query times and a small memory footprint, while also controlling the probability of false positives. However, it may not be suitable for applications that require high precision.