How to make my algorithm significantly faster by reduce for loops?

user_16255612 0
Viewed 161

I am currently working on a project that collects data from the masslottery.com api. I am analyzing this data in all sorts of ways. One way I would like to analyze this data is by checking what 5 spot keno number has come in the most over, lets say the last year. My program that I have written can theoretically do this. However, it is a bit too slow. Right now checking a 3 spot number takes about a minute and 20 seconds. And as you know the number of possibilities I have to count go up and up as you increase numbers. Since keno is 1-80,

80 choose 3 = 82,160 possibilities
80 choose 4 = 1,581,580 possibilities
80 choose 5 =  24,040,016 possibilities

So as you can see if my program takes a minute on only 80 thousand, it would take like 5 hours to finish for a 5 spot number. With that said I am looking for help on how to speed up my program. I believe my issue is my double for loop but I've tried everything to fix this. I will include my code below.

import requests
from itertools import combinations
import operator
import collections
r = requests.get('https://www.masslottery.com/rest/keno/getDrawsByDateRange?startDate=2021-01-01=&endDate=2021-07-11').json()
draw  = (r['draws'])
dict = {}

spot = int(input('How many spots are you trying to check? '))


arr = [
1,2,3,4,5,6,7,8,9,10, 11, 12,
13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
80]
test = combinations(arr,spot)

count= 0
print('Starting Check')
for i in test:
    dict[str(sorted(i))] = 0


for num in draw:
    numbers = num['winningNumbers']
    combin = combinations(numbers,spot)
    for j in combin:
        temp = str(sorted(j))
        dict[temp] = dict[temp] + 1




sorted_dict = sorted(dict.items(), key=operator.itemgetter(1))
dict2 = collections.OrderedDict(sorted_dict)
filename = str(spot) + 'spotTest.txt'
with open(filename,'w') as File:
    for i in dict2:
        File.write(str(i) + '---->'+ str(dict2[i]) +'\n')
        
print('Done')

NOTE: Also I am aware that keno is a game of luck and has no strategy involved. I am only doing this for my entertainment purposes and to practice coding. Thanks to anyone that has ideas on how to speed this up!

api algorithm python performance
1 Answers

In this answer, I'll focus on the technical side of the exact solution to your problem. Note, that if this was a real life problem, you'd probably end up using some kind of approximate frequency analysis instead of optimizing the exact solution.

Now, here are several things that can improve the performance of your program.

1. Use the appropriate data structure, avoid garbage

Python dictionaries are hash tables underneath. That means that they allocate huge continuous array (table) to hold references to your data. If you're actively inserting millions of elements into the dict, at some point it has to grow, meaning new larger array is allocated and old array is copied to the new one. As you can imagine, this is not fast, especially for large arrays.

Generating sorted string keys for combinations is a reasonable approach on a small scale, but not if you're doing it millions of times in a loop.

Instead of using dict with string keys, you can use a Trie. The Trie is a n-ary tree (in your case each node will have at most 80 children), with counters in the leafs. Also, for this problem, as you're storing combinations, each node of the trie will be strictly smaller than its parent.

trie

Here you have combinations {2, 3, 20} with count=1 and {4,79, 80} with count=2 stored in the trie.

If you look at the subsequent combinations, generated by itertools, you'll notice that most of the time they are different only in the last element. The algorithm to generate combinations plays very well with Trie traversal. In fact, you can do both using the same recursive function. When you generate new combination, you don't need to traverse the whole Trie to the leaf, you've already did most of the work for the previous combination!

The signature of this function will look something like this:

def rec(arr, i=-1, rem=spot, node=root):

Where:

  • arr is your winning number to generate combinations from (sorted asc)
  • i is the last index of the element in the current combination (-1 if there are none yet)
  • rem is the number of elements left to generate in current combination
  • node is the parent Trie node (node that corresponds to the last element of the current combination, or root if there are none)

When rem reaches 0, you bump the counter in the node.

So, the overall algorithm would be:

  1. Go through all winning numbers
  2. Sort winning number in ascending order
  3. Run rec for the current winning number
    • rec will generate all combinations out of the winning number, bumping counters in the Trie at the same time
    • Note: don't initialize the Trie with all possible combinations beforehand, it wastes time, and you can always find out which numbers are missing, when traversing the Trie, if you even need that
  4. Recursively traverse the Trie to find maximal number or dump everything in the file

2. Parallellize!

There is a popular paradigm for parallel data processing, called map-reduce. There are lots of frameworks that utilize this approach, but it's not necessary to use them.

This problem is a perfect use case for map-reduce. You have your big data (winning numbers), that you can partition into several chunks.

Then, you have your "map" stage — generating dict (or trie) from the combinations from winning numbers.

Finally, when you have counters from each partition, you can merge them into a single dictionary/trie. This is "reduce" stage.

Now, that may sound simple, but there are several important things to consider:

  1. In python, due to GIL using threads within the same process may not yield the desired performance gain. If you're sticking with python, you'll probably need to spawn separate process for each input partition and dump the results into a file and then merge the files
  2. Merging sorted file is relatively easy and can be done in linear time using merge method, similar to the one from merge sort. Merging dicts is pretty straightforward. Merging trie is also easy, you basically need to traverse both tries at the same time.

3. Get closer to the bare metal

Python is an awesome language for quick prototyping or gluing native code together. However, if you're trying to squeeze every bit of performance out of your machine, you may consider rewriting your code in a more performant language. Same code in C++ or Rust can be orders of magnitude faster than in Python. Even Java can get you some performance improvement.

user_13493660
Related