Efficient + Strongly-Typed Dynamic List,.NET,Developer Tech

# 2 Re: Efficient + Strongly-Typed Dynamic List

"Boris Karadjov" <bbmvp@cpppp.virtualave.net> wrote:
>Since there is no support for generics (template classes) in current .NET
framework
>(but planned for VS 2004 - see
>http://msdn.microsoft.com/vstudio/productinfo/roadmap.aspx), you are left
with the option
>to write a strongly-typed ArrayList (or
>other IList) wrapper for each data type you need. It seems not too complex
to create
>a code or even IL generator for such classes.
>--
>Boris Karadjov
>Brainbench MVP for Visual C++
>http://www.brainbench.com
>
>
Thanks Boris - it works great for full-blown classes, but is there a way
to have a strongly-typed modifiable ArrayList of structure variables? I get
the compiler error "Expression is a value and therefore cannot be the target
of an assignment" when I try to modify the contents of an ArrayList element
for my ArrayList wrapper for a structure.

Dave at 2007-11-11 21:59:34 >

# 4 Re: Efficient + Strongly-Typed Dynamic List

"Jay B. Harlow [MVP - Outlook]" <Jay_Harlow@email.msn.com> wrote:
>Dave,
>I answered this in the vb.dotnet.technical newsgroup.
>
>Hope this helps
>Jay
>
>
>"Dave" <dave_doknjas@yahoo.ca> wrote in message
>news:3f2e73cc$1@tnews.web.dev-archive.com...
>>
>> Is there a way to efficiently grow a strongly-typed simple list in .NET?
>(specifically,
>> a list of structure variables).
>>
>> I don't need to insert into the middle of the list or delete items from
>the
>> list. I just need to add to the end an element at a time. I also don't
>want
>> to be re-copying the entire array every time I add an element.
>>
>> I've tried ArrayList, but since it's not strongly-typed (it accepts
>generic
>> objects) I can't use it to dynamically grow an array of modifiable
>structure
>> variables - I have to use full-blown objects. You can use ArrayList to
>dynamically
>> grow an array of read-only structure variables, but that's not what I
>need.
>>
>> The problem with regular arrays is that they can't be grown dynamically
>with
>> any notable performance. (Interestingly, VB6's ReDim Preserve was
>incredibly
>> fast and since it was used on strongly-typed arrays it was ideal, but
>that's
>> ancient history - VB.NET did away with the efficiency of ReDim Preserve
-
>> and hey, I want to use C#).
>>
>> Thanks
>
>
Yes, but copying the array with every dynamic extension is slow - this is
probably why VB.NET ReDim Preserve is also slow - because it's doing this
behind the scenes.

My best performance so far in .NET is using an ArrayList of objects, but
if there was a way to have an ArrayList of modifiable structure elements
then I think that would be faster.

Dave at 2007-11-11 22:01:39 >

# 6 Re: Efficient + Strongly-Typed Dynamic List

Yes, I did not pay enough attention to your mentioning of structures. Then I would suggest using a "chunked list" - an ArrayList of
fixed-size arrays of structures:

using System;
using System.Collections;

public class ChunkedListOfDateTime
{
private int ItemCount;

private int ChunkSize;

private IList Chunks;

public ChunkedListOfDateTime(int ChunkSize)
{
this.ChunkSize = ChunkSize;
this.Chunks = new ArrayList();
}

public int Count
{
get { return ItemCount; }
}

public int Add(DateTime Item)
{
DateTime[] Chunk;

if (ItemCount % ChunkSize != 0) {
Chunk = (DateTime[]) Chunks[ItemCount / ChunkSize];
} else {
Chunk = new DateTime[ChunkSize];
Chunks.Add(Chunk);
}

Chunk[ItemCount % ChunkSize] = Item;

return ItemCount++;
}

DateTime this[int index] {
get
{
if (index < ItemCount) {
return ((DateTime[]) Chunks[index / ChunkSize])[index % ChunkSize];
} else {
throw new ArgumentOutOfRangeException();
}
}
}
}

Depending on the usage pattern the performance can be somewhat improved by caching the last chunk used. Alas, the overhead
associated with copying structures (as opposed to passing objects by reference) cannot be eliminated (though for the Add method you
can use a ref parameter).
--
Boris Karadjov
Brainbench MVP for Visual C++
http://www.brainbench.com

Boris Karadjov at 2007-11-11 22:03:42 >

# 8 Re: Efficient + Strongly-Typed Dynamic List

Dave,
> Interestingly, object arrays with smart resizing (over-allocation using
the
> double capacity rule) was exactly equivalent performance-wise to
ArrayList's
> of objects.
I would expect the performance to be equivalent, as that is the same
algorithm that ArrayLists use.

See the Capacity property for ArrayList:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpref/html/frlrfSystemCollectionsArrayListClassCapacityTopic.asp

For structure and other value types, I would expect your home grown version
to be faster, as you are avoiding the boxing/unboxing factor.

When we get to Whidbey (VS.NET 2004) I would expect the GenericArrayList to
be top performing in both cases.

http://msdn.microsoft.com/vstudio/productinfo/roadmap.aspx

Hope this helps
Jay

"Dave" <dave_doknjas@yahoo.ca> wrote in message
news:3f305248$1@tnews.web.dev-archive.com...
>
> "Jay B. Harlow [MVP - Outlook]" <Jay_Harlow@email.msn.com> wrote:
> >Dave,
> >> My best performance so far in .NET is using an ArrayList of objects,
but
> >> if there was a way to have an ArrayList of modifiable structure
elements
> >> then I think that would be faster.
> >The ArrayList over allocates.
> >
> >See other thread.
> >
> >Hope this helps
> >Jay
> >
> I thought I'd share my results (copied from the VB.NET group) after really
> delving into this and getting help from Jay, Tom Shelton, and Jason
Sobell:
>
> The ArrayList of objects (instanced from a lightweight class mirroring my
> structure) worked pretty well (much better than the VB6 equivalent), but
> the top performing combination was an array of structures with
over-allocated
> array size (my rule doubled the capacity whenever the capacity was reached
> - hey, memory's cheap!).
>
> Interestingly, object arrays with smart resizing (over-allocation using
the
> double capacity rule) was exactly equivalent performance-wise to
ArrayList's
> of objects. That being the case, I'll always use ArrayList when I'm
dealing
> with a dynamic list of objects rather than structures.
>
> Thanks again,
> Dave Doknjas
>

Jay B. Harlow [MVP - Outlook] at 2007-11-11 22:05:42 >

This is a Technology portal site for all the developer, It's a community, here you can post your question when you are learning, working, and soso...we'll make it better than yesterday Everyday...

Efficient + Strongly-Typed Dynamic List

Developer Tech

All Classified

Developer Tech New Topic

Developer Tech Hot Topic