|
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
|
|
|
|
|
You are trying to remove items from the same listbox you are running your loop on - this is not allowed in C#.
By looking at your code, it appears you are trying to empty your list box.
Use the Clear method (on the listbox).
|
|
|
|
|
yadlaprasad wrote: Lstservices.SelectedItems.Remove(Lstservices.SelectedItem);
I don't think this'll work.
Use this instead :
Lstservices.Items.Remove(o);
|
|
|
|
|
use bellow
while (Lstservices.SelectedItems.Count>0)
{
Lstservices.Items.Remove(Lstservices.SelectedItem);
}
Abdul Rahaman Hamidy
Database Developer
Kabul, Afghanistan
|
|
|
|
|
All that your code does is to remove an item from the SelectedItems collection of your ListBox (i.e. you are unselecting it), not from the ListBox itself.
To remove/delete from the listbox replace
Lstservices.SelectedItems.Remove(Lstservices.SelectedItem);
with
Lstservices.Items.Remove(Lstservices.SelectedItem);
but bear in mind that, as someone else has mentioned, C# will complain if you try this whilst iterating over the collection.
Henry Minute
Do not read medical books! You could die of a misprint. - Mark Twain
Girl: (staring) "Why do you need an icy cucumber?"
“I want to report a fraud. The government is lying to us all.”
|
|
|
|
|
With foreach, you are not allowed to alter the collection; you could use a while loop instead.
|
|
|
|
|
I am using this library (available on CodePlex) to retrieve and parse a web page.
When I compared the retrieved web page to the "page source" reported by a normal web browser, the two results don't match. Before I rewrite the code to use the WebClient object, I figured I'd ask if anyone else noticed this? Since he just wrote CP Vanity, any comments from Luc?
.45 ACP - because shooting twice is just silly
-----
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"The staggering layers of obscenity in your statement make it a work of art on so many levels." - J. Jystad, 2001
|
|
|
|
|
It's possible that the page source (when viewed in a browser) includes content generated by JavaScript, which will of course not show up in content programatically retrieved by WebClient.
/ravi
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
