Hi,
If I am not sure how many items will be in my Hashtable/ArrayList
dynamically (multiple threads can add/remove/check the item), however, I can
estimate the total number will not exceed 60000. How much can I gain in term
of performance if I decalre the hash as
Hashtable h = new Hashtable(60000 );
instead of
Hashtable h = new Hashtable()
Thanks
Chris 8 3726
AFAIK Hashtables of large sizes are less useful than those of smaller
dimension because the tradeoff in accessing the keys diminishes with size.
To ensure a better access time a BTree might be the best choice. There are
several btree implementations available as source.
I've used BTrees before for things like type-ahead string searching in
dictionaries of 65000 phrases. The response times were phenomenally fast.
--
Bob Powell [MVP]
Visual C#, System.Drawing
Ramuseco Limited .NET consulting http://www.ramuseco.com
Find great Windows Forms articles in Windows Forms Tips and Tricks http://www.bobpowell.net/tipstricks.htm
Answer those GDI+ questions with the GDI+ FAQ http://www.bobpowell.net/faqmain.htm
All new articles provide code in C# and VB.NET.
Subscribe to the RSS feeds provided and never miss a new article.
"chrisben" <ch******@discu ssions.microsof t.comwrote in message
news:B6******** *************** ***********@mic rosoft.com...
Hi,
If I am not sure how many items will be in my Hashtable/ArrayList
dynamically (multiple threads can add/remove/check the item), however, I
can
estimate the total number will not exceed 60000. How much can I gain in
term
of performance if I decalre the hash as
Hashtable h = new Hashtable(60000 );
instead of
Hashtable h = new Hashtable()
Thanks
Chris
Bob Powell [MVP] <bob@_spamkille r_.bobpowell.ne twrote:
AFAIK Hashtables of large sizes are less useful than those of smaller
dimension because the tradeoff in accessing the keys diminishes with size.
To ensure a better access time a BTree might be the best choice. There are
several btree implementations available as source.
I've used BTrees before for things like type-ahead string searching in
dictionaries of 65000 phrases. The response times were phenomenally fast.
Do you have any source for that? MSDN documents key retrieval in a
hashtable as an O(1) operation. Of course, if you've got a terrible
hash function, life will be pretty terrible, but I've used large
hashtables before with no problems.
--
Jon Skeet - <sk***@pobox.co m> http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too
Bob Powell [MVP] wrote:
AFAIK Hashtables of large sizes are less useful than those of smaller
dimension because the tradeoff in accessing the keys diminishes with size.
Sorry, Bob... I don't mean to be thick, but I read that statement five
times and have no idea what it means. What "tradeoff in accessing the
keys"? Tradeoff between what and what?
In general the opposite is true. Assuming a good hash function, larger
hash tables diminish the probability of chaining, which increases
access and storage speeds. Because hash tables are statistical
beasties, even having a table larger than the expected number of items
is of benefit (although as the hash table size to item count ratio
increases, you get diminishing returns, but performance still
increases, just not as dramatically).
sorry. I think my subject is misleading. My question is more general
for a collection class, like Queue, ArrayList or Hashtable, we can declare
them either as
new Queue(1000) or
new Queue()
My understanding is that fix size declaration may provide better memoery
allocation internally, but I am not sure whehter I will really gain anything
in performance. Since whenever I declare fix size, I always start a timed
bomb in the future which may explode if my data items go beyond that size and
I forget to handle it.
I see some leftover codes with hash,queue all declared as fixed size, which
I am thinking to change it since I assume that may bring me more trouble than
benefit.
Any thoughts?
Thanks
Chris
"chrisben" wrote:
Hi,
If I am not sure how many items will be in my Hashtable/ArrayList
dynamically (multiple threads can add/remove/check the item), however, I can
estimate the total number will not exceed 60000. How much can I gain in term
of performance if I decalre the hash as
Hashtable h = new Hashtable(60000 );
instead of
Hashtable h = new Hashtable()
Thanks
Chris
In general this isn't a problem, as this is just the initial capacity,
not the limit. There are exceptions (array being the most obvious).
If you expect rougly 60000, then allowing somewhere near that number
may save it having to expand a few times (which involves re-writing the
internal structure) - but since most containers use a doubling strategy
this doesn't hurt as much as you'd think. The hashtable IIRC uses a
"double then find next prime", so it would probably get to 60k in
significantly less than the 16 shuffles that it would take for straight
doubling (from 1; I can't recall the actual default capacity).
Note the other answer re spare capacity. Not my speciality, but useful
input... I must re-cap my theory ;-p
Marc
chrisben wrote:
sorry. I think my subject is misleading. My question is more general
for a collection class, like Queue, ArrayList or Hashtable, we can declare
them either as
new Queue(1000) or
new Queue()
My understanding is that fix size declaration may provide better memoery
allocation internally, but I am not sure whehter I will really gain anything
in performance. Since whenever I declare fix size, I always start a timed
bomb in the future which may explode if my data items go beyond that size and
I forget to handle it.
I see some leftover codes with hash,queue all declared as fixed size, which
I am thinking to change it since I assume that may bring me more trouble than
benefit.
Don't confuse "initial size" with "fixed size".
None of the data structures you mentioned are "fixed size" in .NET. All
expand to accommodate new items if necessary.
The difference between specifying an initial size and not is that you
can save yourself the cost of reallocation and copying. (The only
exception is Hashtable, which works differently, but still has no
maximum... in the case of Hashtable you're really talking about storage
/ retrieval efficiency, not reallocation.)
For example, if you say
ArrayList x = new ArrayList();
and then add 1000 elements to it, your array list will start off with
some default capacity (say, 10) and then when the 11th element is added
the capacity will be increased. The standard algorithm is to double the
size on each reallocation, but I'm not sure what .NET does internally.
If you already know that you are going to have 1000 entries in the
array list, you can declare it
ArrayList x = new ArrayList(1100) ;
or something and save yourself the reallocation. (I used 1100 because
if you "know" there's going to be 1000 and there are in fact 1001 then
it would cost you a reallocation and copy to fit that last element in.
If you're just guessing you might as well use an even number like
1000.)
So, no matter what, you're never going to "hit the limit" on these data
structures. All you're doing is saving the maching a bit of extra work
reallocating and copying the data if you know that you're going to need
lots of items.
thanks
"chrisben" wrote:
sorry. I think my subject is misleading. My question is more general
for a collection class, like Queue, ArrayList or Hashtable, we can declare
them either as
new Queue(1000) or
new Queue()
My understanding is that fix size declaration may provide better memoery
allocation internally, but I am not sure whehter I will really gain anything
in performance. Since whenever I declare fix size, I always start a timed
bomb in the future which may explode if my data items go beyond that size and
I forget to handle it.
I see some leftover codes with hash,queue all declared as fixed size, which
I am thinking to change it since I assume that may bring me more trouble than
benefit.
Any thoughts?
Thanks
Chris
"chrisben" wrote:
Hi,
If I am not sure how many items will be in my Hashtable/ArrayList
dynamically (multiple threads can add/remove/check the item), however, I can
estimate the total number will not exceed 60000. How much can I gain in term
of performance if I decalre the hash as
Hashtable h = new Hashtable(60000 );
instead of
Hashtable h = new Hashtable()
Thanks
Chris
In such a case the benefit comes only if you can predict the size of
your table or list and prevent the system from resizing / reallocating
the collection.
The consideration should be for performance cost, unless you're dealing
with huge structures memory cost is negligable, and if you can predict
your needs in a performance constrained system that's good.
I suggest testing with best / worse case scenarios to provide a good
average.
--
Bob Powell [MVP]
Visual C#, System.Drawing
Ramuseco Limited .NET consulting http://www.ramuseco.com
Find great Windows Forms articles in Windows Forms Tips and Tricks http://www.bobpowell.net/tipstricks.htm
Answer those GDI+ questions with the GDI+ FAQ http://www.bobpowell.net/faqmain.htm
All new articles provide code in C# and VB.NET.
Subscribe to the RSS feeds provided and never miss a new article.
chrisben wrote:
sorry. I think my subject is misleading. My question is more general
for a collection class, like Queue, ArrayList or Hashtable, we can declare
them either as
new Queue(1000) or
new Queue()
My understanding is that fix size declaration may provide better memoery
allocation internally, but I am not sure whehter I will really gain anything
in performance. Since whenever I declare fix size, I always start a timed
bomb in the future which may explode if my data items go beyond that size and
I forget to handle it.
I see some leftover codes with hash,queue all declared as fixed size, which
I am thinking to change it since I assume that may bring me more trouble than
benefit.
Any thoughts?
Thanks
Chris
"chrisben" wrote:
>Hi,
If I am not sure how many items will be in my Hashtable/ArrayList dynamically (multiple threads can add/remove/check the item), however, I can estimate the total number will not exceed 60000. How much can I gain in term of performance if I decalre the hash as
Hashtable h = new Hashtable(60000 );
instead of
Hashtable h = new Hashtable()
Thanks
Chris
This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: SoloCDM |
last post by:
How do I keep my entire web page at a fixed width?
*********************************************************************
Signed,
SoloCDM
|
by: Linny |
last post by:
Hi,
I need some help in declaring an array of pointers to array of a
certain fixed size. I want the pointers to point to arrays of fixed
size only (should not work for variable sized arrays of the same type).
eg:
int arr1;//Array of 20 ints
int arr2;
int arr3;
............
|
by: DC |
last post by:
Hi,
I currently use a SortedList for something like this:
public class DataRow : SortedList
{
public DataRow() : base(3)
{
Add("id", (int)-1);
|
by: Manish Jain |
last post by:
Platform: C# (Windows Application)/XP/Framework 1.1
-----------------------------------------------------------
Hi
I am doing some performance checks, I am using a hashtable that I suspect is
not implemented effeciently.
Can someone tell me how I can find the size of memory occupied by the
hashTable?
|
by: Phil Jones |
last post by:
Is there a way to determine the size (number of bytes) of an object?
I figure this can be done by serializing the object to disk and measuring
the file size - but I definately don't want to do this for performance
reasons. I'm hoping there is some Framework class that dishes up the
in-memory size of an object.
Is there???
Thanks everyone....
| |
by: Ken Varn |
last post by:
I have a managed C++ assembly in which I need to interact with some 'C' APIs
that take fixed size 'C' data blocks. I need to wrap these data blocks into
a managed object. It seems like a lot of redundancy and extra code to have
to marshal .net data from managed to unmanaged for this. Is there some
built-in method in managed C++ that can allow me to create a managed
structure and convert it into a fixed size 'C' data block? I am trying...
|
by: PAzevedo |
last post by:
I have this Hashtable of Hashtables, and I'm accessing this object from
multiple threads, now the Hashtable object is thread safe for reading,
but not for writing, so I lock the object every time I need to write to
it, but now it occurred to me that maybe I could just lock one of the
Hashtables inside without locking the entire object, but then I thought
maybe some thread could instruct the outside Hashtable to remove an
inside Hashtable...
|
by: neuneudr |
last post by:
Hi everybody,
I'm scratching my head with a CSS problem.
I want to have the following (the two pics have these size for
a good reason, the whole point of the page is basically to show
these pices at these fixed sizes) :
spacer - fixed size picture - spacer - fixed size picture - spacer
|
by: Rob Hoelz |
last post by:
Hello everyone,
I'm working on a hashtable-based dictionary implementation in C, and it
uses void pointers for data storage, naturally. However, since one of
the data types I will be using it for is unsigned long -unsigned
long, I figure it'd be a better idea to just cast the unsigned longs
I'm inserted into the void pointer slots to avoid mallocs, frees, and
unnecessary deferencing. On my machine, this is fine; void * are 32
bits. ...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |