473,225 Members | 1,316 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,225 software developers and data experts.

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 32312
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Jeremy Ross | last post by:
Hello, I am looking for a function that will build a mysql table with the results of a query. If you could help that would be great, Thanks, Jeremy Ross
5
by: john_williams_800 | last post by:
Hi; I am just starting to use the DOM to do some more advanced javascripting so please be patient with my question if it is an ignorant question. I would like to use the DOM to dynamically...
1
by: CD | last post by:
I would like some guidance as to how to proceed to build a webpage in asp or aspx. I am going to hit a SQL db needing to get the following data: SELECT ServerName,PrimaryTech FROM tblservers...
2
by: Stanley Sinclair | last post by:
About to create a table which will "include" a BLOB. Am not sure how large to make the container and the tablespace. What I see says that BLOB is stored "separately." However, I don't know...
15
by: kimi | last post by:
I have just started working on a project that is partially complete. It is an application that is using access to store test results. The test results are being stored in two Access 2000 databases....
3
by: John | last post by:
Hi, I need to build a BAUDOT lookup table for an encoder. I see to use a char as the index 'A' or 'B' and get back an array of booleans (five elements long). Baudot = {00011} Baudot =...
7
by: rcamarda | last post by:
I wish to build a table based on values from another table. I need to populate a table between two dates from another table. Using the START_DT and END_DT, create records between those dates. I...
2
by: Alien Clone | last post by:
I am using the following code within an Access database to retrieve data from Oracle and build a local table within the Access database. DoCmd.RunSQL "Select Field1, Field2, " _ & "'' as...
0
by: Mark Rae [MVP] | last post by:
"egsdar" <egsdar@discussions.microsoft.comwrote in message news:6A834615-9B38-4129-931B-9C9114682E26@microsoft.com... OK, first things first: ASP.NET is *TOTALLY DIFFERENT* from ASP Classic. If...
2
by: samvb | last post by:
Hi, From a database, I need to build a dynamic table that looks like this: ITEM1 ITEM2 ITEM3 ITEM4 ITEM5 ITEM6 It is dynamic. Sometimes only there could be 1 item or more than 4 items. I...
1
isladogs
by: isladogs | last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike...
0
by: veera ravala | last post by:
ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: mar23 | last post by:
Here's the situation. I have a form called frmDiceInventory with subform called subfrmDice. The subform's control source is linked to a query called qryDiceInventory. I've been trying to pick up the...
2
by: jimatqsi | last post by:
The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.