How to count value in a ArrayList

[Tony]

Hello!

I have an ArrayList with many double that is sorted some of these double
value exist more then once in the ArrayList.
Is it possible to use some feature in C# or from the framework to count each
unique double value or is the only
solution to run through the list and count every unique double value.

//Tony

[=?Utf-8?B?RmFtaWx5IFRyZWUgTWlrZQ==?=]

If you can use LINQ, then this page is an excelent resource
http://msdn.microsoft.com/en-us/vcsharp/aa336747.aspx.

Look at the example for Aggregate Operators - Count - Grouped.

"Tony" wrote:

Hello!

I have an ArrayList with many double that is sorted some of these double
value exist more then once in the ArrayList.
Is it possible to use some feature in C# or from the framework to count each
unique double value or is the only
solution to run through the list and count every unique double value.

//Tony

[j1mb0jay]

On Fri, 23 May 2008 13:43:17 +0200, Tony wrote:

Hello!

I have an ArrayList with many double that is sorted some of these double
value exist more then once in the ArrayList. Is it possible to use some
feature in C# or from the framework to count each unique double value or
is the only
solution to run through the list and count every unique double value.

//Tony

Maybe try using a hash table rather that an array list, searching of a
hash table is O(1) rather than a list O(n).

Regards j1mb0jay

