CODEWITHSUNDEEP
python
Steve S
Steve S

Reputation: 35

Why Python TypeError: unhashable type: 'list'

Can someone please tell me why I'm getting a TypeError: unhashable type: 'list' error on the print statement below? For some reason it doesn't like the list of data I'm inputting to the function.

from random import randint
from functools import lru_cache


data = []

[data.append(randint(1,1000000)) for i in range(1,1000000)]

data = sorted(data)

low = 0
high = len(data) + 1


target = randint(1,100000)

print(low, high, target)

@lru_cache(maxsize = 1000)
def binary_search(data, target, low, high):
    if low > high:
        return False
    
    else:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            return binary_search(data, target, low, mid+1)
        else:
            return binary_search(data, target, mid+1, high)

print(binary_search(data, target, low, high))

Upvotes: 0

Views: 2756

Answers (1)

Bakuriu
Bakuriu

Reputation: 101929

lru_cache requires the arguments to be hashable:

In [1]: from functools import lru_cache                                                                                                                                                                                                                                                  

In [2]: @lru_cache(maxsize=1000) 
   ...: def f(arg): 
   ...:     print(arg) 
   ...:                                                                                                                                                                                                                                                                                  

In [3]: f([1,2,3])                                                                                                                                                                                                                                                                       
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-3-816cce84b257> in <module>
----> 1 f([1,2,3])

TypeError: unhashable type: 'list'

This is because the implementation uses some hash table to lookup the arguments efficiently. lists are mutable and therefore cannot be hashed.

If you want to use lru_cache the arguments must be, for example, tuples instead of lists.

In your case:

print(binary_search(tuple(data), target, low, high))

should work.

Upvotes: 2

Related Questions