is there a faster way to go through a very large lists?

Question

My goal is to create a function that takes a list as an input and change that list in such way that sum(list) will be the smallest value.

The function also receives an int k; the function will do k times a ceil(num(i)/2) operation, where i should be the max(list) in order to get the minimum sum.

I am trying to improve the speed of the results for large lists, but I cant use numpy. so for list of 7,20,10 and k=4 results = 14

def minmin(list, k):
    for i in range(k):
        maxind = list.index(max(list))
        maxnum = math.ceil(list[maxind] / 2)
        list[maxind] = maxnum

    return sum(list)

could you elaborate, what you're trying to do? Also, perhaps with some examples? — Paritosh Singh, Mar 12 '19 at 09:45
i want to have a sum of an array that will be the minimum sum possible from all the outcome. this can be achieved as far as i know by looking for the max and k it.take for exp array = [20, 7, 50], with k=4 times of ceil(i/2) i should get minimum sum of 24. — Deus Rex, Mar 12 '19 at 09:50
It is not clear but consider using list comprehension instead of that `for` loop — Lunalo John, Mar 12 '19 at 09:51
@DeusRex you should edit that into the question itself. I am afraid it's still very unclear for me. The "minimum sum" term is almost definitely not the right term for this, where is this ceil and k and other stuff coming from? What is all this supposed to mean anyways? — Paritosh Singh, Mar 12 '19 at 10:11
Still not clear whay you are trying to achieve here and I think it is not clear to you either — sebastian, Mar 12 '19 at 10:47
@DeusRex how many items in the list are expected? Are they `float`s or `int`s ? — Ralf, Mar 12 '19 at 10:49
@ Ralf the list could reach thousand of items of the type int. — Deus Rex, Mar 12 '19 at 10:53
@sebastian it an exercise for beginners, needs to minimize the sum of an input to reach the lowest possible outcome of sum(list) and most importantly in the fastest computational way. — Deus Rex, Mar 12 '19 at 11:00

Ralf · Answer 1 · 2019-03-12T13:56:23.027

Given your explanations and restrictions, there is not much that could by improved; you are already using list.index() and max(), taken all the advantage of built-in C implementations.

The only thing that makes a small difference could be the assignment to temp vairables and the call to math.ceil(); read here for alternatives to ceil().

Another possibility is to sort the list in descending order so the search finds elements quicker.

Here is a slightly improved version; f1 is your version, the other is my proposal.

def f1(input_list, repetitions):
    input_list = list(input_list)

    for _ in range(repetitions):
        idx = input_list.index(max(input_list))
        new_num = math.ceil(input_list[idx] / 2)
        input_list[idx] = new_num

    return sum(input_list)


def f2(input_list, repetitions):
    input_list = list(input_list)
    input_list.sort(reverse=True)

    for _ in range(repetitions):
        idx = input_list.index(max(input_list))
        input_list[idx] = ((input_list[idx] + 1) // 2)

    return sum(input_list)

The code to compare durations and assure that the results are the same:

import random
import timeit

for exp_n in range(2, 5):
    n = 10**exp_n
    numbers = [random.randint(1, 9999) for _ in range(n)]

    for exp_k in range(2, 5):
        k = 10**exp_k

        t1 = timeit.timeit(
            'f(numbers, k)', 'from __main__ import numbers, k, f1 as f',
            number=10)
        t2 = timeit.timeit(
            'f(numbers, k)', 'from __main__ import numbers, k, f2 as f',
            number=10)

        print('n {:10,d} | k {:10,d} | {:10.4f} | {:10.4f} | best f{}'.format(
            n, k, t1, t2, '1' if t1 < t2 else '2'))
        assert f1(numbers, k) == f2(numbers, k)

The results are (using Python 3.6 on Ubuntu):

n        100 | k        100 |     0.0027 |     0.0025 | best f2
n        100 | k      1,000 |     0.0280 |     0.0251 | best f2
n        100 | k     10,000 |     0.2097 |     0.1872 | best f2
n      1,000 | k        100 |     0.0232 |     0.0190 | best f2
n      1,000 | k      1,000 |     0.2295 |     0.2009 | best f2
n      1,000 | k     10,000 |     2.2607 |     2.1653 | best f2
n     10,000 | k        100 |     0.2139 |     0.1903 | best f2
n     10,000 | k      1,000 |     2.1379 |     1.6530 | best f2
n     10,000 | k     10,000 |    21.3588 |    18.8767 | best f2

As you can see, the sorting in reverse order does help.

thanks for the effort, still i learn a thing or two from your code. — Deus Rex, Mar 12 '19 at 12:46
i have some unbaked thought.... maybe split the list to two and compare one time their max or better yet their ceil(max/2) so for the at least next iteration the max will run on half of the list... is that make some sense. do you have any idea to implement it better. — Deus Rex, Mar 12 '19 at 12:55
@DeusRex I edited my answer; if you sort the list first in descending order, then the speed improves because the bigger elements are at the beggining of the list and the search `.index()` exits earlier — Ralf, Mar 12 '19 at 13:57

is there a faster way to go through a very large lists?

1 Answers1