0

I know this is similar to How do I pick 2 random items from a Python set?

say you have iterable s, random.sample(s, n) probably does the job.

is the run time O(|s|) or O(n) ?

# my investigation Code

import random, time

a = range(100)
c = range(25)
b = map(lambda x: (1, x), a)
print a
print b

N = 1000000

def sampleIterable(items, n):
    t1 = time.clock()
    for _ in xrange(N):
        random.sample(items, n)
    t2 = time.clock()
    print "Time Elapsed = %s sec" % (t2 - t1)
    print

print "====== sampling ======"
sampleIterable(a, 5)
sampleIterable(b, 5)
sampleIterable(c, 5)
print "-----------"
sampleIterable(a, 20)
sampleIterable(b, 20)
sampleIterable(c, 20)
print "-----------"
sampleIterable(set(a), 20)
sampleIterable(set(b), 20)
sampleIterable(set(c), 20)

Result: ====== sampling ====== Time Elapsed = 4.014588 sec

Time Elapsed = 3.56045 sec

Time Elapsed = 3.619019 sec

Time Elapsed = 10.594099 sec

Time Elapsed = 10.277008 sec

Time Elapsed = 9.707444 sec

Time Elapsed = 19.782511 sec

Time Elapsed = 19.71995 sec

Time Elapsed = 10.212379 sec

Guess the conclusion is: yes it's O(n) not O(|S|) and sampling from list is faster than set.

In general how do I look up the run time of various python method though?

Community
  • 1
  • 1
Jamesszm
  • 101
  • 1
  • 10
  • It's hard to see how the time complexity for picking *n* items (if you want them uniformly) could be O(n) if `s` is for example a linked list that provides no random access; at least not in O(1). – 5gon12eder Dec 12 '14 at 04:28
  • To answer your last question: [time complexity of Python data structure operations](https://wiki.python.org/moin/TimeComplexity) – jme Dec 12 '14 at 04:47
  • Don't understand the downvote, this seems like a valid question. – speedplane Dec 12 '14 at 05:21
  • Theoretically, pick 1 item uniformly at random from a set |S| is O(1). Picking 2 items is O(2) (or (O(1) in |S|), as you just need of make sure the 2 random index from [1..|S|] you generate do not clash, and the expected # of clash / regenereate is 1 or sth. That's why I asked this qn – Jamesszm Dec 15 '14 at 16:43
  • Thanks jme! that link is so helpful! – Jamesszm Dec 15 '14 at 16:46

0 Answers0