哪个更快，为什么？设置还是列表？

发布于 2024-12-09 11:59:57 字数 211 浏览 3 评论 0原文

假设我有一个图表，想查看 N[a] 中是否有 b。哪个实施速度更快，为什么？

a, b = range(2)
N = [set([b]), set([a,b])]

或者

N= [[b],[a,b]]

这显然过于简单化了，但想象一下图变得非常密集。

原文

Lets say that I have a graph and want to see if b in N[a]. Which is the faster implementation and why?

a, b = range(2)
N = [set([b]), set([a,b])]

N= [[b],[a,b]]

This is obviously oversimplified, but imagine that the graph becomes really dense.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

罪#恶を代价 2024-12-16 11:59:57

集合中的成员资格测试要快得多，尤其是对于大型集合。这是因为该集合使用哈希函数来映射到存储桶。由于 Python 实现会自动调整哈希表的大小，因此速度可以是恒定的 (O(1)）无论集合的大小如何（假设哈希函数足够好）。

相反，为了评估一个对象是否是列表的成员，Python 必须比较每个成员是否相等，即测试时间为 O(n)。

回复收藏 0 原文

蘸点软妹酱 2024-12-16 11:59:57

这完全取决于您想要实现的目标。逐字使用示例，使用列表会更快，因为您不必花费创建集合的开销：

import timeit

def use_sets(a, b):
    return [set([b]), set([a, b])]

def use_lists(a, b):
    return [[b], [a, b]]

t=timeit.Timer("use_sets(a, b)", """from __main__ import use_sets
a, b = range(2)""")
print "use_sets()", t.timeit(number=1000000)

t=timeit.Timer("use_lists(a, b)", """from __main__ import use_lists
a, b = range(2)""")
print "use_lists()", t.timeit(number=1000000)

生成：

use_sets() 1.57522511482
use_lists() 0.783344984055

但是，由于此处已经提到的原因，当您搜索<时，您可以从使用集合中受益/em> 大集合。通过你的例子不可能判断拐点对你来说在哪里以及你是否会看到好处。

我建议您对这两种方法进行测试，并选择适合您的特定用例的更快的方法。

It all depends on what you're trying to accomplish. Using your example verbatim, it's faster to use lists, as you don't have to go through the overhead of creating the sets:

import timeit

def use_sets(a, b):
    return [set([b]), set([a, b])]

def use_lists(a, b):
    return [[b], [a, b]]

t=timeit.Timer("use_sets(a, b)", """from __main__ import use_sets
a, b = range(2)""")
print "use_sets()", t.timeit(number=1000000)

t=timeit.Timer("use_lists(a, b)", """from __main__ import use_lists
a, b = range(2)""")
print "use_lists()", t.timeit(number=1000000)

Produces:

use_sets() 1.57522511482
use_lists() 0.783344984055

However, for reasons already mentioned here, you benefit from using sets when you are searching large sets. It's impossible to tell by your example where that inflection point is for you and whether or not you'll see the benefit.

I suggest you test it both ways and go with whatever is faster for your specific use-case.

回复收藏 0 原文