|
Hi, I have tried to implement my own array sort for struct arrays. But I noticed that the performance was not what I expected. So I tried to find out the reason behind and made a very simple test code, using not a struct array but a normal one dimensional long array. The comparer class looks like this:
struct sortKeys : IComparer<long>
{
private static readonly Comparer<long> comparer
= Comparer<long>.Default;
public int Compare(long x, long y)
{
return x.CompareTo(y);
}
public static int GetHashCode(long value)
{
return comparer.GetHashCode();
}
}
and for comparing the Array.Sort without and with the comparer, I wrote the following:
private void compareSortsPerformance()
{
Stopwatch sw = new Stopwatch();
int Maximum = 10000000;
Random rand = new Random();
long[] la = new long[Maximum];
for (int i = 0; i < Maximum; i++)
la[i] = rand.Next();
sw.Start();
Array.Sort(la);
Console.WriteLine("Sort without icomparable" + sw.ElapsedMilliseconds);
for (int i = 0; i < Maximum; i++)
la[i] = rand.Next();
sortKeys sk = new sortKeys();
sw.Restart();
Array.Sort(la, sk);
Console.WriteLine("Sort with icomparable" + sw.ElapsedMilliseconds);
}
Array.Sort(la) is about 3 times faster than Array.Sort(la,sk). If I do the same comparison for a struct array with only one long variable inside, it takes even longer. Does anyone have an idea how to increase the speed for this first step?
Thx
|
|
|
|
|
Interesting question. I've taken your code and come to the same findings.
My suspicion is that because you are using a primitive type 'long' as the thing to sort, .NET has its own optimized method of sorting these effectively bypassing the whole IComparer/IComparable mechanism as a specific performance tuned operation.
What I mean by that is that it knows what a long is, so when sorting without a comparer specified it can use a dedicated long sort rather than something that repeatedly calls IComparer.Equals.
In your example, it gets called around about 300 million times...
Regards,
Rob Philpott.
|
|
|
|
|
Good to know or... bad to know that my code seems to be as efficient as possible... but still 3 times slower than the Array.Sort(la). I have implemented a quicksort as well and found the same performance as when I use the comparer Array.Sort(la,sk). But I read on several pages that C# uses quicksort in Array.Sort(). Using unsafe would increase the performance by about 20%, so something is strange. There must be a possibility to further increase the speed.
It would be interesting to know how they do it, because if I want to improve the speed of the struct array sort, which needs 8 times longer than the Array.Sort(la), I need to understand the mechanism behind the .NET implementation. Do you have an idea of how to get behind their mechanism?
Thx
|
|
|
|
|
|
|
Rob Philpott wrote: Well, you can use something like dotPeek to disassemble mscorlib ...
Or, go to http://sourceof.net/[^] and get the source straight from the horse's mouth. 
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
... which is altogether a much better idea! Good thinking.
Regards,
Rob Philpott.
|
|
|
|
|
In the end I found the source code of the c++ quicksort implementation in clr and it's really very similar to the quicksort algorithm I used in c# (see node below).
So I guess one should switch to c++ if it comes to sorting big structs as well and the average performance difference between c# and c++ of a few percenant points does not hold for this kind of operations. For everybody who tries to find the answer to the same question, here is the code they use:
static void QuickSort(KIND keys[], KIND items[], int left, int right) {
WRAPPER_CONTRACT;
// Make sure left != right in your own code.
_ASSERTE(keys != NULL && left < right);
do {
int i = left;
int j = right;
KIND x = keys[i + ((j - i) >> 1)];
do {
while (keys[i] < x) i++;
while (x < keys[j]) j--;
_ASSERTE(i>=left && j<=right);
if (i > j) break;
if (i < j) {
KIND key = keys[i];
keys[i] = keys[j];
keys[j] = key;
if (items != NULL) {
KIND item = items[i];
items[i] = items[j];
items[j] = item;
}
}
i++;
j--;
} while (i <= j);
if (j - left <= right - i) {
if (left < j) QuickSort(keys, items, left, j);
left = i;
}
else {
if (i < right) QuickSort(keys, items, i, right);
right = j;
}
} while (left < right);
}
|
|
|
|
|
Part of the problem is your code is not in-lined with the code calling your comparer. Just the fact of supplying a comparer introduces the overhead of calling your function and popping the result off the stack.
The only way to solve this problem is to write your own sorting algorithm, specifically typed to sort longs. That way, all the code is completely in-lined and as compact as possible with no function call overhead.
|
|
|
|
|
I tried as well to build a quicksort, taken and adapted to long from Searching and Sorting Algorithms via C#[^]
But it needs longer than Array.Sort... sorry, I forgot to update the stopwatch before. But now quicksort is still slower than the others.
private void compareSortsPerformance()
{
Stopwatch sw = new Stopwatch();
int Maximum = 10000000;
Random rand = new Random();
long[] la = new long[Maximum];
for (int i = 0; i < Maximum; i++)
la[i] = rand.Next();
sw.Start();
Array.Sort(la);
Console.WriteLine("Sort without icomparable" + sw.ElapsedMilliseconds);
for (int i = 0; i < Maximum; i++)
la[i] = rand.Next();
sortKeys sk = new sortKeys();
sw.Restart();
Array.Sort(la, sk);
Console.WriteLine("Sort with icomparable" + sw.ElapsedMilliseconds);
for (int i = 0; i < Maximum; i++)
la[i] = rand.Next();
sw.Restart();
QuickSort(ref la);
Console.WriteLine("Sort with Quicksort" + sw.ElapsedMilliseconds);
}
public static void QuickSort(ref long[] x)
{
qs(x, 0, x.Length - 1);
}
public static void qs(long[] x, long left, long right)
{
long i, j;
long pivot, temp;
i = left;
j = right;
pivot = x[(left + right) / 2];
do
{
while ((x[i] < pivot) && (i < right)) i++;
while ((pivot < x[j]) && (j > left)) j--;
if (i <= j)
{
temp = x[i];
x[i] = x[j];
x[j] = temp;
i++; j--;
}
} while (i <= j);
if (left < j) qs(x, left, j);
if (i < right) qs(x, i, right);
}
|
|
|
|
|
In SAP I created Web Service ZWS_SQRT, which uses the function module Z_SQRT with number as input parameter and square root as output parameter.
Then, in Visual Studio I added an Web Service Reference named SquareRoot and I got ZWS_SQRT control in a toolbox.
The code:
private void button1_Click(object sender, EventArgs e)
{
NetworkCredential credentials = new NetworkCredential("GORENMI1", "tlaxcala3");
zwS_SQRT1.Credentials = credentials;
SquareRoot.ZSqrt x = new SquareRoot.ZSqrt();
x.Number = 16;
SquareRoot.ZSqrtResponse y = zwS_SQRT1.ZSqrt(x);
}
sometimes works (it gives the value 4), but mostly not - it returns the error message "The request was aborted: The request was canceled.". What is wrong ?
Please help. Thanks in advance.
Miran
|
|
|
|
|
Amoxtli wrote: The request was aborted: The request was canceled.". What is wrong ?
Probably something inside the web service. But since you created it then you are best placed to be able to know what it is doing.
|
|
|
|
|
Thank you for your answer. The service works fine localy in SAP test: input
<n0:zsqrt xmlns:n0="urn:sap-com:document:sap:soap:functions:mc-style">
<number>16
gives the result
-<n0:zsqrtresponse xmlns:n0="urn:sap-com:document:sap:soap:functions:mc-style">
<result>4.0E0
The code
WebRequest request = WebRequest.Create("http://guediserr.durs.si:8010/sap/bc/srt/wsdl/flv_10002A111AD1/bndg_url/sap/bc/srt/rfc/sap/zws_sqrt/200/zws_sqrt/jaojao?sap-client=200");
request.Credentials = new System.Net.NetworkCredential("GORENMI1", "tlaxcala3"); ;
HttpWebResponse response = (HttpWebResponse)request.GetResponse();
Stream dataStream = response.GetResponseStream();
StreamReader reader = new StreamReader(dataStream);
string responseFromServer = reader.ReadToEnd();
reader.Close();
dataStream.Close();
response.Close();
also gives the right WSDL content.
regards
|
|
|
|
|
So exactly how do you think anyone here can help?
|
|
|
|
|
It is very simple. Maybe someone solved similar problem and he might help me. If the mistake is in Web Service, like you said in previous post, then the problem is a little harder and I must go study it once again.
regards
Miran
|
|
|
|
|
Maybe I found the solution. Somehow, the service creates an error "The request was aborted: The request was canceled.". But if I wrap the call into While loop, I always get the result (sometimes in first loop, sometimes 5th and so on). If this is a correct solution, I still don't know, but anyway.
while (b)
{
try
{
y = root.ZSqrt(x);
b = false;
}
catch
{
b = true;
}
i++;
}
So, the problem was in Web service, like you said. Thank you.
Regards
|
|
|
|
|
But that is not a solution. You are just hiding the underlying error, and sooner or later it will jump up and bite you.
|
|
|
|
|
Aha, thanks. I'll try to find that error.
|
|
|
|
|
The PdfFileWriter library is great! I am creating a Chinese PDF file by using PdfFileWriter. But I am having trouble with it. Can anyone tell me this library can support Chinese? What's the solution? Thanks in advance!
|
|
|
|
|
Don't post this in a general forum - if you got the code from an article, then there is a "Add a Comment or Question" button at the bottom of that article, which causes an email to be sent to the author. They are then alerted that you wish to speak to them.
Posting this here relies on them "dropping by" and realising it is for them.
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
|
|
|
|
|
I need the input strings to display unsorted first ... then call mergesort to arrange them alphabetically which I can not find any guidance with
The original merge sort works with the numbers and I understand that but getting the size of the array for names to be sorted is confusing me and wont work
private void btnExecute_Click(object sender, EventArgs e)
{
int length = Int32.Parse(Microsoft.VisualBasic.Interaction.InputBox("Enter a Number for how many Names to Sort :"));
string[] nameArray = new string[length];
foreach (string n in nameArray)
{
string name = Microsoft.VisualBasic.Interaction.InputBox("Enter " + length + " Names to add to Array:");
length = length - 1;
txtOutput.Text += name + "\r\n";
}
txtOutput.Text += nameArray.Length + "Names Added to List Unsorted ";
}
public void mergeSort(string[] nameArray, int lower, int upper)
{
int middle;
if (upper == lower)
return;
else
{
middle = (lower + upper) / 2;
mergeSort(nameArray, lower, middle);
mergeSort(nameArray, middle + 1, upper);
Merge(nameArray, lower, middle + 1, upper);
}
}
public void Merge(string[] nameArray, int lower, int middle, int upper)
{
string[] temp = new string[nameArray.Length];
int lowEnd = middle - 1;
int low = lower;
int n = upper - lower + 1;
while ((lower <= lowEnd) && (middle <= upper))
{
if ((nameArray[lower]).CompareTo(nameArray[middle]) <= 0)
{
temp[low] = nameArray[lower];
low++;
lower++;
}
else
{
temp[low] = nameArray[middle];
low++;
middle++;
}
}
while (lower <= lowEnd)
{
temp[low] = nameArray[lower];
low++;
lower++;
}
while (middle <= upper)
{
temp[low] = nameArray[middle];
low++;
middle++;
}
for (int i = 0; i < n; i++)
{
nameArray[upper] = temp[upper];
upper--;
}
}
}
|
|
|
|
|
Um.
That looks like you found some Console based code which sort-of does what you want, and (without thinking about it much at all) hacked it about to run in a WinForms app.
And now you want it fixed to do what your homework requires...
Start again: design a WinForms app that collects strings from the user and added them one at a time to a collection. Then write a merge sort that works with the collected data. You've got the framework code for the sort, it should be relatively simple to tweak.
But this is your homework: and so it's your job to do this.
And I have to say that if I was your tutor, I'd give you a failing grade for that code, even if it did work...
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
|
|
|
|
|
yes Im learning the merge sort is the one to be altered to accept strings ... no I havent HACKED anything Im trying to learn and understand you really dont have to be as mean ablout it learning to understand it Im not asking anyone to DO it im asking for help in how to modify it as when I search everything has to do wwith ints NOT Strings
|
|
|
|
|
That's not being mean: if you had written that code you would understand it and know exactly what (trivial) changes you need to make to the merge sort to make it work with strings.
So what part of it don't you understand?
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
|
|
|
|
|
Hi,
I have a problem in this i have to execute a COBOL code in c#.net. in this COBOL code code in string format. So i just need to execute the code get the result by passing the cobol code.
suppose we have a if condition cobol code
EVALUATE TRUE
WHEN 15 > 13
MOVE ZEROS TO TEST-ADD-STATUS
WHEN OTHER
MOVE TEST-LOGO-RPT TO TEST-ADD-STATUS
END-EVALUATE
Now i want to execute this code in C#. This code generated at run time bu my system. So i need code to generic method to execute the COBOL code.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
