469,303 Members | 1,967 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,303 developers. It's quick & easy.

How to build a look up table?

How to do this in C#?

I want to have a lookup table (hash) of city by zip code (integer) or
phone number (string), and it would look something like

x = book[94555]; // x == "Fremont"
x = book["510-818-8888"]; // x == "Fremont"
x = book[10002]; // x == "Manhattan"
x = book["212-966-1234"]; // x == "Manhattan"

Thanks,
P

Dec 9 '06 #1
16 32060
Podi wrote:
How to do this in C#?

I want to have a lookup table (hash) of city by zip code (integer) or
phone number (string), and it would look something like

x = book[94555]; // x == "Fremont"
x = book["510-818-8888"]; // x == "Fremont"
x = book[10002]; // x == "Manhattan"
x = book["212-966-1234"]; // x == "Manhattan"
There's a range of ways to do it.

A) book is a HashTable. You populate it like

book[94555] = "Fremont";
book["510-818-8888"] = "Fremont";

and you read it like

string x = (string) book[94555]; // x == "Fremont"
x = (string) book["510-818-8888"]; // x == "Fremont"

B) book is a Dictionary<string, object>. You populate it like

book[94555] = "Fremont";
book["510-818-8888"] = "Fremont";

and you read it like

// no cast needed
string x = book[94555]; // x == "Fremont"
x = book["510-818-8888"]; // x == "Fremont"

C) book is a Dictionary<AddressKey, object>. You populate it like

book[new AddressKey(94555)] = "Fremont";
book[new AddressKey("510-818-8888")] = "Fremont";

and you read it like

string x = book[new AddressKey(94555)]; // x == "Fremont"
x = book[new AddressKey("510-818-8888")]; // x == "Fremont"

(C) involves a lot more code, and you'll be essentially duplicating
the same logic that (A) and (B) get for free - a boxed int is never
the same as a string and all that. It is possible, however, boxed
integers don't override Equals in an efficient way, that they do a
bytewise comparison, and AddressKey.Equals might be faster. I suppose
I should do some experiments, but I doubt that (C) will be noticeably
faster.

I'd go with (B), unless I had to stick to 1.1 still.

--

..NET 2.0 for Delphi Programmers
www.midnightbeach.com/.net
What you need to know.
Dec 9 '06 #2
Hi,

Create a business object to encapsulate the data:

class City
{
// use public properties instead
public int Zip;
public string Phone;
}

It depends on whether you want increased performance or less of a memory
footprint. There's a trade-off you'll have to make there. If you're using
the 2.0 framework and want a small memory footprint at the expense of
performance (although it shouldn't really matter anyway for relatively large
sets of data, depending on how frequently searches will be performed):

class CityList
: System.Collections.ObjectModel.Collection<City>
{
public new City this[int zip]
{
get
{
foreach (City city in this)
if (city.Zip == zip)
return city;

throw new KeyNotFoundException(
"City not found with specified zip: " + zip);
}
}

public City this[string phone]
{
get
{
foreach (City city in this)
if (city.Phone == phone)
return city;

throw new KeyNotFoundException(
"City not found with specified phone: " + phone);
}
}
}

If you want to increase performance (at the expense of memory) you can
maintain two sorted indexes (List<T>) within the CityList class itself and
implement IList explicitly instead of inheriting it from Collection<T>. One
List<Tinstance could be sorted by zip and the other by phone (call the
Sort method), and in each respective indexer you could call BinarySearch
instead of iterating over every item in the collection. Any operation
performed on one list must be performed on the other as well. e.g., Clear,
Add, Insert, Remove.

--
Dave Sexton

"Podi" <po*****@gmail.comwrote in message
news:11**********************@80g2000cwy.googlegro ups.com...
How to do this in C#?

I want to have a lookup table (hash) of city by zip code (integer) or
phone number (string), and it would look something like

