1
\$\begingroup\$

I have 1000 dictionaries (grid_1, grid_2.... grid_1000) stored as pickle objects and one original dictionary that I need to compare each of these 1000 dictionaries to. The 1000 dictionaries are generated by a process. My algorithm has below steps:

grid_1 example : {'143741': {'467457':1,'501089':2,'903718':1,'999216':5,'1040952':2},'281092':{'1434': 67,'3345': 345}, '33123': {'4566':5,'56788':45}}

grid_2 example : {'143741': {'467457':5,'501089':7,'1040952':9},'281092':{'1434': 67,'3345': 20}, '33123': {'4566':7,'56788':38}}

grid_density_original : {'143741': {'467457':1,'501089':2,'903718':1,'999216':5,'9990':4},'281092':{'1434': 60,'3345': 3,'9991': 43}, '33123': {'56788':4}}

intersect_1 b/w grid_1 and grid_density_original : {'143741': {'467457':1,'501089':2,'903718':1,'999216':5},'281092':{'1434': 67,'3345': 345}, '33123': {'56788':45}

intersect_2 b/w grid_2 and grid_density_original : {'143741': {'467457':5,'501089':7},'281092':{'1434': 67,'3345': 20}, '33123': {'56788':38}}

combine step b/w intersect_1, intersect_2 (slow parts as inner list size increases each time): combine12 : {'143741': {'467457':[1,5],'501089':[2,7],'903718':[1,99999],'999216':[5,99999]},'281092':{'1434': [67,67],'3345': [345,20]}, '33123': {'56788':[45,38]}

  1. read each of 1000 grids sequentially and find intersection between each grid i.e. grid_1 and original_grid. Store all 1000 intersections. (intersect_1, intersect_2....intersect_1000)
  2. Take intersect_1 dictionary and merge common keys values into a list with next intersect_2. Until all 1000 intersects are completed.

Current steps are very slow for dictionary with big size ~10,000+ keys: took 4 days for below code to complete. Combine step very slow

from collections import defaultdict
from collections import Counter
import pickle
import gc
import copy
import pickle
import scipy.stats as st
from collections import defaultdict


# grid_density_orignal is original nested dictionary we compare each of 1000 grids to: 
with open('path\grid_density_original_intercountry.pickle','rb') as handle:
    grid_density_orignal = pickle.load(handle,encoding ='latin-1')  

    
# Previous process generated 1000 grids and dump them as .pickle files : grid_1,grid_2....grid_1000 

for iteration in range(1,1001):
    # load each grid i.e.grid_1,grid_2...grid_1000 into memory sequentially 
    filename = 'path\grid_%s' %iteration
    with open(filename,'rb') as handle:
        globals()['dictt_%s' % iteration] = pickle.load(handle,encoding ='latin-1') 
        
    # Counter to store grid-grids densities: same dictionary structure as grid_density_orignal
    globals()['g_den_%s' % iteration] = defaultdict(list)
    for k,v in globals()['dictt_%s' % iteration].items():
        globals()['g_den_%s' % iteration][k] = Counter(v)
     
    # here we find the common grid-grid connections between grid_density_orignal and each of the 1000 grids
    globals()['intersect_%s' % iteration] = defaultdict(list)
    for k,v in grid_density_orignal.items():
        pergrid = defaultdict(list)
        common_grid_ids = v.keys() & globals()['g_den_%s' % iteration][k].keys()
        for gridid in common_grid_ids:
            pergrid[gridid] = globals()['g_den_%s' % iteration][k][gridid]
        globals()['intersect_%s' % iteration][k] = pergrid

    
print('All 1000 grids intersection done')


# From previous code we now have 1000 intersection grids : intersect_1,intersect_2 ...... intersect_1000
for iteration in range(1,1000):

    itnext = iteration +1         # to get next intersect out of 1000
    globals()['combine_%s%s' %(iteration,itnext)] = defaultdict(list)  # dictionary to store intermediate combine step results between 2 intersects : intersect_x and intersect_x+1
    
    
  
   
    for k,v in globals()['intersect_%s' %iteration].items():
        innr = []
        combine = defaultdict(list)
        for key in set(list(globals()['intersect_%s' % iteration][k].keys())+ list(globals()['intersect_%s' % itnext][k].keys())):  # key in the union of intersect_1 , intersect_2
            
            if (isinstance(globals()['intersect_%s' % iteration][k].get(key,99999), int) and isinstance(globals()['intersect_%s' % itnext][k].get(key,99999), int)): # get key value if exists, if for e.g. a certain grid doesnt exist in intersect_1, intersect_2 we give it default of 99999 as placeholder, alos check if value is an instance of int or list as in intial step it is an int but later we get lists after combining every 2 intersects 
                
                
                combine[key] = [globals()['intersect_%s' % iteration][k].get(key,99999)] + [globals()['intersect_%s' % itnext][k].get(key,99999)]   # combine into list intersect_1, intersect_2
                
            
            if (isinstance(globals()['intersect_%s' % iteration][k].get(key,99999), list) and isinstance(globals()['intersect_%s' % itnext][k].get(key,99999), int)): # this condition will be reached after initial step of intersect_1 + intersect_2
                
                combine[key] = globals()['intersect_%s' % iteration][k].get(key,99999) + [globals()['intersect_%s' % itnext][k].get(key,99999)]    # combine into list intersect_1, intersect_2

                
        globals()['combine_%s%s' %(iteration,itnext)][k] = combine
        
    globals()['intersect_%s' % itnext] = copy.copy(globals()['combine_%s%s' %(iteration,itnext)])   # copy combine dict onto intersect dict so we can continue combining this dict with the next iteration

    print('2 combined: ',iteration,itnext)
    del globals()['intersect_%s' % iteration]                      # delete older intersect, combine as we dont need them and may cause memory overflow when more dicts are in memory
    del globals()['combine_%s%s' %(iteration,itnext)]
    gc.collect()                                                   # explicitly call the garbage collector as too big for ram

            
   
print('intersection and combine done')  # at the end we have intersect_1000 with is a dict with all grid_id ids as keys and a list of densities (list size is 1000 corresponding to 1000 grids)
\$\endgroup\$
4
  • \$\begingroup\$ If you care about performance, this place in the pipeline is the wrong place to start. Decisions earlier in the pipeline about disk persistence and dictionary representation need to be changed. If it's feasible to include the dictionary generation code here, do so; otherwise any improvements you get in review will be pig cosmetics. \$\endgroup\$
    – Reinderien
    Feb 15, 2022 at 17:26
  • \$\begingroup\$ @Reinderien While I do agree I could have chosen a different appraoch instead of generating 1000 dictionaries pickle files. That part of the code takes 5-6 days to complete and unfortunately cannot be re-run. I would like to decrease this post processing step from 4 days to something lesser. \$\endgroup\$
    – skynaive
    Feb 15, 2022 at 17:28
  • \$\begingroup\$ You said there are ~10,000+ keys in the dicts. The grids are nested dicts. Are you saying that there are ~10,000 total points in the grid, or that the top level dict has ~10,000 keys? If the later, how many total points are in each grid? \$\endgroup\$
    – RootTwo
    Feb 17, 2022 at 5:52
  • \$\begingroup\$ Top level keys are 10,000+ But inner nested keys have variable size. Can be anything from 100 - 10,000 \$\endgroup\$
    – skynaive
    Feb 17, 2022 at 15:04

1 Answer 1

5
\$\begingroup\$

Don't organize programs around global variables. It's one of the worst things you can do to make software more complex, harder to debug, and less amendable to evolution over time. Among other things, this prohibition means that one almost never needs to use the global keyword or the globals() function in a Python program.

Instead, organize programs around functions that receive and return data. The benefits of this approach are wide ranging.

Parameterize your scripts. You current program is hard-coded to expect 1000 pickle files and, as you note, it's very slow. A program in that state is extremely difficult to debug and modify because every execution of the program is a huge ordeal: it's sort of like submitting punch cards at night and waiting until morning to see whether the mainframe accepted them. But scripts can receive inputs in various ways: command-line arguments, configuration files, or environment variables, to name the common examples. One of those inputs could be an integer telling the program to execute on a tiny subset of the pickle data. A small tweak like that would provide immediate practical benefits.

If you find yourself numbering your variables, you probably need a collection. Instead of spawning variables like grid_1, grid_2, grid_3, etc, focus on how you could organize the code in terms of a collection of grids.

When asking programming questions, provide people with a convenient way to execute the code. If we can't run your code easily, we can't understand it as well. For this reason, I won't really be reviewing your program specifically. Instead I'll try to provide a demo that implements roughly similar dict manipulations without trying too hard to mimic your program exactly.

Create a script entry point that takes arguments from command line. Instead of having to process 1000 grids, we can process a subset. That's great for debugging and iterative development as you improve things.

import sys

def main(args):
    n_grids = int(args[0])
    ...

if __name__ == '__main__':
    main(sys.argv[1:])

Load the grids into a collection. I don't have your pickle files, so I'll simulate them via a global constant. Your implementation of load_grids() will be different than mine in the sense that it will traverse the file system, loading pickle files into a list.

GRIDS_ON_DISK = [
    {
        '143741': {'467457': 1, '501089': 2, '903718': 1, '999216': 5, '1040952': 2},
        '281092': {'1434': 67, '3345': 345},
        '33123': {'4566': 5, '56788': 45},
    },
    {
        '143741': {'467457': 5, '501089': 7, '1040952': 9},
        '281092': {'1434': 67, '3345': 20},
        '33123': {'4566': 7, '56788': 38},
    },
    {
        '143741': {'467457': 55, '501089': 77, '1040952': 99},
        '281092': {'1434': 67, '3345': 2220, '77777': 77},
        '33123': {'4566': 7, '56788': 38, '919191': 911},
    },
]

def main(args):
    n_grids = int(args[0]) if args else len(GRIDS_ON_DISK)
    grids = load_grids(n_grids)
    ...

def load_grids(n_grids):
    return [
        GRIDS_ON_DISK[i]
        for i in range(n_grids)
    ]

Compute the intersections. We now have a list of grids. The next step is to create a parallel list of dicts representing the intersection of those dicts against the original reference point. As before, we're going to use a data-oriented function to do the work.

GRID_DENSITY_ORIGINAL = {
    '143741': {'467457':1, '501089':2, '903718':1, '999216':5, '9990':4},
    '281092': {'1434': 60, '3345': 3, '9991': 43},
    '33123': {'56788':4, '919191': 91},
}

def main(args):
    # Same as before.
    ...

    intersections = [
        dict_intersection(g, GRID_DENSITY_ORIGINAL)
        for g in grids
    ]

def dict_intersection(d, orig):
    return {
        kout : {
            kin : d[kout][kin]
            for kin in orig_inner
            if kin in d[kout]
        }
        for kout, orig_inner in orig.items()
        if kout in d
    }

Combine the dicts. Again, we'll use a function. There will be no need to mess around with spawning or deleting global variables. The function will take its input, do its work, and return the result as data.

# Don't sprinkle magic values throughout your code.
# Instead, declare them as named constants.
# This allows you to change your mind later.
MISSING = 99999

def main(args):
    # Same as before.
    ...

    combo = combine_dicts(intersections, default = MISSING)

def key_union(dicts):
    s = set()
    for d in dicts:
        s.update(d)
    return s

def combine_dicts(dicts, default = None):
    combo = {}
    for kout in key_union(dicts):
        combo[kout] = {}
        inners = [d[kout] for d in dicts if kout in d]
        for kin in key_union(inners):
            combo[kout][kin] = [d.get(kin, default) for d in inners]
    return combo

After the program finishes, combo looks like this. This is different than what your code currently does (as best I can tell). Nonetheless, I think you would benefit from trying to apply this function-oriented approach to your current program. After that, if there are still performance problems, come back with a more focused question.

{
    '143741': {
        '467457': [1, 5, 55],
        '903718': [1, 99999, 99999],
        '999216': [5, 99999, 99999],
        '501089': [2, 7, 77],
    },
    '281092': {
        '3345': [345, 20, 2220],
        '1434': [67, 67, 67],
    },
    '33123': {
        '919191': [99999, 99999, 911],
        '56788': [45, 38, 38],
    },
}
\$\endgroup\$

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.