BinarySearch checks same element - C# Discussion Boards

9-Sep-09 1:22

Hello,

I've created a function which walks pixel by pixel on an image, storing the pixel color on a Pixel Class.

The software was doing much processing on this loop because each time a new Pixel was found an instance of a Pixel Class was created. Then, I decided to declare a single Pixel Class instance outside the loop and then modify only its values inside the loop and then add it to the list of Pixel Class.

The problem started appearing after I did that. Now, when I try using BinarySearch on a List<t> it always returns me 0. It seems that C# is checking the Pixel Class instead of its content, which is what I want.

I tried to create an IComparer<t> to check the Pixel Class value but it doesn't work since the function always receive the same Class in both parameters, so the check is in vain.

So here I leave the question: How can I use BinarySearch on a class which only changes its content but not its address?

The (pseudo)code below illustrates the code before and after the changes:

BEFORE:

for (int x...)
 for(int y...) 
 {
  Pixel p = new Pixel();
  p.value = ...
  ...
  int pos = pixels.BinarySearch(p);
 }

AFTER:

Pixel p = new Pixel();
PixelComparer pComp = new PixelComparer();
for (int x...)
 for(int y...) 
 {
  p.value = ...
  ...
  int pos = pixels.BinarySearch(p);
  int pos = pixels.BinarySearch(p, pComp);
  //now both calls above returns fails!!!
 }

public class PixelComparer : IComparer<Pixel>
{
 public int Compare(Pixel a, Pixel b)
 {
  //a.value and b.value is always the same value!!!
  Console.WriteLine("{0} x {1}", a.value, b.value);
  return a.value.CompareTo(b.value);
 }
}

Thanks in advance,

Luc Pattyn9-Sep-09 1:30

Luc Pattyn

9-Sep-09 1:30

Hi,

you can't store a lot of pixels in a single instance of Pixel; if you create only one Pixel, it will end up holding the data you inserted last. Storing a reference to the one Pixel over and over in some collection, does not help, all those references point to the same instance, so they all got changed to contain the same, last, value.

creating a new Pixel every time is too expensive as you discovered. So what you need to do is find a cheaper way for storing the data you want. I suggest an array of the simplest (value) type that can work for you, so either an array of int or an array of a little struct.

Smile | :)

Luc Pattyn

Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.

Caio19859-Sep-09 1:49

9-Sep-09 1:49

Hi Luc,

You are correct. I thought about that but my Pixel class contains two different fields:

1. Pixel color;
2. Number of hits (in order to track statistics of the color).

Since I sort the values in the end according to the number of hits I don't see an alternative but storing them together.

I've though about:
a. Changing the class to a structure to see if that speeds up the allocation time;
b. Using two different arrays but I think it will be hard to keep track of changes when they are rearranged.
c. Try to somehow retrieve the pallet of the image in beforehand and then compare it to the pixel color increasing only a hit vector where the hit position to be increased would be equivalent to the position of the pallet.

I think 'c' is the elegant solution but I don't know if it is the fast one. What do you think?

Regards,

Luc Pattyn9-Sep-09 2:11

Luc Pattyn

9-Sep-09 2:11

OK, some comments:

1.
a general GDI+ image does not have a pallette, each pixel has ARGB values, typically 32-bit in total, and those can take any value. Your image source may be encoded by color index (e.g. 8-bit pallette) but AFAIK that is lost when the image gets loaded into an Image/Bitmap instance.

2.
with two arrays, their size would have to be the size (area) of the input image, that could be rather large. And you would have to implement your own sort algorithm to keep both arrays in sync.

3.
I would consider using a single Dictionary<Color,int> where the key is the pixel color and the value is the multiplicity. So the code to add a pixel would be: if already in dictionary increment value, else insert with value=1. Performing this on a megapixel image will be a slow operation!
BTW: make sure you allocate the dictionary with a well chosen initial capacity, I would pick image area divided by say 4 to avoid dictionary growth which would reallocate and copy all current data.

Smile | :)

Luc Pattyn

Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.

Caio19859-Sep-09 3:03

9-Sep-09 3:03

Hi Luc,

Reply to 1: Yes, I verified that just after I posted the reply.

Reply to 2: Agree.

Reply to 3: In fact, to use statistics I'd need a SortedDictionary since after I insert the values on this dictionary I need to sort them according to the number of hits. The problem here is that I verified that on SortedDictionary, as opposed to Dictionary, when you call Add method for an specific key, it does not update the value of the key, instead you have to remove the element using Remove and add it again using method. Therefore many search calls are done.

