Util functions for IList

  • Thread starter Thread starter cody
  • Start date Start date
cody said:
why arent there some util functions for IList for example Sort()?
Click to expand...

I *suspect* it's because the way to do a reasonably efficient sort in
each case depends on the implementation of the list. Trying to sort a
linked list using the "obvious" kind of approach would be horrendous in
performance terms.

There's also the issue of working out where you'd put such methods,
given that they couldn't be in IList itself.
 
I *suspect* it's because the way to do a reasonably efficient sort in
each case depends on the implementation of the list. Trying to sort a
linked list using the "obvious" kind of approach would be horrendous in
performance terms.
Click to expand...

You are right. This makes me think why a generic IList needs an indexer in
the first place then.
Misusing it would lead to horrible performance, and you often do not see the
internal implementation.
I consider IList a bad interface it should have be broken down into
interfaces with less functionality which would make implementing readonly
wrappers easies. Providing every possible method first, but throwing
InvalidOperationException during runtime is no good idea.
There's also the issue of working out where you'd put such methods,
given that they couldn't be in IList itself.
Click to expand...

A ListUtil or CollectionUtil class with static methods would be fine.
 
cody said:
You are right. This makes me think why a generic IList needs an indexer in
the first place then.
Misusing it would lead to horrible performance, and you often do not see the
internal implementation.
I consider IList a bad interface it should have be broken down into
interfaces with less functionality which would make implementing readonly
wrappers easies. Providing every possible method first, but throwing
InvalidOperationException during runtime is no good idea.
Click to expand...

This would explode BCL's System.Collections namespace:
Take a look at the list of classes that implement IList.

You missed the static ArrayList.Adapter method
that creates an ArrayList wrapper for an IList.
ArrayList hat a Sort-method, so you do't need
another helper classes/methods.

bye
Rob
 
I *suspect* it's because the way to do a reasonably efficient sort in
This would explode BCL's System.Collections namespace:
Take a look at the list of classes that implement IList.


You missed the static ArrayList.Adapter method
that creates an ArrayList wrapper for an IList.
ArrayList hat a Sort-method, so you do't need
another helper classes/methods.
Click to expand...


Iam really starting to hate IList now more than ever :)

The first (and very logical argument was that sorting for IList is not
allowed because of performance issues)
Now I can simply wrap it up in an ArrayList (which then isn't an ArrayList
anymore, isn't it).
 
Iam really starting to hate IList now more than ever :)

The first (and very logical argument was that sorting for IList is not
allowed because of performance issues)
Click to expand...

