m********r
发帖数: 23 | 1 下面的内容是我前面问题的背景. 请大家姑妄读之. 有什么问题, 请
回贴或回信到 m*******[email protected]
对每一个自然数, 我们可以定义一种特殊的自然生成图, 把所有由该自然数生成的
不同的图作为一个集合, 该集合与该自然数之间是否有尚属未知的关系, 是我所研
究的目的.
自然生成图具有以下特征:
1. 该图是无向连通图;
2. 将图置于坐标之上, 任何一个顶点的坐标x和y均为整数;
3. 顶点A和顶点B由边直接相连当且仅当A和B之间的距离为1;
4. 根据规则3, 所有边的长度均为1.
根据以上规则, 由自然数4 可生成以下图:
*-*-*-* *-*-* *-*-* *-* *-*
| | | | |
* * *-* *-*
(1) (2) (3) (4) (5)
在定义了以上规则之后, 我们仍需进一步定义如何区分不同的图. 在此我们引入距
离矩阵.
距离矩阵: 对有n 个顶点组成的连通图, 从每 | g*****g
发帖数: 34805 | 2 It's a large number of combinations out there, and it's certainly CPU
intensive. But you shouldn't have problem with 1G memory. The problem is very
dividable.
You can first generate and computer the matrix one by one and keep them in a
queue, at the same time hash them in a table, once your memory filled, write
out the first one in the queue to memory and remove it from your queue. After
the whole file generated, there should be still some redudancy, then it's an
external sorting problem.
By the | m********r
发帖数: 23 | 3
very
After
I don't think it'll help to store the intermediate result to a file. There's
no need and it can become a bottleneck.
Now it may be the time to rewrite in C++ but I'm not familiar with it and
don't have the time.
The good thing about Java for this is there are very good profilers like
OptimizeIt, JProbe etc which helped me to improve algorithms. I don't know if
profilers in C++ are as good as them.
【在 g*****g 的大作中提到】
: It's a large number of combinations out there, and it's certainly CPU
: intensive. But you shouldn't have problem with 1G memory. The problem is very
: dividable.
: You can first generate and computer the matrix one by one and keep them in a
: queue, at the same time hash them in a table, once your memory filled, write
: out the first one in the queue to memory and remove it from your queue. After
: the whole file generated, there should be still some redudancy, then it's an
: external sorting problem.
: By the
| g*****g
发帖数: 34805 | 4 It all depends on whether you have enough memory.
Many problem sorted externally a decaded ago is now internally.
a
write
an
if
【在 m********r 的大作中提到】
:
: very
: After
: I don't think it'll help to store the intermediate result to a file. There's
: no need and it can become a bottleneck.
: Now it may be the time to rewrite in C++ but I'm not familiar with it and
: don't have the time.
: The good thing about Java for this is there are very good profilers like
: OptimizeIt, JProbe etc which helped me to improve algorithms. I don't know if
: profilers in C++ are as good as them.
| m******t
发帖数: 2416 | 5
I don't think there is going to be essential difference as far as
language is concerned - you are not going to be able to improve
the order of magnitude. In fact, a Java implementation of this algorithm
is not likely very large trunk of code. Most of it might be optimized
by hotspot after a short ramp-up time any way.
【在 m********r 的大作中提到】
:
: very
: After
: I don't think it'll help to store the intermediate result to a file. There's
: no need and it can become a bottleneck.
: Now it may be the time to rewrite in C++ but I'm not familiar with it and
: don't have the time.
: The good thing about Java for this is there are very good profilers like
: OptimizeIt, JProbe etc which helped me to improve algorithms. I don't know if
: profilers in C++ are as good as them.
| g*****g
发帖数: 34805 | 6 When your program is going to run one hour or two before you can see some
result, a C++ implementation over Java may be worth it. Even 50% is much
relief when you need it run over and over again.
if
【在 m******t 的大作中提到】
:
: I don't think there is going to be essential difference as far as
: language is concerned - you are not going to be able to improve
: the order of magnitude. In fact, a Java implementation of this algorithm
: is not likely very large trunk of code. Most of it might be optimized
: by hotspot after a short ramp-up time any way.
| m********r
发帖数: 23 | 7
大家对问题本身有什么看法? 如果确实存在这样的关系:
avg(distsum) = a*n^b
是否有研究的价值?
and
know
【在 g*****g 的大作中提到】
: When your program is going to run one hour or two before you can see some
: result, a C++ implementation over Java may be worth it. Even 50% is much
: relief when you need it run over and over again.
:
: if
|
|
