Python中与Java的TreeSet等价的是什么？

Question

我最近看到了一些Java代码，它把一些字符串放进了一个Java的TreeSet里，并实现了一个基于距离的比较器，然后就顺利地计算出一个分数来解决问题。

我有几个问题：

• 在Python中有没有类似的数据结构？

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

• 我看到有一个关于OrderedDict的PEP文档，但我用的是2.6.x版本。网上有很多有序字典的实现，有没有特别推荐的？

顺便说一下，我可能可以导入DictMixin或UserDict，自己实现一个排序/有序字典，并通过比较器函数来实现，但这样似乎有点复杂。

谢谢。

---

更新：谢谢大家的回答。再详细说一下，假设我有一个比较函数，定义如下（给定一个特定的值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

我有点不确定如何将这个整合到有序字典的排序中，具体可以参考这个链接。

类似这样的：

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

我最近在Python中实现了一个TreeSet，使用了bisect模块。

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.7的collections.OrderedDict文档里有个链接，指向一个OrderedDict的示例，这个示例可以在Python 2.4及更高版本上运行。

补充：关于排序的部分：使用key=而不是cmp=。这样做通常会让代码运行得更快，而且在Python 3中，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)。这个数字在排序时就代表了这个项。想了解更多关于Python中排序的知识，可以查看这篇文章。

顺便说一下，len是Python的内置函数。为了不和这个len冲突，我把变量名改成了length。