x = book[94555]; // x == "Fremont"
x = book["510-818-8888"]; // x == "Fremont"
x = book[10002]; // x == "Manhattan"
x = book["212-966-1234"]; // x == "Manhattan"

Thanks,
P

Dec 9 '06 #3
Hi Jon,
B) book is a Dictionary<string, object>. You populate it like
I think you mean, Dictionary<object, string:)

--
Dave Sexton

"Jon Shemitz" <jo*@midnightbeach.comwrote in message
news:45***************@midnightbeach.com...
Podi wrote:
>How to do this in C#?

I want to have a lookup table (hash) of city by zip code (integer) or
phone number (string), and it would look something like

x = book[94555]; // x == "Fremont"
x = book["510-818-8888"]; // x == "Fremont"
x = book[10002]; // x == "Manhattan"
x = book["212-966-1234"]; // x == "Manhattan"

There's a range of ways to do it.

A) book is a HashTable. You populate it like

book[94555] = "Fremont";
book["510-818-8888"] = "Fremont";

and you read it like

string x = (string) book[94555]; // x == "Fremont"
x = (string) book["510-818-8888"]; // x == "Fremont"

B) book is a Dictionary<string, object>. You populate it like

book[94555] = "Fremont";
book["510-818-8888"] = "Fremont";

and you read it like

// no cast needed
string x = book[94555]; // x == "Fremont"
x = book["510-818-8888"]; // x == "Fremont"

C) book is a Dictionary<AddressKey, object>. You populate it like

book[new AddressKey(94555)] = "Fremont";
book[new AddressKey("510-818-8888")] = "Fremont";

and you read it like

string x = book[new AddressKey(94555)]; // x == "Fremont"
x = book[new AddressKey("510-818-8888")]; // x == "Fremont"

(C) involves a lot more code, and you'll be essentially duplicating
the same logic that (A) and (B) get for free - a boxed int is never
the same as a string and all that. It is possible, however, boxed
integers don't override Equals in an efficient way, that they do a
bytewise comparison, and AddressKey.Equals might be faster. I suppose
I should do some experiments, but I doubt that (C) will be noticeably
faster.

I'd go with (B), unless I had to stick to 1.1 still.

--

.NET 2.0 for Delphi Programmers
www.midnightbeach.com/.net
What you need to know.

Dec 9 '06 #4
Hi,

Actually, I like Jon's solutions better, although adding a business object
to encapsulate "City" might not be such a bad idea :)

--
Dave Sexton

"Dave Sexton" <dave@jwa[remove.this]online.comwrote in message
news:uS**************@TK2MSFTNGP03.phx.gbl...
Hi,

Create a business object to encapsulate the data:

class City
{
// use public properties instead
public int Zip;
public string Phone;
}

It depends on whether you want increased performance or less of a memory
footprint. There's a trade-off you'll have to make there. If you're
using the 2.0 framework and want a small memory footprint at the expense
of performance (although it shouldn't really matter anyway for relatively
large sets of data, depending on how frequently searches will be
performed):

class CityList
: System.Collections.ObjectModel.Collection<City>
{
public new City this[int zip]
{
get
{
foreach (City city in this)
if (city.Zip == zip)
return city;

throw new KeyNotFoundException(
"City not found with specified zip: " + zip);
}
}

public City this[string phone]
{
get
{
foreach (City city in this)
if (city.Phone == phone)
return city;

throw new KeyNotFoundException(
"City not found with specified phone: " + phone);
}
}
}

If you want to increase performance (at the expense of memory) you can
maintain two sorted indexes (List<T>) within the CityList class itself and
implement IList explicitly instead of inheriting it from Collection<T>.
One List<Tinstance could be sorted by zip and the other by phone (call
the Sort method), and in each respective indexer you could call
BinarySearch instead of iterating over every item in the collection. Any
operation performed on one list must be performed on the other as well.
e.g., Clear, Add, Insert, Remove.

--
Dave Sexton

