Skip to content

Instantly share code, notes, and snippets.

@murbard
Last active Oct 3, 2022
Embed
What would you like to do?
average number of queries to sort
import numpy as np
import random
class Oracle():
def __init__(self, n, replace = True):
self.n = n
self.count = 0
self.replace = replace
self.returned = []
def query(self):
# draw random pair of distinct elements
while True:
i, j = random.sample(range(self.n), 2)
ordered = (i, j) if i < j else (j, i)
if self.replace or ordered not in self.returned:
break
if not self.replace:
self.returned.append(ordered)
self.count += 1
return ordered
def test(n, replace = True):
oracle = Oracle(n, replace)
smaller = np.eye(n)
while True:
i, j = oracle.query()
smaller[i, j] = 1
# transitive closure
for k in range(n):
for i in range(n):
for j in range(n):
if smaller[i, k] and smaller[k, j]:
smaller[i, j] = 1
if np.all(smaller + smaller.T > 0):
break
return oracle.count
if __name__ == "__main__":
for i in range(2, 20):
tests = np.array([test(i) for _ in range(10000)])
print('w/ replace', i, tests.mean(), tests.std() / np.sqrt(len(tests)))
for i in range(2, 20):
tests = np.array([test(i, replace=False) for _ in range(10000)])
print('wo replace', i, tests.mean(), tests.std() / np.sqrt(len(tests)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment