Most elegant way to calculate completion times for a list of jobs in Python
<p>I have a list of jobs in form of <code>[(weight, length)]</code>, e.g.</p>

<pre><code>[(99, 1), (100, 3), (100, 3), (99, 2), (99, 2)]
</code></pre>

<p>But much larger. </p>

<p>And i've written a function that schedules them according to different keys that I pass as a parameter. This means that for each job I calculate its finishing time as a sum of all the previous jobs. The ultimate goal is to calculate the weighted finishing times: <code>weight[i] * completion_time[i]</code></p>

<p>Currently I don't see an elegant way to do this without separating all the lengths in a separate list, which doesn't seem very Pythonic to me.</p>

<p>Here is the code</p>

<pre><code>def schedule(jobs_list, sort_key):
     sorted_jobs = sorted(jobs_list, key=sort_key, reverse=True)
     lengths = [job[1] for job in sorted_jobs]
     weighted_completion_times = [sum(lengths[:i + 1]) * sorted_jobs[i][0] for i in range(len(sorted_jobs))]
     return sum(weighted_completion_times)
</code></pre>

<p>and here is the sample usage:</p>

<pre><code>schedule(jobs, lambda t: (t[0] - t[1], t[0]))
</code></pre>

<p>Ideally I would like the solution to be both human-readable and memory efficient (i.e. without creating another list of lengths)</p>

<p>You want to use the <a href="https://docs.python.org/3/library/itertools.html#itertools.accumulate" rel="nofollow"><code>itertools.accumulate()</code> iterable</a> to produce the acumulative weight of your lengths:</p>

<pre><code>from itertools import accumulate

def schedule(jobs_list, sort_key):
     sorted_jobs = sorted(jobs_list, key=sort_key, reverse=True)
     acc_lengths = accumulate(job[1] for job in sorted_jobs)
     weighted_completion_times = (al * job[0] for al, job in zip(acc_lengths, sorted_jobs))
     return sum(weighted_completion_times)
</code></pre>

<p>Note that this at no point builds new lists other than the sorted list. Both by avoiding building intermediary lists as well as avoiding re-summing longer and longer sublists (making this O(N) vs your O(N^2) approach), the above is also much more efficient; just on your short sample there is a 25% improvement in timings:</p>

<pre><code>&gt;&gt;&gt; from itertools import accumulate
&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; def schedule_lists(jobs_list, sort_key):
...      sorted_jobs = sorted(jobs_list, key=sort_key, reverse=True)
...      lengths = [job[1] for job in sorted_jobs]
...      weighted_completion_times = [sum(lengths[:i + 1]) * sorted_jobs[i][0] for i in range(len(sorted_jobs))]
...      return sum(weighted_completion_times)
...
&gt;&gt;&gt; def schedule_acc(jobs_list, sort_key):
...      sorted_jobs = sorted(jobs_list, key=sort_key, reverse=True)
...      acc_lengths = accumulate(job[1] for job in sorted_jobs)
...      weighted_completion_times = (al * job[0] for al, job in zip(acc_lengths, sorted_jobs))
...      return sum(weighted_completion_times)
...
&gt;&gt;&gt; jobs = [(99, 1), (100, 3), (100, 3), (99, 2), (99, 2)]
&gt;&gt;&gt; timeit('schedule(jobs, lambda t: (t[0] - t[1], t[0]))',
...        'from __main__ import jobs, schedule_lists as schedule',
...         number=100000)
0.6098654230008833
&gt;&gt;&gt; timeit('schedule(jobs, lambda t: (t[0] - t[1], t[0]))',
           'from __main__ import jobs, schedule_acc as schedule',
...        number=100000)
0.4608557689934969
</code></pre>

<p>The difference is far more pronounced when you increase the job list size to 1000 however:</p>

<pre><code>&gt;&gt;&gt; import random
&gt;&gt;&gt; jobs = [(random.randrange(80, 150), random.randrange(1, 10)) for _ in range(1000)]
&gt;&gt;&gt; timeit('schedule(jobs, lambda t: (t[0] - t[1], t[0]))',
...        'from __main__ import jobs, schedule_lists as schedule',
...         number=1000)
5.421368871000595
&gt;&gt;&gt; timeit('schedule(jobs, lambda t: (t[0] - t[1], t[0]))',
...        'from __main__ import jobs, schedule_acc as schedule',
...         number=1000)
0.7538741750176996
</code></pre>

python list python-3.x list-comprehension