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==?=]

RE: How to count value in a ArrayList

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]

Re: How to count value in a ArrayList

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]]

Re: How to count value in a ArrayList

On May 23, 12:43 pm, "Tony" <johansson.ande rs...@telia.com 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.

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]

Re: How to count value in a ArrayList

On Fri, 23 May 2008 04:43:17 -0700, Tony <johansson.ande rsson@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 )]

Re: How to count value in a ArrayList

On May 23, 7:43 am, "Tony" <johansson.ande rs...@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.
>
//Tony

Hi,

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

[j1mb0jay]

Re: How to count value in a ArrayList

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

On May 23, 7:43 am, "Tony" <johansson.ande rs...@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.
>>
>//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?=]

Re: How to count value in a ArrayList

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]

Re: How to count value in a ArrayList

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?=]

Re: How to count value in a ArrayList

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]

Re: How to count value in a ArrayList

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?=]

Re: How to count value in a ArrayList

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?=]

Re: How to count value in a ArrayList

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<TYPEw as 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]

Re: How to count value in a ArrayList

On Sat, 24 May 2008 16:47:28 -0700, Peter Duniho
<NpOeStPeAdM@nn owslpianmk.comw rote:

On Sat, 24 May 2008 16:20:12 -0700, j1mb0jay <j1mb0jay@uni.a c.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]

Re: How to count value in a ArrayList

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.