Opened 17 years ago
Closed 6 years ago
#32 closed enhancement (done)
Storing Arcs instead of OutArcIts in Dfs stack
| Reported by: | Balazs Dezso | Owned by: | Balazs Dezso |
|---|---|---|---|
| Priority: | major | Milestone: | LEMON 1.4 release |
| Component: | core | Version: | hg main |
| Keywords: | Cc: | ||
| Revision id: |
Description (last modified by )
The OutArcIt contains an int data field and a pointer to the graph, while the Arc just stores the int member. If we used Arcs in the Dfs stack, that could decrease the memory request of Dfs and it may provide better runtime performance.
Attachments (1)
Change History (15)
comment:1 Changed 17 years ago by
| Description: | modified (diff) |
|---|
comment:2 Changed 17 years ago by
| Milestone: | LEMON 1.0 release → Post 1.0 |
|---|
comment:3 Changed 17 years ago by
| Owner: | changed from Alpar Juttner to Balazs Dezso |
|---|
comment:5 Changed 16 years ago by
Hi I have tested this change, but obviously this is not a real performance enhancement. At most 2.5% speedup can be achieved with this change. What is your opinion, can we close the ticket or should we put the changeset in the repo?
comment:6 follow-up: 7 Changed 16 years ago by
The memory request of this implementation is about half of the current one, and it is not slower, or sometimes slightly faster. Am I right? So if it does not have any disadvantage compared to the current one, then it should be put in the repo, I think.
Did you tested the change on huge graphs (containing millions of nodes and arcs), in which the DFS tree contains very long paths, too?
Changed 16 years ago by
| Attachment: | d5bf497757ff.patch added |
|---|
comment:7 Changed 16 years ago by
Replying to kpeter:
The memory request of this implementation is about half of the current one, and it is not slower, or sometimes slightly faster. Am I right? So if it does not have any disadvantage compared to the current one, then it should be put in the repo, I think.
Did you tested the change on huge graphs (containing millions of nodes and arcs), in which the DFS tree contains very long paths, too?
Thanks for the suggestion, I tested with large cycle graph, and in this case I have measured 10% of improvement in the running time. I have uploaded the patch [d5bf497757ff]. The tester code can be found on the following place, http://lime.cs.elte.hu/~deba/hgwebdir.cgi/deba_lemon_loc/file/badee141a2d0/dfs_test.cc
comment:8 Changed 16 years ago by
| Milestone: | LEMON 1.1 release |
|---|
comment:9 Changed 15 years ago by
| Priority: | minor → major |
|---|
comment:10 Changed 15 years ago by
| Summary: | storing Arcs instead of OutArcIts in Dfs stack → Storing Arcs instead of OutArcIts in Dfs stack |
|---|
comment:11 Changed 15 years ago by
| Milestone: | → LEMON 1.3 release |
|---|
comment:13 Changed 11 years ago by
| Milestone: | LEMON 1.3 release → LEMON 1.4 release |
|---|
comment:14 Changed 6 years ago by
| Resolution: | → done |
|---|---|
| Status: | new → closed |
[d5bf497757ff] has been rebased as [15282595e6f4] and push to the main branch.
Iron decorates your home. They have a wide variety of design, assuring that you will find a special one for display at home. The metal stai http://www.hebei-railings.cn/