Как избежать голодания в приоритетной очереди - PullRequest
Новая
       39

Как избежать голодания в приоритетной очереди

0 голосов
/ 25 августа 2018

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

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self,):
        self.head = Node()

    def append(self, data):
        new_node = Node(data)
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = new_node

    def __str__(self):
        data = []
        current = self.head
        while current is not None:
            data.append(current.data)
            current = current.next
        return "[%s]" %(', '.join(str(i) for i in data))

    def __repr__(self):
        return self.__str__()

    def length(self):
        current = self.head
        total = 0
        while current.next is not None:
            total += 1
            current = current.next
        return total

    def display(self):
        elements = []
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
            elements.append(current_node.data)
        print("Elements ", elements)

    def get(self, index):
        if index >= self.length():
            print("Error: Index is out of range!")
            return None
        current_index = 0
        current_node = self.head
        while True:
            current_node = current_node.next
            if current_index == index:
                return current_node.data
            current_index += 1

    def remove(self):
        current = self.head
        if current is not None:
            self.head = current.next
        else:
            print("Queue is empty!")

def main():
    queue = LinkedList()
    queue.append(5)
    queue.append(2)
    queue.display()


main()

1 Ответ

0 голосов
/ 25 августа 2018

Я бы предложил использовать heapq в python вместо связанного списка. Поскольку вы делаете пользовательское сравнение, вы, вероятно, захотите реализовать что-то вроде того, что описано в heapq с пользовательским предикатом сравнения .

В дополнение к приоритету, добавьте поле, которое содержит время, когда элемент был добавлен в кучу. Затем ваш фактический приоритет является функцией назначенного приоритета и продолжительности времени, в течение которого элемент находился в куче. Например, приоритет может быть что-то вроде: 

elapsed_time = current_time - added_time;
real_priority = assigned_priority * elapsed_time;

Возможно, вы захотите сделать множитель некоторой долей прошедшего времени.

Еще одна возможность, если вы хотите убедиться, что что-то не останется в очереди дольше установленного времени. Например, если вы хотите, чтобы вещи не оставались более 5 минут, вы можете добавить поле dequeue_time. Ваше сравнение становится примерно таким: 

// assume items a and b are being compared
if (a.dequeue_time < current_time) {
    if (b.dequeue_time < a.dequeue_time) {
        // b sorts before a
    }
    else if (b.dequeue_time > a.dequeue_time) {
        // return a sorts before b
    }
    else { // dequeue times are equal
        return result of comparing a.priority to b.priority
    }
}
else {
    // here, return result of comparing a.priority and b.priority
}

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

...