diff -r ca78b9449e04 Lib/random.py
--- a/Lib/random.py	Thu Jul 16 00:24:48 2015 -0500
+++ b/Lib/random.py	Thu Jul 16 22:22:15 2015 +0300
@@ -351,6 +351,84 @@ class Random(_random.Random):
                 return self.sample(tuple(population), k)
         return result
 
+    def sample2(self, population, k):
+        n = len(population)
+        if not 0 <= k <= n:
+            raise ValueError("sample larger than population")
+        random = self.random
+        _int = int
+        result = [None] * k
+        setsize = 21        # size of a small set minus size of an empty list
+        if k > 5:
+            setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
+        if n <= setsize or hasattr(population, "keys"):
+            # An n-length list is smaller than a k-length set, or this is a
+            # mapping type so the other algorithm wouldn't work.
+            pool = list(population)
+            for i in xrange(k):         # invariant:  non-selected at [0,n-i)
+                limit = n - i
+                j = _int(random() * limit)
+                if j == limit:
+                    j = limit - 1
+                result[i] = pool[j]
+                pool[j] = pool[limit-1] # move non-selected item into vacancy
+        else:
+            try:
+                selected = set()
+                selected_add = selected.add
+                for i in xrange(k):
+                    j = _int(random() * n)
+                    if j == n:
+                        j = n - 1
+                    while j in selected:
+                        j = _int(random() * n)
+                        if j == n:
+                            j = n - 1
+                    selected_add(j)
+                    result[i] = population[j]
+            except (TypeError, KeyError):   # handle (at least) sets
+                if isinstance(population, list):
+                    raise
+                return self.sample(tuple(population), k)
+        return result
+
+    def sample3(self, population, k):
+        n = len(population)
+        if not 0 <= k <= n:
+            raise ValueError("sample larger than population")
+        if not n:
+            return []
+        random = self.random
+        _int = int
+        result = [None] * k
+        setsize = 21        # size of a small set minus size of an empty list
+        if k > 5:
+            setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
+        if n <= setsize or hasattr(population, "keys"):
+            # An n-length list is smaller than a k-length set, or this is a
+            # mapping type so the other algorithm wouldn't work.
+            pool = list(population)
+            pool.append(pool[-1])
+            for i in xrange(k):         # invariant:  non-selected at [0,n-i)
+                j = _int(random() * (n-i))
+                result[i] = pool[j]
+                pool[j] = pool[n-i-1]   # move non-selected item into vacancy
+        else:
+            try:
+                selected = {n}
+                selected_add = selected.add
+                for i in xrange(k):
+                    j = _int(random() * n)
+                    while j in selected:
+                        j = _int(random() * n)
+                    selected_add(j)
+                    result[i] = population[j]
+            except (TypeError, KeyError):   # handle (at least) sets
+                if isinstance(population, list):
+                    raise
+                return self.sample(tuple(population), k)
+        return result
+
 ## -------------------- real-valued distributions  -------------------
 
 ## -------------------- uniform distribution -------------------

$ ./python -m timeit -r11 -s 'import random; sample = random.Random(12345).sample; k = 10; p = list(range(k))' -- 'sample(p, k)'
100000 loops, best of 11: 13.9 usec per loop
$ ./python -m timeit -r11 -s 'import random; sample = random.Random(12345).sample2; k = 10; p = list(range(k))' -- 'sample(p, k)'
100000 loops, best of 11: 14.1 usec per loop
$ ./python -m timeit -r11 -s 'import random; sample = random.Random(12345).sample3; k = 10; p = list(range(k))' -- 'sample(p, k)'
100000 loops, best of 11: 14.1 usec per loop

$ ./python -m timeit -r11 -s 'import random; sample = random.Random(12345).sample; k = 100; p = list(range(k))' -- 'sample(p, k)'
10000 loops, best of 11: 94.4 usec per loop
$ ./python -m timeit -r11 -s 'import random; sample = random.Random(12345).sample2; k = 100; p = list(range(k))' -- 'sample(p, k)'
10000 loops, best of 11: 98.1 usec per loop
$ ./python -m timeit -r11 -s 'import random; sample = random.Random(12345).sample3; k = 100; p = list(range(k))' -- 'sample(p, k)'
10000 loops, best of 11: 97.1 usec per loop

$ ./python -m timeit -r11 -s 'import random; sample = random.Random(12345).sample; k = 10000; p = list(range(k))' -- 'sample(p, k)'
100 loops, best of 11: 9.38 msec per loop
$ ./python -m timeit -r11 -s 'import random; sample = random.Random(12345).sample2; k = 10000; p = list(range(k))' -- 'sample(p, k)'
100 loops, best of 11: 9.73 msec per loop
$ ./python -m timeit -r11 -s 'import random; sample = random.Random(12345).sample3; k = 10000; p = list(range(k))' -- 'sample(p, k)'
100 loops, best of 11: 9.42 msec per loop