<commit_before>from __future__ import absolute_import
from __future__ import print_function
from __future__ import division


def sum_list_recur(a_list):
    """Sum list by recursion.

    Time complexity: O(n), where n is the list length.
    Space complexity: O(n).
    """
    if len(a_list) == 1:
        return a_list[0]
    else:
        return a_list[0] + sum_list_recur(a_list[1:])


def sum_list_dp(a_list):
    """Sum list by bottom-up dynamic programming.

    Time complexity: O(n).
    Space complexity: O(1).
    """
    s = 0
    for x in a_list:
        s += x
    return s


def main():
    import time
    import random

    a_list = [random.randint(0, 1000) for _ in range(100)]

    start_time = time.time()
    print('By recursion: {}'.format(sum_list_recur(a_list)))
    print('Time: {}'.format(time.time() - start_time))

    
    start_time = time.time()
    print('By DP: {}'.format(sum_list_dp(a_list)))
    print('Time: {}'.format(time.time() - start_time))


if __name__ == '__main__':
    main()<commit_msg>Add sum_list_dp()<commit_after>from __future__ import absolute_import
from __future__ import print_function
from __future__ import division


def sum_list_recur(a_list):
    """Sum list by recursion.

    Time complexity: O(n).
    Space complexity: O(n).
    """
    if len(a_list) == 1:
        return a_list[0]
    else:
        return a_list[-1] + sum_list_recur(a_list[:-1])


def sum_list_dp(a_list):
    """Sum list by bottom-up dynamic programming.

    Time complexity: O(n).
    Space complexity: O(n).
    """
    s = [None for _ in range(len(a_list))]
    s[0] = a_list[0]
    for i, x in enumerate(a_list[1:]):
        s[i + 1] = x + s[i]
    return s[-1]


def sum_list_dp2(a_list):
    """Sum list by bottom-up dynamic programming w/ optimized space.

    Time complexity: O(n).
    Space complexity: O(1).
    """
    s = 0
    for x in a_list:
        s += x
    return s


def main():
    import time
    import random

    a_list = [random.randint(0, 1000) for _ in range(100)]

    start_time = time.time()
    print('By recursion: {}'.format(sum_list_recur(a_list)))
    print('Time: {}'.format(time.time() - start_time))

    start_time = time.time()
    print('By DP: {}'.format(sum_list_dp(a_list)))
    print('Time: {}'.format(time.time() - start_time))
    
    start_time = time.time()
    print('By DP: {}'.format(sum_list_dp2(a_list)))
    print('Time: {}'.format(time.time() - start_time))


if __name__ == '__main__':
    main()
{'fraction_non_alphanumeric': 0.14509018036072144, 'fraction_numerical': 0.014028056112224449, 'mean_word_length': 2.9369085173501577, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1625116', 'n_tokens_mistral': 928, 'n_tokens_neox': 880, 'n_words': 227}