Java 中的 TreeSet 等效于 Python 吗？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2710651/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java's TreeSet equivalent in Python?
提问by viksit
I recently came across some Java code that simply put some strings into a Java TreeSet, implemented a distance based comparator for it, and then made its merry way into the sunset to compute a given score to solve the given problem.
我最近遇到了一些 Java 代码，它只是将一些字符串放入 Java TreeSet，为它实现了一个基于距离的比较器，然后在日落时分快乐地计算给定的分数来解决给定的问题。
My questions,
我的问题，
Is there an equivalent data structure available for Python?
- The Java treeset looks basically to be an ordered dictionary that can use a comparator of some sort to achieve this ordering.
I see there's a PEP for Py3Kfor an OrderedDict, but I'm using 2.6.x. There are a bunch of ordered dict implementations out there - anyone in particular that can be recommended?
是否有可用于 Python 的等效数据结构？
- Java 树集看起来基本上是一个有序字典，它可以使用某种比较器来实现这种排序。
我看到有一个用于OrderedDict 的Py3K PEP，但我使用的是 2.6.x。那里有一堆有序的 dict 实现 - 特别是有人可以推荐吗？
PS, Just to add - I couldprobably import DictMixin or UserDict and implement my own sorted/ordered dictionary, AND make it happen through a comparator function - but that seems to be overkill.
PS，只是补充一下 - 我可能会导入 DictMixin 或 UserDict 并实现我自己的排序/有序字典，并通过比较器功能实现它 - 但这似乎有点矫枉过正。
Thanks.
谢谢。
Update. Thanks for the answers. To elaborate a bit, lets say I've got a compare function thats defined like, (given a particular value ln),
更新。感谢您的回答。详细说明一下，假设我有一个比较函数，其定义如下（给定特定值 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
I'm a bit unsure about how I'd integrate this into the ordering given in the ordered dict link given here...
我很担心我会如何融入在有序字典给出的排序有点不确定这里给出的链接..。
Something like,
就像是，
OrderedDict(sorted(d.items(), cmp=mycmp(len)))
Ideas would be welcome.
欢迎提出想法。
采纳答案by unutbu
The Python 2.7 docs for collections.OrderedDicthas a link to a OrderedDict recipethat runs on Python 2.4 or better.
Python 2.7文档中collections.OrderedDict有一个链接，指向在 Python 2.4 或更高版本上运行的OrderedDict 配方。
Edit:In regard to sorting: Use key=rather than cmp=. It tends to lead to faster codeand moreover, the cmp=keyword has been eliminated in Python3.
编辑：关于排序：使用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)]
The code you posted for mycmpdoesn't make it clear what you want passed as x1. Below, I assume x1 is supposed to be the valuein each key-value pair. If so, you could do something like this:
您发布的代码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=...is passed a function, lambda item: abs(item[1]-length).
For each itemin d.items(), the lambda function returns the number abs(item[1]-length). This number acts as proxy for the item as far as sorting is concerned. See this essayfor more information on sorting idioms in Python.
key=...传递了一个函数，lambda item: abs(item[1]-length)。对于每个itemin d.items()，lambda 函数返回数字abs(item[1]-length)。就排序而言，此数字充当项目的代理。有关在 Python 中对习语进行排序的更多信息，请参阅这篇文章。
PS. lenis a Python builtin function. So as to not clobber that len, I've changed the variable name to length.
附注。len是一个 Python 内置函数。为了不破坏它len，我已将变量名称更改为length.
回答by ring bearer
1. I don't think python has a built-in Sorted sets. How about something like this?
1.我认为python没有内置的排序集。这样的事情怎么样？
letters = ['w', 'Z', 'Q', 'B', 'C', 'A']
for l in sorted(set(letters)):
print l
2.Java TreeSetis an implementation of the abstraction called SortedSet. Basic types will be sorted on natural order.A TreeSetinstance performs all key comparisons using its compareTo (or compare) method.So your custom keys should implement proper compareTo
2.JavaTreeSet是抽象的实现，称为SortedSet. 基本类型将按自然顺序排序。TreeSet实例使用它的 compareTo（或比较）方法执行所有键比较。所以你的自定义键应该实现正确的compareTo
回答by Matt Anderson
If what you want is a set that always iterates in sorted-order, this might get you most of the way there:
如果你想要的是一个总是按排序顺序迭代的集合，这可能会让你获得大部分方法：
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))
回答by bukzor
I'd need to see some example data, but if you're just trying to do a weighted sort, then the builtin python sorted() can do it, two ways.
我需要查看一些示例数据，但如果您只是尝试进行加权排序，那么内置的 python sorted() 可以通过两种方式完成。
With well ordered tuples and a key() function:
使用有序元组和 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
or with a class with a __cmp__operator.
或带有__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
Both of these return the same output:
这两个都返回相同的输出：
('Moby Dick', 4000, 4.75)
('The Hobbit', 300, 7.25)
("Grey's Anatomy", 3000, 200)
回答by fukatani
I recently implemented TreeSet for Python using bisect module.
我最近使用 bisect 模块为 Python 实现了 TreeSet。
https://github.com/fukatani/TreeSet
https://github.com/fukatani/TreeSet
Its usage is similar to Java's Treeset.
它的用法类似于 Java 的 Treeset。
ex.
前任。
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
回答by satyendra pandey
When you are coming with java treeset:
当您使用 Java 树集时：
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]
