提高一个巨大的双倍周期
你好呀 :) ,
我是一个python的新手,需要按照遵循代码进行任务
外部仿真程序称为" Abaqus",使用Python
访问a的网格(带有XY坐标的nodes的网格)
某些几何模型.
[in是包含要检查节点的启动输入,有
一些具有相同x和y坐标的双节点需要为
删除. SN是包含这种双节点的输出]
代码:选择全部
对于我在范围(len(in))中:#scan列表中的所有元素
对于J范围(Len(in))的J:
如果我
如果在[i] .coordinates [1] == [j] .coordinates [1]:
sn.append(在[i] .label中)
不幸的是,我的Len(in)约为100.000,运行时间大约
15H !!!! :(
有什么想法改善它吗?
我已经尝试将单个" if语句"分组:
代码:选择全部
如果i
但是没有改进.
非常感谢,Alex
# 回答1
Alexunlord,我的Len(in)约为100.000,运行时间
Alexabout 15H !!!! :(
亚历山大改善它的想法?
numpy? http://numpy.scipy.org/ http://www.scipy.org/numpy_example_list
更直接,请注意,您正在构建Len(in)ints的清单
通过内部循环的时间.快速打击可能是这个简单的更改:
索引= range(len(in))
对于i在索引中:#scan列表中的所有元素
对于J中的J索引:
如果我!= j:
if(在[i] .coordinates [0] == [j] .coordinates [0]和
在[i] .coordinates [1] == [j] .coordinates [1])中:
sn.append(在[i] .label中)
跳过
Alexunlord,我的Len(in)约为100.000,运行时间
Alexabout 15H !!!! :(
亚历山大改善它的想法?
numpy? http://numpy.scipy.org/ http://www.scipy.org/numpy_example_list
更直接,请注意,您正在构建Len(in)ints的清单
通过内部循环的时间.快速打击可能是这个简单的更改:
索引= range(len(in))
对于i在索引中:#scan列表中的所有元素
对于J中的J索引:
如果我!= j:
if(在[i] .coordinates [0] == [j] .coordinates [0]和
在[i] .coordinates [1] == [j] .coordinates [1])中:
sn.append(在[i] .label中)
跳过
# 回答2
Alexzive写道:
当您寻找重复时,有效的解决方案可能是
基于集合或dict对象.
#未经测试
从集合导入违约
groups = defaultdict(list)
对于IN in:
c = item.coordinates
组[C [C [0],C [1]].附录(item.Label)
sn = []
对于groups.itervalues()中的标签:
如果Len(标签)1:
sn.extend(标签)#或标签[1:]如果要保留一项
彼得
Alexzive写道:
当您寻找重复时,有效的解决方案可能是
基于集合或dict对象.
#未经测试
从集合导入违约
groups = defaultdict(list)
对于IN in:
c = item.coordinates
组[C [C [0],C [1]].附录(item.Label)
sn = []
对于groups.itervalues()中的标签:
如果Len(标签)1:
sn.extend(标签)#或标签[1:]如果要保留一项
彼得
# 回答3
代码:选择全部
[狙击]
这就像在泰坦尼克号上重新安排甲板椅:)是的,它可能
加快速度,但是当您等待15小时时3秒钟:)
不知道Len(在[x] .coordinate中)或其结构,如果
这是len == 2的列表,您应该只能做
如果i
如果i
拥有一种杀死您的O(n^2)算法.
1)使用Xrange而不是范围用巨大的
不需要的阵列.
2)除非您需要附加重复标签,否则您知道
我和j已交换,您将再次达到相同的状态,所以
可能值得写外圈以消除这一点
场景和此过程,但仅在i+1开始
比我,您可以放弃检查" i <> j".
这样的变化可能看起来像
因为我在Xrang E(Len(in)):
对于Xrange(i+1,len(in))的j:
如果在[i] .coordinates == [j] .coordinates中:
sn.append(在[i] .label中)
如果我的大学算法记忆为我提供了充分的服务,那么
将您的o(n^2)减少到o(n log n),这会给您带来一些
节省不错的时间.
-tkc
代码:选择全部
[狙击]
这就像在泰坦尼克号上重新安排甲板椅:)是的,它可能
加快速度,但是当您等待15小时时3秒钟:)
不知道Len(在[x] .coordinate中)或其结构,如果
这是len == 2的列表,您应该只能做
如果i
如果i
拥有一种杀死您的O(n^2)算法.
1)使用Xrange而不是范围用巨大的
不需要的阵列.
2)除非您需要附加重复标签,否则您知道
我和j已交换,您将再次达到相同的状态,所以
可能值得写外圈以消除这一点
场景和此过程,但仅在i+1开始
比我,您可以放弃检查" i <> j".
这样的变化可能看起来像
因为我在Xrang E(Len(in)):
对于Xrange(i+1,len(in))的j:
如果在[i] .coordinates == [j] .coordinates中:
sn.append(在[i] .label中)
如果我的大学算法记忆为我提供了充分的服务,那么
将您的o(n^2)减少到o(n log n),这会给您带来一些
节省不错的时间.
-tkc
# 回答4
跳过:
不,在两种情况下使用Xrange,然后保存列表.
蒂姆·蔡斯:
仍然是O(n^2),只是半矩阵,一个三角形.
再见,
熊
跳过:
不,在两种情况下使用Xrange,然后保存列表.
蒂姆·蔡斯:
仍然是O(n^2),只是半矩阵,一个三角形.
再见,
熊
# 回答5
Alexzive在THU,2008年9月18日05:25:02 -0700写道:
这是您的算法更好的版本,它避免了未成年人
效率低下,但保持着巨大的效率:
对于node1 in in:
对于node2 in in:
如果Node1不是Node2:
如果node1.coordinates == node2.coordinates:
sn.append(node1.label)
这假设Node.coordinates是定义平等的类型.
如果它们是元组或清单,那应该很好.
但是效率低下的巨大是您不一次检查每个节点,
不是两次,而是100,000次!因此,您必须迭代10,000,000,000
时代,无论您做什么,这都会很慢.特别是在
纯Python.
这是一个更好的主意:仅一遍列表一次:
see = set()
对于节点in in:
coords = tuple(node.coordinates)
如果看到的坐标:
sn.append(node.label)
别的:
sigh.add(坐标)
希望这可以帮助.
- -
史蒂文
Alexzive在THU,2008年9月18日05:25:02 -0700写道:
这是您的算法更好的版本,它避免了未成年人
效率低下,但保持着巨大的效率:
对于node1 in in:
对于node2 in in:
如果Node1不是Node2:
如果node1.coordinates == node2.coordinates:
sn.append(node1.label)
这假设Node.coordinates是定义平等的类型.
如果它们是元组或清单,那应该很好.
但是效率低下的巨大是您不一次检查每个节点,
不是两次,而是100,000次!因此,您必须迭代10,000,000,000
时代,无论您做什么,这都会很慢.特别是在
纯Python.
这是一个更好的主意:仅一遍列表一次:
see = set()
对于节点in in:
coords = tuple(node.coordinates)
如果看到的坐标:
sn.append(node.label)
别的:
sigh.add(坐标)
希望这可以帮助.
- -
史蒂文
# 回答6
蒂姆·蔡斯:
仍然是O(n^2),只是半矩阵,一个三角形.
啊,好吧,我想更多地考虑,你是对的...是
o((n^2)/2)仅O(n^2).叹.我还不够
然而.但是,将时间除以2(从15hr到7.5小时)为
在我的书中仍然是一个重大节省的钱:)
但是,如果列表的理解也更快,您可能是
能够做类似的事情
sn = [d.label
对于(i,d)枚举(in)
对于Xrange(i+1,len(in))的j
如果d.coordinates == [j] .coordinates
这是给予的
或更详细的(但更接近我的原始代码)版本
sn = [in [i] .label
因为我在Xrange(len(in))
对于Xrange(i+1,len(in))的j
如果在[i] .coordinates == [j] .coordinates中
这是给予的
对OP:一如既往,在各种
样本您从列表中返回,看看什么对您有用.
-tkc
蒂姆·蔡斯:
仍然是O(n^2),只是半矩阵,一个三角形.
啊,好吧,我想更多地考虑,你是对的...是
o((n^2)/2)仅O(n^2).叹.我还不够
然而.但是,将时间除以2(从15hr到7.5小时)为
在我的书中仍然是一个重大节省的钱:)
但是,如果列表的理解也更快,您可能是
能够做类似的事情
sn = [d.label
对于(i,d)枚举(in)
对于Xrange(i+1,len(in))的j
如果d.coordinates == [j] .coordinates
这是给予的
或更详细的(但更接近我的原始代码)版本
sn = [in [i] .label
因为我在Xrange(len(in))
对于Xrange(i+1,len(in))的j
如果在[i] .coordinates == [j] .coordinates中
这是给予的
对OP:一如既往,在各种
样本您从列表中返回,看看什么对您有用.
-tkc
# 回答7
蒂姆·蔡斯(Tim Chase)在2008-09-18 thu,2008-09-18,蒂姆·蔡斯(Tim Chase)写道:
如果您不检查j值小于我,那么您可能想同时做
sn.append(在[i] .label中)
sn.append(在[j] .label中)
在同一通行证上.
蒂姆·蔡斯(Tim Chase)在2008-09-18 thu,2008-09-18,蒂姆·蔡斯(Tim Chase)写道:
如果您不检查j值小于我,那么您可能想同时做
sn.append(在[i] .label中)
sn.append(在[j] .label中)
在同一通行证上.
# 回答8
在9月18日,8:25 AM,Alexzive
sn = []
对于IN in:
c = item.coordinates [0],item.coordinates [1]
如果c在dup中:
sn.append(item.Label)
别的:
dup.add(c)
在9月18日,8:25 AM,Alexzive
sn = []
对于IN in:
c = item.coordinates [0],item.coordinates [1]
如果c在dup中:
sn.append(item.Label)
别的:
dup.add(c)
# 回答9
psyco可能会在这里有所帮助(10x-40x); - >
也许请查看将数据倒入SQLite,然后将其拉回.
IT(或其他数据库)设计用于围绕大块扔
数据的.
Alexzive写道:
- -
蒸气锻造
杰克·安德森
专案经理
手机:0412 897 125
电子邮件:jaxper@vapourforge.com
网页:www.vapourforge.com
您的自定义IT服务来源(_@_ _ )
在9月18日,11:18*上午,prueba ...@latinmail.com写道:
O(n)+1
如果item.coordines只是一对(x,y)对,则可以跳过构建c
并节省一些内存:
SIDE_COORDS = SET()
对于节点in in:
如果node.coordins中的sead_coords:
sn.append(node.label)
别的:
see_coords.add(node.coordinates)
sew_coords被引用到现有的引用
node.coordates对象,而不是新的元组.
Geoff G-T
psyco可能会在这里有所帮助(10x-40x); - >
也许请查看将数据倒入SQLite,然后将其拉回.
IT(或其他数据库)设计用于围绕大块扔
数据的.
Alexzive写道:
- -
蒸气锻造
杰克·安德森
专案经理
手机:0412 897 125
电子邮件:jaxper@vapourforge.com
网页:www.vapourforge.com
您的自定义IT服务来源(_@_ _ )
在9月18日,11:18*上午,prueba ...@latinmail.com写道:
O(n)+1
如果item.coordines只是一对(x,y)对,则可以跳过构建c
并节省一些内存:
SIDE_COORDS = SET()
对于节点in in:
如果node.coordins中的sead_coords:
sn.append(node.label)
别的:
see_coords.add(node.coordinates)
sew_coords被引用到现有的引用
node.coordates对象,而不是新的元组.
Geoff G-T
# 回答10
2008年9月18日,Alexzive在THU上写道:
我没有测试语法,但这是一个带有分类列表的想法.
应该是o(nlogn).
DEF SK(X):
返回X.Coordinates [0]
In.Sort(key = sk)
因为我在Xrange(Len(in))中:
对于Xrange(i+1,len(in))的j:
如果在[i] .coordinates [0] == [j] .coordinates [0]:
如果在[i] .coordinates [1] == [j] .coordinates [1]:
sn.append(在[i] .label中)
别的:
休息
Harald
2008年9月18日,Alexzive在THU上写道:
我没有测试语法,但这是一个带有分类列表的想法.
应该是o(nlogn).
DEF SK(X):
返回X.Coordinates [0]
In.Sort(key = sk)
因为我在Xrange(Len(in))中:
对于Xrange(i+1,len(in))的j:
如果在[i] .coordinates [0] == [j] .coordinates [0]:
如果在[i] .coordinates [1] == [j] .coordinates [1]:
sn.append(在[i] .label中)
别的:
休息
Harald
# 回答11
在9月18日,2:25*PM,Alexzive
从集合导入违约
d = defaultdict(int)
for x in in:
D [x] += 1
sn = [x for(x,c)in d.iteritems()如果c 1]
- -
保罗·汉金
在9月18日,2:25*PM,Alexzive
从集合导入违约
d = defaultdict(int)
for x in in:
D [x] += 1
sn = [x for(x,c)in d.iteritems()如果c 1]
- -
保罗·汉金
# 回答12
在9月18日,2:25*PM,Alexzive
时间复杂性):
导入Itertools
in.sort()
sn = [k,v in itertools.groupby(in)if len(list(v))1]
- -
保罗·汉金
在9月18日,2:25*PM,Alexzive
时间复杂性):
导入Itertools
in.sort()
sn = [k,v in itertools.groupby(in)if len(list(v))1]
- -
保罗·汉金
# 回答13
Bruno Desthuilliers:
多一点:
导入Psyco
def dubles10():
dup = set()
sn = []
对于IN in:
c = item.coordinates
如果c在dup中:
sn.append(项目)
别的:
dup.add(c)
返回SN
psyco.bind(双打10)
从收藏品进口Deque
def dubles11():
dup = set()
dup_add = dup.add
sn = deque()
sn_append = sn.append
对于IN in:
c = item.coordinates
如果c在dup中:
sn_append(项目)
别的:
dup_add(c)
返回SN
def doublees12():
dup = set()
sn = deque()
对于IN in:
c = item.coordinates
如果c在dup中:
sn.append(项目)
别的:
dup.add(c)
返回SN
psyco.bind(双打12)
时间:
Dubles00:0.522365288653
Doublees01:0.247219812198
Doublees02:0.237889823898
Dubles03:0.238638921389
Dubles04:0.23821698217
Doubles05:0.177042495425
Doubles06:0.13166199162
Doubles08:0.00569725197252
Doubles09:0.00418566685667
Doubles10:0.00192086920869
双打11:0.0040332453245
Doubles12:0.00184026840268
希望这已经足够快:-)
再见,
熊
Bruno Desthuilliers:
多一点:
导入Psyco
def dubles10():
dup = set()
sn = []
对于IN in:
c = item.coordinates
如果c在dup中:
sn.append(项目)
别的:
dup.add(c)
返回SN
psyco.bind(双打10)
从收藏品进口Deque
def dubles11():
dup = set()
dup_add = dup.add
sn = deque()
sn_append = sn.append
对于IN in:
c = item.coordinates
如果c在dup中:
sn_append(项目)
别的:
dup_add(c)
返回SN
def doublees12():
dup = set()
sn = deque()
对于IN in:
c = item.coordinates
如果c在dup中:
sn.append(项目)
别的:
dup.add(c)
返回SN
psyco.bind(双打12)
时间:
Dubles00:0.522365288653
Doublees01:0.247219812198
Doublees02:0.237889823898
Dubles03:0.238638921389
Dubles04:0.23821698217
Doubles05:0.177042495425
Doubles06:0.13166199162
Doubles08:0.00569725197252
Doubles09:0.00418566685667
Doubles10:0.00192086920869
双打11:0.0040332453245
Doubles12:0.00184026840268
希望这已经足够快:-)
再见,
熊
# 回答14
在2008年9月18日的星期四20:43:00 +0200,布鲁诺·德索利尔(Bruno Desthuilliers)写道:
我对这里的优先级并不狡猾,但我提交了
本质上比Pruebono早两个小时.
人们没有看到我的帖子吗?除了我被所有人杀死的人
经济状况?我还问了一个关于httperror的问题,但我还没有看到任何
完全回答.
- -
史蒂文
在2008年9月18日的星期四20:43:00 +0200,布鲁诺·德索利尔(Bruno Desthuilliers)写道:
我对这里的优先级并不狡猾,但我提交了
本质上比Pruebono早两个小时.
人们没有看到我的帖子吗?除了我被所有人杀死的人
经济状况?我还问了一个关于httperror的问题,但我还没有看到任何
完全回答.
- -
史蒂文
# 回答15
Bearophile:
为了娱乐,要获得几乎基线的参考,我做了一个
D中的小基准也:
导入std.stdio:writefln;
//使用Tango STD lib,您不需要这一切
版本(win32){
导入std.c.windows.windows;
双时钟() {
长t;
QueryPerformanceCounter(＆t);
返回cast(double)t / queryPerformanceFquency;
}
长期查询频率；
静态this(){
QueryPerformanceFrequency(＆queryPerformanceFrequen cy);
}
}
联合n {
struct {int x,y; }
长xy;
}
自动in = [
n(4,9),n(5,0),n(6,6),n(7,2),n(3,6),n(9,6),n(9,6),n(0,1),n (1,
6),,
n(0,5),n(1,2),n(8,9),n(5,4),n(1,6),n(7,6),n(9,1),n (7,
6),,
n(0,1),n(7,4),n(7,4),n(8,4),n(8,4),n(3,5),n(9,6),n (6,
1),,
n(3,4),n(4,5),n(0,5),n(6,3),n(2,4),n(1,6),n(9,5),n (1,
2),,
n(5,8),n(8,5),n(3,1),n(9,4),n(9,4),n(3,3),n(4,8),n (9,
7),,
n(8,4),n(6,2),n(1,5),n(5,8),n(8,6),n(0,8),n(5,2),n (3,
4),,
n(0,5),n(4,4),n(2,9),n(7,7),n(1,0),n(4,2),n(5,7),n (0,
4),,
n(2,5),n(0,8),n(7,3),n(9,1),n(0,4),n(5,0),n(4,9),n (0,
6),,
n(3,0),n(3,0),n(3,9),n(8,3),n(7,9),n(8,5),n(7,6),n (1,
5),,
n(0,6),n(5,9),n(6,8),n(0,0),n(4,1),n(3,3),n(5,4),n (5,
3),,
n(6,1),n(5,4),n(4,5),n(5,8),n(4,1),n(3,6),n(1,9),n (0,
5),,
n(6,5),n(5,5),n(6,0),n(0,9),n(2,6),n(0,7),n(5,9),n (7,
3),,
n(7,9),n(5,4),n(4,9),n(2,9)
];
n [] doublees13(){
size_t [n] dup; //用作集
n [] sn;
foreach(item; in){
如果(DUP中的项目)
sn〜 = item;
别的
dup [item] = 0;
}
返回SN；
}
n [] doublees0(){
n [] sn;
for(int i; i
if(在[i] == in [j]中)
sn〜 = in [i];
返回SN；
}
void test_results(){
size_t [n] set1,set2;
foreach(n; dubles0())
set1 [n] = 0;
foreach(n; doublees13())
set2 [n] = 0;
if(set1.keys.sort!= set2.keys.sort)
投掷新错误("错误");
}
void main(){
int n = 150_000;
试验结果();
int count = n;
auto t0 = clock();
而(count--)
双打13();
auto t1 = clock();
writefln("％0.10f",cast(double)(t1 -t0) / n);
}
Doublees13()需要0.000027-0.000037秒(*),大约60-75次
比Doubles12快,这意味着大约3-4秒而不是15H(开启
原始计算机).
将C ++与GCC一起使用(使用
(*)可能是时间的差异,因为当前
我使用的DMD编译器未在ASM中添加" ALIGN"说明
它像海湾合作委员会一样产生.使用现代CPU对代码非常敏感
对齐这会导致小紧身的运行时间差异20-30％
循环.
再见,
熊
Bearophile:
为了娱乐,要获得几乎基线的参考,我做了一个
D中的小基准也:
导入std.stdio:writefln;
//使用Tango STD lib,您不需要这一切
版本(win32){
导入std.c.windows.windows;
双时钟() {
长t;
QueryPerformanceCounter(＆t);
返回cast(double)t / queryPerformanceFquency;
}
长期查询频率；
静态this(){
QueryPerformanceFrequency(＆queryPerformanceFrequen cy);
}
}
联合n {
struct {int x,y; }
长xy;
}
自动in = [
n(4,9),n(5,0),n(6,6),n(7,2),n(3,6),n(9,6),n(9,6),n(0,1),n (1,
6),,
n(0,5),n(1,2),n(8,9),n(5,4),n(1,6),n(7,6),n(9,1),n (7,
6),,
n(0,1),n(7,4),n(7,4),n(8,4),n(8,4),n(3,5),n(9,6),n (6,
1),,
n(3,4),n(4,5),n(0,5),n(6,3),n(2,4),n(1,6),n(9,5),n (1,
2),,
n(5,8),n(8,5),n(3,1),n(9,4),n(9,4),n(3,3),n(4,8),n (9,
7),,
n(8,4),n(6,2),n(1,5),n(5,8),n(8,6),n(0,8),n(5,2),n (3,
4),,
n(0,5),n(4,4),n(2,9),n(7,7),n(1,0),n(4,2),n(5,7),n (0,
4),,
n(2,5),n(0,8),n(7,3),n(9,1),n(0,4),n(5,0),n(4,9),n (0,
6),,
n(3,0),n(3,0),n(3,9),n(8,3),n(7,9),n(8,5),n(7,6),n (1,
5),,
n(0,6),n(5,9),n(6,8),n(0,0),n(4,1),n(3,3),n(5,4),n (5,
3),,
n(6,1),n(5,4),n(4,5),n(5,8),n(4,1),n(3,6),n(1,9),n (0,
5),,
n(6,5),n(5,5),n(6,0),n(0,9),n(2,6),n(0,7),n(5,9),n (7,
3),,
n(7,9),n(5,4),n(4,9),n(2,9)
];
n [] doublees13(){
size_t [n] dup; //用作集
n [] sn;
foreach(item; in){
如果(DUP中的项目)
sn〜 = item;
别的
dup [item] = 0;
}
返回SN；
}
n [] doublees0(){
n [] sn;
for(int i; i
if(在[i] == in [j]中)
sn〜 = in [i];
返回SN；
}
void test_results(){
size_t [n] set1,set2;
foreach(n; dubles0())
set1 [n] = 0;
foreach(n; doublees13())
set2 [n] = 0;
if(set1.keys.sort!= set2.keys.sort)
投掷新错误("错误");
}
void main(){
int n = 150_000;
试验结果();
int count = n;
auto t0 = clock();
而(count--)
双打13();
auto t1 = clock();
writefln("％0.10f",cast(double)(t1 -t0) / n);
}
Doublees13()需要0.000027-0.000037秒(*),大约60-75次
比Doubles12快,这意味着大约3-4秒而不是15H(开启
原始计算机).
将C ++与GCC一起使用(使用
(*)可能是时间的差异,因为当前
我使用的DMD编译器未在ASM中添加" ALIGN"说明
它像海湾合作委员会一样产生.使用现代CPU对代码非常敏感
对齐这会导致小紧身的运行时间差异20-30％
循环.
再见,
熊
# 回答16
史蒂文·达·阿普拉诺(Steven D'Aprano)写道:
我对这里的优先级并不狡猾,但我提交了
本质上比Pruebono早两个小时.
人们没有看到我的帖子吗?除了我被所有人杀死的人
经济状况?我还问了一个关于httperror的问题,但我还没有看到任何
完全回答.
是的,在弄清楚原始帖子该怎么做之后,我看到了你的
然后Pruebono's,并决定,由于两个人提交了
头奖算法,我不必说更多.我会这么说:这个解决方案
等同于寻找等价类(ITE的集合 MS,给定
"键"),然后找到多个成员的类(集合).
默认值很棒.
tjr
史蒂文·达·阿普拉诺(Steven D'Aprano)写道:
我对这里的优先级并不狡猾,但我提交了
本质上比Pruebono早两个小时.
人们没有看到我的帖子吗?除了我被所有人杀死的人
经济状况?我还问了一个关于httperror的问题,但我还没有看到任何
完全回答.
是的,在弄清楚原始帖子该怎么做之后,我看到了你的
然后Pruebono's,并决定,由于两个人提交了
头奖算法,我不必说更多.我会这么说:这个解决方案
等同于寻找等价类(ITE的集合 MS,给定
"键"),然后找到多个成员的类(集合).
默认值很棒.
tjr
# 回答17
En Fri,2008年9月19日02:11:51 -0300,Tino Wildenhain
escribió:
也许是由于新闻组/列表二元性...
- -
Gabriel Genellina
En Fri,2008年9月19日02:11:51 -0300,Tino Wildenhain
escribió:
也许是由于新闻组/列表二元性...
- -
Gabriel Genellina
# 回答18
Bruno Desthuilliers写道:
已经提交了几个.哈拉德对
冗余测试(即使他的解决方案似乎被打破了,CF下面) -
您的内部循环应该看起来像:
对于Xrange(i+1,len(in))的j
现在,显而易见的赢家是普鲁贝诺 - 甚至不优化,使用套装似乎
与最优化的更正版本相比, *方式 *的速度更快
您的算法.
这是一个快速的替补席 - 请大家双重研究以确保可以:
<剪切代码>
真的
Dubles0:1.55667901039
Doubles1:0.719144105911
Doubles2:0.703393936157
Doubles3:0.700654983521
Doubles4:0.706257104874
Doubles5:0.528184890747
Doubles6:0.461633205414
Doubles8:0.0134379863739
Doubles9:0.0108540058136
毫不奇怪,一半的迭代率缩短了一半的时间.
通常,混叠也被证明是一个很好的优化.但显然,
使用正确的数据结构 /算法组合是关键:更简单
代码,更快的速度为115倍(混叠143次).如果Pruebono
解决方案是正确的(并且是AFAICT),您的15小时计算
现在应该花不到10分钟...
Ubuntu 8.04 Core2 2.6(我认为)
没有心理
Dubles0:0.610555171967
Doubles1:0.29314494133
Doubles2:0.286273956299
Doubles3:0.281984090805
Doubles4:0.28240609169
Doubles5:0.207377910614
Doubles6:0.156388044357
Doubles8:0.00533080101013
Doubles9:0.00458884239197
与Psycho
Dubles0:0.127684116364
Doubles1:0.069571018219
Doubles2:0.064826965332
Doubles3:0.0702300071716
Doubles4:0.0647261142731
Doubles5:0.0522589683533
Doubles6:0.0437579154968
Doubles8:0.00190806388855
Doubles9:0.00214099884033
在这个小测试中,它的差异介于〜6倍至2倍之间,基本上仍然是
免费,为什么不; - >
Bruno Desthuilliers写道:
已经提交了几个.哈拉德对
冗余测试(即使他的解决方案似乎被打破了,CF下面) -
您的内部循环应该看起来像:
对于Xrange(i+1,len(in))的j
现在,显而易见的赢家是普鲁贝诺 - 甚至不优化,使用套装似乎
与最优化的更正版本相比, *方式 *的速度更快
您的算法.
这是一个快速的替补席 - 请大家双重研究以确保可以:
<剪切代码>
真的
Dubles0:1.55667901039
Doubles1:0.719144105911
Doubles2:0.703393936157
Doubles3:0.700654983521
Doubles4:0.706257104874
Doubles5:0.528184890747
Doubles6:0.461633205414
Doubles8:0.0134379863739
Doubles9:0.0108540058136
毫不奇怪,一半的迭代率缩短了一半的时间.
通常,混叠也被证明是一个很好的优化.但显然,
使用正确的数据结构 /算法组合是关键:更简单
代码,更快的速度为115倍(混叠143次).如果Pruebono
解决方案是正确的(并且是AFAICT),您的15小时计算
现在应该花不到10分钟...
Ubuntu 8.04 Core2 2.6(我认为)
没有心理
Dubles0:0.610555171967
Doubles1:0.29314494133
Doubles2:0.286273956299
Doubles3:0.281984090805
Doubles4:0.28240609169
Doubles5:0.207377910614
Doubles6:0.156388044357
Doubles8:0.00533080101013
Doubles9:0.00458884239197
与Psycho
Dubles0:0.127684116364
Doubles1:0.069571018219
Doubles2:0.064826965332
Doubles3:0.0702300071716
Doubles4:0.0647261142731
Doubles5:0.0522589683533
Doubles6:0.0437579154968
Doubles8:0.00190806388855
Doubles9:0.00214099884033
在这个小测试中,它的差异介于〜6倍至2倍之间,基本上仍然是
免费,为什么不; - >
# 回答19
在9月18日,7:42*PM,Steven d'Aprano
我的歉意(Seriosuly).在这种情况下,我认为可能只是
匆忙.对于它的价值,我在Google组上看到了您的帖子,但是我
跳过它.您写了两种解决方案,一个慢速和一个快速(
后者与Pruebono的相同.你把慢的一个放在
顶,我看到了
为了 ...
为了 ...
并直接进入下一条消息而没有阅读更好
解决方案.我知道只有一个需要一个循环,所以我
没有打扰阅读.实际上,我也错过了普鲁宾的帖子
直到我自己弄清楚之后(但在发布之前).
几个人提出了完全相同的解决方案Modulo
只有可变名称,说明了python的禅宗.
Geoff G-T
在9月18日,7:42*PM,Steven d'Aprano
我的歉意(Seriosuly).在这种情况下,我认为可能只是
匆忙.对于它的价值,我在Google组上看到了您的帖子,但是我
跳过它.您写了两种解决方案,一个慢速和一个快速(
后者与Pruebono的相同.你把慢的一个放在
顶,我看到了
为了 ...
为了 ...
并直接进入下一条消息而没有阅读更好
解决方案.我知道只有一个需要一个循环,所以我
没有打扰阅读.实际上,我也错过了普鲁宾的帖子
直到我自己弄清楚之后(但在发布之前).
几个人提出了完全相同的解决方案Modulo
只有可变名称,说明了python的禅宗.
Geoff G-T
# 回答20
2008年9月18日,布鲁诺·德索利尔(Bruno Desthuilliers)在《星期四》上写道:
...
真的
Dubles0:1.5566790103 9doubles1 : 0.719144105911doubles2 : 0.703393936157doubles3 : 0.700654983521doubles4 : 0.706257104874doubles5 : 0.528184890747doubles6 : 0.461633205414doubles8 : 0.0134379863739doubles9 : 0.0108540058136
当您更改我的代码时,请正确执行. :-)
您忘了将IN更改为_every_ place的In7.
sortk应该在_both _ ploce中为sortk7.
我从不让代码在我自己面前运行.我只是写了
在新闻阅读器中.但是现在我做到了,我有了一秒钟
版本作为奖励.
in7 = in [:]
def sortk7(n):
返回n.coordinates [0],n.coordinates [1]
def dubles7():
in7.sort(key = sortk7)
sn = []
sn_append = sn.append
in_len = len(in7)
对于i在Xrange(in_len)中:
node_i = in7 [i]
coords_i = node_i.coordinates
对于Xrange(i+1,in_len)的j:
如果coords_i [0] == in7 [j] .coordinates [0]:
如果coords_i [1] == in7 [j] .coordinates [1]:
sn_append(node_i)
别的:
休息
返回SN
def comp7(x,y):
返回CMP(X.Coordinates,Y.Coordinates)
def dubles7a():
In7.Sort(Comp7)
sn = []
sn_append = sn.append
in_len = len(in7)
对于i在Xrange(in_len)中:
node_i = in7 [i]
对于Xrange(i+1,in_len)的j:
node_j = in7 [j]
如果comp7(node_i,node_j)== 0:
sn_append(node_i)
别的:
休息
返回SN
这是结果. (PY2.5,WindowsXP,pentium4,2.6GHz,1.5GB):
我的版本还不错.
Dubles0:1.03830598582
Doubles1:0.47943719104
Doubles2:0.487412506338
Doubles3:0.475924733451
Doubles4:0.466548681466
Doubles5:0.340487967046
Doubles6:0.278480365521
Doubles7:0.0953190978183
Doubles7a:0.0784233750379
Doubles8:0.010236496538
Doubles9:0.00742803903848
Harald
2008年9月18日,布鲁诺·德索利尔(Bruno Desthuilliers)在《星期四》上写道:
...
真的
Dubles0:1.5566790103 9doubles1 : 0.719144105911doubles2 : 0.703393936157doubles3 : 0.700654983521doubles4 : 0.706257104874doubles5 : 0.528184890747doubles6 : 0.461633205414doubles8 : 0.0134379863739doubles9 : 0.0108540058136
当您更改我的代码时,请正确执行. :-)
您忘了将IN更改为_every_ place的In7.
sortk应该在_both _ ploce中为sortk7.
我从不让代码在我自己面前运行.我只是写了
在新闻阅读器中.但是现在我做到了,我有了一秒钟
版本作为奖励.
in7 = in [:]
def sortk7(n):
返回n.coordinates [0],n.coordinates [1]
def dubles7():
in7.sort(key = sortk7)
sn = []
sn_append = sn.append
in_len = len(in7)
对于i在Xrange(in_len)中:
node_i = in7 [i]
coords_i = node_i.coordinates
对于Xrange(i+1,in_len)的j:
如果coords_i [0] == in7 [j] .coordinates [0]:
如果coords_i [1] == in7 [j] .coordinates [1]:
sn_append(node_i)
别的:
休息
返回SN
def comp7(x,y):
返回CMP(X.Coordinates,Y.Coordinates)
def dubles7a():
In7.Sort(Comp7)
sn = []
sn_append = sn.append
in_len = len(in7)
对于i在Xrange(in_len)中:
node_i = in7 [i]
对于Xrange(i+1,in_len)的j:
node_j = in7 [j]
如果comp7(node_i,node_j)== 0:
sn_append(node_i)
别的:
休息
返回SN
这是结果. (PY2.5,WindowsXP,pentium4,2.6GHz,1.5GB):
我的版本还不错.
Dubles0:1.03830598582
Doubles1:0.47943719104
Doubles2:0.487412506338
Doubles3:0.475924733451
Doubles4:0.466548681466
Doubles5:0.340487967046
Doubles6:0.278480365521
Doubles7:0.0953190978183
Doubles7a:0.0784233750379
Doubles8:0.010236496538
Doubles9:0.00742803903848
Harald
# 回答21
在9月18日,晚上7:42,Steven d'Aprano
我对这里的优先级并不狡猾,但我提交了
本质上比Pruebono早两个小时.
人们没有看到我的帖子吗?除了我被所有人杀死的人
经济状况?我还问了一个关于httperror的问题,但我还没有看到任何
完全回答.
- -
史蒂文
我现在看到您的帖子,但是我在发布时没有注意到它.
可能是因为我正在使用明显的糟糕的Google组界面
这以不可靠而闻名.关于Usenet的重复解决方案是
几乎给定的,我认为重复解决方案是一件好事,
意味着其他人将能够理解该代码.
无论如何,我都不在这里荣耀,我以化名发布,所以
没有人发现我在工作中懒惰[usen [carrier
丢失的]
在9月18日,晚上7:42,Steven d'Aprano
我对这里的优先级并不狡猾,但我提交了
本质上比Pruebono早两个小时.
人们没有看到我的帖子吗?除了我被所有人杀死的人
经济状况?我还问了一个关于httperror的问题,但我还没有看到任何
完全回答.
- -
史蒂文
我现在看到您的帖子,但是我在发布时没有注意到它.
可能是因为我正在使用明显的糟糕的Google组界面
这以不可靠而闻名.关于Usenet的重复解决方案是
几乎给定的,我认为重复解决方案是一件好事,
意味着其他人将能够理解该代码.
无论如何,我都不在这里荣耀,我以化名发布,所以
没有人发现我在工作中懒惰[usen [carrier
丢失的]
# 回答22
Gabriel Genellina写道:
也许是由于新闻组/列表二元性...
实际上,情况是c.l.p <== python-list <==>
Gane.C.P.General Triality.
Gabriel Genellina写道:
也许是由于新闻组/列表二元性...
实际上,情况是c.l.p <== python-list <==>
Gane.C.P.General Triality.
# 回答23
在2008年9月20日星期六,19:01:42 +0200,布鲁诺·德索利尔(Bruno Desthuilliers)写道:
你是什么意思?还有多少其他人在谈论
我?
*眨眼*
- -
史蒂文
在2008年9月20日星期六,19:01:42 +0200,布鲁诺·德索利尔(Bruno Desthuilliers)写道:
你是什么意思?还有多少其他人在谈论
我?
*眨眼*
- -
史蒂文
# 回答24
在9月20日,9:20*PM,Steven d'Aprano
你是什么意思?还有多少其他人在谈论
我?
*赢 K* - - 史蒂文 为什么,不少于平常! *眨眼*
在9月20日,9:20*PM,Steven d'Aprano
你是什么意思?还有多少其他人在谈论
我?
*赢 K* - - 史蒂文 为什么,不少于平常! *眨眼*
# 回答25
KM写道: 这有一个根问题,即评估"如果"语句 n*n次,这是丑陋/慢的O(n^2)行为. 我的解决方案 设法通过恒定的乘数减少它,但是有几个人 提出了一个更优雅的O(n)解决方案,该解决方案是飞跃和界限 快点. -tkc