订购python集 [英] Ordering python sets
问题描述
我需要一个结构来表示一组整数。我还需要
对此套装执行一些基本的设置操作，例如添加或
删除元素，加入其他套装并检查
存在特定元素。
我认为使用Python集合将是最佳选择，但我还需要
需要整数才能在集合中进行排序而我刚发现
相反，Python集合是无序集合。
是否有其他方便的结构或者我应该使用列表和定义
我需要的操作？
谢谢。
周六，2008年10月25日08:58:18 +0000，Lie Ryan写道：
< anotherrandommusing>
由于python是动态语言，我认为应该可以做这样的事情：
a = list（[1,2,3,4,5]，implementation =' 'linkedlist''）
b = dict（{'' a''：''A''}，implementation =''binarytree''）
c = dict（{''''：''A''}，implementation =''binarytree' '）
哦，我希望不是。我认为你错了动态对于混乱。
当我看到一个字典时，我想知道任何两个字母都以相同的方式工作。我不想要搜索整个项目的源代码来查找
，如果它是一个用O实现为哈希表的dict（ 1）查找或dict
实现为具有O（log N）查找的二叉树，或实现dict
作为具有O（N）查找的线性数组。
如果我想要那种噩梦，我已经可以通过遮蔽
内置来实现：
dict = binarytree
D = dict（{''''：''A''}）＃制作二叉树
没有这个建议可能带来的好处。
Python的美妙之处在于内置的数据结构（列表，字典，集合）足够强大，可以满足99％的使用[1]，并且其他1％，你可以很容易地b / b
明确地使用别的东西。
但*明确*是重点。从来没有时间你可以这样做
这个：
类型（mydict）是dict
并且不确切知道mydict将具有什么性能特征。
（除非你影响字典或类型，否则做一些打破
规则的事情。）你永远不需要问，好吧，这是一个字典。什么样的字典？
如果你想要一棵二叉树，可以要一棵二叉树。
[1 ]你的里程可能会有所不同。
-
史蒂文
2008年10月25日星期六09:21： 05 +0000，Steven D''Aprano写道：
On Sat，2008年10月25日08:58:18 +0000，Lie Ryan写道：
< blockquote class =post_quotes>
>< anotherrandommusing>
由于python是动态语言，我认为应该可以做到这样的事情：
a = list（[1,2,3,4,5]，implementation =''linkedlist''）b = dict（{''''：
''A''}，implementation =' 'binarytree''）c = dict（{''''：''A''}，
implementation =''binarytree''）
哦，我希望不是。我认为你错了动态对于混乱。
当我看到一个字典时，我想知道任何两个字母都以相同的方式工作。
哦不，这两个dict实现在外面的
中工作_exactly_相同，它们是透明可互换的。由于实现的不同，只有性能
特性不同。实际上
我从一本关于算法和数据结构的书中得到了这个想法，那本书
表示抽象数据类型（例如dict，set，list）有几个
竞争实现或数据结构（例如二叉树字典，
哈希dict，数组字典）。数据的实现和接口可以分开，以便我们可以在不更改其余代码的情况下切换数据结构的实现
。这本书是算法设计
由Skiena手册。
提示：阅读下面的PS
我不想搜索整个项目的源代码来查找
out如果它是一个dict实现为带有O（1）查找的哈希表，或者
dict实现为具有O（log N）查找的二叉树，或者实现为具有O（N）查找的线性数组的字典
。
不，你只需要看看dict'的创建点（或者实际上
更好的项目文档，但不是每个人都创造出好的文档）。你在下面提到的
替代方案，内置阴影，既是黑客又是b $ b，更有可能被遗漏。
如果我想要那种噩梦，我已经可以通过遮蔽
内置来实现：
dict = binarytree
D =字典（{''''：''A''}）＃制作二叉树
我不要想要你提到的那种噩梦...
并且不可能有两个字典有两个不同的
实现。
这个建议没有任何可能的好处。
Python的美妙之处在于内置的数据结构（列表，字典，集合）足够强大，可以满足99％的使用[1]，并且其他1％，你可以轻松地b $ b并明确使用别的东西。
哦，真的吗？据我所知，如果你在列表的开头插入数据，那么python'的列表非常糟糕（例如lst.insert（0）需要
整个数组被复制一个地址）。这是因为python的
列表使用数组数据结构，使得寻址（例如[2]）快，但插入的速度很慢。另一方面，如果它是使用二进制
树实现的，它会插入O（log n）但是寻址有点棘手。
关键字是权衡。
但*明确*是重点。从来没有时间你可以这样做
这个：
是的，是的，明确是重点。你有多明确：
dict（{foo：bar}，implementation =''binarytree''）
type（ mydict）是dict
如果我的记忆正确，二进制树字典和散列表字典是
a dict对吗？ （鸭子打字）
只有他们的实施不同。实现是......好吧，
实现细节。
并且不确切知道mydict将具有哪些性能特征。
哦......为什么我需要知道mydict
的性能特征是什么？除非我知道我在做什么。
（除非你影响字典或输入，否则做一些破坏的事情
规则你永远不需要问，好吧，这是一个字典。什么样的
dict？
好吧，这是一个字典。什么样的咒语？谁在乎呢？我不需要知道，他们看起来和行为都一样（鸭子打字）......至少直到
我描述它们（因为分析是一个深黑魔法本身，它不能用来诋毁切换实现。
有时候我们需要一种数据类型来使用特定的数据结构
一些特定的性能特征，因为我们知道我们将比其他操作更多地执行特定操作。
如果你真的需要知道当前使用的实现是什么，你可以实现一个dict.implementation属性。
如果你想要一棵二叉树，要求一棵二叉树。
是的，你要求二叉树显眼：
bintreedict = dict（{a：b}，implementation =''binarytree'' ）
这个：
regularhasheddict = dict（{a：b}）
会有合理的默认值。
PS：我承认我在上一篇文章中使用了错误的术语。我使用了
术语数据结构，而应该是抽象数据类型，数据
结构。是实施的同义词。在这篇文章中，我希望我已经修正了所有用法。
Lie Ryan写道：
>
< anotherrandommusing>
由于python是动态语言，我认为应该可以做到
这样的事情：
a = list（[1,2,3,4,5]，implementation =''linkedlist''）
为此，抽象列表必须知道抽象的所有
实现。
b = dict（{''''：''A''}，implementation =''binarytree''）
c = dict（{''''：'''一个''}，implementation =''binarytree''）
即基本上因为数据结构可以有不同的实现，
和不同的实现有不同的性能特征，
它应该是可能的dyna mically更改使用的实现。
在不久的将来，数据结构及其实现可以进一步抽象：
：
a = list（）＃ordered list
b = set（）#unordered list
c = dict（）#unordered dictionary
d = sorteddict（）＃ordered dictionary
每个实现都会共享一个公共的方法子集和
可能是一些只能依赖于实现的方法
某些实现（或者在正确的
实现中非常慢）。
< / anotherrandommusing>
未来是3.0，至少部分是使用抽象基类。
在collectons模块中有16个。
"除了容器之外，collections模块还提供了一些ABC
（抽象基类），可以用来测试一个类
是否提供了例如，特定的界面是可以使用的还是
映射，其中一些也可以用作mixin类。
ABC for数字在数字模块中。
tjr
Hi,
I need a structure to represent a set of integers. I also need to
perform on this set some basic set operations, such as adding or
removing elements, joining with other sets and checking for the
presence of specific elements.
I think that using Python sets would be the best choice, but I also
need integers to be ordered inside the set and I''ve just found out
that, instead, Python sets are unordered collections.
Is there another convenient structure or shall I use lists and define
the operations I need?
Thanks.
On Sat, 25 Oct 2008 08:58:18 +0000, Lie Ryan wrote:
<anotherrandommusing>
Since python is dynamic language, I think it should be possible to do
something like this:
a = list([1, 2, 3, 4, 5], implementation = ''linkedlist'')
b = dict({''a'': ''A''}, implementation = ''binarytree'')
c = dict({''a'': ''A''}, implementation = ''binarytree'')Oh I hope not. I think you have mistaken "dynamic" for "chaotic".
When I see a dict, I want to know that any two dicts work the same way. I
don''t want to have to search the entire project''s source code to find out
if it is a dict implemented as a hash table with O(1) lookups, or a dict
implemented as a binary tree with O(log N) lookups, or a dict implemented
as a linear array with O(N) lookups.
If I wanted that sort of nightmare, I can already do it by shadowing the
builtin:
dict = binarytree
D = dict({''a'': ''A''}) # make a binary tree
There is no possible good that come from this suggestion. The beauty of
Python is that the built-in data structures (list, dict, set) are
powerful enough for 99% of uses[1], and for the other 1%, you can easily
and explicitly use something else.
But *explicitly* is the point. There''s never any time where you can do
this:
type(mydict) is dict
and not know exactly what performance characteristics mydict will have.
(Unless you shadow dict or type, or otherwise do something that breaks
the rules.) You never need to ask, "Okay, it''s a dict. What sort of dict?"
If you want a binary tree, ask for a binary tree.
[1] Your mileage may vary.
--
Steven
On Sat, 25 Oct 2008 09:21:05 +0000, Steven D''Aprano wrote:
On Sat, 25 Oct 2008 08:58:18 +0000, Lie Ryan wrote:
><anotherrandommusing>
Since python is dynamic language, I think it should be possible to do
something like this:
a = list([1, 2, 3, 4, 5], implementation = ''linkedlist'') b = dict({''a'':
''A''}, implementation = ''binarytree'') c = dict({''a'': ''A''},
implementation = ''binarytree'')
Oh I hope not. I think you have mistaken "dynamic" for "chaotic".
When I see a dict, I want to know that any two dicts work the same way.Oh no, the two dict implementation would work _exactly_ the same from the
outside, they are transparently interchangeable. Only the performance
characteristic differs because of the different implementation. Actually
I got this idea from a book about algorithm and data structure, that book
said that an abstract data type (e.g. dict, set, list) have several
competing implementations or data structures (e.g. binary tree dict,
hashed dict, array dict). A data''s implementation and interface can be
separated so that we can switch the data structure''s implementation
without changing the rest of the code. The book is Algorithm Design
Manual by Skiena.
hint: read the PS below
I don''t want to have to search the entire project''s source code to find
out if it is a dict implemented as a hash table with O(1) lookups, or a
dict implemented as a binary tree with O(log N) lookups, or a dict
implemented as a linear array with O(N) lookups.No, you''d only need to look at the dict''s creation point (or actually
much better at projects docs, but not everyone create good docs). The
alternative you mentioned below, by shadowing built-in, is both a hack
and is much more likely to be missed.
If I wanted that sort of nightmare, I can already do it by shadowing the
builtin:
dict = binarytree
D = dict({''a'': ''A''}) # make a binary treeI DON''T want THAT sort of nightmare you mentioned...
And it''d be impossible to have two dictionary that have two different
implementations.
There is no possible good that come from this suggestion. The beauty of
Python is that the built-in data structures (list, dict, set) are
powerful enough for 99% of uses[1], and for the other 1%, you can easily
and explicitly use something else.Oh really? As far as I know, python''s list is extremely bad if you''re
inserting data at the beginning of the list (e.g. lst.insert(0) requires
the whole array be "copied" one address away). This is because python''s
list uses array data structure, making addressing (e.g. a[2]) fast, but
insertion slow. If, on the other hand, it is implemented using binary
tree, it''d make insertion O(log n) but addressing is a bit tricky on it.
The keyword is "tradeoffs".
But *explicitly* is the point. There''s never any time where you can do
this:Yes, true, explicitly IS the point. How more explicit can you be than:
dict({foo: bar}, implementation = ''binarytree'')
type(mydict) is dictIf my memory serves right, binary tree dict and hashed table dict is both
a dict right? (Duck Typing)
Only their implementation differs. Implementation is... well,
"implementation detail".
and not know exactly what performance characteristics mydict will have.Oh... why do I need to know what the performance characteristic of mydict
is? Unless I know what I''m doing.
(Unless you shadow dict or type, or otherwise do something that breaks
the rules.) You never need to ask, "Okay, it''s a dict. What sort of
dict?"Okay, it''s a dict. What sort of dict? Who the hell cares? I don''t need to
know, they all looks and behave the same (Duck Typing)... at least until
I profile them (since profiling is a deep black magic by itself, it
cannot be used to discredit switching implementations).
Sometimes we need a data type to use a specific data structure that have
some specific performance characteristic, because we know we''ll be doing
a specific operation a lot more than other operations.
If you actually need to know what the implementation is currently being
used, you could implement a dict.implementation property.
If you want a binary tree, ask for a binary tree.Yeah, you ask for binary tree EXPLICITLY:
bintreedict = dict({a:b}, implementation = ''binarytree'')
this:
regularhasheddict = dict({a:b})
would have a reasonable default.
PS: I do admit I have used the wrong terms in the last post. I used the
term "data structure", instead it should be "abstract data type", "data
structure" is a synonym for "implementation". In this post, I hope I''ve
corrected all of the usage.
Lie Ryan wrote:
>
<anotherrandommusing>
Since python is dynamic language, I think it should be possible to do
something like this:
a = list([1, 2, 3, 4, 5], implementation = ''linkedlist'')For this to work, the abstract list would have to know about all
implementations of the abstraction.
b = dict({''a'': ''A''}, implementation = ''binarytree'')
c = dict({''a'': ''A''}, implementation = ''binarytree'')
i.e. basically since a data structure can have different implementations,
and different implementations have different performance characteristics,
it should be possible to dynamically change the implementation used.
In the far future, the data structure and its implementation could be
abstracted even further:
a = list() # ordered list
b = set() # unordered list
c = dict() # unordered dictionary
d = sorteddict() # ordered dictionary
Each of the implementations would share a common subset of methods and
possibly a few implementation dependent method that could only work on
certain implementations (or is extremely slow except in the correct
implementation).
</anotherrandommusing>The future is 3.0, at least in part, with Abstract Base Classes.
There are 16 in the collectons module.
"In addition to containers, the collections module provides some ABCs
(abstract base classes) that can be used to test whether a class
provides a particular interface, for example, is it hashable or a
mapping, and some of them can also be used as mixin classes."
The ABCs for numbers are in the numbers module.
tjr
这篇关于订购python集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
