0

I want to count the number of items in a dictionary with the given value (suppose the value in dictionary is just number), I've searched online and find two approaches, the first one:

sum(x == chosen_value for x in d.values())

the second approach is using Counter in Collections module.

However, I think the running time of both approaches is O(N), where N is the total number of items in the dictionary. I want to find out a way to do this in O(logN), is it possible?

Thanks in advance for any help and suggestion!

Update:

Thanks for all the quick reply! It cannot be done in O(logN). I may use binary tree to store the (key,value) pairs instead.

Community
  • 1
  • 1
mitchelllc
  • 1,607
  • 4
  • 20
  • 24
  • 1
    What makes you think that it can be done in `log n`? – Jeff Mercado Sep 08 '13 at 23:46
  • 2
    I think there is no way, You'll need to check every value in the dictionary anyway. – alecxe Sep 08 '13 at 23:46
  • 2
    You cannot do that with a standard dictionary, because you can only access the values as a list; you'd have to convert to a tree structure instead, which requires you first to list the values; a O(N) operation.. – Martijn Pieters Sep 08 '13 at 23:46
  • 4
    You need a tree structure to do this in O(log n) or if you want to do it in O(1) just use another "counter" dictionary where the keys are the values for your current dictionary and the values are the counts. o_O But obviously without taking the time to create another structure, you can't do this in O(log n) – Shashank Sep 08 '13 at 23:47

3 Answers3

5

No. Why would you expect it to be possible? It might be if you had a binary search tree, but dicts are unordered, so you have to iterate through the values.

user2357112
  • 260,549
  • 28
  • 431
  • 505
2

You have to read every value in a given dictionary if you have no prior knowledge of these values, which is the normal case. So in the usual case, it has to be O(N).

Paul Evans
  • 27,315
  • 3
  • 37
  • 54
0

You could maintain another dictionary which maps values to count. That would give you the counts that you seek in O(1). The idea would be to implement a higher order data structure that acts like a dictionary, but adds the capability to return counts for values by maintaining another dictionary internally.

I realize that this is probably not what you are asking. Just putting it out there, just on the off chance.

Ziffusion
  • 8,779
  • 4
  • 29
  • 57