Tương đương TreeSet của Java tương đương với Python?

Question

Gần đây tôi đã gặp một số mã Java đơn giản đặt một số chuỗi vào một Java TreeSet, thực hiện một phép so sánh dựa trên khoảng cách, và sau đó thực hiện một cách vui vẻ để tính toán một số điểm nhất định để giải quyết vấn đề.

Câu hỏi của tôi,

• Có một cấu trúc dữ liệu tương đương có sẵn cho Python?

  • Cây Java trông cơ bản là từ điển đặt hàng có thể sử dụng bộ so sánh một số loại để đạt được thứ tự này.

• Tôi thấy có PEP for Py3K cho một OrderedDict, nhưng tôi đang sử dụng 2.6.x. Có một loạt các lệnh triển khai dict được đặt hàng ngoài kia - bất kỳ ai đặc biệt có thể được đề xuất?

PS, Chỉ cần thêm - Tôi thể lẽ nhập DictMixin hay UserDict và thực hiện của riêng tôi sắp xếp/ra lệnh từ điển, và làm cho nó xảy ra thông qua một hàm so sánh - nhưng điều đó dường như là quá mức cần thiết.

Cảm ơn.

---

Cập nhật. Cảm ơn câu trả lời. Để xây dựng một chút, cho phép nói rằng tôi đã có một chức năng so sánh Thats định nghĩa như thế, (được đưa ra một giá trị ln cụ thể),

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 

tôi là một chút không chắc chắn về cách tôi muốn tích hợp này vào đặt hàng cho trong lệnh dict link given here...

Cái gì đó như,

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

Ý tưởng sẽ được hoan nghênh.

Answer 1

Các Python 2.7 docs for collections.OrderedDict có một liên kết đến một OrderedDict recipe chạy trên Python 2.4 hoặc cao hơn.

Chỉnh sửa: Về phân loại: Sử dụng key= thay vì cmp=. Nó có xu hướng dẫn đến faster code và hơn nữa, từ khóa cmp= đã được loại bỏ bằng 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)] 

Mã bạn gửi cho mycmp không làm cho nó rõ ràng những gì bạn muốn truyền như x1.Dưới đây, tôi giả định x1 được cho là giá trị trong mỗi cặp khóa-giá trị. Nếu vậy, bạn có thể làm một cái gì đó như thế này:

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

key=... được truyền một chức năng, lambda item: abs(item[1]-length). Đối với mỗi item trong d.items(), hàm lambda trả về số abs(item[1]-length). Con số này hoạt động như một proxy cho mục đó khi sắp xếp có liên quan. Xem this essay để biết thêm thông tin về cách sắp xếp thành ngữ trong Python.

PS. len là một hàm dựng sẵn Python. Vì vậy, để không phải là clobber rằng len, tôi đã thay đổi tên biến thành length.

Answer 2

1. Tôi không nghĩ python có bộ Sắp xếp được tích hợp sẵn. Làm thế nào về một cái gì đó như thế này?

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

2.Java TreeSet là một thực hiện các trừu tượng gọi là SortedSet. loại cơ bản sẽ được sắp xếp trên order.A tự nhiên TreeSet dụ thực hiện mọi sự so sánh chính sử dụng compareTo của nó (hoặc so sánh) method.So phím tùy chỉnh của bạn nên thực hiện đúng compareTo

Answer 3

Nếu những gì bạn muốn là một tập hợp luôn lặp trong sắp xếp trật tự, điều này có thể giúp bạn có được hầu hết các con đường đó:

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)) 

Answer 4

tôi cần phải nhìn thấy một số dữ liệu ví dụ, nhưng nếu bạn' chỉ cần cố gắng để làm một loại trọng số, sau đó python xây dựng được sắp xếp() có thể làm điều đó, hai cách.

Với các bộ cũng ra lệnh và chức năng chủ chốt():

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 

hoặc với một lớp học với một nhà điều hành __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 

Cả hai trở về cùng công suất:

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

Answer 5

Gần đây tôi đã thực hiện TreeSet cho Python sử dụng chia hai nga module.

https://github.com/fukatani/TreeSet

Cách sử dụng của nó tương tự như Treeset của Java.

ví dụ:

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