"Podi" <po*****@gmail.comwrote in message
news:11**********************@80g2000cwy.googlegro ups.com...
>How to do this in C#?

I want to have a lookup table (hash) of city by zip code (integer) or
phone number (string), and it would look something like

x = book[94555]; // x == "Fremont"
x = book["510-818-8888"]; // x == "Fremont"
x = book[10002]; // x == "Manhattan"
x = book["212-966-1234"]; // x == "Manhattan"

Thanks,
P


Dec 9 '06 #5
Dave Sexton wrote:
B) book is a Dictionary<string, object>. You populate it like

I think you mean, Dictionary<object, string:)
Not again!

OK, time to volunteer for Soylent Green conversion.

--

..NET 2.0 for Delphi Programmers
www.midnightbeach.com/.net
What you need to know.
Dec 9 '06 #6
Prodi,

I like the often missed sortedlist for this.

http://msdn.microsoft.com/library/de...classtopic.asp

Cor

"Podi" <po*****@gmail.comschreef in bericht
news:11**********************@80g2000cwy.googlegro ups.com...
How to do this in C#?

I want to have a lookup table (hash) of city by zip code (integer) or
phone number (string), and it would look something like

x = book[94555]; // x == "Fremont"
x = book["510-818-8888"]; // x == "Fremont"
x = book[10002]; // x == "Manhattan"
x = book["212-966-1234"]; // x == "Manhattan"

Thanks,
P

Dec 9 '06 #7
Dave Sexton wrote:
Hi,

Actually, I like Jon's solutions better, although adding a business object
to encapsulate "City" might not be such a bad idea :)
Thanks to all for the suggestions.

The simple HashTable is nice and clean.

I now have some new requirements such as the look up table takes other
objects as keys. Two classes are added:

class Person
{ // Implementation details not shown
};

class Company
{ // Implementation details not shown
};

Person me = new Person();
Person myFriend = new Person();

Company csco = new Company();
Company intc = new Company();

// Is this possible? Preferrablly without change any existing code.
book[me] = "Milpitas";
book[myFriend] = "Sunnyvale";
book[csco] = "San Jose";
book[intc] = "Santa Clara";

Dec 11 '06 #8
Podi wrote:
Thanks to all for the suggestions.

The simple HashTable is nice and clean.
Imho, the Dictionary<object, stringis a lot cleaner - no need to
cast the result every time you read a value.
I now have some new requirements such as the look up table takes other
objects as keys. Two classes are added:

class Person
{ // Implementation details not shown
};

class Company
{ // Implementation details not shown
};

Person me = new Person();
Person myFriend = new Person();

Company csco = new Company();
Company intc = new Company();

// Is this possible? Preferrablly without change any existing code.
book[me] = "Milpitas";
book[myFriend] = "Sunnyvale";
book[csco] = "San Jose";
book[intc] = "Santa Clara";
Of course. Just be sure that the classes you use as keys override
GetHashCode and Equals.

--

..NET 2.0 for Delphi Programmers
www.midnightbeach.com/.net
What you need to know.
Dec 11 '06 #9
Cor,

You don't think a Hashtable or Dictionary<TKey, TValuewould be better
in this case?

Brian

Cor Ligthert [MVP] wrote:
Prodi,

I like the often missed sortedlist for this.

http://msdn.microsoft.com/library/de...classtopic.asp

Cor
Dec 11 '06 #10
Hi Jon,
Of course. Just be sure that the classes you use as keys override
GetHashCode and Equals.
Actually, I would recommend that the OP doesn't override either. It would
be acceptable if Equals is required for certain business logic, in which
case a struct should be considered instead (although it isn't entirely
necessary to use a structure just to override Equals). The reason for this
is simple: when I see a class I think "reference". If I didn't know that
Equals and GetHashCode were overridden, which is the not usually the case
for classes, then I would assume reference equality (which is an object's
framework-assigned "value"), and therefore might see some unexpected results
when using either class to key a Hashtable.

