Array.Sort a struct -- c#

c# : Array.Sort a struct

Mythran
2/3/2006 3:20:20 PM

[quoted text, click to view]

You'd have to create an IComparer class. The following *should* be what you
need :)

public struct mp3file
{
public int tracknr;
public int length;
public string filename;
public string artist;
public string title;
}

public class Class1
{

public Class1() { }

public void Mp3Files()
{
mp3file[] files = new mp3file[2];
files[0].tracknr = 2;
files[0].length = 5000;
files[0].filename = "blah2";
files[0].title = "Title 2";
files[1].tracknr = 1;
files[1].length = 5000;
files[1].filename = "blah1";
files[1].title = "Title 1";
Array.Sort(files, new Mp3FileComparer());

foreach (mp3file file in files) {
Console.WriteLine(file.tracknr);
}
}
}

public class Mp3FileComparer : System.Collections.IComparer
{
public Mp3FileComparer() { }

public int Compare(object Object1, object Object2)
{
if (!(Object1 is mp3file)) {
throw new ArgumentException(
"Object1 must be of type mp3file.",
"Object1"
);
} else if (!(Object2 is mp3file)) {
throw new ArgumentException(
"Object2 must be of type mp3file.",
"Object2"
);
}

int n1 = ((mp3file) Object1).tracknr;
int n2 = ((mp3file) Object2).tracknr;

if (n1 > n2) {
return 1;
} else if (n1 == n2) {
return 0;
} else {
return -1;
}
}
}

HTH :)

Mythran

Mythran
2/3/2006 3:40:19 PM

[quoted text, click to view]

And to extend on what Jon was stating...the following is v1.1 code and uses
the IComparable interface instead of the IComparer interface. The MP3File
class implements this interface and containts the implementation of
CompareTo, which is all Array.Sort method needs to sort the class (notice,
it is no longer just a struct, but a full class w/o comments).

public class MP3File : IComparable
{

#region Private Members
// =================================================================
// Private Members
// =================================================================

private int mTrackNumber;
private int mLength;
private string mFileName;
private string mArtist;
private string mTitle;
#endregion

#region Constructors / Destructors
// =================================================================
// Constructors / Destructors
// =================================================================

public MP3File() { }
#endregion

#region Public Properties
// =================================================================
// Public Properties
// =================================================================

public int TrackNumber
{
get { return mTrackNumber; }
set { mTrackNumber = value; }
}

public int Length
{
get { return mLength; }
set { mLength = value; }
}

public string FileName
{
get { return mFileName; }
set { mFileName = value; }
}

public string Artist
{
get { return mArtist; }
set { mArtist = value; }
}

public string Title
{
get { return mTitle; }
set { mTitle = value; }
}
#endregion

#region Public Methods
// =================================================================
// Public Methods
// =================================================================

public int CompareTo(object obj)
{
if (!(obj is MP3File)) {
throw new ArgumentException(
"Argument 'obj' is not of type MP3File.",
"obj"
);
}

int num = ((MP3File) obj).TrackNumber;
if (this.TrackNumber < num) {
return -1;
} else if (this.TrackNumber == num) {
return 0;
} else {
return 1;
}
}

public override string ToString()
{
return string.Format(
"{0} : {1} : {2}",
this.TrackNumber,
this.Artist,
this.Title
);
}
#endregion

}

/// The following class should be created and the Mp3Files method called to
/// test the functionality of the MP3File and IComparable.
public class Class1
{

public Class1() { }

public void Mp3Files()
{
MP3File[] files = new MP3File[3];

files[0] = new MP3File();
files[0].TrackNumber = 3;
files[0].Length = 5000;
files[0].Artist = "Me";
files[0].FileName = "MyFileName3";
files[0].Title = "Title 3";

files[1] = new MP3File();
files[1].TrackNumber = 1;
files[1].Length = 23422;
files[1].Artist = "My";
files[1].FileName = "MyFileName1";
files[1].Title = "Title 1";

files[2] = new MP3File();
files[2].TrackNumber = 2;
files[2].Length = 23421;
files[2].Artist = "Mine";
files[2].FileName = "MyFileName2";
files[2].Title = "Title 2";

Array.Sort(files);

foreach (MP3File file in files) {
Console.WriteLine(file);
}
}
}

:)

HTH some more.

Mythran

James Park
2/3/2006 5:38:33 PM

