Skip to content

Instantly share code, notes, and snippets.

@zpconn

zpconn/reservoir_max.py

Created August 6, 2014 04:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save zpconn/f2ec0e22e2ed8d00a78e to your computer and use it in GitHub Desktop.
Save zpconn/f2ec0e22e2ed8d00a78e to your computer and use it in GitHub Desktop.
Download ZIP
Any finite list of integers has a maximum element. There may be multiple occurrences of this maximum. This finds uniformly and randomly the index of one of the occurrences of the maximum element with a single pass over the array using reservoir sampling.
Raw
reservoir_max.py
import random
def rand_max(arr):
curr_max = 0
curr_max_idx = 0
curr_max_count = 1
for i,x in enumerate(arr):
if x > curr_max:
curr_max = x
curr_max_idx = i
curr_max_count = 1
elif x == curr_max:
curr_max_count = curr_max_count + 1
if random.random() < 1.0 / curr_max_count:
curr_max_idx = i
return curr_max_idx
print(rand_max([3,2,4,6,5,6,4,6,5,4,2,3,6,5,4,3,4,6]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment