List<T> Question

[Sean]

I have been using List(of String) when I could easily be using a string array
instead.

Is it still considered best practice to use Generic list of string rather
then a string array?
Thanks

[Helge Jensen]

Sean wrote:

I have been using List(of String) when I could easily be using a string array
instead.

Is it still considered best practice to use Generic list of string rather
then a string array?

Use whatever suits the occasion.

The most important difference is that string[] is fixed-length and
List<string> is variable-length.

Remember that they can both be used iterchangeable after creation
through IList<string>.

--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Sharon]

One more important difference:
The string array gives you insertion cost of O(1),
and array list of type string insertion cost is O(n).
So, string array gives better performance, but is less comfortable to use.
Sharon.

"Helge Jensen" <he**********@slog.dk> wrote in message
news:Om**************@TK2MSFTNGP10.phx.gbl...

Sean wrote:

I have been using List(of String) when I could easily be using a string
array
instead.

Is it still considered best practice to use Generic list of string rather
then a string array?

Use whatever suits the occasion.

The most important difference is that string[] is fixed-length and
List<string> is variable-length.

Remember that they can both be used iterchangeable after creation
through IList<string>.

--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Bruce Wood]

> array list of type string insertion cost is O(n)

Really? Why? Where is that information from?

So far as I know, ArrayList insertion cost is O(1), unless the
ArrayList is full, in which case it must be reallocated elsewhere and
copied to increase its capacity. So, it all rather depends upon whether
it's instantiated (at least) large enough in the first place.

I thought that ArrayList is backed by an array and a "used length", and
the array is simply copied to a bigger array when it gets full.

For a traditional linked list, the insertion cost is typically also
O(1), but the seek cost (for linkedList[i]) is O(n).

[Helge Jensen]

Sharon wrote:

One more important difference:
The string array gives you insertion cost of O(1),
A string-array doesn't support "inserting", it has constant size.
and array list of type string insertion cost is O(n).
yes, insertion is expensive on AraryLists, but appending isn't. And you
can probably use Append and later do .Reverse if needed.

If you allocate the array with a certain capacity the .Add upto that
limit are certainly O(1).

I think -- but haven't actually tested -- that .Add in arraylists are
amortized O(1). I havent had any performance problems filling lists with
100s of thousands of entries, so I find it hard to believe that
ArrayList.Add has complexity O(n).
So, string array gives better performance, but is less comfortable to use.

If perfomance is the issue, use a profiler to find the problems. Don't
micro-optimize.

--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Bruce Wood]

> yes, insertion is expensive on AraryLists, but appending isn't.

Yes... silly me. I was thinking of appending when I wrote my post. But
then, inserting into the middle of an array (assuming it doesn't have
to grow, which it can't) is the same cost as inserting into an
ArrayList. So far as I know they're the same data structure under the
covers.

If perfomance is the issue, use a profiler to find the problems. Don't micro-optimize.

Amen. Too many programmers think they're being clever by using obscure
constructs to be more "efficient" when in fact their programs are
spending 90% of their time elsewhere.

[Sharon]

"Helge Jensen" <he**********@slog.dk> wrote in message
news:OR**************@TK2MSFTNGP12.phx.gbl...

Sharon wrote:

One more important difference:
The string array gives you insertion cost of O(1),
A string-array doesn't support "inserting", it has constant size.

I used the wrong word here.
By inserting i mean: string[1] = value.
Not creating a new element.

and array list of type string insertion cost is O(n).
yes, insertion is expensive on AraryLists, but appending isn't. And you
can probably use Append and later do .Reverse if needed.

Append??

If you allocate the array with a certain capacity the .Add upto that
limit are certainly O(1).
True.
About Add method at msdn:
If Count is less than Capacity, this method is an O(1) operation. If the
capacity needs to be increased to accommodate the new element, this method
becomes an O(n) operation, where n is Count.

I think -- but haven't actually tested -- that .Add in arraylists are
amortized O(1). I havent had any performance problems filling lists with
100s of thousands of entries, so I find it hard to believe that
ArrayList.Add has complexity O(n).
But it does, when Count == Capacity.

So, string array gives better performance, but is less comfortable to
use.
If perfomance is the issue, use a profiler to find the problems. Don't
micro-optimize.

It really depends, if the array is fixed size, then there is no need to use
ArrayList.
I thinks it's better to understand how a collection works, than later change
the implementation
because the profiler shows a problem.
Sharon.

--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Kevin Spencer]

