Блог

У меня есть список заданий в виде [(weight, length)] , например

 [(99, 1), (100, 3), (100, 3), (99, 2), (99, 2)]
  

Но намного больше.

И я написал функцию, которая планирует их в соответствии с разными ключами, которые я передаю в качестве параметра. Это означает, что для каждого задания я вычисляю время его завершения как сумму всех предыдущих заданий. Конечная цель — рассчитать взвешенное время завершения: weight[i] * completion_time[i]

В настоящее время я не вижу элегантного способа сделать это без разделения всех длин в отдельном списке, что мне кажется не очень питоническим.

Вот код

 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)
  

и вот пример использования:

 schedule(jobs, lambda t: (t[0] - t[1], t[0]))
  

В идеале я хотел бы, чтобы решение было как удобочитаемым, так и эффективным с точки зрения памяти (т. Е. Без создания другого списка длин)

Вы хотите использовать itertools.accumulate() итерацию для получения суммарного веса ваших длин:

 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)
  

Обратите внимание, что это ни в коем случае не создает новые списки, отличные от отсортированного списка. Как за счет того, что вы избегаете создания промежуточных списков, так и за счет того, что вы избегаете повторного суммирования все более и более длинных подсписков (делая это O (N) по сравнению с вашим подходом O (N ^ 2)), вышеупомянутое также намного эффективнее; только в вашем коротком примере время улучшается на 25%:

 >>> from itertools import accumulate
>>> from timeit import timeit
>>> 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)
...
>>> 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)
...
>>> jobs = [(99, 1), (100, 3), (100, 3), (99, 2), (99, 2)]
>>> timeit('schedule(jobs, lambda t: (t[0] - t[1], t[0]))',
...        'from __main__ import jobs, schedule_lists as schedule',
...         number=100000)
0.6098654230008833
>>> timeit('schedule(jobs, lambda t: (t[0] - t[1], t[0]))',
           'from __main__ import jobs, schedule_acc as schedule',
...        number=100000)
0.4608557689934969
  

Однако разница становится гораздо более заметной, когда вы увеличиваете размер списка заданий до 1000:

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