在 python 中，如何创建一个按一个值排序并由另一个值索引的集合

Question

我需要一个集合，在其中插入诸如 [1,'b42b00d6-76c8-4d68-b22e-ff4653bb01c8'] 之类的项目。

它需要按第一个元素排序，但可以按第二个元素索引。

以下是我能想到的最好的。它有两个缺陷：

它不能用同一个键接受多个项目，因为它是字典.
无法从列表中正确删除项目。

我的尝试：

from rbtree import rbtree

class Item(object):
    def __init__(self, value, id):
         self.value = value
         self.id = id

item1 = Item(1,'b42b00d6-76c8-4d68-b22e-ff4653bb01c8')
item2 = Item(2,'60eda62f-f05d-4134-9e92-9bb9a1f52daf')
item3 = Item(2,'77d9a028-bd4b-4634-b230-234f88ff010a')
item4 = Item(3,'7e7118cd-7145-41c8-8413-79670bdc81dc')

myList = rbtree()
myList[item2.value] = item2
myList[item1.value] = item1
myList[item3.value] = item3
myList[item4.value] = item4

# Correctly ordered by the first element
# But it's missing item2.

for k,v in myList.iteritems():
    print "%s %s" % (v.value, v.id)

# But I also need to index by the second element.
# So:

listIndexedBySecondElement = {}
listIndexedBySecondElement[item1.id] = item1
listIndexedBySecondElement[item2.id] = item2
listIndexedBySecondElement[item3.id] = item3
listIndexedBySecondElement[item4.id] = item4

item = listIndexedBySecondElement['7e7118cd-7145-41c8-8413-79670bdc81dc']
print item.value # correctly prints 3

# Now I need to delete an element.

del listIndexedBySecondElement['b42b00d6-76c8-4d68-b22e-ff4653bb01c8']
# But I also need to delete it from myList. How do I do that?

Answer 1

在你之前运行:

del listIndexedBySecondElement['b42b00d6-76c8-4d68-b22e-ff4653bb01c8']

抓住物品：

itm = listIndexedBySecondElement['b42b00d6-76c8-4d68-b22e-ff4653bb01c8']

现在您可以从两者中删除它：

del listIndexedBySecondElement['b42b00d6-76c8-4d68-b22e-ff4653bb01c8']
del myList[itm.value]

至于 "order" 部分 - 字典不是有序的数据结构，因此您必须实现其他东西。

Answer 2

您可以改为使用 id 到值的字典：

mydict = {}
mydict['77d9a028-bd4b-4634-b230-234f88ff010a'] = 2
mydict['b42b00d6-76c8-4d68-b22e-ff4653bb01c8'] = 1
mydict['7e7118cd-7145-41c8-8413-79670bdc81dc'] = 3
mydict['60eda62f-f05d-4134-9e92-9bb9a1f52daf'] = 2

字典现在可以通过 id 进行索引。您可以像这样按 value 排序和打印：

sorted_dict = sorted(mydict.items(), key=lambda x:x[1])
for id, value in sorted_dict:
    print("{0} {1}".format(id, value))

正在打印：

b42b00d6-76c8-4d68-b22e-ff4653bb01c8 1
77d9a028-bd4b-4634-b230-234f88ff010a 2
60eda62f-f05d-4134-9e92-9bb9a1f52daf 2
7e7118cd-7145-41c8-8413-79670bdc81dc 3

按值排序。

Answer 3

我的最终解决方案是结合使用 alfasin 的答案，并从 rbtree 切换到 pyavl。 Pyavl 是一个集合而不是字典，所以它可以有重复项。

代码：

import avl

class Item(object):
    def __init__(self, value, id):
        self.value = value
        self.id = id

item1 = Item(1,'b42b00d6-76c8-4d68-b22e-ff4653bb01c8')
item2 = Item(2,'60eda62f-f05d-4134-9e92-9bb9a1f52daf')
item3 = Item(2,'77d9a028-bd4b-4634-b230-234f88ff010a')
item4 = Item(3,'7e7118cd-7145-41c8-8413-79670bdc81dc')

myList = avl.new()
myList.insert(item2)
myList.insert(item1)
myList.insert(item3)
myList.insert(item4)

# Correctly ordered by the first element
for item in myList:
    print "%s %s" % (item.value, item.id)

# But I also need to index by the second element.
# So:

listIndexedBySecondElement = {}
listIndexedBySecondElement[item1.id] = item1
listIndexedBySecondElement[item2.id] = item2
listIndexedBySecondElement[item3.id] = item3
listIndexedBySecondElement[item4.id] = item4

item = listIndexedBySecondElement['7e7118cd-7145-41c8-8413-79670bdc81dc']
print item.value # correctly prints 3

# Now I need to delete an element.

itm = listIndexedBySecondElement['60eda62f-f05d-4134-9e92-9bb9a1f52daf']
del listIndexedBySecondElement['60eda62f-f05d-4134-9e92-9bb9a1f52daf']
myList.remove(itm)

在 python 中，如何创建一个按一个值排序并由另一个值索引的集合

In python, how do I make a collection that is sorted by one value, and indexable by another

python

collections

sorted

indexed