Solved

Faster Alternative to Hashtable

Posted on 2003-11-06
7
1,921 Views
Last Modified: 2008-02-01
I've been trying to use a Hashtable or a ListDictionary to store name/value pairs, where the value is of type "single".

Now either method works, but the problem is that I use the values in calculations, and lose a lot of performance because the Hashtable/ListDictionary stores the value as an object, and I have to convert to single before doing my calculation.

I've tried creating my own CustomHashtable that inherits from Hashtable, but that doesn't improve things because it is essentially adds strong typing on top of the existing Hashtable code, and internally still ends up converting to single.

What I think I need is a Hashtable implementation written from scratch that natively stores the values as singles. Does anyone know if any such class exists (full points to anyone who can provide such a class), or do I have to try and write one myself?

Thanks
0
Comment
Question by:akashchopra
7 Comments
 
LVL 6

Accepted Solution

by:
purpleblob earned 125 total points
ID: 9694353
An single is really a System.Single and this in turn is derived from a System.ValueType which itself is derived from good old System.Object - so basically when storing an object you are storing it's native type.

You will have to cast this object to a single anyway to get back what you want. So even if you wrote your own your stuck with the same problem, i.e. basically you're just going to cast to the single from the object yourself.

The only time this may change is when generics come into C# (I don't believe this will exist in VB.NET from what I'm aware) and this will be type safe and probably (as it's done internally) be more effient.

0
 

Assisted Solution

by:siqubal
siqubal earned 125 total points
ID: 9694382
I have created my own custom class that acts like a dictionary/collection. I did because i saw some limitation in all like SortedList, Collection, Hashtable. Here is my implementation in C#. Hope it helps

--- The Class is Called Map.CS

using System;
using System.Collections.Specialized;

namespace TestClass
{

      /// <summary>
            /// Summary description for Map.
            /// </summary>

            public class Map :  NameObjectCollectionBase
            {
                  public void Clear()
                  {
                        BaseClear();
                  }

                  public void Add(string Key, float Value)
                  {
                        BaseAdd(Key, Value);
                  }

                  public void Remove(string Key)
                  {
                        BaseRemove(Key);
                  }

                  public void RemoveAt(int Index)
                  {
                        BaseRemoveAt(Index);
                  }

                  public object ItemByIndex(int Index)
                  {
                        return (object) BaseGet(Index);
                        //get {return (object)BaseGet(Index);}
                        //set {BaseSet(Index, value);}
                  }

                  public object ItemByKey(string Key)
                  {
                        return (object)BaseGet(Key);//}
                        //set {BaseSet(Key, value);
                        //}
                  }

                  public object this[string Key]
                  {
                        get {return (object)BaseGet(Key);}
                        set {BaseSet(Key, value);}
                  }
            }

      }

-- Client Code
            Map oMap = new Map();
                  
                  for(int i=0;i<1000;i++)
                  {
                        oMap.Add(i.ToString(),i);
                  }


Let me know if this is of any help


0
 
LVL 2

Assisted Solution

by:ThePantmaster
ThePantmaster earned 125 total points
ID: 9694471
akashchopra,

Create a wrapper class for your single and add THAT class to the hashtable. When you retrieve the wrapper class, just directly access the value from it, which will never be converted. If performance is that big of an issue, just expose the Single value as a public member instead of as a property. For example:

Public Class SingleWrapper
    Public Value As Single
    Public Sub New(value as Single)
        Me.Value = value
    End Sub
End Class

Dim m as Single

mHashTable.Add New SingleWrapper(mSingle1)
m = mHashTable.Item(0).Value
0
Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

 
LVL 22

Assisted Solution

by:_TAD_
_TAD_ earned 125 total points
ID: 9694892


If you are in such dire straights, why use a hashtable at all?

why not just use a struct or create your own class and use it as an array.


You don't get to add and remove values, but it will be faster.


public struct Data
{
    public single key;
    public string value;
}



Data[] myData = new Data[100];

myData[0].key = 1.23
myData[0].value = "one-two-three";


0
 
LVL 1

Author Comment

by:akashchopra
ID: 9707126
I've been investigating this some more, and I think the man performance hit comes from accessing the value, rather than converting it from object to single.

I replaced the hashtable with a simple array of objects, and it was much faster than than using the hashtable. In other words accessing myArray(5) is significantly faster than accessing myHash("red"). The problem of course is that the code is much harder to maintain and use, and I would much prefer to access values by key rather than index.

_TAD_: you suggested using an array of structs, but I'm guessing that unless I access the array by index it will still be slow (I'll have to implement a search for the key that I want).

ThePostMaster: I tried your idea of creating a wrapper class, but accessing mHashTable.Item(0).Value (as per your example), still involves a conversion between object and SingleWrapper, and is no faster than a plain old hashtable.

siqubal: Thanks for posting your implementation,but I don't see how it is any faster than a hashtable - maybe I'm missing something?

purpleblob: thanks for explaining that - doesn't seem like a solution will be available for some time.


So, after all that, I'm still stuck. I've tries reducing the load factor of the hashtable to make it faster, but the effect is minimal.

I'm going to leave this question open for another day or two, to see if anyone else suggests anything. If not, then I'll split the points between the responses so far.

Thanks for your comments so far.
0
 
LVL 1

Author Comment

by:akashchopra
ID: 9746001
No further comments, so I've split the points between all of you. Hope you find this acceptable!

Akash
0
 
LVL 2

Expert Comment

by:ThePantmaster
ID: 9747808
Hmmm... If it's the lookup that's taking time, then you're probably out of luck. The hashtable will use a binary search, and there <i>simply ain't anything faster</i>. As a last resort, you could write your own typed hashtable and binary search from scratch, and that would get rid of the conversion issue.

Sorry I didn't comment sooner, I wasn't receiving e-mail because my mailbox was jammed full of SWEN virus e-mails.
0

Featured Post

Resolve Critical IT Incidents Fast

If your data, services or processes become compromised, your organization can suffer damage in just minutes and how fast you communicate during a major IT incident is everything. Learn how to immediately identify incidents & best practices to resolve them quickly and effectively.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Welcome my friends to the second instalment and follow-up to our Minify and Concatenate Your Scripts and Stylesheets (http://www.experts-exchange.com/Programming/Languages/.NET/ASP.NET/A_4334-Minify-and-Concatenate-Your-Scripts-and-Stylesheets.html)…
Real-time is more about the business, not the technology. In day-to-day life, to make real-time decisions like buying or investing, business needs the latest information(e.g. Gold Rate/Stock Rate). Unlike traditional days, you need not wait for a fe…
In a recent question (https://www.experts-exchange.com/questions/28997919/Pagination-in-Adobe-Acrobat.html) here at Experts Exchange, a member asked how to add page numbers to a PDF file using Adobe Acrobat XI Pro. This short video Micro Tutorial sh…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

825 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question