[Jon Skeet [C# MVP]]

On May 23, 12:43 pm, "Tony" <[e-mail]:

I have an ArrayList with many double that is sorted some of these double
value exist more then once in the ArrayList.
Is it possible to use some feature in C# or from the framework to count each
unique double value or is the only
solution to run through the list and count every unique double value.

Leaving aside the other responses, I'd note that comparing double
values against each other directly is usually a bad thing. Two
sequences of calculations which are "logically" identical can have
different results, sometimes for very odd reasons to do with JIT
optimisations etc. It's usually better to compare within a certain
tolerance. What are these doubles representing, and where have they
come from? Different situations merit different approaches.

Jon

[Peter Duniho]

On Fri, 23 May 2008 04:43:17 -0700, Tony <jo*****************@telia.com>
wrote:

Hello!

I have an ArrayList with many double that is sorted some of these double
value exist more then once in the ArrayList.
Is it possible to use some feature in C# or from the framework to count
each
unique double value or is the only
solution to run through the list and count every unique double value.

And in addition to Jon's excellent point, I'll point out that if the list
is in fact sorted as you say, then you should use a binary search to find
the first instance of the value you're looking for. Then you only need to
examine from that point forward until you reach the next value not "equal"
(using whatever definition is appropriate).

For lists of any significant size, this would be _much_ more efficient
than enumerating the entire list.

Pete

[Ignacio Machin ( .NET/ C# MVP )]

On May 23, 7:43*am, "Tony" <[e-mail]:

Hello!

I have an ArrayList with many double that is sorted some of these double
value exist more then once in the ArrayList.
Is it possible to use some feature in C# or from the framework to count each
unique double value or is the only
solution to run through the list and count every unique double value.

//Tony

Hi,

You will have to run through the list, there is no way to avoid that.

[j1mb0jay]

On Fri, 23 May 2008 12:11:48 -0700, Ignacio Machin ( .NET/ C# MVP ) wrote:

On May 23, 7:43Â*am, "Tony" <[e-mail]:

>Hello!

I have an ArrayList with many double that is sorted some of these
double value exist more then once in the ArrayList. Is it possible to
use some feature in C# or from the framework to count each unique
double value or is the only
solution to run through the list and count every unique double value.

//Tony

Hi,

You will have to run through the list, there is no way to avoid that.

If you input the the data into a hash table rather than a ArrayList, that
will clone itself when it gets full and is rather slow. Then when you
want to look for an item you will only have to look at one item to see if
you have it, rather than the whole list.

Regards j1mb0jay

[=?UTF-8?B?QXJuZSBWYWpow7hq?=]

j1mb0jay wrote:

If you input the the data into a hash table rather than a ArrayList, that
will clone itself when it gets full and is rather slow. Then when you
want to look for an item you will only have to look at one item to see if
you have it, rather than the whole list.

Is that different from ArrayList ??

Arne

[j1mb0jay]

On Sat, 24 May 2008 11:01:49 -0400, Arne Vajhøj wrote:

j1mb0jay wrote:

>If you input the the data into a hash table rather than a ArrayList,
that will clone itself when it gets full and is rather slow. Then when
you want to look for an item you will only have to look at one item to
see if you have it, rather than the whole list.

Is that different from ArrayList ??

Arne

A well distributed hash table has a BigO(1) for all operations (Insert,
Search and Remove).

http://en.wikipedia.org/wiki/Hash_table

Regards j1mb0jay

[=?UTF-8?B?QXJuZSBWYWpow7hq?=]

j1mb0jay wrote:

On Sat, 24 May 2008 11:01:49 -0400, Arne Vajhøj wrote:

>j1mb0jay wrote:

>>If you input the the data into a hash table rather than a ArrayList,
that will clone itself when it gets full and is rather slow. Then when
you want to look for an item you will only have to look at one item to
see if you have it, rather than the whole list.

Is that different from ArrayList ??

A well distributed hash table has a BigO(1) for all operations (Insert,
Search and Remove).

So does an array list for operations at the tail.

Until the backing array is full.

And a hash table has the same issue.

Arne

[j1mb0jay]

On Sat, 24 May 2008 13:35:03 -0400, Arne Vajhøj wrote:

j1mb0jay wrote:

>On Sat, 24 May 2008 11:01:49 -0400, Arne Vajhøj wrote:

>>j1mb0jay wrote:
If you input the the data into a hash table rather than a ArrayList,
that will clone itself when it gets full and is rather slow. Then
when you want to look for an item you will only have to look at one
item to see if you have it, rather than the whole list.
Is that different from ArrayList ??

A well distributed hash table has a BigO(1) for all operations (Insert,
Search and Remove).

So does an array list for operations at the tail.

Until the backing array is full.

And a hash table has the same issue.

Arne

How can an array list have a O(1) Search, when it has to look at each
item and compare. Dont be so silly !!!

j1mb0jay

[=?UTF-8?B?QXJuZSBWYWpow7hq?=]

j1mb0jay wrote:

On Sat, 24 May 2008 13:35:03 -0400, Arne Vajhøj wrote:

>j1mb0jay wrote:

>>On Sat, 24 May 2008 11:01:49 -0400, Arne Vajhøj wrote:
j1mb0jay wrote:
If you input the the data into a hash table rather than a ArrayList,
that will clone itself when it gets full and is rather slow. Then
when you want to look for an item you will only have to look at one
item to see if you have it, rather than the whole list.
Is that different from ArrayList ??
A well distributed hash table has a BigO(1) for all operations (Insert,
Search and Remove).

So does an array list for operations at the tail.

Until the backing array is full.

And a hash table has the same issue.

How can an array list have a O(1) Search, when it has to look at each
item and compare. Dont be so silly !!!

Both inserting at the tail and removing from the tail is O(1).
Technically speaking searching at the tail is also O(1), but there
is not much point in that.

Arne

[=?UTF-8?B?QXJuZSBWYWpow7hq?=]

j1mb0jay wrote:

On Sat, 24 May 2008 18:31:49 -0400, Arne Vajhøj wrote:

>j1mb0jay wrote:

>>I was always taught to stay away from ArrayList at all costs.

You were taugth wrong.

ArrayList (or List<in newer .NET versions) is in most cases a very
good choice of data structure.

I thought the new ArrayList<TYPEwas just to stop unwanted items been
added item your list which in turn would be processed by your program
that maybe "harmful", and of course you no longer need to cast objects
when pulling them out structure.

It is more type safe.

Type safeness is a very good thing.

It also has a positive impact on performance of lists
of value types.

ArrayLists are simple to use and perfect
for most simple programs.

Also for complex programs.

Although you may argue that the more complex
programs be written in C of Assembly, for example Folding@Home.

It is the other way around. You can do simple programs in assembler
(and to some extent C). For complex programs you need a more
high level language.

I still stick with my argument, you do not have to re hash a hash table
when a large amount of collisions happen, you can just keep adding more
items, once a array list is full you have to clone it to a larger table.

You are free to stick with your argument.

But everybody can lookup in the .NET code and see that you are wrong -
the Hashtable/Dictionary also reallocates and copy data when it
is full.

Arne

[Peter Duniho]

On Sat, 24 May 2008 16:47:28 -0700, Peter Duniho
<Np*********@nnowslpianmk.comwrote:

On Sat, 24 May 2008 16:20:12 -0700, j1mb0jay <j1******@uni.ac.ukwrote:
[...]

>I still stick with my argument, you do not have to re hash a hash table
when a large amount of collisions happen, you can just keep adding more
items,

You really should look at the actual classes in question before you make
that claim. There is a reason that the .NET hash table implementations
have a way to declare and inspect its "Capacity".

Sorry...my mistake. The capacity is internal, non-public. The docs refer
to it, but you can't access it directly.

Still, the basic point about the implementation remains. And as Arne
says, if you don't believe us, just look at the code.

Pete

[Rudy Velthuis]

j1mb0jay wrote:

Then
when you want to look for an item you will only have to look at one
item to see if you have it, rather than the whole list.

If a hash table is full of collisions, as you put it, it is in fact
just a list of linked lists, and not that much faster anymore. You must
most definitely look at more than one item, although of course only for
the bucket corresponding to the hash value you are looking for.

So rehashing is most definitely something that must be done, sometimes,
if you keep on having collisions, or if the list is rather full.

And reallocations in an ArrayList do not occur for each new item
either. If it is full, the capacity is doubled and the data is copied
over. From then on, you can add quite a few more items before it is
full.
--
Rudy Velthuis http://rvelthuis.de

"Your Highness, I have no need of this hypothesis."
-- Pierre Laplace (1749-1827), to Napoleon on why his works on
celestial mechanics make no mention of God.

[j1mb0jay]

On Sat, 24 May 2008 19:33:49 -0400, Arne Vajhøj wrote:

j1mb0jay wrote:

>On Sat, 24 May 2008 18:31:49 -0400, Arne Vajhøj wrote:

>>j1mb0jay wrote:
I was always taught to stay away from ArrayList at all costs.
You were taugth wrong.

ArrayList (or List<in newer .NET versions) is in most cases a very
good choice of data structure.

I thought the new ArrayList<TYPEwas just to stop unwanted items been
added item your list which in turn would be processed by your program
that maybe "harmful", and of course you no longer need to cast objects
when pulling them out structure.

It is more type safe.

Type safeness is a very good thing.

It also has a positive impact on performance of lists of value types.

> ArrayLists are simple to use and
perfect
for most simple programs.

Also for complex programs.

> Although you may argue that the more complex
programs be written in C of Assembly, for example Folding@Home.

It is the other way around. You can do simple programs in assembler (and
to some extent C). For complex programs you need a more high level
language.

>I still stick with my argument, you do not have to re hash a hash table
when a large amount of collisions happen, you can just keep adding more
items, once a array list is full you have to clone it to a larger
table.

You are free to stick with your argument.

But everybody can lookup in the .NET code and see that you are wrong -
the Hashtable/Dictionary also reallocates and copy data when it is full.

Arne

I never said anything about the .net version !!!

j1mb0jay

[Peter Duniho]

On Sat, 24 May 2008 17:58:45 -0700, j1mb0jay <j1******@uni.ac.ukwrote:

I never said anything about the .net version !!!

Well...

Whose version are you talking about then?

You can't make accurate statements about a hash table implementation
without knowing _which_ implementation you're talking about.

This being the C# newsgroup, the .NET hash table implementations certainly
seem like a reasonable assumption. If that's not the implementation
you're talking about, you need to be specific.

Pete

[=?UTF-8?B?QXJuZSBWYWpow7hq?=]

j1mb0jay wrote:

On Sat, 24 May 2008 19:33:49 -0400, Arne Vajhøj wrote:

>But everybody can lookup in the .NET code and see that you are wrong -
the Hashtable/Dictionary also reallocates and copy data when it is full.

I never said anything about the .net version !!!

There are not much point in posting about non-.NET in a
..NET newsgroup.

Arne

[=?ISO-8859-1?Q?Arne_Vajh=F8j?=]

Tony wrote:

I have an ArrayList with many double that is sorted some of these double
value exist more then once in the ArrayList.
Is it possible to use some feature in C# or from the framework to count each
unique double value or is the only
solution to run through the list and count every unique double value.

You can not avoid the loop (with a list as data structure).

If you used List<doubleinstead of ArrayList you could use an
implicit loop as in:

int ndistinct = 0;
double lastx = double.NaN;
lst.ForEach(delegate(double x) { if(x != lastx) ndistinct++; lastx = x; });

But if you consider that nicer than a simple for loop is up to you.

And please pay attention to Jon's note about floating point
comparison.

Arne