Python: how to search for a substring in a set the fast way?

Python: how to search for a substring in a set the fast way?

I have a set containing ~300.000 tuples
In [26]: sa = set(o.node for o in vrts_l2_5)
In [27]: len(sa)
Out[27]: 289798
In [31]: random.sample(sa, 1)
Out[31]: [('835644', '4696507')]
Now I want to lookup elements based on a common substring, e.g. the first
4 'digits' (in fact the elements are strings). This is my approach:
def lookup_set(x_appr, y_appr):
return [n for n in sa if n[0].startswith(x_appr) and
n[1].startswith(y_appr)]
In [36]: lookup_set('6652','46529')
Out[36]: [('665274', '4652941'), ('665266', '4652956')]
Is there a more efficient, that is, faster way to to this?