1

假设我有一个具有以下定义的项目：

Item(id: str, sequence: int)

id是一个随机字符串。

sequence是表示将其Item放入数据结构中的顺序的数字。

我想将所有Item对象组织在某种数据结构中，该结构Item基于其sequence. 所以我使用了一个SortedKeyList，它们的键设置为sequence.

import sortedcontainers

items = sortedcontainers.SortedKeyList(key=lambda x: x.sequence)

对于大多数操作，这可以正常工作。但问题是我有一个操作需要Item使用特定的id，但是没有办法使用上面的键来做到这一点。

我想做类似的事情：

items.add(Item('abc', 0))
items.add(Item('www', 1))
items.add(Item('zyx', 2))

# This should be the 2nd item added.
item = items['www']

附加信息：

我打算添加的操作需要能够Item从特定的id.

load_n_items_from_id(num: int, id: str) -> [Item]

使用上面的示例，此方法应返回以下结果：

loaded = load_n_items_from_id(2, 'www')
# loaded should contain [Item('www', 1), Item('zyx', 2)]
4

2 回答 2

0

鉴于：

import sortedcontainers


class Item(object):
    def __init__(self, ident: str, sequence: int):
        self.ident = ident
        self.sequence = sequence

    def __repr__(self):
        return f"<Item id={self.ident} sequence={self.sequence}>"


items = sortedcontainers.SortedKeyList(key=lambda x: x.sequence)
items.add(Item("abc", 0))
items.add(Item("www", 1))
items.add(Item("zyx", 2))

要找到该项目将需要 O(n) 复杂度，因为您正在搜索它未排序的东西。最简单的方法是只搜索该项目，我喜欢使用next它，因为它最接近find于 python 中带有谓词的 a ，而且它很懒：

print(next((item for item in items if item.ident == "www"), None))

给出：

<Item id=www sequence=1>

我只是把它扔到一个辅助函数中：

def find_by_ident(items, ident):
    return next((item for item in items if item.ident == ident), None)

此外，如果SortedKeyList被封装，您还可以在它旁边维护一个简单的 dict，ident -> item如果您希望在这里也有 O(1) 复杂性，但这可能没什么大不了或不值得额外的内存/代码复杂度。

于 2020-01-06T18:03:18.527 回答
0

如果我没有错，问题只是对维护我插入元素的顺序感兴趣，如果是这种情况，我们可以简单地使用内置函数 OrderedDictionary https://docs.python.org/3/library/ collections.html#ordereddict-objects而不是通过 pip 安装 sortedcontainers。

from collections import OrderedDict

items= OrderedDict()
#Items can be inserted according to your convenience either by loop or manually
items['abc']=0
items['www']=1
items['zyx']=2

print(items) #Prints dictionary in the given order

如果有帮助不要忘记接受答案，如果还有疑问，您可以删除评论。事实上，我猜你甚至可以使用普通字典（无序），如果你想要的只是你在输入时已经给出的相应键的值。

于 2020-01-06T17:53:04.230 回答