The Generic LinkedList class can perform inserts and other tasks with the
same 0(1) performance.

--
HTH,

Kevin Spencer
Microsoft MVP
Professional Numbskull

Show me your certification without works,
and I'll show my certification
*by* my works.

"Sharon" <no*****@null.void> wrote in message
news:OS**************@TK2MSFTNGP11.phx.gbl...

"Helge Jensen" <he**********@slog.dk> wrote in message
news:OR**************@TK2MSFTNGP12.phx.gbl...

Sharon wrote:

One more important difference:
The string array gives you insertion cost of O(1),

A string-array doesn't support "inserting", it has constant size.

I used the wrong word here.
By inserting i mean: string[1] = value.
Not creating a new element.

and array list of type string insertion cost is O(n).

yes, insertion is expensive on AraryLists, but appending isn't. And you
can probably use Append and later do .Reverse if needed.

Append??

If you allocate the array with a certain capacity the .Add upto that
limit are certainly O(1).

True.
About Add method at msdn:
If Count is less than Capacity, this method is an O(1) operation. If the
capacity needs to be increased to accommodate the new element, this method
becomes an O(n) operation, where n is Count.

I think -- but haven't actually tested -- that .Add in arraylists are
amortized O(1). I havent had any performance problems filling lists with
100s of thousands of entries, so I find it hard to believe that
ArrayList.Add has complexity O(n).

But it does, when Count == Capacity.

So, string array gives better performance, but is less comfortable to
use.

If perfomance is the issue, use a profiler to find the problems. Don't
micro-optimize.

It really depends, if the array is fixed size, then there is no need to
use ArrayList.
I thinks it's better to understand how a collection works, than later
change the implementation
because the profiler shows a problem.
Sharon.

--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Helge Jensen]

Sharon wrote:

I used the wrong word here.
By inserting i mean: string[1] = value.
Not creating a new element.

List<T> have exactly the same compleity on assignment.

yes, insertion is expensive on AraryLists, but appending isn't. And you
can probably use Append and later do .Reverse if needed.

Append??

Sorry, I should have said "..you can probably use .Add to append and
later..."

If you allocate the array with a certain capacity the .Add upto that
limit are certainly O(1).

True.
About Add method at msdn:
If Count is less than Capacity, this method is an O(1) operation. If the
capacity needs to be increased to accommodate the new element, this method
becomes an O(n) operation, where n is Count.

However I have never had a problem filling a list, and i've made some
pretty big ones, so an O(n) insert, giving O(n^2) list-filling should
probably have bit me by now.

Lets look at a small test program:

using System;
using System.Collections.Generic;
using System.Collections;

class ArrayListAddComplexityTest
{
[STAThread]
static void Main(string[] args)
{
int half_count = 10000000;
List<int> l = new List<int>();
DateTime start = DateTime.Now;
for (int i = 0; i < half_count; ++i)
l.Add(i);
DateTime half = DateTime.Now;
for (int i = 0; i < half_count; ++i)
l.Add(i);
DateTime end = DateTime.Now;

Console.WriteLine("first half = {0}s, second half = {1}s", (half
- start).TotalSeconds, (end - half).TotalSeconds);
if (hack)
foreach (int i in l)
Console.WriteLine(i);
}
public static volatile bool hack = false;
}

The volatile boolean hack makes sure the compiler or runtime can't
optimize away the actual generation of the list :)

This program terminates with the output:

first half = 0,3605184s, second half = 0,3404896s

Which clearly shows:

1. List<T>.Add is fast enough for most anything
2. List<T>.Add is O(1), no matter what Capacity is used

Actually, it seems like .Add is sublinear, but that's just GC and
realloc messing with you. The figures are *definatly* solid enouogh to
prove that while List<T>.Add is O(n), it is also O(1) on my system,
atleast for upto 10 million ints.

I think -- but haven't actually tested -- that .Add in arraylists are
amortized O(1). I havent had any performance problems filling lists with
100s of thousands of entries, so I find it hard to believe that
ArrayList.Add has complexity O(n).

But it does, when Count == Capacity.

Well, now it's tested and it's amortized O(1), Capacity doesn't matter.

If perfomance is the issue, use a profiler to find the problems. Don't
micro-optimize.

It really depends, if the array is fixed size, then there is no need to use
ArrayList.
I thinks it's better to understand how a collection works, than later change
the implementation
because the profiler shows a problem.

