Python列表元素赋值操作效率有关问题
Python列表元素赋值操作效率问题
题目：一个五位数减去另一个五位数，差为20085，且这两个五位数的的各位数字都不相同，求这两个五位数。
我的思路是从0123456789穷举到9876543210，用前五位减后五位。用python实现的代码如下：
但是执行速度十分慢，从0123456789到1023456789用了40分钟左右。而我用java实现的代码则在4分钟左右的时间运行结束。下面是java的代码：
运行结果：
python里用的是列表，java里用的是数组，求帮忙分析执行速度慢的原因。谢谢！
------解决思路----------------------
python比java慢10倍基本上算正常(http://benchmarksgame.alioth.debian.org/u32/python.php), 不是很奇怪.
关键是改进算法.
测试结果:
选择下面的文字看代码.
In [6]: def is_valid(a, b):
...: return len(set(str(a)+str(b))) == 10
In [7]: def solve(diff):
...: for i in range(10000, 100000-diff):
...: if is_valid(i, i+diff):
...: print i, i+diff
题目：一个五位数减去另一个五位数，差为20085，且这两个五位数的的各位数字都不相同，求这两个五位数。
我的思路是从0123456789穷举到9876543210，用前五位减后五位。用python实现的代码如下：
from time import *
t_format = '%d-%02d-%02d %02d:%02d:%02d'
num = list(range(10))
last = list(range(9, -1, -1))
bo = 20085
def B_Last(num):
if num == last:
return True
return False
def B_Next(num):
i = -1
while i >= -len(num):
if num[i] == 9:
num[i] = 0
else:
num[i] += 1
return
i -= 1
def B_Repl(num):
for n in num:
if num.count(n) != 1:
return True
return False
def B_Cal(num):
a = num[0:5]
b = num[5:]
a_sum = 0
b_sum = 0
for n in a:
i = 4
a_sum = n * (10 ** 4)
i -= 1
for n in b:
i = 4
b_sum = n * (10 ** 4)
i -= 1
if a_sum - b_sum == bo:
print(num)
t1 = localtime(time())
print(t_format % t1[0:6])
while not B_Last(num):
if B_Repl(num):
B_Next(num)
continue
B_Cal(num)
B_Next(num)
t2 = localtime(time())
print(t_format % t2[0:6])
但是执行速度十分慢，从0123456789到1023456789用了40分钟左右。而我用java实现的代码则在4分钟左右的时间运行结束。下面是java的代码：
import java.util.Date;
import java.text.SimpleDateFormat;
import java.text.ParseException;
public class BjOlympic {
private static int[] num = new int[10];
private static int bo = 20085;
private static boolean[] tag = new boolean[10];
// 初始化数组
private static void B_Init() {
for (int i = 0; i < num.length; i++) {
num[i] = i;
}
}
// 判断是否最后一个数
private static boolean B_Last() {
for (int i = 0, k = num.length - 1; i < num.length; i++, k--) {
if (num[i] != k) {
return false;
}
}
return true;
}
// 取下一个数
private static void B_Next() {
for (int i = num.length - 1; i >= 0; i--) {
if (num[i] == 9) {
num[i] = 0;
} else {
num[i] = num[i] + 1;
return;
}
}
}
// 判断各位数字是否有重复
private static boolean B_Repl() {
for (int i = 0; i < 10; i++) {
tag[i] = false;
}
for (int i = 0; i < 10; i++) {
if (tag[num[i]] == true) {
return true;
}
tag[num[i]] = true;
}
return false;
}
// 计算差是否为20085，并输出结果
private static void B_Cal() {
int s1 = 0, s2 = 0;
for (int i = 0, e = 4; i < num.length/2; i++, e--) {
s1 += num[i] * (int) Math.pow(10, e);
}
for (int i = num.length/2, e = 4; i < num.length; i++, e--) {
s2 += num[i] * (int) Math.pow(10, e);
}
if (s1 - s2 == bo) {
for (int i = 0; i < num.length; i++) {
System.out.print(num[i]);
if (i == ((num.length - 1) / 2)) {
System.out.print(" ");
}
}
System.out.println("");
}
}
public static void main(String[] args) {
SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String bg = df.format(new Date());
System.out.println(bg);
for (B_Init(); !B_Last(); B_Next()) {
if (B_Repl()) {
continue;
}
B_Cal();
}
String ed = df.format(new Date());
System.out.println(ed);
try {
Date bg1 = df.parse(bg);
Date ed1 = df.parse(ed);
long l = (ed1.getTime() - bg1.getTime()) / 1000;
System.out.println(l + "seconds");
} catch (ParseException e) {
e.printStackTrace();
}
}
}
运行结果：
Compiling BjOlympic.java.......
-----------OUTPUT-----------
2015-09-29 15:55:58
35067 14982
48036 27951
58026 37941
62058 41973
72048 51963
85017 64932
2015-09-29 16:00:33
275seconds
[Finished in 275.7s]
python里用的是列表，java里用的是数组，求帮忙分析执行速度慢的原因。谢谢！
------解决思路----------------------
python比java慢10倍基本上算正常(http://benchmarksgame.alioth.debian.org/u32/python.php), 不是很奇怪.
关键是改进算法.
测试结果:
In [8]: %time solve(20085)
14982 35067
27951 48036
37941 58026
41973 62058
51963 72048
64932 85017
CPU times: user 156 ms, sys: 24 ms, total: 180 ms
Wall time: 159 ms
选择下面的文字看代码.
In [6]: def is_valid(a, b):
...: return len(set(str(a)+str(b))) == 10
In [7]: def solve(diff):
...: for i in range(10000, 100000-diff):
...: if is_valid(i, i+diff):
...: print i, i+diff