Array handling
-
I have a two dimensional array of 600 by 800 integers, and while processing this array, I need to visit each element approximately 250 times. This increases the total number of references I need to make to a mammoth figure of 120 million, accordingly increasing the time taken by this method (am using C#.NET) to around 3.5 seconds. This time figure however, is more than what is acceptable in my scenario. I would want to bring it down to around 2 seconds... So, I was wondering - is there a way to construct and process a matrix-like structure (without or without using two-dimensional arrays; or using pointers or something) which will take less time? Any assistance is appreciated...
Try using the
System.Collections.ArrayList. You'll be surprised, but the ArrayList is 100's of times faster than an Array. Enumeration is also lightning fast compared to the Array. It's all I use unless some prebuilt function just must use the standard Array. The ArrayList is also Dynamic, which means it can shrink and grow automatically without the need to "Redim" or move values in and out of one Array to the next. One quick note about the ArrayList constructor. It must be instantiated by calling the New method, unlike the Array -Dim TestArray(15) As String, you must create the ArrayList,Dim TestArrayList As New ArrayList, then add to it like this...TestArrayList.Add(_Value_). Hope this helps, Scott Page -
Try using the
System.Collections.ArrayList. You'll be surprised, but the ArrayList is 100's of times faster than an Array. Enumeration is also lightning fast compared to the Array. It's all I use unless some prebuilt function just must use the standard Array. The ArrayList is also Dynamic, which means it can shrink and grow automatically without the need to "Redim" or move values in and out of one Array to the next. One quick note about the ArrayList constructor. It must be instantiated by calling the New method, unlike the Array -Dim TestArray(15) As String, you must create the ArrayList,Dim TestArrayList As New ArrayList, then add to it like this...TestArrayList.Add(_Value_). Hope this helps, Scott Page -
Try using the
System.Collections.ArrayList. You'll be surprised, but the ArrayList is 100's of times faster than an Array. Enumeration is also lightning fast compared to the Array. It's all I use unless some prebuilt function just must use the standard Array. The ArrayList is also Dynamic, which means it can shrink and grow automatically without the need to "Redim" or move values in and out of one Array to the next. One quick note about the ArrayList constructor. It must be instantiated by calling the New method, unlike the Array -Dim TestArray(15) As String, you must create the ArrayList,Dim TestArrayList As New ArrayList, then add to it like this...TestArrayList.Add(_Value_). Hope this helps, Scott PageNopes! no success... I understand an ArrayList is better when a dynamic data structure is required - but I don't need a dynamic structure - I basically add the values to the array once at the beginning (takes less than a fraction of a second), process them (this is what takes ~ 3-4 seconds), and then read them back from the array (also takes almost no time). Besides, I need a two-dimensional array. Building such a structure would require me to add new ArrayList objects for each row - this in turn adds to the overhead I pay when referencing each element since I now need to cast each row to ArrayList. The use of ArrayList also adds extra-overhead of casting the object to int each time I need to refer to it as well as calling two functions (ArrayList.RemoveAt() and ArrayList.Insert()) when I need to update a value in the stucture (something I need to do often in my processing). The time improvement I'm looking for isn't as much in updating the data structure I use, but more about how do I store the values such that they can be read and written to fast (faster than they are in an array). Hope you have a solution...
-
I have a two dimensional array of 600 by 800 integers, and while processing this array, I need to visit each element approximately 250 times. This increases the total number of references I need to make to a mammoth figure of 120 million, accordingly increasing the time taken by this method (am using C#.NET) to around 3.5 seconds. This time figure however, is more than what is acceptable in my scenario. I would want to bring it down to around 2 seconds... So, I was wondering - is there a way to construct and process a matrix-like structure (without or without using two-dimensional arrays; or using pointers or something) which will take less time? Any assistance is appreciated...
Unsafe code + poiters. David Never forget: "Stay kul and happy" (I.A.)
David's thoughts / dnhsoftware.org / MyHTMLTidy -
Nopes! no success... I understand an ArrayList is better when a dynamic data structure is required - but I don't need a dynamic structure - I basically add the values to the array once at the beginning (takes less than a fraction of a second), process them (this is what takes ~ 3-4 seconds), and then read them back from the array (also takes almost no time). Besides, I need a two-dimensional array. Building such a structure would require me to add new ArrayList objects for each row - this in turn adds to the overhead I pay when referencing each element since I now need to cast each row to ArrayList. The use of ArrayList also adds extra-overhead of casting the object to int each time I need to refer to it as well as calling two functions (ArrayList.RemoveAt() and ArrayList.Insert()) when I need to update a value in the stucture (something I need to do often in my processing). The time improvement I'm looking for isn't as much in updating the data structure I use, but more about how do I store the values such that they can be read and written to fast (faster than they are in an array). Hope you have a solution...
I deal with large amounts of data on a regular basis as well, and most of the time I only need to manipulate a small portion to get the results I need. I'm not sure if this applies to your problem, but if you know the specific points you need, you could reference that location within the array and calculate a smaller amount of data. If you need all of the data and can't live without any of it, then as far as I know right now, processing 120 million data points is just a slow process no matter how you code it. Sorry I couldn't provide more help, hope someone knows of a solution for you. Scott
-
I have a two dimensional array of 600 by 800 integers, and while processing this array, I need to visit each element approximately 250 times. This increases the total number of references I need to make to a mammoth figure of 120 million, accordingly increasing the time taken by this method (am using C#.NET) to around 3.5 seconds. This time figure however, is more than what is acceptable in my scenario. I would want to bring it down to around 2 seconds... So, I was wondering - is there a way to construct and process a matrix-like structure (without or without using two-dimensional arrays; or using pointers or something) which will take less time? Any assistance is appreciated...
This is probably not a data structure but an algorithm problem :) It would help much if you could describe what you are actually doing or what result you are expecting. I always like crunching performance issues but for that some more input is needed. Nevertheless some suggestions: 1. Dont use Length or GetLength within a loop. Assign the length of the two dimensions to some variables and use them. Depending on what you are doing within those loops this could speed things up up to 50% (only true for Release mode). 2. Test with Release mode. Depending on what operations you are doing this can have a real impact on your performance. 3. Take a better processor :laugh:
-
Unsafe code + poiters. David Never forget: "Stay kul and happy" (I.A.)
David's thoughts / dnhsoftware.org / MyHTMLTidy -
This is probably not a data structure but an algorithm problem :) It would help much if you could describe what you are actually doing or what result you are expecting. I always like crunching performance issues but for that some more input is needed. Nevertheless some suggestions: 1. Dont use Length or GetLength within a loop. Assign the length of the two dimensions to some variables and use them. Depending on what you are doing within those loops this could speed things up up to 50% (only true for Release mode). 2. Test with Release mode. Depending on what operations you are doing this can have a real impact on your performance. 3. Take a better processor :laugh:
I've tried my best to make my algorithm as optimal as I can... 1. Here's what I'm trying to do - the two dimensional matrix I had mentioned is a pixel map of an image. I need to process the image, updating the value of each pixel depending upon the characteristics of a 10x10 pixel window with the pixel I wish to update at its center.. A typical loop for example goes like: /* iht - height of array iwd - width of array iPix - two dimensional array n1, n2, n3 - integers iWindowSize - size of processing window */ for (int y=0;yiwd-iWindowSize-1)?iwd:x+iWindowSize+1; yt=(yiht-iWindowSize-1)?iht:y+iWindowSize+1; // get mean value n1=0; n2=0; for (int i=yt;i
-
This is probably not a data structure but an algorithm problem :) It would help much if you could describe what you are actually doing or what result you are expecting. I always like crunching performance issues but for that some more input is needed. Nevertheless some suggestions: 1. Dont use Length or GetLength within a loop. Assign the length of the two dimensions to some variables and use them. Depending on what you are doing within those loops this could speed things up up to 50% (only true for Release mode). 2. Test with Release mode. Depending on what operations you are doing this can have a real impact on your performance. 3. Take a better processor :laugh:
-
Release mode doesn't provide any advantage. Instead, whereas in debug mode, the average processing time for 14 pictures was 3.411 seconds, it climbed upto 3.540 seconds for the same set of pictures in release mode!
Hmmmm... Ive tested exactly the code you posted and on my machine the relese mode version cut down the time needed to nearly the half. Have you tested it within VS or standalone? Check that the 'optimize' flag is set to true, 'check for arithmetic overflow' to false and 'generate debug info' also to false. But I think I have found something to increase the speed of the algorithm itsself: If I get it right you loop through all columns and in that loop through all rows. Then you sum up all values within this window. One big part is summing up the values within this window. If you imagine all those windows in a chart you can imagine that they all overlap each other. Thus you are summing up the same values some dozens times. My suggestion would be to sum up the values for the needed rows for all columns at once before processing a line. This way you dont have to sum all values within the window but only the prepared column sums. The same is probably possible for the variance. I hope this was somehow clear. If not I'll probably implement it myself when I have some minutes free :). Btw: Do You only work with integers? Are those matrix values calculated for only one color chanel (red, green , blue) or is really the complete RGB-value stored? If latter then summing up those values could easily overflow an integer variable :confused:
-
This is probably not a data structure but an algorithm problem :) It would help much if you could describe what you are actually doing or what result you are expecting. I always like crunching performance issues but for that some more input is needed. Nevertheless some suggestions: 1. Dont use Length or GetLength within a loop. Assign the length of the two dimensions to some variables and use them. Depending on what you are doing within those loops this could speed things up up to 50% (only true for Release mode). 2. Test with Release mode. Depending on what operations you are doing this can have a real impact on your performance. 3. Take a better processor :laugh:
Robert Rohde wrote: Dont use Length or GetLength within a loop Really? I think JIT optimizes it. David Never forget: "Stay kul and happy" (I.A.)
David's thoughts / dnhsoftware.org / MyHTMLTidy -
Do you have information about any resources on how to implement multi-dimensional arrays as pointers (in unsafe code) in C# or in C?
What I mean is direct access to array items using poiters. Here is where I saw it : http://blog.vyvojar.cz/tomas/archive/2004/12/22/2728.aspx[^] Unfortunately i's in czech language, however code should be readable and fuction name says it all :) David Never forget: "Stay kul and happy" (I.A.)
David's thoughts / dnhsoftware.org / MyHTMLTidy -
Robert Rohde wrote: Dont use Length or GetLength within a loop Really? I think JIT optimizes it. David Never forget: "Stay kul and happy" (I.A.)
David's thoughts / dnhsoftware.org / MyHTMLTidyNo he doesn't. He can't. Why? Lets assume you have something like this:
for (int i = 0; i < myArray.Length; i++)
{
//Do something
}How can the compiler know what is done within the loop. The loop could probably change the array:
for (int i = 0; i < myArray.Length; i++)
{
myArray = new int[myArray.Length + 10];
}If the JIT had replaced the condition in the loop with a constant value than the program would not behave correct anymore. This simple example could probably be resolved, but there are more complex examples a compiler can never resolve... so it doesn't even try :laugh: I've measured this already as well in debug as in release mode and it can have a real impact on your performance (about 50% if you e.g. just sum up the values of an array).
-
No he doesn't. He can't. Why? Lets assume you have something like this:
for (int i = 0; i < myArray.Length; i++)
{
//Do something
}How can the compiler know what is done within the loop. The loop could probably change the array:
for (int i = 0; i < myArray.Length; i++)
{
myArray = new int[myArray.Length + 10];
}If the JIT had replaced the condition in the loop with a constant value than the program would not behave correct anymore. This simple example could probably be resolved, but there are more complex examples a compiler can never resolve... so it doesn't even try :laugh: I've measured this already as well in debug as in release mode and it can have a real impact on your performance (about 50% if you e.g. just sum up the values of an array).
Robert Rohde wrote: No he doesn't. He can't. hmm. BratBrad says he does[^] :suss: Or maybe I missed something? David Never forget: "Stay kul and happy" (I.A.)
David's thoughts / dnhsoftware.org / MyHTMLTidy -
Robert Rohde wrote: No he doesn't. He can't. hmm. BratBrad says he does[^] :suss: Or maybe I missed something? David Never forget: "Stay kul and happy" (I.A.)
David's thoughts / dnhsoftware.org / MyHTMLTidyHmmm... I've tested some constellations. As far at it goes to GetLength Im totally right. Caching the length makes it by far faster. For the normal Length property its a bit more complicated. Brad is true if the arrays is declared locally. If its a field member the cached version will still be a bit faster (about 15%). Seems to be hard to give some general hints on thic topic. Its mostly like Brad stated: "The lesson here is more along the lines of measure, measure, measure when you are doing perf work"
-
Hmmm... I've tested some constellations. As far at it goes to GetLength Im totally right. Caching the length makes it by far faster. For the normal Length property its a bit more complicated. Brad is true if the arrays is declared locally. If its a field member the cached version will still be a bit faster (about 15%). Seems to be hard to give some general hints on thic topic. Its mostly like Brad stated: "The lesson here is more along the lines of measure, measure, measure when you are doing perf work"
Robert Rohde wrote: Seems to be hard to give some general hints on thic topic. Its mostly like Brad stated: "The lesson here is more along the lines of measure, measure, measure when you are doing perf work" I agree. David Never forget: "Stay kul and happy" (I.A.)
David's thoughts / dnhsoftware.org / MyHTMLTidy -
Hmmmm... Ive tested exactly the code you posted and on my machine the relese mode version cut down the time needed to nearly the half. Have you tested it within VS or standalone? Check that the 'optimize' flag is set to true, 'check for arithmetic overflow' to false and 'generate debug info' also to false. But I think I have found something to increase the speed of the algorithm itsself: If I get it right you loop through all columns and in that loop through all rows. Then you sum up all values within this window. One big part is summing up the values within this window. If you imagine all those windows in a chart you can imagine that they all overlap each other. Thus you are summing up the same values some dozens times. My suggestion would be to sum up the values for the needed rows for all columns at once before processing a line. This way you dont have to sum all values within the window but only the prepared column sums. The same is probably possible for the variance. I hope this was somehow clear. If not I'll probably implement it myself when I have some minutes free :). Btw: Do You only work with integers? Are those matrix values calculated for only one color chanel (red, green , blue) or is really the complete RGB-value stored? If latter then summing up those values could easily overflow an integer variable :confused:
Great find! I've made the changes you'd suggested in my algorithm (to avoid repeatedly summing up columns in overlapping windows), and have been able to shed over 1 second! The release mode however is still not giving much improvement. The 'optimize' flag is true and 'check for arithmetic overflow' and 'generate debug info' are both set to false. I must mention that the code I had posted is only a small section of my entire procedure. On my end, I'm processing the input image through a series of functions(/filters), each of which update pixel values depending upon the environments and are similar to the extract in my previous post. Currently, the entire procedure takes an average of ~ 2.4 seconds for a set of 14 test pictures in both Debug and Release modes. Also, am only working with integers. The input images are 8-bit grayscale images, so these integers are only between 0 and 255. Thanks...
-
What I mean is direct access to array items using poiters. Here is where I saw it : http://blog.vyvojar.cz/tomas/archive/2004/12/22/2728.aspx[^] Unfortunately i's in czech language, however code should be readable and fuction name says it all :) David Never forget: "Stay kul and happy" (I.A.)
David's thoughts / dnhsoftware.org / MyHTMLTidyI'm already using pointers + unsafe code to convert the input image to a pixel matrix, and to reconvert the processed matrix back to an image. I don't see using pointers throughout my code providing much improvements since most of my operations are basic mathematical operations which I perform on the integer matrix. Besides, a pixel map resembles the image more than the Bitmap data, which is a linear list of pixel values in the input image. I often need to analyze 2-dimensional "windows" around each pixel which is simpler to do in a 2-dimensional map than in a linear data structure. As for now, the methods suggested by Robert have given some improvements. I'll look into pointers again - am just not very familiar with their use at this point. Thanks...
-
Robert Rohde wrote: Seems to be hard to give some general hints on thic topic. Its mostly like Brad stated: "The lesson here is more along the lines of measure, measure, measure when you are doing perf work" I agree. David Never forget: "Stay kul and happy" (I.A.)
David's thoughts / dnhsoftware.org / MyHTMLTidy -
Great find! I've made the changes you'd suggested in my algorithm (to avoid repeatedly summing up columns in overlapping windows), and have been able to shed over 1 second! The release mode however is still not giving much improvement. The 'optimize' flag is true and 'check for arithmetic overflow' and 'generate debug info' are both set to false. I must mention that the code I had posted is only a small section of my entire procedure. On my end, I'm processing the input image through a series of functions(/filters), each of which update pixel values depending upon the environments and are similar to the extract in my previous post. Currently, the entire procedure takes an average of ~ 2.4 seconds for a set of 14 test pictures in both Debug and Release modes. Also, am only working with integers. The input images are 8-bit grayscale images, so these integers are only between 0 and 255. Thanks...
So you are now relatively close to your goal... You say you are working on images. Where does the data come from? Do you convert a Bitmap into a matrix, do your calculations and then recreate the image? If yes you could instead work directly (unsafe) on the bitmap data with the LockBits function from the Bitmap. Its a bit complicated (I don't like pointer handling) but its worth the try.