python - 添加到列表时排序日期列表的最快方法

Question

我正在编写类似于任务调度程序的东西。我有两组任务，一些是固定的(给定了开始和结束日期和时间)，一些不固定(给定了开始日期和时间以及持续时间)。

非固定任务受固定任务的影响，因此如果非固定任务与固定任务重叠，则非固定任务的持续时间将延长其重叠量。

我从一个元组列表开始，其中第一项是开始日期，第二项是该固定任务的 ID，如下所示:

[(2012-04-30, 1), (2012-05-01, 5), (2012-05-04, 2)]

然后我有另一个非固定任务列表，由用户排序。我的想法是，我将遍历此列表，在该循环内，我将遍历第一个列表以找到可能与此任务重叠的任务，并可以计算出将非固定任务扩展到多少.

这是我向您寻求帮助的地方。现在我知道了这个非固定任务的计算开始和结束时间，我需要将其视为“固定”，以便它影响其余的非固定任务。

我可以将此任务添加到固定任务的第一个列表中并再次对其进行排序，但这意味着我每次向其中添加任务时都会对列表进行排序。

我可以遍历第一个列表并找到应该插入该任务的点，然后将其插入到那里。但是，如果它的位置在列表的前面，则将时间花在将所有其他项目移到一个位置上。如果它的位置在列表的后面，我将不得不遍历很多元素才能到达正确的位置。

因此，我不赞成使用这些选项中的任何一个。这里真正的问题是:在向列表中添加内容的同时保持列表排序的最佳方法是什么？还是有更好的方法来完成这一切？

Answer 1

这是使用二分法和使用部分排序列表的排序进行比较的示例。平分解决方案显然胜出:

import bisect
import random
import timeit


def bisect_solution(size=10000):
    lst = []
    for n in xrange(size):
        value = random.randint(1, 1000000)
        bisect.insort_left(lst, value)
    return lst


# Cut out of the bisect module to be used in bisect_solution2()
def insort_left(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the left of the leftmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    a.insert(lo, x)


def bisect_solution2(size=10000):
    lst = []
    for n in xrange(size):
        value = random.randint(1, 1000000)
        insort_left(lst, value)
    return lst


def sort_solution(size=10000):
    lst = []
    for n in xrange(size):
        value = random.randint(1, 1000000)
        lst.append(value)
        lst.sort()
    return lst


t = timeit.timeit('bisect_solution()', 'from __main__ import bisect_solution', number = 10)
print "bisect_solution: ", t

t = timeit.timeit('bisect_solution2()', 'from __main__ import bisect_solution2', number = 10)
print "bisect_solution2: ", t

t = timeit.timeit('sort_solution()', 'from __main__ import sort_solution', number = 10)
print "sort_solution: ", t

bisect_solution2() 几乎与 bisect_solution() 相同——只是代码从模块中复制出来。其他人应该解释为什么需要更多时间:)

bisect_solution2() 在这里被修改为 cmp() 函数能够比较元组。

在我的电脑上显示如下结果:

bisect_solution:  0.637892403587
bisect_solution2:  0.988893038133
sort_solution:  15.3521410901

这是对日期为字符串的元组采用的二等分解决方案:

import random
import timeit


def random_date_tuple():
    s1 = '{0}-{1:02}-{2:02}'.format(random.randint(2000, 2050),
                                    random.randint(1, 12),
                                    random.randint(1, 31))
    e2 = random.randint(1,50)
    return (s1, e2)


def my_cmp(a, b):
    result = cmp(a[0], b[0])   # comparing the date part of the tuple
    if result == 0:
        return cmp(a[1], b[1]) # comparint the other part of the tuple
    return result


def my_insort_left(a, x, cmp=my_cmp, lo=0, hi=None):
    """The bisect.insort_left() modified for comparison of tuples."""

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if cmp(a[mid], x) < 0: 
            lo = mid+1
        else: 
            hi = mid
    a.insert(lo, x)


def bisect_solution3(size=1000):
    lst = []
    for n in xrange(size):
        value = random_date_tuple()
        my_insort_left(lst, value)
    return lst


def sort_solution(size=1000):
    lst = []
    for n in xrange(size):
        value = random_date_tuple()
        lst.append(value)
        lst.sort(cmp=my_cmp)
    return lst


t = timeit.timeit('bisect_solution3()', 'from __main__ import bisect_solution3', number = 10)
print "bisect_solution3: ", t

t = timeit.timeit('sort_solution()', 'from __main__ import sort_solution', number = 10)
print "sort_solution: ", t

print bisect_solution3()[:10]

请注意，由于排序解决方案非常慢，因此列表大小比之前小了 10 倍。它打印:

bisect_solution3:  0.223602245968
sort_solution:  3.69388944301
[('2000-02-01', 20), ('2000-02-13', 48), ('2000-03-11', 25), ('2000-03-13', 43),
 ('2000-03-26', 48), ('2000-05-04', 17), ('2000-06-06', 23), ('2000-06-12', 31),
 ('2000-06-15', 15), ('2000-07-07', 50)]