Re: How to count value in a ArrayList

Tech Tip: Click here to run a free scan for Windows Errors and optimize PC performance

j1mb0jay wrote:
From reading the OP, i thought that they where inserting double values into a data structure and wanted to make sure that the value that they were adding was not already stored in the data structure. To me this means they will need to compare every insert item with ever single item in the list O(n). Doing this with a ArrayList is a lot slower than a hash table, as you could hash the double value to find out which linked list the value would be stored in, then just check the few values in the list.

That makes sense, but that was not the statement of yours we
disagreed with.

We disagreed with the suggestion that ArrayList was slower than
Hashtable due to the reallocate and copy at expansion of the backing
array.

When an array list is full is needs to be cloned to another larger array list. I thought that hash tables where are array of linked lists

It is not.

And I suspect it would be significant slower doing it that way. The
reason Hashtable is fast is the ability to lookup directly based on
hash value.

If the OP is using a ArrayList and would like to keep the items in order when inserting a new item this would mean moving all of items along one in the list, again another slow process, maybe a tree of some kind would be a better option.

ArrayList is not a good choice to insert sorted into.

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.

Arne
.

Relevant Pages

  • Re: How to count value in a ArrayList
    ... were adding was not already stored in the data structure. ... Doing this with a ArrayList is a lot slower than a hash ... But presumably they use a relatively common technique of having a fixed-sized array of bins that grows as the hash table accumulates items. ... Some implementations use bins that are either arrays or linked lists, while others simply use the next available spot in the hash table. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: beginning with ML
    ... What's the preferred data structure? ... Lists are commonly used, being functional, but hash tables are also ... I use the RedBlackTree implemenation in the utility library ...
    (comp.lang.functional)
  • Re: A (psossibly) fast, novel search table technique
    ... [new data structure for table] ... technique (in terms of time and space cost) for an ... it's faster than hash tables for searches. ... slower than a search but shouldn't be slower by much. ...
    (comp.programming)
  • Re: How to improve my summarizing code
    ... a list of lists. ... If you don't need the result sorted, then using a hash table you can ... (defun value (row) ... You probably need a more sophisticated data structure for rows, ...
    (comp.lang.lisp)
  • Re: [Full-Disclosure] Show me the Virrii!
    ... the resources necessary to assemble definitive lists of ... audit process execution at just the right time. ... To complete what turned out to be a three-part-series on using hash ... BOOL validatehash(HANDLE hProfile,char *sHash,DWORD hashlen); ...
    (Full-Disclosure)