[Tutor] how to understand unhashable type: 'list'

[Steven D'Aprano]

lina wrote:
> list1
> [['61', '34', '61', '34'], ['61', '35', '61', '70', '61'], ['61',
> '70', '61', '34'], ['34', '58', '34', '58']]

You have a list of lists.


>>>> weight={}
>>>> weight{list1[0]}=1
> SyntaxError: invalid syntax

In Python, {} are used for dicts, and in Python 3, sets. They aren't 
used for anything else. obj{...} is illegal syntax.


>>>> weight[list1[0]]=1
> 
> Traceback (most recent call last):
>   File "<pyshell#292>", line 1, in <module>
>     weight[list1[0]]=1
> TypeError: unhashable type: 'list'

You are trying to store a list as a key inside a dict. This cannot be 
done because lists (like all mutable types) can't be hashed.

If your list of lists is small, say, less than a few thousand items, it 
would be fast enough to do this:

counts = []
seen = []
for sublist in list1:
     if sublist in seen:
         # No need to do it again.
         continue
     seen.append(sublist)
     counts.append( (sublist, list1.count(sublist)) )


If I run this code on your list1, I get these counts:

[(['61', '34', '61', '34'], 1), (['61', '35', '61', '70', '61'], 1), 
(['61', '70', '61', '34'], 1), (['34', '58', '34', '58'], 1)]


That is, each list is unique.

However, if you have many thousands of items, the above may be too slow. 
It is slow because of all the linear searches: "sublist in seen" 
searches seen for the sublist, one item at a time, and 
"list1.count(sublist)" searches list1 for sublist, also one item at a 
time. If there are many items, this will be slow.

To speed it up, you can do this:

(1) Keep the seen list sorted, and use binary search instead of linear 
search. See the bisect module for help.

(2) Sort list1, and write your own smarter count() function that doesn't 
have to travel along the entire list.


All that involves writing a lot of code though. Probably much faster 
would be to make a temporary copy of list1, with the inner lists 
converted to tuples:


list2 = [tuple(l) for l in list1]
counts = {}
for t in list2:
     counts[t] = 1 + counts.get(t, 0)

for t, n in counts.items():
     print list(t), n


-- 
Steven