I agree that it's good to know how collections works, but just use
whatever's most handy untill there is actually a problem.

The tests i've done now shows clearly that using [] over IList<T> should
probably not be done for performance reasons anytime.

--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Helge Jensen]

Kevin Spencer wrote:

The Generic LinkedList class can perform inserts and other tasks with the
same 0(1) performance.

At the expense of having lookup: this[int index] worst-case and expected
complexity O(n) ;)

--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Nick Malik [Microsoft]]

"Sharon" <no*****@null.void> wrote in message
news:OS**************@TK2MSFTNGP11.phx.gbl...

About Add method at msdn:
If Count is less than Capacity, this method is an O(1) operation. If the
capacity needs to be increased to accommodate the new element, this method
becomes an O(n) operation, where n is Count.

I believe, Sharon, that there is a point to this... if you allocate an
initial size of 1000 elements, and you hit the 1000th element, then
performing a .Add operation is O(1000). However, once that operation is
performed, you are now using a memory structure that is 2000 elements in
size. Therefore, adding the 1001st element is O(1) again.

If you are using an array, you must feel pretty confident that you /know/
the maximum array size to use. Therefore, if you allocate to that size, you
will get exactly the same performance for an array as you will for a list,
up to that size.

Then, adding one more element for an array causes an exception. Adding one
more element for a list causes a single slow operation followed by thousands
more quick ones.

Given the choice, I'll go with List every time. Think of it as simple
defensive coding. You wouldn't code a limit into your app if you could
easily avoid doing so, would you? (if you say: it doesn't matter, just
remember the 640K limit in DOS. It matters).

--
--- Nick Malik [Microsoft]
MCSD, CFPS, Certified Scrummaster
http://blogs.msdn.com/nickmalik

Disclaimer: Opinions expressed in this forum are my own, and not
representative of my employer.
I do not answer questions on behalf of my employer. I'm just a
programmer helping programmers.
--

[Sharon]

Check the performance on this one:

using System;
using System.Collections.Generic;
using System.Collections;

class ArrayListAddComplexityTest
{
[STAThread]
static void Main(string[] args)
{
int half_count = 10000000;
List<int> l = new List<int>();

DateTime start = DateTime.Now;
for (int i = 0; i < half_count; ++i)
l.Add(i);

DateTime half = DateTime.Now;

for (int i = 0; i < half_count; ++i)
l.Add(i);
DateTime end = DateTime.Now;

DateTime arrStart = DateTime.Now;
int[] ia = new int[half_count];
for (int i = 0; i < half_count; ++i)
ia[i] = i;
DateTime arrEnd = DateTime.Now;

Console.WriteLine("first half = {0}s, second half = {1}s", (half
- start).TotalSeconds, (end - half).TotalSeconds);
Console.WriteLine("arr = {0}", (arrEnd - arrStart).TotalSeconds);

if (hack)
foreach (int i in l)
Console.WriteLine(i);

Console.ReadLine();
}

public static volatile bool hack = false;
}
"Helge Jensen" <he**********@slog.dk> wrote in message
news:un**************@TK2MSFTNGP12.phx.gbl...

Sharon wrote:

I used the wrong word here.
By inserting i mean: string[1] = value.
Not creating a new element.

List<T> have exactly the same compleity on assignment.

yes, insertion is expensive on AraryLists, but appending isn't. And you
can probably use Append and later do .Reverse if needed.

Append??

Sorry, I should have said "..you can probably use .Add to append and
later..."

If you allocate the array with a certain capacity the .Add upto that
limit are certainly O(1).

True.
About Add method at msdn:
If Count is less than Capacity, this method is an O(1) operation. If the
capacity needs to be increased to accommodate the new element, this
method
becomes an O(n) operation, where n is Count.

However I have never had a problem filling a list, and i've made some
pretty big ones, so an O(n) insert, giving O(n^2) list-filling should
probably have bit me by now.

Lets look at a small test program:

using System;
using System.Collections.Generic;
using System.Collections;

class ArrayListAddComplexityTest
{
[STAThread]
static void Main(string[] args)
{
int half_count = 10000000;
List<int> l = new List<int>();
DateTime start = DateTime.Now;
for (int i = 0; i < half_count; ++i)
l.Add(i);
DateTime half = DateTime.Now;
for (int i = 0; i < half_count; ++i)
l.Add(i);
DateTime end = DateTime.Now;

Console.WriteLine("first half = {0}s, second half = {1}s", (half
- start).TotalSeconds, (end - half).TotalSeconds);
if (hack)
foreach (int i in l)
Console.WriteLine(i);
}
public static volatile bool hack = false;
}

