在Python中Java的TreeSet等价物？

Question

我最近遇到了一些Java代码，它们只是将一些字符串放入一个Java TreeSet中，为它实现了一个基于距离的比较器，然后在日落时分愉快地计算出一个给定的分数来解决给定的问题。

我的问题

• Python是否有等效的数据结构？

  • Java treeset看起来基本上是一个有序字典，可以使用某种比较器来实现这种排序。

• 我知道ordered dict有一个PEP for Py3K，但我使用的是2.6.x。有很多有序的dict实现，有谁特别值得推荐？

PS，只需添加-I就可以可能导入DictMixin或UserDict并实现我自己的排序/排序字典，并通过一个comparator函数实现它-但这似乎有点过头了。

谢谢。

---

更新。谢谢你的回答。详细说明一下，假设我有一个比较函数，它的定义如下（给定一个特定的值ln）

def mycmp(x1, y1, ln):
  a = abs(x1-ln)
  b = abs(y1-ln)
  if a<b:
    return -1
  elif a>b:
    return 1
  else:
    return 0

我有点不确定如何将其集成到有序dictlink given here..中给出的排序中。

有点像

OrderedDict(sorted(d.items(), cmp=mycmp(len)))

欢迎提出意见。

Answer 1

我需要看一些示例数据，但是如果您只是尝试进行加权排序，那么内置的python sorted（）可以通过两种方式完成。

使用有序元组和一个key（）函数：

def cost_per_page(book):
    title, pagecount, cost = book
    return float(cost)/pagecount

booklist = [
        ("Grey's Anatomy", 3000, 200),
        ('The Hobbit', 300, 7.25),
        ('Moby Dick', 4000, 4.75),
]
for book in sorted(booklist, key=cost_per_page):
    print book

或者使用带有__cmp__运算符的类。

class Book(object):
    def __init__(self, title, pagecount, cost):
        self.title = title
        self.pagecount = pagecount
        self.cost = cost
    def pagecost(self):
        return float(self.cost)/self.pagecount
    def __cmp__(self, other):
        'only comparable with other books'
        return cmp(self.pagecost(), other.pagecost())
    def __str__(self):
        return str((self.title, self.pagecount, self.cost))

booklist = [
        Book("Grey's Anatomy", 3000, 200),
        Book('The Hobbit', 300, 7.25),
        Book('Moby Dick', 4000, 4.75),
]
for book in sorted(booklist):
    print book

两者返回相同的输出：

('Moby Dick', 4000, 4.75)
('The Hobbit', 300, 7.25)
("Grey's Anatomy", 3000, 200)

Answer 2

我最近使用bisect模块实现了Python的TreeSet。

https://github.com/fukatani/TreeSet

它的用法类似于Java的Treeset。

例如

from treeset import TreeSet
ts = TreeSet([3,7,2,7,1,3])
print(ts)
>>> [1, 2, 3, 7]

ts.add(4)
print(ts)
>>> [1, 2, 3, 4, 7]

ts.remove(7)
print(ts)
>>> [1, 2, 3, 4]

print(ts[2])
>>> 3

Answer 3

Python 2.7docs for ^{}有一个指向在python2.4或更高版本上运行的OrderedDict recipe的链接。

编辑：关于排序：使用key=，而不是cmp=。它往往会导致faster code，而且，Python3中的cmp=关键字已经被删除。

d={5:6,7:8,100:101,1:2,3:4}
print(d.items())
# [(1, 2), (3, 4), (100, 101), (5, 6), (7, 8)]

您为mycmp发布的代码并没有明确您希望作为x1传递的内容。下面，我假设x1应该是每个键值对中的值。如果是这样，你可以这样做：

length=4
print(sorted(d.items(),key=lambda item: abs(item[1]-length) ))
# [(3, 4), (1, 2), (5, 6), (7, 8), (100, 101)]

key=...被传递一个函数，lambda item: abs(item[1]-length)。 对于d.items()中的每个item，lambda函数返回数字abs(item[1]-length)。就排序而言，此数字充当项目的代理。请参阅this essay以获取有关在Python中排序习惯用法的更多信息。

PS.len是一个Python内置函数。为了不破坏len，我将变量名改为length。