Fast random element from set - Python

I'm looking for a faster of way of sampling a single element at random from a large Python set. Below I've benchmarked three obvious examples.

import random
import time

test_set = set(["".join(["elem-", str(l)]) for l in range(0, 1000000)])

t0 = time.time()
random_element = random.choice(list(test_set))
print(time.time() - t0)

t0 = time.time()
random_element = random.sample(test_set, 1)
print(time.time() - t0)

t0 = time.time()
rand_idx = random.randrange(0, len(test_set)-1)
random_element = list(test_set)[rand_idx]
print(time.time() - t0)

Output:

0.0692291259765625
0.06741929054260254
0.07094502449035645