The volatile boolean hack makes sure the compiler or runtime can't
optimize away the actual generation of the list :)

This program terminates with the output:

first half = 0,3605184s, second half = 0,3404896s

Which clearly shows:

1. List<T>.Add is fast enough for most anything
2. List<T>.Add is O(1), no matter what Capacity is used

Actually, it seems like .Add is sublinear, but that's just GC and
realloc messing with you. The figures are *definatly* solid enouogh to
prove that while List<T>.Add is O(n), it is also O(1) on my system,
atleast for upto 10 million ints.

I think -- but haven't actually tested -- that .Add in arraylists are
amortized O(1). I havent had any performance problems filling lists with
100s of thousands of entries, so I find it hard to believe that
ArrayList.Add has complexity O(n).

But it does, when Count == Capacity.

Well, now it's tested and it's amortized O(1), Capacity doesn't matter.

If perfomance is the issue, use a profiler to find the problems. Don't
micro-optimize.

It really depends, if the array is fixed size, then there is no need to
use
ArrayList.
I thinks it's better to understand how a collection works, than later
change
the implementation
because the profiler shows a problem.

I agree that it's good to know how collections works, but just use
whatever's most handy untill there is actually a problem.

The tests i've done now shows clearly that using [] over IList<T> should
probably not be done for performance reasons anytime.

--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Kevin Spencer]

Agreed. I haven't used one yet, but I can certainly see why it's there.

--
HTH,

Kevin Spencer
Microsoft MVP
Professional Numbskull

Show me your certification without works,
and I'll show my certification
*by* my works.

"Helge Jensen" <he**********@slog.dk> wrote in message
news:%2***************@TK2MSFTNGP12.phx.gbl...

Kevin Spencer wrote:

The Generic LinkedList class can perform inserts and other tasks with the
same 0(1) performance.

At the expense of having lookup: this[int index] worst-case and expected
complexity O(n) ;)

--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Sean]

I asked a question I already knew the answer to and I asked it wrong.

What I ment to ask was it is List(of string()) instead of an arraylist of
strings.

Answer is List(of string()) is better. Even more so when dealing with value
types becuase List( of..) is a value type already.

"Sean" wrote:

I have been using List(of String) when I could easily be using a string array
instead.

Is it still considered best practice to use Generic list of string rather
then a string array?
Thanks

[Helge Jensen]

Sharon wrote:

Check the performance on this one:
That code is not a fair comparison.

List<int> l = new List<int>();
If the array is allocated to a certain capacity you can allocate the
List<int> to the same capacity.

l = new List<int>(half_count);

You are measuring the allocation time of the array too. I would move it
to the front.

DateTime arrStart = DateTime.Now;
DateTime start = DateTime.Now;
for (int i = 0; i < half_count; ++i)
l.Add(i);

DateTime half = DateTime.Now;

for (int i = 0; i < half_count; ++i)
l.Add(i);
DateTime end = DateTime.Now; DateTime arrStart = DateTime.Now;
int[] ia = new int[half_count];
for (int i = 0; i < half_count; ++i)
ia[i] = i;
DateTime arrEnd = DateTime.Now;
You are only inserting half_count items in the array, but 2*half_count
in the List
if (hack)
foreach (int i in l)
Console.WriteLine(i);

You forgot to ensure that ia is used. Possibly the compiler or runtime
will remove the entire creation and filling of the array.

Below is my modified test-program, to compare List<int> and int[], not
that these micro-bechmarks mean that much, but I get:

first half = 0,1802592s, second half = 0,1301872s
total: 0,3104464s

which shows that there is very little difference in performance.
Definatly not enough unless the code runs in a real tight loop around
that peice of code -- which would definatly show up in the profiler.

using System;
using System.Collections.Generic;
using System.Collections;

