0

Can we write a data structure which will search directly by taking the values in O(1) time?

For example, in this code in python3, we can get morse code by taking the keys and output the values.

    morse={'A':'.-','B':'-...','C':'-.-.','D':'-..','E':'.',\
           'F':'..-.','G':'--.','H':'....','I':'..','J':'.---',\
           'K':'-.-','L':'.-..','M':'--','N':'_.','O':'---',\
           'P':'.--.','Q':'--.-','R':'.-.','S':'...','T':'-',\
           'U':'..-','V':'...-','W':'.--','X':'-..-','Y':'-.--',\
           'Z':'--..','1':'.---','2':'..---','3':'...--','4':'....-',\
           '5':'.....','6':'-....','7':'--...','8':'---..','9':'----.',\
           '0':'----'}
    n=input()
    n=''.join(i.upper() for i in n if i!=' ')
    for i in n:
        print(morse[i],end=' ')

This gives the output:

    >>> 
    S O S
    ... --- ...

If we want to search by taking the morse code as input and giving the string as output:

    >>> 
    ... --- ... 
    S O S

how do we do that without making another dictionary of morse code?

Please provide the proper reasoning and what are the limitations if any.

hungry_python
  • 13
  • 1
  • 6
  • 1
    Please do your own homework – kylieCatt Oct 23 '15 at 06:48
  • @IanAuld I believe this is a genuine question as similar questions on SO only seem to suggest workarounds but do not clearly state why the problem occurs and why it is difficult to find a reasonable solution to it. – Swastik Padhi Oct 23 '15 at 07:03
  • @IanAuld That's not my homework. It is a question asked out of curiosity while trying a random code. :) – hungry_python Oct 23 '15 at 08:59
  • @OP: you mentioned in a comment elsewhere in the answers that you would also be satisfied with other data structures. This leaves you the option to write your own two-way dictionary that internally keeps two ordinary dicts and keeps key-value relations on both directions. Note though that this is not a common data structure because of the uniqueness reasons given in the various answers. – mike3996 Oct 23 '15 at 09:41
  • 1
    This might be the only option left. – hungry_python Oct 23 '15 at 10:00

4 Answers4

1

Python dictionaries are hashmaps behind the scenes. The keys are hashed to achieve O(1) lookups. The same is not done for values for a few reasons, one of which is the reason @CrakC mentioned: the dict doesn't have to have unique values. Maintaining an automatic reverse lookup would be nonconsistent at best. Another reason could be that fundamental data structures are best kept to a minimum set of operations for predictability reasons.

Hence the correct & common pattern is to maintain a separate dict with key-value pairs reversed if you want to have reverse lookups in O(1). If you cannot do that, you'll have to settle for greater time complexities.

mike3996
  • 17,047
  • 9
  • 64
  • 80
  • Thanks. That means we always have to settle with other dictionary of values: key for O(1). – hungry_python Oct 23 '15 at 09:14
  • Thanks for adding this part, I forgot to mention that the values should be hashable. – Swastik Padhi Oct 23 '15 at 09:14
  • @hungry_python Actually, you should avoid reversing dictionaries altogether. Might lead to ambiguity. – Swastik Padhi Oct 23 '15 at 09:17
  • Yes and that might take more time reversing the whole thing. – hungry_python Oct 23 '15 at 09:19
  • @CrakC: by 'reversing dicts' do you mean they shouldn't be constructed (as needed by the problem at hand) or iterating them 'by values'? – mike3996 Oct 23 '15 at 09:19
  • 1
    @hungry_python: if you truly need a two-way lookup with data you know is unique either way, there's no shame in making an inverse dict. Reversing it is a one-time O(n) operation and after that you have O(1) lookups either way – mike3996 Oct 23 '15 at 09:21
  • yes this is mentioned all over the SO, no alternate solution is provided for this problem. – hungry_python Oct 23 '15 at 09:23
  • @progo I mean, they should not be constructed. Moreover, to know that the `values` in a `dict` are unique would require more loops, increasing the time complexity by `O(n*logn)`. – Swastik Padhi Oct 23 '15 at 09:25
  • @CrakC: just for curiosity's sake: how would you make an alphabet-morse-alphabet translator that makes character transformations in (amortized) O(1) time? – mike3996 Oct 23 '15 at 09:28
  • Now the topic becomes debatable. :D – hungry_python Oct 23 '15 at 09:30
  • @progo I am afraid, I could not understand your question. Is it about the same implementation as shown by the OP?? – Swastik Padhi Oct 23 '15 at 09:42
