Fastest way to find all numbers with digits

Question

I have a huge set of over a million numbers of variable lengths.

['773', '2267', '8957251', '170597519', '373590109', '982451707', '999999937', ......]

Now given a bunch of digits, say 3 and 7, I intend to create a subset of all numbers which contain those digits. That is:

['773', '373590109', '999999937', ......]

This kind of lookup happens multiple times for different digits. Thus iterating over the entire list each time is not an option.

I am considering creating 10 subsets, one for each digit, on program startup. Each set will contain all numbers containing that digit. I then plan to use set intersection on each lookup. What do think of this method? Is there a better way which would achieve faster results?

I am implementing this in C++. But I am open to do the same in Python if there is an easier way available.

Answer 1

Lets take a step back for a moment and try to understand why you want to do this. You want to be able to perform a lookup for the existence of a value in a list of millions of numbers? Do you need to do this many times or just once?

The reason I ask is because if it is just once, the most efficient way is simply to load the numbers into memory perform a single pass for the existence of that number in the array. Threads would make this even more efficient, breaking the work into smaller pieces. If the array were too large for this, you could load it one chunk at a time, though I assume if you're potentially duplicating numbers in 10 different arrays, one per digit, memory is not an issue here.

If you need to perform repeated lookups, may I recommend using a trie. You create 9 bins containing the first digit to search for. That child then has 10 bins containing the the second digit to search for. Repeat as often as you wish. With respect to the 10 arrays approach that you mentioned, this would most certainly occupy less memory (the non-leaf nodes in the tree represent multiple numbers, not just one).

The reason why your approach might be potentially inefficient is because the chance of a number containing a digit increase significantly with each additional digit. With a 10 digit number, the chance of a particular digit not showing up is roughly (9/10)^10 or 34%. That means there's a 66% chance that a 10 digit number will show up in a given set, which roughly means we're talking about a 66% duplication of data. Smaller numbers might be more favorable, but even a 3 digit number has a 27% duplication rate.

Even if memory were not an issue, the replication of numbers is making your lookup algorithm less efficient.

Therefore my recommendation is to use a Trie for lookups. Though to answer your question, to get a list of all numbers containing a specific digit, your approach is best. Though unless I can't see the tree from the forest, this approach is probably not what you want to achieve.

Answer 2

Set intersection is definitely a possibility. Another method is to use a bitfield to describe which digits are contained in a number. Then you can do a simple logical operation and compare. For example, for the number 773, it would have bits 7 and 3 set, so its bit mask would be: 0x88 (binary = 10001000). You could then take the logical "AND" of any number's bit mask and 0x88, and if the result is 0x88, then that number contains the digits in question.

Answer 3

Finding the intersection of sets would involve something like a hash join. While much of the setup could be pre-computed and kept in memory, you still need to do all of the following:

1. Assume we are searching list N for digits a and b.
2. Iterate through N, which has ~one million numbers
3. For each number in the list:
   • Search the hash table for digit a to see if N[i] exists
     • Scan the hash pointers for the right hash bucket
     • Scan the hash bucket to see if N[i] exists
   • Search the hash table for digit b to see if N[i] exists
     • Scan the hash pointers for the right hash bucket
     • Scan the hash bucket to see if N[i] exists

On the other hand, if you skipped the tables and wrote an efficient algorithm for checking on the spot, you could:

1. Assume we are searching list N for digits a and b.
2. Iterate through N, which has ~one million numbers
3. For each number in the list:
   • For each digit in the number
     • Divide by 10
     • Compare the remainder to a and b

So for the hash join, you have several complicated search and location functions, per individual N[i], all of which require memory read, increment, and comparison operations. This means {number of numbers} x {number of hashtables} x {rows in hash lookup + rows in hash bucket}. They all multiply! Meanwhile, for a straight scan, you have two low-level operations (a division+modulus operation and a comparison) per number. That is much, much less processing.

It is hard to assess performance in isolation, but I'm guessing you're not going to gain much performance, if any, from a hash join solution. In fact it may be worse due to the low selectivity-- given a number between 1 and 1,000,000, roughly 50% of them will have any given digit. If that number were much smaller, a hash table would boost performance quite a bit, but if you're pulling back half or more of the data, a scan starts looking better and better. When you consider the increased memory utilization (and therefore increased working set) required to support the hash tables, I'm going to make a bet that the performance of the hash/intersection design would be worse.

Here is some simple code that efficiently checks for the presence of a set of digits. I used this algorithm on my Dell Precision laptop and was able to scan 1,000,000 numbers in 0.0120 seconds. I would just run this function, per number in the list, when needed.

int ContainsDigits(int numberToCheck, int digitsToFind[], int digitCount)
{
    int result;
    int digits[10];

    memcpy(digits, digitsToFind, digitCount * sizeof(int));

    while (numberToCheck > 0)
    {
        std::div_t result = std::div(numberToCheck, 10);
        for (int i = digitCount -1; i >= 0; i--)
        {
            if (result.rem == digits[i])
            {
                if (!--digitCount) return 1;
                digits[i] = digits[digitCount];
            }
        }
        numberToCheck = result.quot;
    }
    return 0;
}

The algorithm checks the least significant digit (given by n % 10) in a loop then shifts the number right (equivalent to n / 10). We can get the modulus and quotient in a single operation (std::div).

Digits sought are stored in an array. When a digit is found, the array is shortened by one element, with the end element moved into the place of the discovered digit, thus keeping the list compacted. When the array is empty all digits have been found. If the loop exits and not all digits have been found, the function returns false.

Answer 4

It's easy enough to do this in Python:

def find_nums_with_digits(nums, digits):
    digits = ''.join(sorted(digits))

    char_map = {c: c if c in digits else None for c in '0123456789'}
    trans = str.maketrans(char_map)

    for num in nums:
        if digits in ''.join(sorted(num.translate(trans))):
            yield num

nums = ['773', '2267', '8957251', '170597519', '373590109', '982451707', '999999937']
for num in find_nums_with_digits(nums, '73'):
    print(num)

The idea here is that if we sort the digit strings and remove the digits we're not interested in then your condition just becomes a substring test.

As mentioned in the other answers there will be more efficient ways to do this if you are looking to test many combinations of digits with the same large set of number strings.

Answer 5

Another option that is somewhat like your original idea is to create a hashtable like structure where the hash is the bitmask (as described in user1118321's answer) of the digits in each number. Each number is then bucketed into one of the 1024 possible sets. Then to lookup, you use the corresponding bit mask and AND the keys to find the set as in the other answer. The difference here being that you need to check at most 1024 values as opposed to looping over the entire set.

One advantage of this is there would be zero duplication across the buckets. The storage would be N plus the 1024 keys. If you wanted to build a trie over the keys ala Neil's solution, you can also do that.