- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
我预计 ThreeSum 的 Python 实现会很慢:
def count(a):
"""ThreeSum: Given N distinct integers, how many triples sum to exactly zero?"""
N = len(a)
cnt = 0
for i in range(N):
for j in range(i+1, N):
for k in range(j+1, N):
if sum([a[i], a[j], a[k]]) == 0:
cnt += 1
return cnt
但令我震惊的是这个版本看起来也很慢:
def count_python(a):
"""ThreeSum using itertools"""
return sum(map(lambda X: sum(X)==0, itertools.combinations(a, r=3)))
谁能推荐一个更快的 Python 实现?这两种实现看起来都很慢......谢谢
...
答案摘要:以下是 O(N^3)(用于教育目的,未在现实生活中使用)版本的此线程中提供的所有不同版本在我的机器上运行的方式:
56 秒 RUNNING count_slow...
28 秒运行 count_itertools,由 Ashwini Chaudhary 编写...
14 秒 RUNNING count_fixed,由 roippi 编写...
11 秒运行 count_itertools(更快),由 Veedrak 编写...
08 秒 RUNNING count_enumerate,由 roippi 编写...
*注意:需要修改 Veedrak 的解决方案以获得正确的计数输出:
sum(1 for x, y, z in itertools.combinations(a, r=3) if x+y==-z)
最佳答案
提供第二个答案。从各种评论来看,您似乎主要关心的是为什么这个特定的 O(n**3) 算法在从 Java 移植过来时速度很慢。让我们开始吧。
def count(a):
"""ThreeSum: Given N distinct integers, how many triples sum to exactly zero?"""
N = len(a)
cnt = 0
for i in range(N):
for j in range(i+1, N):
for k in range(j+1, N):
if sum([a[i], a[j], a[k]]) == 0:
cnt += 1
return cnt
立即出现的一个主要问题是您正在做您的 Java 代码几乎肯定不会做的事情:具体化一个 3 元素列表只是为了将三个数字加在一起!
if sum([a[i], a[j], a[k]]) == 0:
呸!就这样写吧
if a[i] + a[j] + a[k] == 0:
一些基准测试表明,您这样做会增加 50% 以上的开销只是。哎呀。
此处的另一个问题是您在本应使用迭代的地方使用了索引。在 python 中尽量避免编写这样的代码:
for i in range(len(some_list)):
do_something(some_list[i])
而只是写:
for x in some_list:
do_something(x)
如果您明确需要您所在的索引(正如您在代码中实际做的那样),请使用enumerate
:
for i,x in enumerate(some_list):
#etc
一般来说,这是一种风格的东西(尽管它比那更深入,使用鸭子类型和迭代器协议(protocol))——但它也是一种性能的东西。为了查找 a[i]
的值,该调用被转换为 a.__getitem__(i)
,然后 python 必须动态解析一个 __getitem__
方法查找,调用它,并返回值。每次。这不是一个疯狂的开销 - 至少在内置类型上 - 但如果你在循环中做很多事情,它就会加起来。另一方面,将 a
视为可迭代对象可以避免很多开销。
考虑到这一变化,您可以再次重写您的函数:
def count_enumerate(a):
cnt = 0
for i, x in enumerate(a):
for j, y in enumerate(a[i+1:], i+1):
for z in a[j+1:]:
if x + y + z == 0:
cnt += 1
return cnt
让我们看一些时间:
%timeit count(range(-100,100))
1 loops, best of 3: 394 ms per loop
%timeit count_fixed(range(-100,100)) #just fixing your sum() line
10 loops, best of 3: 158 ms per loop
%timeit count_enumerate(range(-100,100))
10 loops, best of 3: 88.9 ms per loop
这将是最快的速度。您可以通过将所有内容包装在理解中而不是执行 cnt += 1
来削减大约一个百分比,但这非常小。
我玩过一些 itertools
实现,但实际上我无法让它们运行得比这个显式循环版本更快。如果您考虑一下,这是有道理的 - 对于每次迭代,itertools.combinations
版本必须重新绑定(bind)所有三个变量所引用的内容,而显式循环会“作弊” "并且在外循环中重新绑定(bind)变量的频率要低得多。
但是现实检查时间:在一切都说完之后,您仍然可以期望 cPython 运行此算法比现代 JVM 慢一个数量级。 python 内置了太多的抽象,妨碍了快速循环。如果您关心速度(并且您无法修复您的算法 - 请参阅我的其他答案),要么使用类似 numpy
的东西来花费所有时间在 C 中循环,要么使用不同的 python 实现.
后记:pypy
为了好玩,我在 cPython 和 pypy 上对 1000 个元素的列表运行了 count_fixed
。
cPython:
In [81]: timeit.timeit('count_fixed(range(-500,500))', setup='from __main__ import count_fixed', number = 1)
Out[81]: 19.230753898620605
pypy:
>>>> timeit.timeit('count_fixed(range(-500,500))', setup='from __main__ import count_fixed', number = 1)
0.6961538791656494
快点!
我可能会在稍后添加一些 java 测试来进行比较:-)
关于python - 为什么 "map"版本的ThreeSum这么慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25712596/
自己试试看: import pandas as pd s=pd.Series(xrange(5000000)) %timeit s.loc[[0]] # You need pandas 0.15.1
我最近开始使用 Delphi 中的 DataSnap 来生成 RESTful Web 服务。在遵循 Marco Cantu 本人和互联网上其他几个人的指导后,我成功地使整个“链条”正常工作。 但是有一
我一直在为操作系统类(class)编写以下代码,但结果有些奇怪。该代码创建x线程并同时运行它们,以便将两个平方矩阵相乘。每个线程将输入矩阵的Number_of_rows/Number_of_threa
我正在尝试确定何时使用 parallel包以加快运行某些分析所需的时间。我需要做的一件事是创建矩阵,比较具有不同行数的两个数据框中的变量。我在 StackOverflow 上问了一个关于有效方法的问题
我最近对我的代码进行了一些清理,并在此过程中更改了此内容(不完全是真实的代码): read = act readSTRef test1 term i var = do t v^!terms.
我正在计时查询和同一个查询的执行时间,分页。 foreach (var x in productSource.OrderBy(p => p.AdminDisplayName) .Wher
我正在开发一个项目 (WPF),我有一个 Datagrid 从数据库加载超过 5000 条记录,所以我使用 BackgroundWorker 来通知用户数据正在加载,但它太慢了,我需要等待将近 2分钟
我在查询中添加 ORDER BY 时遇到问题。没有 ORDER BY 查询大约需要 26ms,一旦我添加 ORDER BY,它大约需要 20s。 我尝试了几种不同的方法,但似乎可以减少时间。 尝试 F
我是 Android 开发新手,遇到了性能问题。当我的 GridView 有太多项目时,它会变得有点慢。有什么方法可以让它运行得更快一些吗? 这是我使用的代码: 适配器: public class C
这里的要点是: 1.设置query_cache_type = 0;重置查询缓存; 2.在 heidisql(或任何其他客户端 UI)中运行任何查询 --> 执行,例如 45 毫秒 3.使用以下代码运行
想象下表: CREATE TABLE drops( id BIGSERIAL PRIMARY KEY, loc VARCHAR(5) NOT NULL, tag INT NOT
我的表 test_table 中的示例数据: date symbol value created_time 2010-01-09 symbol1
首先,如果已经有人问过这个问题,我深表歉意,至少我找不到任何东西。 无论如何,我将每 5 分钟运行一次 cron 任务。该脚本加载 79 个外部页面,而每个页面包含大约 200 个我需要在数据库中检查
我有下面的 SQL 代码,它来自 MySQL 数据库。现在它给了我期望的结果,但是查询很慢,我想我应该在进一步之前加快这个查询的速度。 表agentstatusinformation有: PKEY(主
我需要获取一个对象在 Core Data 中数千个其他对象之间的排名。现在,这是我的代码: - (void)rankMethod { //Fetch all objects NSFet
我正在编写一个应用程序,我需要在其中读取用户的地址簿并显示他所有联系人的列表。我正在测试的 iPhone 有大约 100 个联系人,加载联系人确实需要很多时间。 ABAddressBookRef ad
我正在使用 javascript 将 160 行添加到包含 10 列的表格中。如果我这样做: var cellText = document.createTextNode(value); cell.a
我是 Swift 的新手,我已经设置了一个 tableView,它从 JSON 提要中提取数据并将其加载到表中。 表格加载正常,但是当表格中有超过 10 个单元格时,它会变得缓慢且有些滞后,特别是它到
我在 InitializeCulture 和 Page_PreInit 事件之间的 asp.net 页面中遇到性能问题。当我重写 DeterminePostBackMode() 时,我发现问题出在 b
我在 Hetzner 上有一个带有 256GB RAM 6 个 CPU(12 个线程) 的专用服务器,它位于德国。我有 CENTOS 7.5。 EA4。 我的问题是 SSL。每天大约 2 小时,我们在
我是一名优秀的程序员,十分优秀!