0

As CrakC has correctly stated it is not possible to get the key from the dictionary in O(1) time, you will need to traverse the dictionary once in O(n) time in order to search for the key in the dictionary. As you do not want to create another dictionary this would be your only option.

Rahul Nori
  • 698
  • 6
  • 17
  • Just because it is programmatically possible to invert a dictionary, it should not be preferred. The inverse is only possible if the values in a dictionary are unique in nature and to ensure that, you would need another algorithm that runs in O(n*logn) time on an average. Ans yes, speed is a concern for the OP as mentioned above. – Swastik Padhi Oct 23 '15 at 05:18
  • 1
    @CrakC where did he mention speed is a concern? Just because he doesn't want to make another dictionary doesn't mean he wants to save time, it could be to save space too. – Rahul Nori Oct 23 '15 at 05:26
  • Did you read the title of the question? Did you read the first line of the question? Do you understand what O(1) time means? – Swastik Padhi Oct 23 '15 at 05:42
  • @CrakC I apologize for the haste. I need to read the question more properly from the next time. – Rahul Nori Oct 23 '15 at 06:28
0

Can we write a data structure which will search directly by taking the values in O(1) time?

The answer to that question would be yes, and it's a HasMap or HashTable.

Following your example, what actually happens there is that Python Dictionaries are implemented as HashMap's. From that follows that search complexity is O(1) but, as I understand, your real problem is how to search the key by the value in O(1) too. Well, being dictionaries implemented as hashmaps, if Python provided (I am not 100% sure it doesn't) that reverse searching functionality it wouldn't be O(1) because HashMaps are not designed to provide it. It can be shown looking at how HashMaps work: you would need a hashing function which would map the key and the value to the same index in the array which, if not impossible, is pretty hard to do.

I guess that your best option is to define de inverse dictionary. It's not that uncommon to sacrifice memory to achieve better times.

Community
  • 1
  • 1
fnocetti
  • 243
  • 1
  • 9
  • I think you contradicted your words- 'The answer to that question would be yes, and it's a HasMap or HashTable.' and 'because HashMaps are not designed to provide it'. Please state a clear point. – Swastik Padhi Oct 23 '15 at 05:07
  • What I mean is that dictionaries are designed to do searches (of values) in O(1), as first asked, but not to do O(1) searches of keys, as the code example implied. – fnocetti Oct 23 '15 at 21:35
0

Yes, getting the name of the key from its value in a dictionary is not possible in python. The reason for this is quite obvious. The keys in a dictionary are unique in nature i.e., there cannot be two entries in the dictionary for the same key. But the inverse is not always true. Unique keys might have non-unique values. It should be noted here that the immutable nature of the keys actually defines the structure of the dictionary. Since they are unique in nature, they can be indexed and so fetching the value of a given key executes in O(1) time. The inverse, as explained above, cannot be realized in O(1) time and will always take an average time of O(n). The most important point that you should know here is that python dictionaries are not meant to be used this way.

Further reading: http://stupidpythonideas.blogspot.in/2014/07/reverse-dictionary-lookup-and-more-on.html

Swastik Padhi
  • 1,849
  • 15
  • 27
  • Thanks. I am aware of reversing the dictionary and yes that takes O(n) time, that's why I asked if anyone has implemented any data structure to reduce this time. Anyone at this point I have to settle with making another dictionary. :) – hungry_python Oct 23 '15 at 08:56
  • Do accept the answer that solved your problem so that the question can be closed – Swastik Padhi Oct 23 '15 at 09:00
  • Accepted. I don't think anything more can be said on this topic. – hungry_python Oct 23 '15 at 09:20