Response to: https://www.linkedin.com/feed/update/urn:li:activity:6654295788988006400/

move-zeroes.py

from copy import deepcopy
from functools import wraps
from random import sample
from time import time
from typing import List

DEBUG = False


def id_checker(func):
    @wraps(func)
    def wrapper(nums):
        before = id(nums)
        func(nums)
        after = id(nums)

        if DEBUG:
            print(f"{'before':>8}: {before}")
            print(f"{'after':>8}: {after}\n")

        if before != after:
            print("The nums list is not the same!")

    return wrapper


def timer(func):
    @wraps(func)
    def wrapper(nums):
        start = time()
        func(nums)
        stop = time()
        print(f"{func.__name__:>8}: {stop - start:.10f}")

    return wrapper


@id_checker
@timer
def mridu(nums: List[int]):
    """Does not return anything.

    Modifies nums in-place instead.
    """
    L1 = []  # never used...
    count = nums.count(0)
    counter = 0
    for x in nums:
        if x == 0:
            nums.remove(x)
            nums.append(x)
            counter += 1
        if counter == count:
            break


@id_checker
@timer
def clamytoe(nums: List[int]):
    count = 0
    while True:
        try:
            nums.remove(0)
            count += 1
        except ValueError:
            break
    # nums.extend([0] * count)
    for _ in range(count):
        nums.insert(len(nums), 0)


@id_checker
@timer
def striker(sequence: List[int]):
    index = 0
    for data in sequence:
        if not data:
            continue
        sequence[index] = data
        index += 1
    while index < len(sequence):
        sequence[index] = 0
        index += 1
    return " ".join(list(map(str, sequence)))


def generate_nums(size: int) -> List[int]:
    numbers = [0]
    for _ in range(size - 1):
        numbers.extend(sample(range(10), 1))

    return numbers


def test_one(original):
    nums1 = deepcopy(original)
    nums2 = deepcopy(original)
    nums3 = deepcopy(original)

    mridu(nums1)
    clamytoe(nums2)
    striker(nums3)

    try:
        assert nums1 == nums2 == nums3
    except AssertionError:
        print("Outputs do not match!")
        print(f"original: \n{original}")
        print(f"mridu: \n{nums1}")
        print(f"clamytoe: \n{nums2}")
        print(f"striker: \n{nums3}")


if __name__ == "__main__":
    sizes = [10, 100, 1_000, 10_000, 100_000]
    for size in sizes:
        original = generate_nums(size)
        print(f"Working with {original.count(0)} zeroes out of {len(original):,} numbers")
        test_one(original)

This problem is interesting in that with smaller occurrences of zeroes my solution is faster, but once you start to add more, it can sometimes be the slowest! Nice going striker!

Working with 992 zeroes out of 10000 numbers
   mridu: 0.1031861305
clamytoe: 0.1007750034
 striker: 0.0048718452

@clamytoe, thanks for writing the gist, learned something new about how to benchmark the program using python.

You’re welcome @strikersps! There’s also the timeit module, which actually runs each test several times and then returns the fastest time for a more accurate benchmark. If you’re interested, when I get some time, I can cook one up using it.