# Sparse Vector to Dictionary

Page 1 of 1

## 2 Replies - 2262 Views - Last Post: 05 October 2009 - 07:52 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=130063&amp;s=7ace2c1a98550a9d5710c72ace1921cb&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 reyno2ac

Reputation: 0
• Posts: 4
• Joined: 10-September 09

# Sparse Vector to Dictionary

Posted 05 October 2009 - 12:24 PM

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:
```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:
```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

```

Is This A Good Question/Topic? 0

## Replies To: Sparse Vector to Dictionary

### #2 Nallo

• D.I.C Regular

Reputation: 163
• Posts: 257
• Joined: 19-July 09

## Re: Sparse Vector to Dictionary

Posted 05 October 2009 - 06:06 PM

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:
```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].

### #3 reyno2ac

Reputation: 0
• Posts: 4
• Joined: 10-September 09

## Re: Sparse Vector to Dictionary

Posted 05 October 2009 - 07:52 PM

I know there are probably much better ways to go about solving this problem but here is what I came up with.
```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