Benchmark termial random

termial_bench.py

#!/usr/bin/env python3

import math
import os
import random
import sys
import timeit

_ROUNDS = int(os.getenv("TERMIAL_DEFAULT_ROUNDS", 3))
_ITERATIONS = int(os.getenv("TERMIAL_ITERATIONS", 1000000))
_N = int(os.getenv("TERMIAL_N", 10000))


def random_termial_v1(n: int) -> int:
    """Get index to an item from a list of size n.

    The higher index of an item is, the lower probability of picking it.
    """
    termial_of_n = ((n ** 2) + n) >> 1
    choice = random.randrange(termial_of_n)
    i = math.floor(-0.5 + math.sqrt(0.25 + (choice << 1)))
    return n - 1 - i


def random_termial_v2(n: int) -> int:
    """Get index to an item from a list of size n.

    The higher index of an item is, the lower probability of picking it.
    """
    if n % 2:  # or n & 1
        # odd numbers
        nearest = n + 1
        termial_of_n = ((1 + nearest) * (nearest / 2)) - nearest
    else:
        termial_of_n = (1 + n) * (n / 2)

    choice = random.randrange(termial_of_n)
    i = math.floor(-0.5 + math.sqrt(0.25 + (choice << 1)))
    return n - 1 - i


def random_termial_v3(n: int) -> int:
    """Get index to an item from a list of size n.

    The higher index of an item is, the lower probability of picking it.
    """
    addition = (n * (n & 1))
    nearest = n + addition
    termial_of_n = ((1 + nearest) * (nearest >> 1)) - addition
    choice = random.randrange(termial_of_n)
    i = math.floor(-0.5 + math.sqrt(0.25 + (choice << 1)))
    return n - 1 - i


def main():
    print("n          = ", _N)
    print("rounds     = ", _ROUNDS)
    print("iterations = ", _ITERATIONS)
    print()
    for i in range(_ROUNDS):
        print(f">>> Round {i}")
        for func in (random_termial_v1, random_termial_v2, random_termial_v3):
            print(
                "\t",
                func.__name__,
                ": ",
                timeit.timeit(
                    f"{func.__name__}({_N})",
                    number=_ITERATIONS,
                    globals=globals(),
                ),
            )


__name__ == "__main__" and main()

A sample output:

n          =  10000
rounds     =  3
iterations =  1000000

>>> Round 0
	 random_termial_v1 :  1.2930944599938812
	 random_termial_v2 :  1.1842346990015358
	 random_termial_v3 :  1.2038043739958084
>>> Round 1
	 random_termial_v1 :  1.252645685999596
	 random_termial_v2 :  1.2228172000031918
	 random_termial_v3 :  1.1677252829977078
>>> Round 2
	 random_termial_v1 :  1.2524847129971022
	 random_termial_v2 :  1.200186534995737
	 random_termial_v3 :  1.179394767001213