It's better to not assign a "value" to a class unless it's absolutely
required, and even then it should be well documented, IMO.

--
Dave Sexton

"Jon Shemitz" <jo*@midnightbeach.comwrote in message
news:45***************@midnightbeach.com...
Podi wrote:
>Thanks to all for the suggestions.

The simple HashTable is nice and clean.

Imho, the Dictionary<object, stringis a lot cleaner - no need to
cast the result every time you read a value.
>I now have some new requirements such as the look up table takes other
objects as keys. Two classes are added:

class Person
{ // Implementation details not shown
};

class Company
{ // Implementation details not shown
};

Person me = new Person();
Person myFriend = new Person();

Company csco = new Company();
Company intc = new Company();

// Is this possible? Preferrablly without change any existing code.
book[me] = "Milpitas";
book[myFriend] = "Sunnyvale";
book[csco] = "San Jose";
book[intc] = "Santa Clara";

Of course. Just be sure that the classes you use as keys override
GetHashCode and Equals.

--

.NET 2.0 for Delphi Programmers
www.midnightbeach.com/.net
What you need to know.

Dec 11 '06 #11
Hi Brian,

Actually, a SortedList will use a BinarySearch when setting a key, so it may
help to increase performance (although I'd recommend the generic SortedList
instead).

The current solution that the OP has posted uses classes instead of strings
and ints as keys, so a SortedList might not be appropriate anymore unless
the OP is willing to assign value-type semantics to the classes (I've
addressed this in response to Jon Shemtiz's latest post to this thread)

--
Dave Sexton

"Brian Gideon" <br*********@yahoo.comwrote in message
news:11*********************@79g2000cws.googlegrou ps.com...
Cor,

You don't think a Hashtable or Dictionary<TKey, TValuewould be better
in this case?

Brian

Cor Ligthert [MVP] wrote:
>Prodi,

I like the often missed sortedlist for this.

http://msdn.microsoft.com/library/de...classtopic.asp

Cor

Dec 11 '06 #12
Hi,

Ok, I rethought my last comment and I've come up with the following (I'm
still trying to get my head around the different sorting algorithms and
their performance):

I realize now that Dictionary will most likely provide better performance
over SortedList since the distribution of keys will most likely be good
(even though there is a chance for some collisions since the OP was
originally using strings and ints as keys). When the number of elements is
small it really doesn't matter either way, but as the number of elements
grows I believe that Hashtable will out-perform SortedList as long as the
number of collisions remains low. Sound good? :)

--
Dave Sexton

"Dave Sexton" <dave@jwa[remove.this]online.comwrote in message
news:uF**************@TK2MSFTNGP06.phx.gbl...
Hi Brian,

Actually, a SortedList will use a BinarySearch when setting a key, so it
may help to increase performance (although I'd recommend the generic
SortedList instead).

The current solution that the OP has posted uses classes instead of
strings and ints as keys, so a SortedList might not be appropriate anymore
unless the OP is willing to assign value-type semantics to the classes
(I've addressed this in response to Jon Shemtiz's latest post to this
thread)

--
Dave Sexton

"Brian Gideon" <br*********@yahoo.comwrote in message
news:11*********************@79g2000cws.googlegrou ps.com...
>Cor,

You don't think a Hashtable or Dictionary<TKey, TValuewould be better
in this case?

Brian

Cor Ligthert [MVP] wrote:
>>Prodi,

I like the often missed sortedlist for this.

http://msdn.microsoft.com/library/de...classtopic.asp

Cor


Dec 11 '06 #13

Dave Sexton wrote:
Hi Brian,

Actually, a SortedList will use a BinarySearch when setting a key, so it may
help to increase performance (although I'd recommend the generic SortedList
instead).
If the key already exists then the data structure will use a binary
search to find and replace the value. If the key does not exist then
it will use a binary search to find the insertion point and then
recreate its internal array by copying all existing items around the
new item. So the worst case complexity for setting a key is O(n) as
opposed to a hashtable's O(1).

