保持对象按多个键排序的高效数据结构

Question

我有一个 python 程序，我在其中使用优先级队列来跟踪要处理的对象。目前，队列是使用 SortedList 实现的，效果很好。

但是，我需要扩展这段代码，以便列表保持按多个键排序。有点像一个 SQL 数据库，在多个列上有索引，这样我就可以高效地访问、添加和删除所有键上的对象。我的工作量add/delete很重。为了了解我想做什么，这里有一些伪代码：

ml = MultiSortedList()
ml.append((1, "z", 1.5), a)
ml.append((2, "a", 40.0), b)
ml.append((3, "f", 0.5), c)

print(ml.sorted(0))
   [((1, "z", 1.5), a),
   ((2, "a", 40.0), b),
   ((3, "f", 0.5), c),]

print(ml.sorted(2))
   [((3, "f", 0.5), c),
   ((1, "z", 1.5), a),
   ((2, "a", 40.0), b)]

print(ml.sorted(2).pop(1)
   (1, "z", 1.5), a)

print(ml.sorted(0))
   [((2, "a", 40.0), b),
   ((3, "f", 0.5), c)]

我不太明白如何有效地做到这一点。当然，我可以为每次访问不同的列再次对列表进行排序，但这太昂贵了。此外，对 python 列表的 O(n) 删除操作变得很痛苦，因为列表可能包含数千个对象。

是否有解决此问题的现有数据结构（最好已在 python 中实现）？如果没有，你能帮我制定一个如何有效实施的大纲吗？

Answer 1

您应该使用 heap，而不是使用排序列表作为优先级队列的实现。比如一个二叉堆，有log(n)个插入和删除。斐波那契堆将有 O(1) 插入。

您在标准库中有一个实现：heapq 模块。

对于您的用例，您需要保留多个堆：一个用于每个排序顺序。为了实现的清晰度，您可能希望将原始数据保存在字典中（可能使用随机或递增键）并且仅将其键保留在堆上。

使用这个技巧，你可以很容易地得到O(1)插入和O(log(n))删除。你并没有真正指定你将拥有什么样的访问权限，但是如果你需要随机访问，你可以在适当的堆上使用 binary search 来获得 O(log(n))

Answer 2

一种方法是在内部维护 n 列表，每个排序顺序一个，每个排序 add/remove 项。这样，您 "only" 将数据结构的操作时间乘以一个常数值（即，如果使用 3 个键而不是一个键，则得到 3 log(n) 而不是 log(n) 到 delete/insert一个元素）。

我想象的这种实现背后的概念是 java 的比较器。

为每个键创建一个用于对它们进行排序的比较器方法，然后在插入和删除时使用它。

它将按如下方式工作：

class SortedList(list):
    def __init__(self, comparator = None):
        list.__init__(self)

        self.comparator = comparator

    def add(self, element):
        """ Adds the element into the sorted list.
        If no comparator where provided at initialisation, then try to compare
        the element to item already stored in the list using standard __gt__ 
        and __eq__.

        Argument :
            element : the element to insert in the list

        /!\ NB : A more inteligent implementation should be used, such as binary search... /!\
        """
        index = 0
        while (index < len(self)):
            if self.isGreatterThan(element, self[index]):
                index += 1
            else:
                break

        self.insert(index, element)

    def remove(self, element):
        """ Same as previous, a better approach is possible that use binary search """
        list.remove(self, element)


    def isGreatterThan(self, element, otherElement):
        """ Compare if element is greater than other element. """
        if self.comparator != None:
            return self.comparator(element, otherElement)
        else:
            return element.__gt__(otherElement)


class MultipleKeysObjectContainer():
    def __init__(self, comparators):
        #register the comparators
        self.comparators = comparators
        #create a List for each comparator
        self.data = {}
        for key in self.comparators.keys():
            self.data[key] = SortedList(comparator = self.comparators[key])

    def add(self, element):
        for key in self.data.keys():
            self.data[key].add(element)

    def __repr__(self):
        return "<MultipleKeysObjectContainer :"+self.data.__repr__()+">"

    def __str__(self):
        result = "MultipleKeysObjectContainer{\n"
        for key in self.data.keys():
            result += "\tOrder by : "+key+"{\n"
            for element in self.data[key]:
                result += "\t\t" + str(element) + "\n"
            result += "\t}\n"
        result += "}"
        return result

    def popOrderedBy(self, key, position):
        """ pop the item a the position in the list of item ordered by the key.
        Remove also from other data containers. """
        item = self.data[key].pop(position)
        for dataKey in self.data.keys():
            if dataKey != key:
                self.data[dataKey].remove(item)

        return item



if __name__ == "__main__":
    a = SortedList(lambda x,y : x[0][0] > y[0][0])

    item1 = ((1, "z", 1.5),"foo")
    item2 = ((2, "a", 40.0), "bar")
    item3 = ((3, "f", 0.5), "barfoo")

    a.add(item1)
    a.add(item3)
    a.add(item2)
    print("Example of sorted list")
    print(a)
    a.remove(item3)
    print("The same list without the barfoo")
    print(a)


    b = MultipleKeysObjectContainer({"id": (lambda x,y : x[0][0] > y[0][0]), "letter": (lambda x,y : x[0][1] > y[0][1] ), "value":(lambda x,y : x[0][2] > y[0][2])})

    b.add(item1)
    b.add(item3)
    b.add(item2)
    print("A multiple key container, object are ordered according three criterion.")
    print(b)
    print("Remove the first item if items are ordered by letter", b.popOrderedBy("letter", 0))
    print("After this removing the container contains :")
    print(b)

这导致：

Example of sorted list
[((1, 'z', 1.5), 'foo'), ((2, 'a', 40.0), 'bar'), ((3, 'f', 0.5), 'barfoo')]
The same list without the barfoo
[((1, 'z', 1.5), 'foo'), ((2, 'a', 40.0), 'bar')]
A multiple key container, object are ordered according three criterion.
MultipleKeysObjectContainer{
    Order by : id{
        ((1, 'z', 1.5), 'foo')
        ((2, 'a', 40.0), 'bar')
        ((3, 'f', 0.5), 'barfoo')
    }
    Order by : value{
        ((3, 'f', 0.5), 'barfoo')
        ((1, 'z', 1.5), 'foo')
        ((2, 'a', 40.0), 'bar')
    }
    Order by : letter{
        ((2, 'a', 40.0), 'bar')
        ((3, 'f', 0.5), 'barfoo')
        ((1, 'z', 1.5), 'foo')
    }
}
Remove the first item if items are ordered by letter ((2, 'a', 40.0), 'bar')
After this removing the container contains :
MultipleKeysObjectContainer{
    Order by : id{
        ((1, 'z', 1.5), 'foo')
        ((3, 'f', 0.5), 'barfoo')
    }
    Order by : value{
        ((3, 'f', 0.5), 'barfoo')
        ((1, 'z', 1.5), 'foo')
    }
    Order by : letter{
        ((3, 'f', 0.5), 'barfoo')
        ((1, 'z', 1.5), 'foo')
    }
}

这看起来像你正在寻找的（几乎，只需要添加二进制搜索 :p ）祝你好运！

保持对象按多个键排序的高效数据结构

Efficient data structure keeping objects sorted on multiple keys

python

sorting

heap

data-structures