Python: Check the occurrences in a list against a value

lst = [1,2,3,4,1]

I want to know 1开发者_如何学Python occurs twice in this list, is there any efficient way to do?

lst.count(1) would return the number of times it occurs. If you're going to be counting items in a list, O(n) is what you're going to get.

The general function on the list is list.count(x), and will return the number of times x occurs in a list.

Are you asking whether every item in the list is unique?

len(set(lst)) == len(lst)

Whether 1 occurs more than once?

lst.count(1) > 1

Note that the above is not maximally efficient, because it won't short-circuit -- even if 1 occurs twice, it will still count the rest of the occurrences. If you want it to short-circuit you will have to write something a little more complicated.

Whether the first element occurs more than once?

lst[0] in lst[1:]

How often each element occurs?

import collections
collections.Counter(lst)

Something else?

For multiple occurrences, this give you the index of each occurence:

>>> lst=[1,2,3,4,5,1]
>>> tgt=1
>>> found=[]
>>> for index, suspect in enumerate(lst):
...     if(tgt==suspect):
...        found.append(index)
...
>>> print len(found), "found at index:",", ".join(map(str,found))
2 found at index: 0, 5

If you want the count of each item in the list:

>>> lst=[1,2,3,4,5,2,2,1,5,5,5,5,6]
>>> count={}
>>> for item in lst:
...     count[item]=lst.count(item)
...
>>> count
{1: 2, 2: 3, 3: 1, 4: 1, 5: 5, 6: 1}

def valCount(lst):
    res = {}
    for v in lst:
        try:
            res[v] += 1
        except KeyError:
            res[v] = 1
    return res

u = [ x for x,y in valCount(lst).iteritems() if y > 1 ]

u is now a list of all values which appear more than once.

Edit:

@katrielalex: thank you for pointing out collections.Counter, of which I was not previously aware. It can also be written more concisely using a collections.defaultdict, as demonstrated in the following tests. All three methods are roughly O(n) and reasonably close in run-time performance (using collections.defaultdict is in fact slightly faster than collections.Counter).

My intention was to give an easy-to-understand response to what seemed a relatively unsophisticated request. Given that, are there any other senses in which you consider it "bad code" or "done poorly"?

import collections
import random
import time

def test1(lst):
    res = {}
    for v in lst:
        try:
            res[v] += 1
        except KeyError:
            res[v] = 1
    return res

def test2(lst):
    res = collections.defaultdict(lambda: 0)
    for v in lst:
        res[v] += 1
    return res

def test3(lst):
    return collections.Counter(lst)

def rndLst(lstLen):
    r = random.randint
    return [r(0,lstLen) for i in xrange(lstLen)]

def timeFn(fn, *args):
    st = time.clock()
    res = fn(*args)
    return time.clock() - st

def main():
    reps = 5000

    res = []
    tests = [test1, test2, test3]

    for t in xrange(reps):
        lstLen = random.randint(10,50000)
        lst = rndLst(lstLen)
        res.append( [lstLen] + [timeFn(fn, lst) for fn in tests] )

    res.sort()
    return res

And the results, for random lists containing up to 50,000 items, are as follows: (Vertical axis is time in seconds, horizontal axis is number of items in list)

Another way to get all items that occur more than once:

lst = [1,2,3,4,1]
d = {}
for x in lst: 
    d[x] = x in d
print d[1] # True
print d[2] # False
print [x for x in d if d[x]] # [1]

You could also sort the list which is O(n*log(n)), then check the adjacent elements for equality, which is O(n). The result is O(n*log(n)). This has the disadvantage of requiring the entire list be sorted before possibly bailing when a duplicate is found.

For a large list with a relatively rare duplicates, this could be the about the best you can do. The best way to approach this really does depend on the size of the data involved and its nature.