I've said this before. I dislike the SortedList collection. I
especially dislike it now that Microsoft included the SortedDictionary
which uses a superior algorithm. Yeah, I know the SortedList uses less
memory than the SortedDictionary and that (supposedly) is its
advantage. But it's only by a marginal constant factor; not to mention
that it temporarily doubles when a resize occurs. The speed
improvement of an insertion on a SortedDictionary is an order of
magnitude faster. Obviously, I question why the SortedDictionary
appeared after the SortedList.

Dec 11 '06 #14

Dave Sexton wrote:
Hi,

Ok, I rethought my last comment and I've come up with the following (I'm
still trying to get my head around the different sorting algorithms and
their performance):

I realize now that Dictionary will most likely provide better performance
over SortedList since the distribution of keys will most likely be good
(even though there is a chance for some collisions since the OP was
originally using strings and ints as keys). When the number of elements is
small it really doesn't matter either way, but as the number of elements
grows I believe that Hashtable will out-perform SortedList as long as the
number of collisions remains low. Sound good? :)

--
Yes, that does sound good :)

Dec 11 '06 #15
Dave Sexton wrote:
Of course. Just be sure that the classes you use as keys override
GetHashCode and Equals.

Actually, I would recommend that the OP doesn't override either. It would
be acceptable if Equals is required for certain business logic, in which
case a struct should be considered instead (although it isn't entirely
necessary to use a structure just to override Equals). The reason for this
is simple: when I see a class I think "reference". If I didn't know that
Equals and GetHashCode were overridden, which is the not usually the case
for classes, then I would assume reference equality (which is an object's
framework-assigned "value"), and therefore might see some unexpected results
when using either class to key a Hashtable.

It's better to not assign a "value" to a class unless it's absolutely
required, and even then it should be well documented, IMO.
Good point. The decision the OP needs to make is whether one Company
instance should ever be the same as another Company instance for the
purposes of hashtable lookup.

For example, "this" == "this.string".Substring(0, 4), even though the
two are NOT reference equal. Similarly, object(11) == object(11), even
though the two boxed integers are not reference equal.

Conversely, new Regex(".*") != new Regex(".*"), even though the two
are field-for-field equal.

--

..NET 2.0 for Delphi Programmers
www.midnightbeach.com/.net
What you need to know.
Dec 11 '06 #16
Hi Brian,

Interesting, thanks.

--
Dave Sexton

"Brian Gideon" <br*********@yahoo.comwrote in message
news:11*********************@16g2000cwy.googlegrou ps.com...
>
Dave Sexton wrote:
>Hi Brian,

Actually, a SortedList will use a BinarySearch when setting a key, so it
may
help to increase performance (although I'd recommend the generic
SortedList
instead).

If the key already exists then the data structure will use a binary
search to find and replace the value. If the key does not exist then
it will use a binary search to find the insertion point and then
recreate its internal array by copying all existing items around the
new item. So the worst case complexity for setting a key is O(n) as
opposed to a hashtable's O(1).

I've said this before. I dislike the SortedList collection. I
especially dislike it now that Microsoft included the SortedDictionary
which uses a superior algorithm. Yeah, I know the SortedList uses less
memory than the SortedDictionary and that (supposedly) is its
advantage. But it's only by a marginal constant factor; not to mention
that it temporarily doubles when a resize occurs. The speed
improvement of an insertion on a SortedDictionary is an order of
magnitude faster. Obviously, I question why the SortedDictionary
appeared after the SortedList.

Dec 11 '06 #17

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

2 posts views Thread by Jeremy Ross | last post: by
5 posts views Thread by john_williams_800 | last post: by
2 posts views Thread by Stanley Sinclair | last post: by
15 posts views Thread by kimi | last post: by
reply views Thread by Mark Rae [MVP] | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by suresh191 | last post: by
1 post views Thread by Geralt96 | last post: by
reply views Thread by harlem98 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.