4
\$\begingroup\$

I'm looking for a way to speed this code up. It took about 4.5 hours to run on ~20k decks. I'm open to restructuring my SQL query, but feel adjusting the python would be more effective. The goal of this code is to see how many times a pair of cards occurs in all the decks. For example if ("card", "name") appears in 27/100 decks, it returns .27.

This code takes every deck in a format, and returns the cards in those decks. This gives me a list of a lot of cards ((cardId, "card name", deckId), ... (cardId "card name", deckId)). I use the deckId to make a bunch of lists representing each deck (newList). Using those lists I get each unique card and put it into a separate list (superSet).

From there I loop through superSet twice to get each possible pair. Then loop through newList to see if a pair is in a deck.

I know it's somewhat complicated and I probably didn't explain it the best. I'll gladly update this post to clarify anything I can.

from classes.general import Database

def main():
    dbm = Database()
    with dbm.con:
        dbm.cur.execute("""SELECT c.id, c.name, ctd.deckId FROM cards c 
        JOIN cardToDeck ctd ON ctd.cardId = c.id 
        JOIN deckToEvent dte ON dte.deckId = ctd.deckId 
        JOIN eventToFormat etf ON etf.eventId = dte.eventId 
        WHERE etf.formatId = 5
        ORDER BY ctd.deckId""")
        decks = dbm.cur.fetchall()
        
        #print(decks)

        #I'm not entirely sure how this works
        #Somehow it takes everything with the same deckId (index:2) and puts them into one list
        values = set(map(lambda x:x[2], decks))
        newlist = [[y[1] for y in decks if y[2] == x] for x in values]

        #print(newlist[0])
        
        superSet = []
        for l in newlist:
            for c in l:
                if c not in superSet:
                    superSet.append(c)

        #print(superSet)
        
        count = 0
        for x in superSet:
            for y in superSet:
                if x is y:
                    continue
                #print(x)
                #print(y)
                for d in newlist:
                    #print(d)
                    if x in d and y in d:
                        count += 1
                deckPerc = count / len(newlist)
                if deckPerc != 0.0:
                    print(count / len(newlist)) #needs to go into the db
                count = 0           

if __name__== "__main__":
    main()
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Creating your list of decks

"""-- ORIGINAL CODE --"""
#I'm not entirely sure how this works
#Somehow it takes everything with the same deckId (index:2) and puts them into one list
values = set(map(lambda x:x[2], decks))
newlist = [[y[1] for y in decks if y[2] == x] for x in values]

map() takes the function in the first argument, and applies it to every item in the iterable in the second argument. In this case, each item is a (cardId, "card name", deckId) tuple, and the function returns the value in index 2 of that tuple, namely deckId. set() takes the iterable returned by map() and converts it into a set, which contains exactly one of each unique value in the iterable - in this case, each unique deckId.

Your second line uses two list comprehensions. The outer one iterates over values (your set of deckIds) and for each deckId it uses another list comprehension to iterate over decks and returns index 1 of each tuple (namely "card name") if index 2 of the item equals the deckId currently being used from the outer list comprehension.

You could also write this line as a double for-loop:

newlist = []
for x in values:
    temp = []
    for y in decks:
        if y[2] == x:
            temp.append(y[1])
    newlist.append(temp)
    

But in general, this is pretty messy. You loop over the entirely of decks in order to create values, then loop over values * decks. That's very inefficent

You'd be much better off using a dictionary, where you can then fold this all into a single loop

deck_dict = {}
for (id, name, deck_id) in decks:
    if deck_id not in deck_dict:
        deck_dict[deck_id] = []
    deck_dict[deck_id].append(name)
    

You can even ditch the initial check to create the list if you use a defaultdict

from collections import defaultdict

deck_dict = defaultdict(list)
for (id, name, deck_id) in decks:
    deck_dict[deck_id].append(name)
    

However, this is still the wrong structure, because you don't actually cares about which cards are in each deck - you care about which decks contain each card.

from collections import defaultdict

card_dict = defaultdict(set)
for (id, name, deck_id) in decks:
    card_dict[name].add(deck_id)
    

Creating you superset

"""-- ORIGINAL CODE --"""
superSet = []
for l in newlist:
    for c in l:
        if c not in superSet:
            superSet.append(c)
                

Then you create loop through every item in an item in newlist to create your superSet. You have the same number of items in items in newlist as you had in decks, just organized differently, so all you get for using it instead is a slightly more complicated for loop

superSet = []
for (id, name, deck_id) in decks:
    if name not in superSet:
        superSet.append(name)
        

Notably, since now you're iterating over decks, you could roll this into the same loop you used to create deck_dict. But there's still room for improvement, because you made superSet a list, while it would make much more sense for it to be a set.

superSet = set()
for (id, name, deck_id) in decks:
    superSet.add(name)
    

Since a set only ever contains one of each unique value, this saves you from having to check whether each object is in superSet before you add it. The operation x in s is a lot faster for a set than a list (O(1) on average instead of O(n)).

