How to build a look up table?

[Podi]

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

 

[Jon Shemitz]

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.

 

[Dave Sexton]

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<T> instance 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]

Hi Jon,

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

I think you mean, Dictionary<object, string>

--
Dave Sexton

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.

 

[Dave Sexton]

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

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<T> instance 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

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

 

[Jon Shemitz]

I think you mean, Dictionary<object, string>

Not again!

OK, time to volunteer for Soylent Green conversion.

 

[Cor Ligthert [MVP]]

Prodi,

I like the often missed sortedlist for this.

http://msdn.microsoft.com/library/d...rlrfsystemcollectionssortedlistclasstopic.asp

Cor

 

[Podi]

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";

 

[Jon Shemitz]

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";

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

 

[Brian Gideon]

Cor,

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

Brian

 

[Dave Sexton]

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

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";

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.

 

[Dave Sexton]

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]

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?

 

[Brian Gideon]

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.

 

[Brian Gideon]

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

 

[Jon Shemitz]

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.

 

[Dave Sexton]

Hi Brian,

Interesting, thanks.

--
Dave Sexton

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.