Collection Types

[jwilson128]

I am looking for some help on the best type of collection to use and/
or best way to implement the collection with the following
functionality:

I have defined an object to represent an interest rate:
Public Class IRFcast
Public CloseDate As Date
Public RateIndex As String
Public RateClose As Double
End Class

I would like to define a collection of these interest rate objects
(there could be a large number of them - tens of thousands) such that
they can be quickly searched on a CloseDate and RateIndex combination.
Furthermore, I need to implement a search that will return (again, as
quickly as possible) the IRFcast object with a RateIndex=the searched
RateIndex and the maximum CloseDate<=the searched CloseDate.

Any suggestions on the best path to pursue here would be much
appreciated.

 

[Tom Shelton]

I am looking for some help on the best type of collection to use and/
or best way to implement the collection with the following
functionality:

I have defined an object to represent an interest rate:
Public Class IRFcast
Public CloseDate As Date
Public RateIndex As String
Public RateClose As Double
End Class

I would like to define a collection of these interest rate objects
(there could be a large number of them - tens of thousands) such that
they can be quickly searched on a CloseDate and RateIndex combination.
Furthermore, I need to implement a search that will return (again, as
quickly as possible) the IRFcast object with a RateIndex=the searched
RateIndex and the maximum CloseDate<=the searched CloseDate.

Any suggestions on the best path to pursue here would be much
appreciated.

As far as lists go, I would use List(Of T). It has search functions
like find and findall, etc that take delegates that can aid in your
search. Since you seem to want to define multiple search criteria....

But, I have to ask, might it not be more effiecient to store these in
a db and then use a query to get at the ones you need? Just a
thought.

 

[Brian Gideon]

I am looking for some help on the best type of collection to use and/
or best way to implement the collection with the following
functionality:

I have defined an object to represent an interest rate:
Public Class IRFcast
Public CloseDate As Date
Public RateIndex As String
Public RateClose As Double
End Class

I would like to define a collection of these interest rate objects
(there could be a large number of them - tens of thousands) such that
they can be quickly searched on a CloseDate and RateIndex combination.
Furthermore, I need to implement a search that will return (again, as
quickly as possible) the IRFcast object with a RateIndex=the searched
RateIndex and the maximum CloseDate<=the searched CloseDate.

Any suggestions on the best path to pursue here would be much
appreciated.

Hi,

I'm assuming that CloseDate and RateIndex can uniquely identify an
IRFcast object. Write a custom collection that internally uses two
hashtables (Dictionary<Of T> or Hashtable). We'll call them A and B.
The first hashtable (A) will cross reference a combination the
CloseDate and RateIndex fields to an IRFcast object. The second
hashtable (B) will cross reference the RateIndex field to a sorted
list (SortedList, SortedList<Of T>, or an array that is manually
sorted) of IRFcast objects with the same RateIndex field.

The first search use case can be done by using hashtable A. It is a
O(1) operation.

The second search use case can be done by using hashtable B to locate
the sorted list of IRFcast objects of like RateIndex and then doing a
binary search on that list. That is a O(log(n')) average case
operation where n' is the average distribution of IRFcast objects to a
RateIndex.

Brian

 

[jwilson128]

Brian - thanks for the info. A couple follow-up questions:

1) does this mean storing all of the IRFcast objects twice (once for
each use case). I'm assuming that I would just think about the
tradeoff in storing the info twice vs the performance benefit of
accessing an object quicker?

2) when doing the suggested binary search on IRFcast objects with like
RateIndex, is there a better way to do it than to cycle through the
list? something comparable to the SQL logic of SELECT MAX(closedate)
WHERE closedate<=search date?

-Jeff

 

[Brian Gideon]

Brian - thanks for the info. A couple follow-up questions:

1) does this mean storing all of the IRFcast objects twice (once for
each use case). I'm assuming that I would just think about the
tradeoff in storing the info twice vs the performance benefit of
accessing an object quicker?

Well, you're not exactly storing the IRFcast objects twice. You're
storing the references to those objects twice. But, yeah, that's
basically true. You just need to determine if the memory trade off is
worth it.

2) when doing the suggested binary search on IRFcast objects with like
RateIndex, is there a better way to do it than to cycle through the
list? something comparable to the SQL logic of SELECT MAX(closedate)
WHERE closedate<=search date?

Not really. LINQ promises to offer this kind of SQL-like syntax, but
you'll have to wait since it's not available in VB 2005. I'm afraid
you'll have to implement your own binary search. It's really not that
difficult though. If you're not comfortable with the binary search
then you could always traverse the sorted list (or array) from the
tail one at a time to find the correct object. It would be slower,
but simpler.

 

[=?ISO-8859-1?Q?G=F6ran_Andersson?=]

2) when doing the suggested binary search on IRFcast objects with like
RateIndex, is there a better way to do it than to cycle through the
list? something comparable to the SQL logic of SELECT MAX(closedate)
WHERE closedate<=search date?

You don't have to loop through the list. Using a binary seach means that
you use the fact that the list is sorted to rule out half of the list
for each comparison that you do. Finding a value in a list of 1000 items
can be done with just ten comparisons.

http://en.wikipedia.org/wiki/Binary_search_algorithm