See ArrayList.Adapter's docs.
Now I can simply wrap it up in an ArrayList (which then isn't an ArrayList
anymore, isn't it).
Click to expand...

Of course it's still an ArrayList. The only difference
is where the data is coming from: from the IList.

bye
Rob
 
The first (and very logical argument was that sorting for IList is not
See ArrayList.Adapter's docs.
Click to expand...

Adapter doesn't copy the contents of the list - so in case we have used a
LinkedList to create the list, using the wrapper we have still an underlying
LinkedList which makes sorting extremely slow.
Of course it's still an ArrayList. The only difference
is where the data is coming from: from the IList.
Click to expand...

My "definition" of an ArrayList is a list which is guaranteed to have an
Array as underlying implementation (this is at least what the docs say).
 
cody said:
Adapter doesn't copy the contents of the list - so in case we have used a
LinkedList to create the list, using the wrapper we have still an underlying
LinkedList which makes sorting extremely slow.
Click to expand...

There is no reason why sorting a linked list should be slow. In many
cases, it's faster than sorting an array as there's less copying (although
in a reference-based environment like .Net, it'll be a wash).

QuickSort, one of the fastest sort algorithms, works fine with a
linked-list.

--
Truth,
James Curran
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com
(note new day job!)
 
James Curran said:
There is no reason why sorting a linked list should be slow. In many
cases, it's faster than sorting an array as there's less copying (although
in a reference-based environment like .Net, it'll be a wash).

QuickSort, one of the fastest sort algorithms, works fine with a
linked-list.
Click to expand...

Not if it swaps elements by saying:

object tmp = list[x];
list[x] = list[y];
list[y] = tmp;

That's going to be painfully slow with a linked list, as it would have
to walk down to element x or y each time... and that's my guess as to
how it works in ArrayList.Sort.
 
Jon Skeet said:
QuickSort, one of the fastest sort algorithms, works fine with a
linked-list.
Click to expand...

Not if it swaps elements by saying:

object tmp = list[x];
list[x] = list[y];
list[y] = tmp;
Click to expand...

Well, I was speaking about the algorithm in general rather than a
particular implementation. When described in general terms, no items are
"swapped" in QuickSorting, they are moved to new lists, an operation perfect
for linked lists.
That's going to be painfully slow with a linked list, as it would have
to walk down to element x or y each time... and that's my guess as to
how it works in ArrayList.Sort.
Click to expand...

Upon closer reading of ArrayList.Sort (which states it calls
Array.Sort), it appears you are right. Sheesh.... It is a dumb design.....

--
Truth,
James Curran
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com
(note new day job!)
 
James Curran said:
Upon closer reading of ArrayList.Sort (which states it calls
Array.Sort), it appears you are right. Sheesh.... It is a dumb
Click to expand...
design.....

Well, I just spent about an hour trying to create a proper IList
implementation of QuickSort. It's turning out to be harder than expect,
mainly due to the rather sucky design of IList. It seems that someone at
MSFT just doesn't understand linked-lists, and treats them just as "bad
arrays" instead of proper data structures with their own advantages. So,
methods that would be difficult for arrays, but are natural for linked lists
(like "split" and "join") are missing.

--
Truth,
James Curran
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com
(note new day job!)
 
James Curran said:
Jon Skeet said:
QuickSort, one of the fastest sort algorithms, works fine with a
linked-list.
Click to expand...

Not if it swaps elements by saying:

object tmp = list[x];
list[x] = list[y];
list[y] = tmp;
Click to expand...

Well, I was speaking about the algorithm in general rather than a
particular implementation. When described in general terms, no items are
"swapped" in QuickSorting, they are moved to new lists, an operation perfect
for linked lists.
Click to expand...

Hmmm... that's not the description I've got in front of me.

From "Introduction to Algorithms" (Corwen, Leiserson, Rivest):

<quote>
It also has the advantage of sorting in place [...]
</quote>

The algorithm is then described in terms of partitioning which includes
a swap operation.
Upon closer reading of ArrayList.Sort (which states it calls
Array.Sort), it appears you are right. Sheesh.... It is a dumb design.....
Click to expand...

I don't think it is, really. It suits most implementations of lists -
just not linked lists.

If you think you can come up with an IList interface and a
corresponding quicksort implementation which is efficient for both
array-based lists *and* linked lists, without any special-casing, I'll
be impressed. As you say in another post, what is natural for one is
horrible for another, so general purpose algorithms operating on the
interface are likely to be nasty.

A list interface which included some kind of "cursor" type object (just
an index in the ArrayList case, and the node itself in the LinkedList
case) and which allowed swapping the contents of two cursors *might*
work - but that would really be designed almost specifically for
sorting, and would be a pain to implement when not required.
 
Jon said:
From "Introduction to Algorithms" (Corwen, Leiserson, Rivest):

<quote>
It also has the advantage of sorting in place [...]
</quote>
The algorithm is then described in terms of partitioning which
includes a swap operation.
Click to expand...

They are discussion their particular inplementation, which is
specifically for arrays. Note, later in the page :"Here is the three-step
divide-and-conquer process for sorting a typical *subarray* A[p..r]" (my
emphasis)

For a more agnostic description, see See "Dictionary of Computing"
entry: http://burks.brighton.ac.uk/burks/foldoc/60/95.htm
If you think you can come up with an IList interface and a
corresponding quicksort implementation which is efficient for both
array-based lists *and* linked lists, without any special-casing, I'll
be impressed.
Click to expand...

"array-based lists" is an abuse of the concept. I've never heard the
term "list" (used in a data structures context) to refer to anything beside
a linked-list (or more correctly, to a DS which demostrates the features of
a linked-list regardless of implementation) Array are arrays and lists are
lists. Each has it own strengths and weaknesses. Creating one interface
for which is a mish-mash of both is a design flaw.

(See "Disctionary of Computing" entry:
http://burks.brighton.ac.uk/burks/foldoc/38/67.htm)
 
"array-based lists" is an abuse of the concept. I've never heard the
term "list" (used in a data structures context) to refer to anything beside
a linked-list (or more correctly, to a DS which demostrates the features of
a linked-list regardless of implementation)
Click to expand...

Then that's the problem. In my experience, "list" is commonly used as
just "an ordered sequence" which covers arrays as well. I don't see any
reason to limit it to data structures where it's expensive to access an
element directly, or indeed to data structures where it's cheap to
perform split and join operations.

Just a matter of definition though - both .NET and Java happen to use
the one I favour, and not yours...
 
Back
Top