Самый быстрый способ сортировки списка дат при добавлении в список

Question

Я пишу что-то похожее на планировщик задач. У меня есть два набора задач, некоторые из которых фиксированы (им даны дата и время начала и окончания), а некоторые из них не фиксированы (им даются дата и время начала и продолжительность).

Нефиксированные задачи зависят от фиксированных задач, так что если нефиксированная задача перекрывается фиксированной задачей, нефиксированная задача будет продлевать ее продолжительность на величину перекрытия.

я начала со списком кортежей, где первый элемент является дата начала и второй элемент является идентификатором для фиксированной задачи, как это:

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

Я тогда еще один список, который заказанную пользователем, нефиксированных задач. Идея состоит в том, что я пройду через этот список, и внутри этого цикла я пройду через первый список, чтобы найти задачи, которые могут пересекаться с этой задачей, и может выяснить, какой из них можно увеличить нефиксированную задачу ,

Здесь я прошу вас о помощи. Теперь, когда я знаю рассчитанные начальные и конечные времена этой нефиксированной задачи, мне нужно считать ее «фиксированной», чтобы она влияла на остальную часть нефиксированных задач.

Я могу добавить эту задачу в первый список фиксированных задач и отсортировать ее снова, но это означает, что я сортирую список каждый раз, когда добавляю к нему задачу.

Я могу прокрутить первый список и найти точку, в которую должна быть вставлена ​​эта задача, а затем вставить ее туда. Но, если его место рано в списке, время тратится на перенос всех остальных предметов на одно место. И если его место задерживается в списке, мне нужно будет пройти через множество элементов, чтобы добраться до правильного места.

Итак, я не продаюсь, используя любой из этих вариантов. Реальный вопрос здесь: Каков наилучший способ сохранить список, отсортированный при добавлении к нему вещей? Или есть намного лучший способ сделать все это?

Answer 1

Вот пример использования bisect и сравнения с использованием сортированного частично отсортированного списка. Решение Bisect явно выигрывает:

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 

Вот является Bisect решение, принятое для кортежей, где дата является строкой:

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)] 

Answer 2

Настоящий вопрос: что является лучшим способом сохранить список, отсортированный при добавлении к нему вещей?

Insertion Sort - это путь. Но вам может и не понравиться, как это уже известно. Следующее, что вы можете сделать, это,

1. Не сортировать при добавлении.
2. Когда вы получаете элементы сортировки и кеширования. Когда его запрашивается в следующий раз Show из предыдущего кеша.
3. Недействительный кеш при добавлении новых элементов.

Я не программист на языке python.

class SortedList(){ 
    public $list = array(); 
    private $cached_list; 

    public function add($item){ 
     array_push($this->list, $item); 
     $this->sorted = false; 
    } 
    public function get(){ 
     if($this->sorted==true){ 
      return $this->cached_list; 
     } 

     // sort the array; 

     // copying the list to cached list and sort it 
     $this->cached_list = $this->list; 
     sort($this->cached_list); 

     // set the flag 
     $this->sorted = true; 
     return $this->cached_list 
    } 

} 

Answer 3

A Heap Queue - твой друг.Материал из Википедии:

операции обычно выполняются с кучей являются:

• создание кучи: создать пустую кучу
• находка-макс: найти максимальный элемент макс кучи
• удалить-макс: удаление корневой узел макс кучи
• увеличение ключа: обновление ключа в пределах максимальной кучи
• вставки: добавление нового ключа к куче
• слияния: соединяющие две кучки, чтобы сформировать правильную новую кучу, содержащую все элементов обоего.

Существует встроенная версия Python Heap Queue. Кучи оптимизированы для 1) удаления максимального элемента, 2) вставки новых элементов для поддержания порядка кучи.

Answer 4

Я могу прокрутить первый список и найти точку, в которой должна быть вставлена ​​эта задача , а затем вставить ее туда. Но, если его место в начале списка, время тратится на перенос всех других предметов один место. И если его место задерживается в списке, мне нужно было бы петлить через множество элементов, чтобы добраться до нужного места.

Поиск нужного места для вставки чего-либо в отсортированный список можно сделать в O (log n) с помощью binary search. Вставка все равно будет O (n).

Существуют более сложные структуры данных, такие как B-Trees, которые позволяют вставлять и искать в O (log n). Посмотрите на this и this.