Construction of 5 level tree structure in python

Question

i want to reduce the number of times i hit the data base to retrieve data. So i think taking entire data into a tree will increase the performance of the system as i will not be hitting the database frequently.

I am a beginner in python, so please do help and advice me in creating the tree structure.

That's a pretty open-ended question. Are you looking to pull the whole database into a tree? Store recent lookups in a tree? There are multiple kinds of tree data structures. Which one were you planning on using? Why 5 levels? In a binary tree, that's only 31 values. — JerseyMike, Mar 27 '12 at 12:47
This link might help: http://stackoverflow.com/questions/2358045/how-can-i-implement-a-tree-in-python-are-there-any-built-in-data-structures-in — Jack_of_All_Trades, Mar 27 '12 at 12:48
hi JerseyMike, i am trying to pull the whole database into a tree. do u have any idea or better solution, me bit confused here.... — shiva, Mar 27 '12 at 13:03
Ok, how many entries are in the database, what kind of data is in the records and how do you identify a particular record? These kinds of things are important when choosing the correct data structure. — JerseyMike, Mar 27 '12 at 13:06
Without seeing your database or your code that uses the database, it's hard to help you. But generically, if you are making lots of small queries, you may get a large performance gain by consolidating the small queries into one large query. — Li-aung Yip, Mar 27 '12 at 13:09
You also haven't given us a measure of how long execution of your program is taking, and how fast you would like it to be. If it's already fast enough, and you are just doing this because "I want to make it faster", then that's *premature optimisation*. — Li-aung Yip, Mar 27 '12 at 13:10
my data is divided as Menu(Root)->category->subcategory->items->items attributes. This is restaurant food menu data. i want whole data at the initial start of the program — shiva, Mar 27 '12 at 14:46
Now I understand what you want. I believe that Janne is correct. You will want to use nested dictionaries. I'll try to put together a quick example. — JerseyMike, Mar 27 '12 at 15:14

Janne Karila · Accepted Answer · 2012-03-27T19:01:39.593

1

You can use nested dictionaries. Nested means that the value of a key:value pair can be another dictionary.

JerseyMike has given a nice example, I just want to point out that his addItemAttributes function is equivalent to the more concise

def addItemAttributes(tree, idList):
    (menu, cat, subcat, item, attribs) = idList;

    currDict = tree.setdefault(menu, {})\
        .setdefault(cat, {})\
        .setdefault(subcat, {})\
        .setdefault(item, {})

    for a in attribs:
        currDict[a[0]] = a[1]

...and that you might like to wrap getItemAttributes in a try block so you can deal with the case that one of the keys is missing, eg.

try:
    getItemAttributes(...)
except KeyError:
    #key was incorrect, deal with the situation

edited Mar 27 '12 at 19:01

answered Mar 27 '12 at 13:03

Janne Karila

24,266
6
53
94

hi JerseyMike,i don't have data in dictionary i have data in the form of tuples with in the list.so for that how can i construct a tree – shiva Mar 28 '12 at 03:59
@shiva Add some example data to your question. – Janne Karila Mar 28 '12 at 05:45
@shiva, yes, please give us an example of your tuples from menu to item_attribute. The dictionary is what you will be producing. We realize that you aren't starting with your data in a dictionary. – JerseyMike Mar 28 '12 at 13:37
@Janne, I like your consolidation of the addItemAttributes. I was going to implement it as "currDict = reduce(lambda tr, dt: tr.setdefault(dt, {}), idList[:-1])". This makes the function able to handle any depth. However, I didn't want to throw shiva into the Python deep end. ;) – JerseyMike Mar 28 '12 at 14:05

score 0 · Answer 2 · edited Dec 08 '13 at 16:07

I'm putting this together on the fly since I don't have my Python interpreter handy. Here are two functions for populating and reading from the nested dictionary structures. The first parameter passed to each is the base dictionary that will hold all of your menu information.

This function is used to add to the dictionaries. This function can be probably be more efficient, code-wise, but I wanted you to understand what was going on. For each item of each subcategory of each category of menu, you will need to construct a list of the attributes to pass in.

# idList is a tuple consisting of the following elements:
#    menu: string   - menu name
#    cat: string    - category name
#    subcat: string - subcategory name
#    item: string   - item name
#    attribs: list  - a list of the attributes tied to this item in the form of
#                     [('Price', '7.95'),('ContainsPeanuts', 'Yes'),('Vegan', 'No'),...].
#                     You can do the attribs another way, this was convenient for
#                     the example.

def addItemAttributes(tree, idList):
    (menu, cat, subcat, item, attribs) = idList;

    if not tree.has_key(menu):  # if the menu does not exist...
        tree[menu] = {}         # Create a new dictionary for this menu
    currDict = tree[menu]       # currDict now holds the menu dictionary

    if not currDict.has_key(cat): # if the category does not exist...
        currDict[cat] = {}        # Create a new dictionary for this category
    currDict = currDict[cat]      # currDict now holds the category dictionary

    if not currDict.has_key(subcat): # if the subcategory does not exist...
        currDict[subcat] = {}        # Create a new dictionary for this subcategory
    currDict = currDict[subcat]      # currDict now holds the subcategory dictionary

    if not currDict.has_key(item): # if the category does not exist...
        currDict[item] = {}        # Create a new dictionary for this category
    currDict = currDict[item]      # currDict now holds the category dictionary

    for a in attribs
        currDict[a(0)] = a(1)

The function to read from the nested structure is easier to follow:

# Understand that if any of the vaules passed to the following function
# have not been loaded, you will get an error.  This is the quick and
# dirty way.  Thank you to Janne for jarring my mind to the try/except.

def getItemAttributes(tree, menu, cat, subcat, item):
    try:
        return tree[menu][cat][subcat][item].items()
    except KeyError:
        # take care of missing keys

I hope this helps. :)

Construction of 5 level tree structure in python

2 Answers2