To illustrate:

if (color.ContainsKey(intColor))
 {
     int value = color[intColor] + 1;
     color.Remove(intColor);
     color.Add(intColor, value);
 }
 else
 {
     color.Add(intColor, 1);
 }

Is there any other way to do that?

Regards,

Caio19859-Sep-09 4:16

9-Sep-09 4:16

NOTE:

Using Dictionary for a 180 x 120 image seems faster than a SortedDictionary.

I've found that: http://dotnetperls.com/sorteddictionary[^]

Regards,

obtain Ram and Monitor features

Luc Pattyn9-Sep-09 10:24

Luc Pattyn

9-Sep-09 10:24

No. You don't need a SortedList, as it does not make sense to get the order updated after every pixel, you only need it sorted when done collecting all info. And you want to sort by value, not by key.

Furthermore:

if (colorHistogram.ContainsKey(intColor)) colorHistogram[intColor]++;
else colorHistogram.Add(intColor, 1);

Luc Pattyn

Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.

Where to POST?

Jacobb Michael9-Sep-09 0:43

Jacobb Michael

9-Sep-09 0:43

Hi all,

Can some one help me ?

where to post the questions related DOM and BHO that is on C#?

i never get answers for those questions.

can some one guide me for the proper place to post ! so that it cold be useful or me and others as well...

thanks

Developing messenger

Xmen Real 9-Sep-09 0:40

Xmen Real

9-Sep-09 0:40

I'm developing a messenger like yahoo or windows live. I'm almost done and the way I choose is Web Service. One method receives byte array from user, some user info and saves in DB. Another method checks if any message available for that user if yes then return byte array. Its fine but I'm just confuse now that how to transfer a file. What I thought is that write chunk by chunk of file to server with last offset of original file. And when a chunk is read by other-end user the sender will write next part of file. So in that way transfer can be resume. But I'm wondering that is there any other better way to do that ?

TVMU^P[[IGIOQHG^JSH`A#@`RFJ\c^JPL>;"[,*/|+&WLEZGc`AFXc!L
%^]*IRXD#@GKCQ`R\^SF_WcHbORY87֦ʻ6ϣN8ȤBcRAV\Z^&SU~%CSWQ@#2
W_AD`EPABIKRDFVS)EVLQK)JKQUFK[M`UKs*$GwU#QDXBER@CBN%
R0~53%eYrd8mt^7Z6]iTF+(EWfJ9zaK-iTV.C\y<pjxsg-b$f4ia>

-----------------------------------------------
128 bit encrypted signature, crack if you can

Re: Developing messenger

CoderForEver9-Sep-09 23:45

CoderForEver

9-Sep-09 23:45

Hey budy am not here to answer ur question. But to ask u something on the Messenger .........
I am also to develop an application similar to urs ..... I have been doing C# applications for 1 and half year ...... but I havent do any applications that include networking ............. So what is the general idea behind that ...... Or can u point me a site or notes which help me to do Messenger in C#.

Thank you.

moein.serpico9-Sep-09 0:33

moein.serpico

9-Sep-09 0:33

I could collect all of features about any hardware but i could not obtain information about manufacture of RAM and MONITOR .
If it's possible help me about collectiong information about Ram and Monitore manufacture

Eddy Vluggen9-Sep-09 0:52

Eddy Vluggen

9-Sep-09 0:52

Add a reference to Microsoft.VisualBasic; there's a ComputerInfo[^] class and a Computer[^] class that holds info on the screen Smile | :)

"Optimism is an occupational hazard of programming; feedback is the treatment."

-- Kent Beck

moein.serpico9-Sep-09 4:17

moein.serpico

9-Sep-09 4:17

i ask this question in c# form body!
NOT VISUAL BASIC

OriginalGriff9-Sep-09 4:30

OriginalGriff

9-Sep-09 4:30

moein.serpico wrote:
i ask this question in c# form body!
NOT VISUAL BASIC

I think he knows that, so no need to shout. What he said was "Add a reference to Microsoft.VisualBasic; there's a ComputerInfo class and a Computer class" These are available to and fully usable in C#, but you have to add the reference to your project or VS can't find them. Why are they in Microsoft.VisualBasic.dll? Ask Mr Gates.

No trees were harmed in the sending of this message; however, a significant number of electrons were slightly inconvenienced.

This message is made of fully recyclable Zeros and Ones