If superSet is a set, you can actually use the same assignment you were using earlier for values: superSet = set(map(lambda x:x[1], decks)). Note that we're using x[1] here instead of x[2] because we want the card name instead of the deckId. You can also replace map with a generator comprehension: superSet = set(x[1] for x in decks), which is generally considered more 'pythonic' than using map().

Counting your pairs

"""-- ORIGINAL CODE --"""
count = 0
for x in superSet:
    for y in superSet:
        if x is y:
            continue
        #print(x)
        #print(y)
        for d in newlist:
            #print(d)
            if x in d and y in d:
                count += 1
        deckPerc = count / len(newlist)
        if deckPerc != 0.0:
            print(count / len(newlist)) #needs to go into the db
        count = 0   
        

Iterating over superSet twice like this actually gives you every pair you need twice - once as x='Shock' and y='Bolt', and once as x='Bolt' and y='Shock'. Fortunately, the itertools library has you covered with the combinations() function. And with card_dict providing the set of decks that contain each card, finding out the total number of decks that contain a pair is simply a matter of taking the union of the sets like so:

from itertools import combinations
for card1, card2 in combinations(superSet, 2):
    shared_decks = card_dict[card1] & card_dict[card2]
    count = len(shared_decks)
    if count > 0:
        print(f'{card1} + {card2}: {count}')
        

Now, rather than calculate the deck percentage, I merely used the count of decks that share the pair. This is because I ditched deck_dict in favor of card_dict, and don't actually have a simple way of calculating the total number of decks at this point in the code. This isn't a problem for the code shown, as if deckPerc != 0.0 is equivalent to if count != 0, but if you need the percentage for your actual use case, then we need to go back to before this loop and create it. You can use deck_count = len(set(card[2] for card in decks)), or you can fold the set construction into the existing loop through decks to avoid having to loop through it twice.

Bringing it all together

from classes.general import Database
from collections import defaultdict
from itertools import combinations

def main():
    dbm = Database()
    with dbm.con:
        dbm.cur.execute("""SELECT c.id, c.name, ctd.deckId FROM cards c 
        JOIN cardToDeck ctd ON ctd.cardId = c.id 
        JOIN deckToEvent dte ON dte.deckId = ctd.deckId 
        JOIN eventToFormat etf ON etf.eventId = dte.eventId 
        WHERE etf.formatId = 5
        ORDER BY ctd.deckId""")
        decks = dbm.cur.fetchall()
        
        deck_set = set()
        card_set = set()
        card_dict = defaultdict(set)
        for card_id, card_name, deck_id in decks:
            deck_set.add(deck_id)
            card_set.add(card_name)
            card_dict[card_name].add(deck_id)
            
        deck_count = len(deck_set)
        
        for card1, card2 in combinations(card_set, 2):
            shared_decks = card_dict[card1] & card_dict[card2]
            deckPerc = len(shared_decks) / deck_count
            if deckPerc > 0:
                print(f'{card1} + {card2}: {count}') # needs to go into the db
                
if __name__ == "__main__":
    main()

And there you have it! You have two loops, one of which iterates through decks once, and the other loops through N*(N-1)/2 items, where N is the number of unique cards. Using sets and dicts mean that the time complexity of the operations inside the loops are all O(1), so this is pretty much as fast as you can make it.

Additional Notes

I know very little about databases, so there may be improvements possible in that area that I am unaware of. I noticed that you kept the entirety of the code in the with block with the connection open, even though you never use it after you create decks. This doesn't harm anything that I'm aware of, but it's good practice to exit a context as soon as you no longer need it (and it reduces the level of indenting your code is at, which is nice). On the other hand, if you plan on using the connection to modify the database at the end of the code, then obviously leave everything as it is.

Style-wise, you could stand to improve your naming conventions. values, newlist, and superSet are not very descriptive names. Notice how I used deck_set, card_set, and card_dict to provide some indication as to what is in each object. Additionally, most python style guides (in particular PEP 8 the style guide for Python's standard library) recommend using lower_case_with_underscores for the names of variables rather than camelCase as you are using. You are of course free to pick any naming convention you want, but you should conciously choose your convention, and (unless you have a reason not to) it is best to use one of the standard conventions.

\$\endgroup\$
3
  • \$\begingroup\$ TIL PEP 8 covers variable names. I've always defaulted to camelCase due to my history with Java. I will also happily admit my variable names are trash and need to be updated. I am planning to use the connection again later, which is why I kept everything in the with block. Wanted to improve speed first. Which is exactly what you helped me with. I'll need to read over it again to get everything, but this is great. Thank you so much! \$\endgroup\$
    – raviga151
    Commented Feb 7, 2021 at 21:39
  • \$\begingroup\$ @raviga151 It's generally considered good etiquette to hold off on accepting an answer until 24 hrs have passed since the question's posting, to give everyone (particularly people in different time zones or with different work schedules) a chance to give their feedback. Also, I don't entirely follow the PEP 8 naming conventions myself, for similar reasons. \$\endgroup\$ Commented Feb 7, 2021 at 22:06
  • \$\begingroup\$ I'll un-accept for now and wait the remaining time then. \$\endgroup\$
    – raviga151
    Commented Feb 7, 2021 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.