fastest searchable datastructure?

[Pieter]

Hi,

I need some type of array/list/... In which I can store objects together
with a unique key. The most important thing is performance: I will need to
do the whole time searches in the list of given keys. Which datastructure
will be best suited for this? A Hashtable? The list may contain upto 10^12
items, bit more proably most of the time +- 10^9 of even 10^6...

Thanks a lot in advance,
Pieter

[Kevin Spencer]

A Hashtable would be faster in terms of searching, as long as one was
searching by a key value.

--
HTH,

Kevin Spencer
Chicken Salad Surgeon
Microsoft MVP

"Peter Bromberg [C# MVP]" <pb*******@yaho o.NoSpamMaam.co mwrote in message
news:E9******** *************** ***********@mic rosoft.com...

I'd think that a Generic List or Generic Dictionary would be faster as
there
would be no boxing / unboxing involved in adding or retrieving typed
elements.
-- Peter
Site: http://www.eggheadcafe.com
UnBlog: http://petesbloggerama.blogspot.com
MetaFinder: http://www.blogmetafinder.com
"Pieter" wrote:

>Hi,

I need some type of array/list/... In which I can store objects together
with a unique key. The most important thing is performance: I will need
to
do the whole time searches in the list of given keys. Which datastructure
will be best suited for this? A Hashtable? The list may contain upto
10^12
items, bit more proably most of the time +- 10^9 of even 10^6...

Thanks a lot in advance,
Pieter

[Marc Gravell]

(of course, given the numbers in question, *any* in-memory approach is
doomed... doomed...)

[Cor Ligthert]

System.Collecti ons.SortedList

&
[Kevin Spencer]

A Hashtable would be faster in terms of searching, as long as one was
searching by a key value.

Yes, a hash-table implementation is better than a flat list, but
Hashtable is the non-typed version; for the reasons already given by
Peter the generic versions would generally be preferable -
specifically one of Dictionary<TKey , TValue>, SortedDictionar y<TKey,
TValueand SortedList<TKey , TValue(dependin g on what operations are
important). The OP indicates that *read* performance is the key here
(not insertion/deletion); these report O(1), O(log n) and O(log n) for
retrieval - hence Dictionary<TKey , TValuewould be my first choice.
But the real answer is to test it with typical data: if you code the
app to work against the IDictionary<TKe y, TValueinterface (rather
than any concrete implementation) you should be able to try different
implementations with likely data.

Marc

[Michel Posseth [MCP]]

Hello Pieter

Balena did some tests and posted the results on his website , however with
the transition form VB2themax to dotnet2themax the article seems to be
disapeared
However the result was that the hashtable was and still is the fastest key
value pair object , the higher the amount of data was the more efiicient the
hashtable was in comparisation to other methods for sowell insertion as
retrieving of the key value pairs ( Balena timed both the time it took to
built up the data tree as the time it took to retrieve n elements ) ,
however with the hughe amounts you are talking about a database would be a
much bether idea
HTH

Michel



"Pieter" <pi************ ****@hotmail.co mschreef in bericht
news:OH******** ********@TK2MSF TNGP04.phx.gbl. ..

Hi,

I need some type of array/list/... In which I can store objects together
with a unique key. The most important thing is performance: I will need to
do the whole time searches in the list of given keys. Which datastructure
will be best suited for this? A Hashtable? The list may contain upto 10^12
items, bit more proably most of the time +- 10^9 of even 10^6...

Thanks a lot in advance,
Pieter

[Michel Posseth [MCP]]

Found some numbers ( needed to do some translation )

The test was with 100.000 items

compared was ArrayList, HashTable en SortedList

Arraylist was 4 times faster as the hashtable , hashtable was 8 - 100 times
faster as the sortedlist

please if you write some comparisation routines yourself then don`t forget
to set compile options in VB.Net remove overflow checks and enable
optimizations
otherwise we get again trolling messages here that C# is so much faster as
VB.Net with these options the same as they are in C# they should evaluate at
the same speed


"Pieter" <pi************ ****@hotmail.co mschreef in bericht
news:OH******** ********@TK2MSF TNGP04.phx.gbl. ..

Hi,

I need some type of array/list/... In which I can store objects together
with a unique key. The most important thing is performance: I will need to
do the whole time searches in the list of given keys. Which datastructure
will be best suited for this? A Hashtable? The list may contain upto 10^12
items, bit more proably most of the time +- 10^9 of even 10^6...

Thanks a lot in advance,
Pieter

[Jon Skeet [C# MVP]]

On Jan 16, 9:59 pm, "Michel Posseth [MCP]" <M...@posseth.c omwrote:

Found some numbers ( needed to do some translation )

The test was with 100.000 items

compared was ArrayList, HashTable en SortedList

Arraylist was 4 times faster as the hashtable , hashtable was 8 - 100 times
faster as the sortedlist

It really surprises me that you found an ArrayList faster than a
Hashtable with that many items. I could understand it for a really
small dataset, but at 100,000 a hashtable should be much faster than a
list. Could you post a link to the code?

Jon

[Marc Gravell]

Arraylist was 4 times faster as the hashtable
The other question would be: "at what, exactly?"

If the timings include the insertion time, then yes: a hash-table
(Hashtable or Dictionary<TKey ,TValue>) will take longer: it needs to
obtain hashes, build buckets, etc (an ArrayList or List<Tjust has to
copy an array a few times). But the *read* performance should then be
/significantly/ better, assuming that the items are being fetched by
key (and not by looping).

Without inspectable, reproducable code I'm going to take this with a
pinch of salt...

Marc

[Michel Posseth [MCP]]

Before anyone takes this out of perspective

1 . these tests were done by Balena not by me , however the results and code
are not annymore on the website , but i have read on a dutch website that
you can find this in his 2003 book ( i have the 2002 and 2005 version )

2 . The conclusion was that the hashtable was the fastest when values were
retrieved with the key , however a arraylist was faster when looping
through the values

"Although the statistics might tell you that the Amazone rivers average
depth is 50 cm this does not mean that you can walk to the other side"

Michel


"Marc Gravell" <ma**********@g mail.comschreef in bericht
news:%2******** ********@TK2MSF TNGP06.phx.gbl. ..

>Arraylist was 4 times faster as the hashtable

The other question would be: "at what, exactly?"

If the timings include the insertion time, then yes: a hash-table
(Hashtable or Dictionary<TKey ,TValue>) will take longer: it needs to
obtain hashes, build buckets, etc (an ArrayList or List<Tjust has to
copy an array a few times). But the *read* performance should then be
/significantly/ better, assuming that the items are being fetched by key
(and not by looping).

Without inspectable, reproducable code I'm going to take this with a pinch
of salt...

Marc

[Jon Skeet [C# MVP]]

Michel Posseth [MCP] <MS**@posseth.c omwrote:

Before anyone takes this out of perspective

1 . these tests were done by Balena not by me , however the results and code
are not annymore on the website , but i have read on a dutch website that
you can find this in his 2003 book ( i have the 2002 and 2005 version )

2 . The conclusion was that the hashtable was the fastest when values were
retrieved with the key , however a arraylist was faster when looping
through the values

Right. That makes a lot more sense. As far as I'm aware, this thread is
about looking up by key, at which point the hashtable should win
easily.

--
Jon Skeet - <sk***@pobox.co m>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
World class .NET training in the UK: http://iterativetraining.co.uk

[Michel Posseth [MCP]]

IMHO

The Hashtable will not work for the TS as the object limit in .Net = 2 GB
the hashtable way will blow up with a out of memory exception wit the
amounts the TS wants to store

so the only way that will probably work is the also in this thread proposed
database aproach

Michel


"Jon Skeet [C# MVP]" <sk***@pobox.co mschreef in bericht
news:MP******** *************@m snews.microsoft .com...

Michel Posseth [MCP] <MS**@posseth.c omwrote:

>Before anyone takes this out of perspective

1 . these tests were done by Balena not by me , however the results and
code
are not annymore on the website , but i have read on a dutch website that
you can find this in his 2003 book ( i have the 2002 and 2005
ersion )

2 . The conclusion was that the hashtable was the fastest when values
were
retrieved with the key , however a arraylist was faster when looping
through the values

Right. That makes a lot more sense. As far as I'm aware, this thread is
about looking up by key, at which point the hashtable should win
easily.

--
Jon Skeet - <sk***@pobox.co m>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
World class .NET training in the UK: http://iterativetraining.co.uk

[Bill McCarthy]

"Jon Skeet [C# MVP]" <sk***@pobox.co mwrote in message
news:1e******** *************** ***********@e23 g2000prf.google groups.com...

>
I've got a datastructure of 100 million records in memory. I probably
shouldn't say what it's for, but it basically ends up being a 10,000
squared lookup, with a single byte result.

Doing this in memory (for the low, low cost of 100M of memory) gave me
a ~100,000% performance improvement over a database lookup :)

That of course would not be a searchable datastructure, more like an indexed
array where the location is calculated by offset ;) If it was a key per
item, then each item would require at least a 4 byte key, making the in
memory size at least 500M