class ArrayListAddComplexityTest
{
[STAThread]
static void Main(string[] args)
{
int half_count = 10000000;
List<int> l = new List<int>(half_count);
int[] a = new int[half_count];
DateTime start = DateTime.Now;
for (int i = 0; i < half_count; ++i)
l.Add(i);
DateTime half = DateTime.Now;
for (int i = 0; i < half_count; ++i)
a[i] = i;
DateTime end = DateTime.Now;

Console.WriteLine("first half = {0}s, second half = {1}s", (half
- start).TotalSeconds, (end - half).TotalSeconds);
Console.WriteLine("total: {0}s", (end - start).TotalSeconds);
if (hack)
foreach (int i in l)
Console.WriteLine(i);
if (hack)
foreach (int i in a)
Console.WriteLine(i);
}
public static volatile bool hack = false;
}

--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Bruce Wood]

> ...just use whatever's most handy untill there is actually a problem.

....and that, folks, is the bottom line. Micro-optimization up front
leads to stupid code. Serious gains in performance come with design
changes, not code tweaks, *unless* you've profiled the code and found a
real problem.

[Sharon]

You are right Helge.
My results using 1000000 items:
generic list = 0.015625
array = 0.015625
The same, and should be when capacity is set in the constructor.
Sharon.

"Helge Jensen" <he**********@slog.dk> wrote in message
news:ua**************@TK2MSFTNGP11.phx.gbl...

Sharon wrote:

Check the performance on this one:

That code is not a fair comparison.

List<int> l = new List<int>();

If the array is allocated to a certain capacity you can allocate the
List<int> to the same capacity.

l = new List<int>(half_count);

You are measuring the allocation time of the array too. I would move it
to the front.

DateTime arrStart = DateTime.Now;

DateTime start = DateTime.Now;
for (int i = 0; i < half_count; ++i)
l.Add(i);

DateTime half = DateTime.Now;

for (int i = 0; i < half_count; ++i)
l.Add(i);
DateTime end = DateTime.Now;

DateTime arrStart = DateTime.Now;
int[] ia = new int[half_count];
for (int i = 0; i < half_count; ++i)
ia[i] = i;
DateTime arrEnd = DateTime.Now;

You are only inserting half_count items in the array, but 2*half_count
in the List

if (hack)
foreach (int i in l)
Console.WriteLine(i);

You forgot to ensure that ia is used. Possibly the compiler or runtime
will remove the entire creation and filling of the array.

Below is my modified test-program, to compare List<int> and int[], not
that these micro-bechmarks mean that much, but I get:

first half = 0,1802592s, second half = 0,1301872s
total: 0,3104464s

which shows that there is very little difference in performance.
Definatly not enough unless the code runs in a real tight loop around
that peice of code -- which would definatly show up in the profiler.

using System;
using System.Collections.Generic;
using System.Collections;

class ArrayListAddComplexityTest
{
[STAThread]
static void Main(string[] args)
{
int half_count = 10000000;
List<int> l = new List<int>(half_count);
int[] a = new int[half_count];
DateTime start = DateTime.Now;
for (int i = 0; i < half_count; ++i)
l.Add(i);
DateTime half = DateTime.Now;
for (int i = 0; i < half_count; ++i)
a[i] = i;
DateTime end = DateTime.Now;

Console.WriteLine("first half = {0}s, second half = {1}s", (half
- start).TotalSeconds, (end - half).TotalSeconds);
Console.WriteLine("total: {0}s", (end - start).TotalSeconds);
if (hack)
foreach (int i in l)
Console.WriteLine(i);
if (hack)
foreach (int i in a)
Console.WriteLine(i);
}
public static volatile bool hack = false;
}

--
Helge Jensen
mailto:he**********@slog.dk
sip:he**********@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Jon Skeet [C# MVP]]

Sean <Se**@discussions.microsoft.com> wrote:

<snip>

Answer is List(of string()) is better. Even more so when dealing with value
types becuase List( of..) is a value type already.

No, List<T> isn't a value type. However, when T is a value type, the
array used inside List<T> is an array of the appropriate type, rather
than still an object array as it is in ArrayList. In other words, you
avoid the boxing/unboxing overhad. None of that makes List<T> a value
type though...

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Joanna Carter [TeamB]]

"Sean" <Se**@discussions.microsoft.com> a écrit dans le message de news:
21**********************************@microsoft.com...

|I have been using List(of String) when I could easily be using a string
array
| instead.
|
| Is it still considered best practice to use Generic list of string rather
| then a string array?

Arrays are typically resized by copying which can be slow; generic lists are
generally faster when just adding to the end.

Joanna

--
Joanna Carter [TeamB]
Consultant Software Engineer