Following code was supposed to sort an ArrayList of strings while keeping
one "fixed" element at the last position.
However, the code hangs in .NET 1.1. I think that answering these questions
should be an interesting and instructive task for .NET learners:
1. why the code hangs in .NET 1.1?
2. why it does not hang in .NET 2.0?
3. why it does not hang in .NET 1.1 when you keep the "fixed" element at the
first (instead of last) position:
if ( ys == "fixed" )
return 1;
if ( xs == "fixed" )
return -1;
4. how to fix the code of the comparer so that sorting works in .NET 1.1?
Regards,
Wiktor Zychla
using System;
using System.Collecti ons;
class TestComparer : IComparer
{
public int Compare(object x, object y)
{
if (!( x is string )) return 0;
if (!( y is string )) return 0;
string xs = x as string;
string ys = y as string;
if ( ys == "fixed" )
return -1;
if ( xs == "fixed" )
return 1;
return xs.CompareTo( ys );
}
}
class Test
{
public static void Main()
{
ArrayList test = new ArrayList();
test.Add( "test2" );
test.Add( "test1" );
test.Add( "fixed" );
test.Add( "test5" );
test.Add( "test4" );
test.Add( "test3" );
foreach ( string s in test )
Console.WriteLi ne( s );
Console.WriteLi ne();
test.Sort( new TestComparer() );
foreach ( string s in test )
Console.WriteLi ne( s );
}
}
Jan 26 '06
18 1726
my knowledge of quicksort and sorting algorithms isn't accomplished
enough to work it out. Please reveal all!
Chris S. wrote: my knowledge of quicksort and sorting algorithms isn't accomplished enough to work it out. Please reveal all!
Okay, another hint: the problem is in the comparator, and the fact that
quicksort is being used isn't really relevant. Look at what the
contract for IComparer, and think about different possibilities for
what might be passed as the parameters...
(Bill: the algorithm has been tweaked. I don't believe it was tweaked
specifically to get around this flaw, but it's the kind of flaw which
is quite data-sensitive; depending on the data given, 2.0 either
notices the problem or happens to get the result right.)
Jon
> (Bill: the algorithm has been tweaked. I don't believe it was tweaked specifically to get around this flaw, but it's the kind of flaw which
I do not even believe that they were aware of that. Seems that the tweaked
version is by chance better in handling such inconsistent comparers but is a
little controversial for other reasons: http://tinyurl.com/7qab5 (I had a short discussion on that with Ryan
Byington from the dev team and I hope that we could expect it to be tuned
someday)
Wiktor Zychla
Jon Skeet [C# MVP] wrote: Chris S. wrote: my knowledge of quicksort and sorting algorithms isn't accomplished enough to work it out. Please reveal all!
Okay, another hint: the problem is in the comparator, and the fact that quicksort is being used isn't really relevant. Look at what the contract for IComparer, and think about different possibilities for what might be passed as the parameters...
Oh I know I know! I think...
rot13
Jung unccraf vs Pbzcner vf pnyyrq jvgu k naq l OBGU rdhny gb "svkrq"?
Gur erghea inyhr fubhyq or mreb va guvf pnfr ohg vg ergheaf -1, fb gur
fbeg vf crecrghnyyl gelvat gb fbeg svkrq gb gur yrsg bs vgfrys, be
fbzrguvat yvxr gung.
/rot13
--
Larry Lard
Replies to group please
> rot13 Jung unccraf vs Pbzcner vf pnyyrq jvgu k naq l OBGU rdhny gb "svkrq"? Gur erghea inyhr fubhyq or mreb va guvf pnfr ohg vg ergheaf -1, fb gur fbeg vf crecrghnyyl gelvat gb fbeg svkrq gb gur yrsg bs vgfrys, be fbzrguvat yvxr gung.
/rot13
although you does not seem to be fluent in ancient gnomish yet ("fubhyq" is
an irregular verb and the "guvf" noun should not be used in such content),
your explanation is fine ;)
Wiktor Zychla
Larry Lard wrote: Oh I know I know! I think...
rot13
Jung unccraf vs Pbzcner vf pnyyrq jvgu k naq l OBGU rdhny gb "svkrq"? Gur erghea inyhr fubhyq or mreb va guvf pnfr ohg vg ergheaf -1, fb gur fbeg vf crecrghnyyl gelvat gb fbeg svkrq gb gur yrsg bs vgfrys, be fbzrguvat yvxr gung.
/rot13
Spot on. Nice idea to rot13, too - it hadn't even occurred to me
(despite having seen it similarly used before). Doh!
Jon
Hi,
"Jon Skeet [C# MVP]" <sk***@pobox.co m> wrote in message
news:11******** **************@ g49g2000cwa.goo glegroups.com.. . Larry Lard wrote: Oh I know I know! I think...
rot13
Jung unccraf vs Pbzcner vf pnyyrq jvgu k naq l OBGU rdhny gb "svkrq"? Gur erghea inyhr fubhyq or mreb va guvf pnfr ohg vg ergheaf -1, fb gur fbeg vf crecrghnyyl gelvat gb fbeg svkrq gb gur yrsg bs vgfrys, be fbzrguvat yvxr gung.
/rot13
Spot on. Nice idea to rot13, too - it hadn't even occurred to me (despite having seen it similarly used before). Doh!
First time for me, luckily wikipedia clarified it: http://en.wikipedia.org/wiki/ROT13
I have one question though, IIRC the pivot should not be included in either
list when you divide your starting list. This is to avoid comparing a value
to itself (which is the cause of the problem in the particular example) ,
would it be that the quicksort argorithm has a bug after all?
Of course that even with a correct QS in place you may have errors, but only
when you have two "fixed" elements in the list, with one it should not be a
problem
Am I correct in the above?
It's early in the morning and I have had no coffe yet ;)
I may be missing something
--
Ignacio Machin,
ignacio.machin AT dot.state.fl.us
Florida Department Of Transportation
"Jon Skeet [C# MVP]" <sk***@pobox.co m> wrote in message
news:11******** **************@ f14g2000cwb.goo glegroups.com.. . (Bill: the algorithm has been tweaked. I don't believe it was tweaked specifically to get around this flaw, but it's the kind of flaw which is quite data-sensitive; depending on the data given, 2.0 either notices the problem or happens to get the result right.)
I don't mean that the algorithm was tweaked to fix this problem, but rather a slight optimization
accidentally fixed a broken IComparer. Similar to the standard C++ idiom to prevent self assignment.
I can explain what I mean more fully, but I am still being semi-cryptic.
Bill This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Jesse Martinez |
last post by:
My problem occurs when I use an ArrayList as a ListBox.DataSource. When the
ArrayList attached to the Listbox is not empty the Listbox behave normal
without problem, but if I remove all items from the ArrayList and re-attach
the ArrayList to the ListBox the program hangs for about 3-5 seconds then
keep running normal.
I'm following the examples from the MSDN and dont see anything abnormal.
This is a sample of the code I'm using:
1...
|
by: Adam J. Schaff |
last post by:
Hello. I recently noticed that the Sort method of the .NET ArrayList class
does not behave as I expected. I expect 'A' < '_' < 'a' (as per their ascii
values) but what I got was the opposite. Simple code:
Dim y As New ArrayList
y.Add("Abc")
y.Add("abc")
y.Add("_bc")
|
by: Derek Martin |
last post by:
Hi there, I have been playing with sorting my arraylist and having some
troubles. Maybe just going about it wrong. My arraylist contains objects
and one of the members of the object is 'name.' I would like to sort the
arraylist based on object.name - is that possible?
Thanks!
Derek
|
by: Dennis |
last post by:
I use the following code for a strongly typed arraylist and it works great.
However, I was wondering if this is the proper way to do it. I realize that
if I want to implement sorting of the arraylist then I have to handle this
with a sort method that uses comparer. I can reference the properties of the
Arraylist directly such as
dim mylist as new FrameList
mylist.Add(new FrameStructure)
mylist(0).first = "blabla..."
mylist(0).second...
|
by: JohnR |
last post by:
I have an arraylist of string values. I would like to search the arraylist
to find the index of a particular string and I would like the search to be
case insensitive.
dim al as new arraylist
al.add("one")
al.add("two")
dim x as integer = al.indexof("ONE") I would like this to find the match
and return 0
| |
by: Grant Wickman |
last post by:
Our team has just fixed a really nasty problem that appears to be
caused by an obscure bug in the sort method of Arraylist and
daisy-chained webservice stubs.
We've fixed the bug so I'll not investigate any further but there was
nothing about it when googling the newsgroups so I am posting a note in
case it helps somebody else out.
The problem was in a system with a web front end calling through to a
chain of 3 webservices i.e.
|
by: RCS |
last post by:
So I have an ArrayList that gets populated with objects like:
myAL.Add(new CustomObject(parm1,parm2));
I'm consuming this ArrayList from an ObjectDataSource and would like to have
this support sorting (because it's ultimately being consumed in a GridView).
I can't simply sort the ArrayList (because it only knows it's holding a
bunch of objects). So I need a way to sort the ArrayList, based on the
data - that is within the objects that...
|
by: Alex Chudnovsky |
last post by:
I have come across with what appears to be a significant performance bug in
..NET 2.0 ArrayList.Sort method when compared with Array.Sort on the same
data. Same data on the same CPU gets sorted a lot faster with both methods
using .NET 1.1, that's why I am pretty sure its a (rather serious) bug. Below
you can find C# test case that should allow you to reproduce this error, to
run it you will need to put 2 data files into current directory...
|
by: Stuart |
last post by:
I am using Visual Basic 2005.
I have created a two dimensional ArrayList named aSystem that is populated as
follows:-
aSystem.Add(New PickList(0, "Undefined"))
aSystem.Add(New PickList(-1, "Standard UTM"))
aSystem.Add(New PickList(-2, "UTM-NAD83"))
aSystem.Add(New PickList(-3, "UTM-NAD27"))
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
| |
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |