speed diff between set and list

tags: learning diff-between programming

content

task: finding a user in a list

using list

def find_user(user, users: List):
	for user in users:
		if user == target:
			return user
	return None

using set

def find_user(user, users: Set):
	if user in users:
		return user
	return None

it’s obvious that
- set is O(1) constant time for search
- and list is O(n) linear time for search
BUT
- in this example, when numbers of users is low, searching through list is FASTER than set
- because in a list, objects are right next to each other in memory, looping through elements is FAST
- but for set, elements are usually far from each other due to collision algorithm
- Premature Optimization

up

down

reference