27

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

我的问题，

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

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

  • 我看到有一个PEP for Py3K for an OrderedDict，但我使用的是 2.6.x。那里有一堆有序的 dict 实现 - 特别是可以推荐的任何人？

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

我有点不确定如何将其集成到此处给出的有序 dict 链接中给出的排序中......

就像是，

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

欢迎提出想法。

4

6 回答 6

8

Python 2.7文档collections.OrderedDict有一个指向在 Python 2.4 或更高版本上运行的OrderedDict 配方的链接。

编辑：关于排序：使用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). 对于每个itemin d.items()，lambda 函数返回数字abs(item[1]-length)。就排序而言，此数字充当项目的代理。有关在 Python 中排序习语的更多信息，请参阅这篇文章。

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

于 2010-04-26T01:47:41.630 回答
4

我最近使用 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
于 2016-03-19T08:52:06.730 回答
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)
于 2010-04-26T02:57:37.900 回答
0

如果您想要的是一个始终按排序顺序迭代的集合，那么这可能会让您大部分时间到达那里：

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))
于 2010-04-26T02:47:45.143 回答
0

1.我不认为python有内置的Sorted sets。这样的事情怎么样？

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

2.JavaTreeSet是一种抽象的实现，称为SortedSet. 基本类型将按自然顺序排序。TreeSet实例使用其 compareTo（或比较）方法执行所有键比较。因此您的自定义键应该正确实现compareTo

于 2010-04-26T01:38:32.113 回答
-3

当您使用 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]
于 2020-02-26T14:24:20.670 回答