Python中与Java的TreeSet相对应的是什么？

Question

我最近看到一些Java代码，它简单地将一些字符串放入了Java TreeSet中，实现了一个基于距离的比较器，然后通过计算给定问题的得分来解决问题。

我的问题是，

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

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

• 我看到Py3K有一个PEP for Py3K用于OrderedDict，但我正在使用2.6.x。有许多有序字典实现 - 有没有特别推荐的？

PS，只是想补充一下 - 我可能可以导入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)))

欢迎提出想法。

- viksit

---

请注意，OrderedDict不像Java中的TreeMap。 这里的“有序”是指元素按插入时间排序。这不是你想要的。你基本上正在寻找通过二叉搜索树实现的集合。 - Albert

Answer 1

Python 2.7的 collections.OrderedDict文档 中有一个链接到适用于Python 2.4或更高版本的OrderedDict recipe的链接。 编辑： 关于排序：使用key=而不是cmp=。它往往会导致更快的代码，而且cmp=关键字已在Python3中被删除。

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中排序惯用语的更多信息，请参见此文。

PS. len是Python内置函数。为了不覆盖该len，我已将变量名更改为length。

- unutbu

---

哦，感谢指针。我还有一件事不太确定，已经在问题中更新了。欢迎提供想法。谢谢！ - viksit

太棒了，我认为它会完全符合我的要求 - 让我检查一下！ - viksit

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

- fukatani

---

你应该加入 1 in ts 功能。 - Will Sherwood

谢谢！我同意你的观点。我实现了TreeSet.__iter__。 因此，这些函数的工作方式如下。print(1 in Treeset([1, 2]))

True

print(3 in Treeset([1, 2]))

False

for i in Treeset([2,5,2,3]): print(i) - fukatani

看起来很不错 - 希望能看到一些测试。 - viksit

谢谢！我在这里添加了测试。https://github.com/fukatani/TreeSet/blob/master/test_treeset.py并且使用bysect提高了'in'运算符的性能。 - fukatani

与Java的 TreeSet 不同，由于需要将插入位置之后的所有元素向后移动，该实现的插入性能为 O(n)。 - augurar

Answer 3

我需要看一些示例数据，但如果您只是想进行加权排序，则内置的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)

- bukzor

---

我不明白这如何排除重复项，这正是Java Treeset所做的。 - rayzinnz

Answer 4

1. 我认为Python没有内置的排序集合。那么这样怎么样？

letters = ['w', 'Z', 'Q', 'B', 'C', 'A']
  for l in sorted(set(letters)):
     print l

Java中的TreeSet是抽象类SortedSet的一个实现。基本类型将按照自然顺序排序。TreeSet实例通过其compareTo（或compare）方法执行所有关键字比较。因此，您的自定义键应该实现适当的compareTo方法。

- ring bearer

Answer 5

如果你想要一个总是按排序顺序迭代的集合，那么这个方法可能会让你实现大部分功能：

def invalidate_sorted(f):
    def wrapper(self, *args, **kwargs):
        self._sort_cache = None
        return f(self, *args, **kwargs)
    return wrapper

class SortedSet(set):
    _sort_cache = None

    _invalidate_sort_methods = """
        add clear difference_update discard intersection_update
        symmetric_difference_update pop remove update
        __iand__ __ior__ __isub__ __ixor__
        """.split()

    def __iter__(self):
        if not self._sort_cache:
            self._sort_cache = sorted(set.__iter__(self))
        for item in self._sort_cache:
            yield item

    def __repr__(self):
        return '%s(%r)' % (type(self).__name__, list(self))

    for methodname in _invalidate_sort_methods:
        locals()[methodname] = invalidate_sorted(getattr(set, methodname))

- Matt Anderson

---

与真正的TreeSet相比，这个算法很慢。 - Albert

Answer 6

当你使用Java TreeSet时：

 import java.util.*;
class Main{
         public static void main(String args[])
          {
             TreeSet<Integer> tr=new TreeSet<>();
             tr.add(3);
             tr.add(5);
             tr.add(7);
             tr.add(6);
             tr.add(3);
             tr.add(8);

             Iterator itr=tr.iterator();
             for(int i=0;i<tr.size();i++)
            {
               System.out.print(tr.get(i)+" ");  
            } 
          }
     }

    >>>> **3 5 6 7 8**


  same AS in python:
from treeset import TreeSet
tr = TreeSet([1,2,2,7,4,3])
print(tr)
>>> [1, 2, 3, 4,7] 

- satyendra pandey