Task for ezhome.com

merge_sorted_arrays.py

#!/usr/bin/env python
# encoding: utf-8
# Write a function that accepts 2 arrays.
# The arrays contain numbers and each input array is already sorted in increasing order.
# The function should create and return another array
# which contains all of the numbers that are in the 2 input arrays.
# The numbers in the returned array should also be sorted in increasing order.
# The goal is to write code that executes as fast as possible for large arrays.
# Implement without using any third party libraries.
#
# For example if the input arrays are [1,2,5] and [2,3] then the result should be [1,2,2,3,5]
# Describe and explain your implementation in a few words.
from time import time
from heapq import merge
from operator import add
from random import randint


input_data = (
    ((1, 2, 5), (2, 3)),
    ((50, 100, 200, 400, 1000), (1, 2, 3, 4, 10, 20, 40, 50, 60, 110)),
    (
        sorted([randint(0, 100000) for _ in xrange(100000)]),
        sorted([randint(0, 200000) for _ in xrange(200000)])
    ),
)


def solution1(*args):
    """
    Super simple function that return sorted sum of all arrays
    Rewritten to support any number of arrays
    """
    return sorted(reduce(add, args))


def solution2(*args):
    """
    Generator that returns minimal from all arrays every iteration
    """
    args = [iter(_) for _ in args]
    tmp = [next(_, '') for _ in args]
    while [_ for _ in tmp if _ is not '']:
        i = tmp.index(min(tmp))
        yield tmp[i]
        tmp[i] = next(args[i], '')


def solution3(*args):
    """
    Solution that uses heapq module
    """
    return merge(*args)


if __name__ == '__main__':
    solutions = [(n, f) for n, f in locals().items() if 'solution' in n and callable(f)]

    for one, two in input_data:
        for name, func in solutions:
            elapsed = time()
            result = [x for x in func(one, two)]
            print name, round(time() - elapsed, 4), 'sec'
            result, total = result[:10], len(result) - 10
            print 'Result', result, total > 0 and 'and {0} more'.format(total) or ''

        print '\n'

    print 'Completed'