School Assignment? Project Due Tomorrow? Chat LIVE With A Programming Expert!

Welcome to Dream.In.Code
Become an Expert!

Join 307,114 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 2,008 people online right now. Registration is fast and FREE... Join Now!




Sparse Vector to Dictionary

 

Sparse Vector to Dictionary, {len: 10, 2:5, 8:3}

reyno2ac

5 Oct, 2009 - 11:24 AM
Post #1

New D.I.C Head
*

Joined: 10 Sep, 2009
Posts: 4


My Contributions
Sorry to start another thread but I misunderstood the original problem given to us so I am trying not to get it mixed up.

I'm having a really hard time understanding how this assignment is supposed to be completed. We are supposed to take, as arguments, two sparse vectors as dictionaries and add them together. For example:
CODE

dicA = {len: 10, 2:5, 8:3} = 0, 0, 5, 0, 0, 0, 0, 0, 3, 0, 0
dicB = {len: 10, 1:4, 8:1} = 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0
A+B ={len:10, 1:4, 2:5, 8:4} = 4, 0, 5, 0, 0, 0, 0, 0, 4, 0, 0


What I think I am supposed to do is take the first dictionary and populate all the keys < len with zeros, if they do not already have a value. My question is, how do I take {len: 10, 1:4, 8:1} and turn it into [4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]?

My other thought was to make an additional step and place all the keys into a list then sort the list to be sure I was retrieving the correct element from the dictionary. Something like this:
CODE

total_dic = {}
key1, key2 = dic1.keys(), dic2.keys()

    key1.sort()
    key2.sort()
  
    i = 0
    total = []
    while i < len(key1):
        #returns total as a dictionary
        total_dic[i] = dic1[key1[i]] + dic2[key2[i]]
        i = i+1


User is offlineProfile CardPM
+Quote Post


Nallo

RE: Sparse Vector To Dictionary

5 Oct, 2009 - 05:06 PM
Post #2

New D.I.C Head
*

Joined: 19 Jul, 2009
Posts: 24



Thanked: 3 times
My Contributions
You shouldnt try to turn {len: 10, 1:4, 8:1} into [0, 4, 0, 0, 0, 0, 0, 0, 1, 0, 0]. The whole idea of storing sparse vectors in a dictionary is to avoid the memory filling zeros.

What you want to write is something like:
CODE
dicresult = {}
for i in relevant_indexes:
  dicresult[i] = dicA[i] + dicB[i]

where the relevant indexes in your example are 1,2 and 8.

Obviously this wil fail, as dicA has no key 1 (and dicB has no key 2). But dictionaries have a method to check, whether a key is present: dicA.has_key(1) will be false, dicA.has_key(2) will be true.

So you can test if dicA or dicB have a key i before you write an expression like dicA[i] + dicB[i].
User is offlineProfile CardPM
+Quote Post

reyno2ac

RE: Sparse Vector To Dictionary

5 Oct, 2009 - 06:52 PM
Post #3

New D.I.C Head
*

Joined: 10 Sep, 2009
Posts: 4


My Contributions
I know there are probably much better ways to go about solving this problem but here is what I came up with.
CODE

def sparse_add(vec1, vec2):
    dic1 = {}
    dic2 = {}
    temp_dic = {}
    total_dic = {}

    a = 0
    while a < vec1['len']:
        if a in vec1:
            dic1[a] = vec1[a]
        else:
            dic1[a] = 0
        a += 1
    
    b = 0
    while b < vec2['len']:
        if b in vec2:
            dic2[b] = vec2[b]
        else:
            dic2[b] = 0
        b +=1

    c = 0
    while c < len(dic2):
        temp_dic[c] = dic1[c] + dic2[c]
        c += 1
    
    d = 0
    while d < len(dic2):
        if temp_dic[d] > 0:
            total_dic[d] = temp_dic[d]
        else:
            pass
        d += 1

    print 'The sparse dictionary is:', total_dic

if __name__ == '__main__':
    sparse_add({'len':10, 0:8, 4:5, 2:7}, {'len':10, 7:3, 4:2, 9:9})


This seems to work.

Now, does anyone know how to write a nose test to test the program? I have no idea where to even begin with that blink.gif
User is offlineProfile CardPM
+Quote Post

Fast ReplyReply to this topicStart new topic

Time is now: 11/21/09 01:20PM

Live Help!

Be Social

Dream.In.Code RSS Feed Dream.In.Code LinkedIn Group Follow Us On Twitter Fan Us On Facebook

Tutorials

Programming

Web Development

Reference Sheets

Code Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month