[quoted text, click to view]

Why is it being a struct a bad idea? I just read the "Structs Tutorial" on
MSDN and it said "Whenever you have a need for a type that will be used
often and is mostly just a piece of data, structs might be a good option."
It looks like all data to me, so if you could clear up what's bad about it,
that'd be great.

James Park
2/3/2006 10:00:34 PM

[quoted text, click to view]

Hi Bill

[quoted text, click to view]

I'm not the OP, but that's okay. :)

[quoted text, click to view]

I ran some Stopwatch tests on Mythran's code.
As written (sample size 200,000):
structs: 2998 milliseconds
classes: 368 milliseconds <-- winner

Modified to use generics (sample size 2,000,000):
structs: 1508 milliseconds <-- winner
classes: 2213 milliseconds

I'm not savvy enough to speculate why the performance balance shifts, but it
indeed does.

[quoted text, click to view]

I wouldn't think this would be such a problem, but then again I don't have a
good feel for how frequently that misunderstanding would occur or how much
time would be wasted on it.

[quoted text, click to view]

Personally, I only use structs for P/Invoke stuff, but I'd like to know
other situations where they should be used. It just seemed to me that this
could be a legitimate situation.

Jon Skeet [C# MVP]
2/3/2006 11:02:10 PM

[quoted text, click to view]

Why is this a struct? That seems like a bad idea to me. (I'd also
suggest that you don't have public fields, by the way.)

[quoted text, click to view]

<snip>

[quoted text, click to view]

You still want to sort the array, so you need to call Array.Sort with
mp3 as one parameter - but there's an overload which takes an IComparer
(or one which takes an IComparer<T> if you're using .NET 2.0) which is
used for the sorting. You need to implement IComparer in some class or
other to descibe the ordering you want.

--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet

Gerrit
2/3/2006 11:44:07 PM

Hello,

Is it possible to sort an array with a struct in it?

example:

I have a struct:
public struct mp3file
{
public int tracknr;
public int length;
public string filename;
public string artist;
public string title;
}

and than I have this:

mp3file[] mp3 = new mp3file[files.Length];
int t = 0;

foreach (FileInfo fi in files)
{
MP3File mp3File = ShellID3TagReader.ReadID3Tags(fi.FullName);
mp3[t].length = mp3File.Length;
mp3[t].artist = mp3File.ArtistName;
mp3[t].title = mp3File.SongTitle;
mp3[t].tracknr = mp3File.TrackNumber;
mp3[t].filename = mp3File.FileName;
t++;
}

this is working, but now I want to sort the array by tracknr, so I can make
a playlist, sorted by tracknr.
with something like:

Array.Sort(mp3.tracknr)

but that doesn't work

How can I do this?

Thanks for your help!
--

www.gsnel.nl

James Park
2/3/2006 11:52:32 PM

[quoted text, click to view]

Good to know. By the way, my browser is cutting the code examples in your
article off on the right side, but it may be because I'm using the IE7 beta.

[quoted text, click to view]

Here's my take.
1) It looks like the type is atomic (assuming my interpretation of the
word's definition is right).
2) It doesn't look like a lot of data needs to be stored.
3) Depending on how the type is used, it may or may not need to be mutable.

Hmm, it still looks like a struct could be used. Maybe I could use some more
clarification.

Jon Skeet [C# MVP]
2/4/2006 12:00:00 AM

[quoted text, click to view]

Wow, that's odd - the examples are pretty narrow. Could you mail me a
screenshot? (skeet@pobox.com)

[quoted text, click to view]

It's not really - it makes sense to modify each of the fields
individually. It's a collection of data about something.

[quoted text, click to view]

There are 2 ints and 3 references, which means 20 bytes on x86 or 28
bytes on x64. Now performance isn't really an issue most of the time,
but it means that any time an mp3file is passed to a method, it's got
to copy all 20 or 28 bytes into the parameter (and likewise if one is
returned). That's like having 5 or 7 reference type parameters.

When it comes to sorting the array, that's going to be slower than
sorting it if mp3file were a reference type - then only the references
would need to be shuffled around, instead of of all the data.

[quoted text, click to view]

Well a struct *could* be used - but it feels like the wrong decision to
me. I don't see any reason why value type semantics would be desired in
this case.

--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet

Jon Skeet [C# MVP]
2/4/2006 12:00:00 AM

[quoted text, click to view]

That's just a bad article, unfortunately. It's incorrect in terms of
heap vs stack, too - see http://www.pobox.com/~skeet/csharp/memory.html

Whether you want to use a struct or a class has nothing to with whether
it's "just a piece of data". See my reply on the thread "Structure v/s
classes" for more information.

--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet

Bill Butler
2/4/2006 12:00:00 AM

[quoted text, click to view]

Hi James,

// First C++
If you pass a struct to a function it will be copied (value semantics). If you want reference
semantics, you pass in a pointer or a reference.

Now C#
structs in C# act ALOT like C++ structs. If you pass it into a function you will get a copy of the
struct and not the original struct. This is where C# Classes come in. You NEVER deal directly with
an object, You ALWAYS deal with a reference to the object. Unlike C++ reference, which cannot be
reassigned, C# references are more like auto dereferenced pointers.

So, why is it a bad idea in your case???
Passing your struct to a function is more expensive than passing the same data as a class, since the
struct has to be totally copied whereas only the reference to the class needs to be copied. Granted,
your struct is not huge, but it will still be slower (like that Sort you were asking about).

There are other subtle gotchas as well.
Take the following code.
----------------------------------
Thing myThing = new Thing(/*blah*/);
Foo(myThing );

public void Foo(Thing thing)
{
thing.X = 3;
}
---------------------------------
Will myThing be modified??
YES:If it is a class
NO : If it is a struct

Most C# programmers will expect the code to work (Assume it is a class)
Without looking at the declaration of your struct it is hard to tell that it is not a class.
Subtle bugs are the result.

If you are using struct over class as an optimization....DON'T.
Test it for yourself if you don't believe us.
Classes are almost always the right way to go

There ARE good uses of struct in C#, but in general, you should use classes.
In C# structs are kind of like gotos
Both can be useful in certain optimization situations, but I would REALLY think twice before using
one without a very good reason.

Bill

Mark R. Dawson
2/4/2006 6:23:31 AM

I would also add a constrctor while you are at it that takes all of the
default parameters, so:

files[2] = new MP3File();
files[2].TrackNumber = 2;
files[2].Length = 23421;
files[2].Artist = "Mine";
files[2].FileName = "MyFileName2";
files[2].Title = "Title 2";

is replaced by:

files[2] = new MP3File(2, 23421, "Mine", "MyFileName2", "Title 2");

which nicely cuts down on the bulk of the code, IMO :-)

[quoted text, click to view]

James Park
2/4/2006 9:55:48 AM

[quoted text, click to view]

Sent.

[quoted text, click to view]

I think it depends on the type of program. If it's like an editor and can
modify the mp3 file itself, then sure, the fields are pretty much fair game
individually. If it's like a player and isn't supposed to modify the file,
then it wouldn't make sense to mess with individual fields.

[quoted text, click to view]

I found sorting the array was actually faster using structs. In fact, when I
originally tested in my other post, I didn't assign any of the string
fields. Doing that, the structs performed just as quickly, but the classes
were bogged down even more (classes took twice as long as structs
afterward). The performance may shift drastically using x64, but I don't
have the OS installed to test it.

Btw, the total size under x64 would be 32 and not 28.

[quoted text, click to view]

I found some more advice in the MSDN article "Value Type Usage Guidelines"

It is recommended that you use a struct for types that meet any of the
following criteria:
Act like primitive types.
Have an instance size under 16 bytes.
Are immutable.
Value semantics are desirable.

I think the answers here are no, no, maybe, and maybe (if sorting
performance is an issue and I did the test correctly). Would it be fair to
say this article is more accurate as to what should be a struct?

James Park
2/4/2006 10:14:25 AM

[quoted text, click to view]

Thanks for the good explanation Bill.

Mark R. Dawson
2/4/2006 11:15:32 AM

Hi Gerrit,
to the sort method you need to pass your array but also some logic that
know how to compare based on the desired property of your struct. There are
many overloads in the Sort method but one way to do it is using the
Comparison<T> delegate like below:

static void Main(string[] args)
{

mp3file m1 = new mp3file();
m1.tracknr = 20;

mp3file m2 = new mp3file();
m2.tracknr = 10;

mp3file[] arr = new mp3file[2];
arr[0] = m1;
arr[1] = m2;

Array.Sort(arr, delegate(mp3file file1, mp3file file2)
{
return file1.tracknr.CompareTo(file2.tracknr);
});
}

If you dont want to use the Comparison<T> then you can use something else
like creating an object that implements the IComparer interface (a quick look
in google should show you how to use that).

Hope that helps
Mark Dawson
www.markdawson.org

[quoted text, click to view]

Bill Butler
2/4/2006 5:21:24 PM

[quoted text, click to view]

Ooops, sorry about that

[quoted text, click to view]

Many people come the C# with a C++ mindset and choose structs over classes for the wrong reasons.
They will ,by default, choose a struct over a class for a Plain Old Data(POD) type.
They do this because they think of a struct as a lightweight class ( ie faster).
They figure that they don't need that object baggage (methods and stuff)
In short, they do it to improve performance.
More often than not they actually get worse performance due to boxing and full copying on method
calls.

Objects access in c# is quite fast and most Properties will get inlined by the JITer, so POD types
should ,by default, be classes.

So, when should you consider converting your class to a struct?
Suppose you have a small object (not expensive to copy) and you create alot of them in tight looping
situations (a Point comes to mind.) . The potential performance improvement comes from faster
creation of the struct on the stack. This is offset against longer method call times (unless the
struct is tiny),and Boxing (although generics can help). So if you have tiny , immutable objects
that you create frequently and it is effecting performance, you MIGHT get a performance boost by
changing it to a class.
The important thing to note is that it is the cost of creation that you are saving. So structs
might help in short lifetime conditions. The choice should NOT be made lightly.

In C# the object should always be the DEFAULT unit of data storage.
In most situations it will outperform structs.

In the specific case of Gerrit's Playlist.
The data MIGHT be immutable (at least it is in his quick sample)
The data is NOT created frequently (he creates 1 for each file in a folder)
His struct is small but not Tiny (more expensive method calls).

So, He could use a stuct to represent his data and most likely only suffer a small performance hit.
Of course that depends on the actual logic.

The real point is that he probably chose the struct over a class in order to make it MORE
performant.
It is doubtful that the end result will bear this out.
This is why we tend to steer developers away from structs.

Bill

Gerrit
2/4/2006 6:28:46 PM

"Mythran" <kip_potter@hotmail.comREMOVETRAIL> schreef in bericht
news:OidbtsRKGHA.2248@TK2MSFTNGP15.phx.gbl...
[quoted text, click to view]

.........

[quoted text, click to view]

I'm new with C# and my English is not very good, so I don 't understand
exactly the discussion about the difference between the use of a struct or
a class in this case, but with this code, my program is working how I want
it must working. So thank you very much.

Gerrit

--

www.gsnel.nl

Jon Skeet [C# MVP]
2/5/2006 12:00:00 AM

[quoted text, click to view]

But the point is that *logically* it makes sense for them to be
mutable. They are, in some ways, independent values, even though the
all refer to the same file.

[quoted text, click to view]

I suspect that will depend on how many entries you've got - more memory
in total will be used for classes, but shifting each entry around will
be easier. If everything fits in the cache for structs but not for
classes, that could explain the difference - otherwise I really would
expect it to be faster for classes. (It partly depends on whether
you're sorting using IComparer, IComparer<T> or IComparable - with
plain IComparer you have to box on every comparison too when using
structs.)

[quoted text, click to view]

Oops, yes.

[quoted text, click to view]

Yes - that's much, much better.

--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet

Got something to say? Click here to post a reply to this thread.

Don't see what you're looking for? Try a search.

View other messages about c#

View Other Months
June 2003
July 2003
August 2003
September 2003
October 2003
November 2003
December 2003
January 2004
February 2004
March 2004
April 2004
May 2004
June 2004
July 2004
August 2004
September 2004
October 2004
November 2004
December 2004
January 2005
February 2005
March 2005
April 2005
May 2005
June 2005
July 2005
August 2005
September 2005
October 2005
November 2005
December 2005
January 2006
February 2006
March 2006
April 2006
May 2006
June 2006
July 2006
August 2006
September 2006
October 2006
November 2006
December 2006
January 2007
February 2007
March 2007
April 2007
May 2007
June 2007
July 2007
August 2007
September 2007
October 2007
November 2007
December 2007
January 2008
February 2008
March 2008
April 2008

home · blog · groups

Questions? Comments? Contact the dn