Python "valueless" dictionary

Question

I have a problem where I want to keep track over a large number of values. If I never encountered the value, I'll do action A, otherwise - action B. Naturally, I considered using dictionary to keep track of the values, since the lookup is fast, ~O(1).

However, dictionary is a key-value system, while all I want to take advantage of, is the key. I can assign a bogus value

"myvalue": None

but I can't help but wonder if there's a more elegant way to go about it.

Thoughts? Ideas? Thanks!

Why to add the key to the dictionary at all then? – Michael Butscher Dec 14 '19 at 16:20 — Michael Butscher, Dec 14 '19 at 16:20
Add a key - to know I've encountered it – Ruslan Dec 14 '19 at 16:22 — Ruslan, Dec 14 '19 at 16:22

Carcigenicate · Accepted Answer · 2019-12-14T16:54:09.280

3

That's what a set is for:

members = set()
members.add("mykey")
members.add("otherkey")

if "mykey" in members:
  . . .

edited Dec 14 '19 at 16:54

answered Dec 14 '19 at 16:22

Carcigenicate

43,494
9
68
117

Oh - great, that solves two problems indeed. 'in set' is implemented with a hash table right? So I can expect to get ~O(1) – Ruslan Dec 14 '19 at 16:24
1

@Ruslan It has, afaik, the same performance guarentees as dictionaries. It may even be implemented using a dictionary. In Java, iirc, their HashSet is just a HashMap that automatically maps the keys to `null`. For convenience, I wouldn't be surprised if Python does the same. – Carcigenicate Dec 14 '19 at 16:28
2

@Carcigenicate Semantically, a set is a dict with `None` values. The implementation is probably a little more streamlined, since it doesn't actually need to store the `None`s. – chepner Dec 14 '19 at 16:31

score 1 · Answer 2 · answered Dec 14 '19 at 16:23

1

If I were to stick to your dict implementation, I would:

if value in dict:
    #Action B
else:
    #Action A
    dict[value] = 1

so that you wouldn't need to save unseen values in your dict in the first place.

answered Dec 14 '19 at 16:23

wookiekim

1,156
7
20

I think that the in dict is implemented O(n), right? So I'd try to avoid that – Ruslan Dec 14 '19 at 16:26
1

@Ruslan `in` is very fast for dictionaries. You'll only get O(n) if you a massive amount of hash collisions afaik. – Carcigenicate Dec 14 '19 at 16:31
1

@Ruslan See [here](https://wiki.python.org/moin/TimeComplexity). – Carcigenicate Dec 14 '19 at 16:31
@Ruslan In Python 2, `if value in dict.keys()` would have been O(n), since `keys` just returned a list, so `list.__contains__` would have been used. `dict.__contains__` is O(1). In Python 3, even `value in dict.keys()` would be O(1), as `keys` returns a special set-like object. – chepner Dec 14 '19 at 16:33

Geeocode · Answer 3 · 2019-12-14T16:55:21.970

1

The best suited for your task is frozenset().

The frozenset type is immutable and hashable — its contents cannot be altered after it is created; it can therefore be used as a dictionary key or as an element of another set.

members = frozenset([keylist])
    if "mykey" in members:

Based on your question, this is the best suited collection form for your task in python.

edited Dec 14 '19 at 16:55

answered Dec 14 '19 at 16:37

Geeocode

5,705
3
20
34

One of the actions I do once I encounter a new value, is to update the set, so I'm not sure immutable types qualify here. I didn't specify about my "action A" or "action B" so sorry for the misunderstanding. Good to be reminded of frozen set though – Ruslan Dec 14 '19 at 16:45
@Ruslan All right, my pleasure, though if you found my answer useful you can give it an up, to help the future reader. – Geeocode Dec 14 '19 at 16:52

Python "valueless" dictionary

3 Answers3