3 ms·
Ask YC: Any resources on the complexity of built in type methods in Python?
I'd like to know the complexity of functions on built in types in Python. O() notation is perfect.
Empirical tests would also be good.
This came up recently in a Twitter conversation (I'm @tipjoy) about eliminating duplicates in a list. I like using dictionaries:
def dupe(aList):
d={}
for x in aList:
d[x] = True
# or to count: d[x] = d.get(x,0) + 1
return d.keys()
Compare this to an alternative using the list count method:
def dupe(aList):
f=[]
for x in aList:
if not f.count(x):
f.append(x)
ret f
I think N hash lookups are probably faster than N calls to count, but I don't actually know. The difference could be small enough that doing what you think looks better is all that matters.
Anyone know a good resource?
What about for other languages?
- earle 19y agothat's what sets are for. >>> list(set(['1', '2', '3', '1'])) ['1', '3', '2']
- ivankirigin 19y agoCool More often than not, I do want the count though. I would be surprised if a set didn't use the exact same hashing subroutines that a dict uses. Am I wrong?
- MarkTwinia 19y agoYes, but as gp said, don't bother yourself with these details.
- bootload 19y ago"... list(set(['1', '2', '3', '1'])) ..." Nice earle. That's what I've come to expect from python. There is always a shorter better way. The only difference I've found is the returned list is sorted & broke my test suite. Here's the docs & PEP. - http://docs.python.org/lib/module-sets.html http://docs.python.org/lib/module-sets.html - http://www.python.org/dev/peps/pep-0218/ http://www.python.org/dev/peps/pep-0218/ Thx @Tipjoy for posting this or I'd still be using a 4-6 line clunker.
- gms 19y agoHow about list(set(aList)) ? Anyway, to answer your question, look in the Python FAQ at http://www.python.org/doc/faq/general/ http://www.python.org/doc/faq/general/ But really, you shouldn't care about this sort of thing, until it actually matters.
- ivankirigin 19y agoYou're right, don't do this till it matters. But even in profiling and optimizing, the first steps are algorithmic. If you can't change the "outer loop" algorithm, you'll probably look into things like this.
- earle 19y agoIf you don't have set (< python 2.4): def distinct(l): d = {} map(setitem, (d,)*len(l), l, []) return d.keys()