|
Your inner loop is executing 8 billion times; no wonder it takes a while.
The Floyd-Warshall algorithm is O(n^3), so if you double the number of nodes in the graph, it will slow down another factor of 8. A brute force approach like this is reasonable only for small graphs.
One way to somewhat improve speed is by using pointers; multi-dimensional array lookup isn't very efficient.
Another possible improvement is getting better cache efficiency by reordering the operations (a bit tricky). And then you could go for more elaborate algorithms, requiring a lot more code.
|
|
|
|
|
If you use 25% cpu, on a quad CPU, with a single thread, there is room for improvement, unfortunately, it's bit more complicated than what you're using. HAve a look at this[^].
|
|
|
|
|
Exactly what he needs. Plz send codez ASAP. 
|
|
|
|
|
There's a reason you're only at 25% on your CPU. You're running the process on a single thread which means only one core is being used. So, you're actually maxing out that single core and using nothing on the other cores.
I don't really see any way to speed up that algorithm.
I take it back...Pete may have found a great solution with 4.0
modified on Monday, May 3, 2010 2:37 PM
|
|
|
|
|
If you are using .NET 4, you might want to take a look at Parallel.For. Take a look at the Task Parallel Library[^].
"WPF has many lovers. It's a veritable porn star!" - Josh Smith As Braveheart once said, "You can take our freedom but you'll never take our Hobnobs!" - Martin Hughes.
My blog | My articles | MoXAML PowerToys | Onyx
|
|
|
|
|
Would that really work, with all the odd data dependencies? (I don't know, which is why I'm asking..)
|
|
|
|
|
With careful marshalling, yes. It would move the calculation off one core, and it would be interesting to see how it performs.
"WPF has many lovers. It's a veritable porn star!" - Josh Smith As Braveheart once said, "You can take our freedom but you'll never take our Hobnobs!" - Martin Hughes.
My blog | My articles | MoXAML PowerToys | Onyx
|
|
|
|
|
Hi Harold,
in
for (int k = 0; k < 2000; k++) {
for (int i = 0; i < 2000; i++) {
for (int j = 0; j < 2000; j++) {
G[i, j] = Math.Min(G[i, j], G[i, k] + G[k, j]);
}
}
}
each element G[i,j] depends on the elements from the row and column it sits in, so you can execute the iterations of the inner loop in parallel as they all modify a different matrix element, and all read elements that are not going to be written, unless k==i or k==j. You can deal with the former right away (outside the inner loop), and the latter can be handled separately. So it becomes:
for (int k = 0; k < 2000; k++) {
for (int i = 0; i < 2000; i++) {
if (i==k) {
for (int j = 0; j < 2000; j++) {
G[i, j] = Math.Min(G[i, j], G[i, k] + G[k, j]);
}
} else {
//G[i, j] = Math.Min(G[i, j], G[i, j] + G[j, j]); // special case k==j
G[i, k] = Math.Min(G[i, k], G[i, k] + G[k, k]); // special case k==j
for (int j = 0; j < 2000; j++) {
if (j!=k) G[i, j] = Math.Min(G[i, j], G[i, k] + G[k, j]);
}
}
}
}
And now the highlighted loop has no data dependencies any more.
Furthermore, the diagonal elements start at value zero; assuming no negative cycles in the graph, their MIN operation won't affect them, and the special cases do not need to be set aside, so we are back at the original code.
If negative cycles are allowed, proper handling still allows parallellization with negative cycle detection (which turns diagonal elements into negative values), and even then the special cases are not really necessary as the presence of negative cycles makes the results not optimal as the optimum would be minus infinity anyway.
[EDIT]
fixed a mistake, signaled by Pete
[\EDIT]
|
|
|
|
|
Nice thanks
|
|
|
|
|
you're welcome.
Now go install .NET 4.0 and write that article!
|
|
|
|
|
I'm not sure.. that's actually quite advanced.. and I'm still only halfway understanding linear time suffix array construction (bit slow I know..)
|
|
|
|
|
If things are getting slow, you should start doing some of them in parallel...
|
|
|
|
|
Win
Anyway, how's your prime number thing going?
|
|
|
|
|
very good, thanks, it currently uses 1.1 threads. There isn't enough work to keep a dual-core busy
I'll publish it later this year.
|
|
|
|
|
I've just knocked up a blog post[^] to show how this code could be accomplished using .NET 4. Here's the same code rewritten to use the Task Parallel Library.
"WPF has many lovers. It's a veritable porn star!" - Josh Smith As Braveheart once said, "You can take our freedom but you'll never take our Hobnobs!" - Martin Hughes.
My blog | My articles | MoXAML PowerToys | Onyx
|
|
|
|
|
Hi Pete,
I'm afraid I disagree with your parallel sample in this particular case; it seems to violate the Floyd-Warshall_algorithm[^], which theoretically uses a three-dimensional array, but then maps the k-iterations (the outer loop) onto a single two-dimensional array, provided it gets executed in the correct sequence.
In another part of this thread I have shown Harold how parts of the calculation could be executed in parallel, but your and my approach are quite different.
FWIW: I have no clue what the speed up would be for say a 2000 node graph and a 4-way core; I'm not overly optimistic as there is a lot of data involved, so using multiple cores is likely to seriously reduce cache efficiency.
|
|
|
|
|
Luc - I wasn't trying to demonstrate the algorithm. I was demonstrating purely and simply how to convert his code into a Parallel.For.
"WPF has many lovers. It's a veritable porn star!" - Josh Smith As Braveheart once said, "You can take our freedom but you'll never take our Hobnobs!" - Martin Hughes.
My blog | My articles | MoXAML PowerToys | Onyx
|
|
|
|
|
I appreciate that, Pete. However I'm afraid you wrecked the algorithm, which isn't a very nice thing to do. When the results aren't the same, there isn't much point in measuring the speed difference, is there?
|
|
|
|
|
BTW - your code sample won't compile. The following line is the problem because of an uninitialized variable:
G[i, j] = Math.Min(G[i, j], G[i, j] + G[j, j]);
"WPF has many lovers. It's a veritable porn star!" - Josh Smith As Braveheart once said, "You can take our freedom but you'll never take our Hobnobs!" - Martin Hughes.
My blog | My articles | MoXAML PowerToys | Onyx
|
|
|
|
|
you're right, I replaced k's by j's, it should have been the other way around. Sorry for that.
|
|
|
|
|
hi ,i modified my code folowing that, but i get some error
folowing code running !
double[,] a, b, c;<br />
a = new double[2000, 2000];<br />
b=new double[2000,2000];<br />
c=new double[2000,2000];<br />
int s = 2000;<br />
<br />
Parallel.For(0, s, delegate(int i)<br />
{<br />
for (int j = 0; j < s; j++)<br />
{<br />
double v = 0;<br />
<br />
for (int k = 0; k < s; k++)<br />
{<br />
v += a[i, k] * b[k, j];<br />
}<br />
<br />
c[i, j] = v;<br />
}<br />
});
bu my code isn't run 
Parallel.For(0, nrons, delegate(int k)<br />
{<br />
for (i = 0; i < nrons; i++)<br />
for (j = 0; j < nrons; j++)<br />
if (G[i, j]> (G[i, k] + G[k, j]) )<br />
G[i, j] =(G[i, k] + G[k, j]) ;<br />
<br />
<br />
}<br />
<br />
<br />
);<br />
why did i get error ?
|
|
|
|
|
karayel_kara wrote: my code isn't run
is not informative. does it compile? if not, what is the first error? does it run? if not, what is the first exception, with all the details? and at what line is it pointing?
anyway, your code looks all wrong. You now have three arrays. Why? You don't initialize the arrays. I see six for loops, you only need three. And the way I understand the algorithm you can not possibly run the outer loop in parallel (that was the essence of my comment to Pete too).
And please, please, please, please, please, please, show code in PRE tags, not in CODE tags.
Final remark: when all you do to the algorithm is run it in parallel, the best you can hope for is to get it N times faster, with N the number of cores, say 4. That is something, but not much. And there are no guarantees. My first experiment did run 5 times slower, because it trashed the caches all the time! (and I'm afraid that will be true for your app too).
|
|
|
|
|
Hello,
I was trying to get the content of a file in a string. I have used the following code ...
String strContent = "";
FileStream flDoc = new FileStream(m_tbxBrowser.Text, FileMode.Open, FileAccess.Read);
Byte[] bytContent = new Byte[flDoc.Length];
flDoc.Read(bytContent, 0, Convert.ToInt32(flDoc.Length));
strContent = System.Text.ASCIIEncoding.ASCII.GetString(bytContent);
But in the output, strContect some special symbols like
® is missing, and is replaced by
???
Can anyone help me to solve this? Thanks in advance.
Sebastian
|
|
|
|
|
The ASCII encoder substitutes a ? when it encounters a character code above 127. What you probably have in the file is an extended ascii character set, the most common of which is represented in Windows by the code page 1252, Single Byte Character Sets (SBCS)[^]. You can get an instance of the encoding with
Encoding coder = Encoding.GetEncoding(1252);
If you are going to write to the file I strongly suggest that you do some round trip tests to check that you have selected the correct encoding.
i.e.
Read the file
Convert to a string using the encoding
Convert the string back to bytes
Write to a new file
Check that the orignal and rewritten file are identical
Alan.
|
|
|
|
|
Hi,
i am trying remove some items from the listbox in C# windows application. but it doesn't work for me. can you please help??
below is the code snippet
foreach (object o in Lstservices.SelectedItems)
{
MessageBox.Show(Lstservices.SelectedItem.ToString());
Lstservices.SelectedItems.Remove(Lstservices.SelectedItem);
}
fttyhtrhyfytrytrysetyetytesystryrty
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
