Fast Searches of a Thread Safe Collection of Structs

[Jeff S.]

In a Windows Forms application I plan to have a collection of structs - each
of which contains a bunch of properties describing a person (e.g., LastName,
FirstName, EmployeeID, HomeAddress, ZipCode, etc). So each instance of the
struct will describe a person - and about 900 instances (people) will be
contained in the collection.

Users must be able to search for a specific person by any of the properties
(e.g., LastName, FirstName, EmployeeID, HomeAddress, ZipCode, etc). So the
collection must be searchable by all of the properties of the contained
struct instances.

Please note that the comparison will be between (1) a string the user is
typing into a textbox, and (2) the specified property (e.g., LastName) --
such that AS the user types, a list displayed elsewhere on the form will
dynamically show ALL of the closest matches (closest to the string the user
is typing AS the user types).

The collection will periodically be updated on a background thread (every 15
or so minutes) - so the collection must be "thread safe."

MY QUESTIONS:
1. How do I make the collection of structs searchable by *each* of its
properties (LastName, FirstName, Zip, etc...). Of course only one property
at a time would be searched on. I would think implementing IComparable would
work - but apparently doing so would let me enable searching on only one of
the properties (but I need to enable searching on ALL of the properties).

2. How do I make the collection "thread safe" so that the collection can be
updated by a background thread while users may be searching for a person in
the collection. Note: people [in the collection] will almost never be
deleted - so phantom matches are not really a concern.

Just looking for high-level direction on this.

Thank you very much!

 

[William Stacey [MVP]]

Lock the list during reads and writes. Use List<struct> and Find() using
different Predicate delegates for your different search needs.

--
William Stacey [MVP]

| In a Windows Forms application I plan to have a collection of structs -
each
| of which contains a bunch of properties describing a person (e.g.,
LastName,
| FirstName, EmployeeID, HomeAddress, ZipCode, etc). So each instance of the
| struct will describe a person - and about 900 instances (people) will be
| contained in the collection.
|
| Users must be able to search for a specific person by any of the
properties
| (e.g., LastName, FirstName, EmployeeID, HomeAddress, ZipCode, etc). So the
| collection must be searchable by all of the properties of the contained
| struct instances.
|
| Please note that the comparison will be between (1) a string the user is
| typing into a textbox, and (2) the specified property (e.g., LastName) --
| such that AS the user types, a list displayed elsewhere on the form will
| dynamically show ALL of the closest matches (closest to the string the
user
| is typing AS the user types).
|
| The collection will periodically be updated on a background thread (every
15
| or so minutes) - so the collection must be "thread safe."
|
| MY QUESTIONS:
| 1. How do I make the collection of structs searchable by *each* of its
| properties (LastName, FirstName, Zip, etc...). Of course only one property
| at a time would be searched on. I would think implementing IComparable
would
| work - but apparently doing so would let me enable searching on only one
of
| the properties (but I need to enable searching on ALL of the properties).
|
| 2. How do I make the collection "thread safe" so that the collection can
be
| updated by a background thread while users may be searching for a person
in
| the collection. Note: people [in the collection] will almost never be
| deleted - so phantom matches are not really a concern.
|
| Just looking for high-level direction on this.
|
| Thank you very much!
|
|
|
|

 

[Nick Hounsome]

And you almost certainly shouldn't be using use structs for a Person class.

Your post talks about the string that the person is "typing" into a box -
this sounds like an incremental search to me - if so you would need to sort
the list for the particular property instead of using predicates.

 

[Jeff S.]

Thanks William... can you expand just a bit? I'm not clear on [... Predicate
delegates... ].

-Jeff

 

[Jon Skeet [C# MVP]]

Thanks William... can you expand just a bit? I'm not clear on [... Predicate
delegates... ].

Just to check before too much detail is gone into - are you using .NET
2.0 or 1.1? You won't be able to use List<T> if you're only using 1.1.

Also, do you *have* to use structs? Why are you using structs rather
than classes?

 

[Jeff S.]

RE:
<< are you using 2.0 or 1.1?>>
I could develop in either. Preference is for 2.0 although preliminary work
has been done in 1.1 (I'll be migrating soon and this particular issue may
cause me to go to 2.0 immediately)... This also means I haven't used
generics yet and I haven't done any non trivial work yet in 2.0.

RE:
<<do you *have* to use structs? Why are you using structs rather than
classes?>>
I was using structs simply because they are lighter weight than classes. All
I really need here is "a bunch of properties that identify a person" and my
thinking was that a struct would be sufficient. That's all. I could just as
easily implement with classes or ?? (this thing is still in the design phase
and I haven't written much code for it yet.

Thanks!

Thanks William... can you expand just a bit? I'm not clear on [...
Predicate
delegates... ].

Just to check before too much detail is gone into - are you using .NET
2.0 or 1.1? You won't be able to use List<T> if you're only using 1.1.

Also, do you *have* to use structs? Why are you using structs rather
than classes?

 

[Jon Skeet [C# MVP]]

RE:
<< are you using 2.0 or 1.1?>>
I could develop in either. Preference is for 2.0 although preliminary work
has been done in 1.1 (I'll be migrating soon and this particular issue may
cause me to go to 2.0 immediately)... This also means I haven't used
generics yet and I haven't done any non trivial work yet in 2.0.

Using generics in .NET 2.0 would mean you could avoid boxing
performance overheads using generic collections, if you do end up using
a value type.

RE:
<<do you *have* to use structs? Why are you using structs rather than
classes?>>
I was using structs simply because they are lighter weight than classes.

Actually, they're often heavier. Any time you're passing round a struct
which has more than a few properties, that's going to heavier than
using a class. Value types can often be harder to work with, too.

All I really need here is "a bunch of properties that identify a
person" and my thinking was that a struct would be sufficient. That's
all. I could just as easily implement with classes or ?? (this thing
is still in the design phase and I haven't written much code for it
yet.

I *strongly* suggest that you learn more about .NET and C# before going
any further. A decent understanding of the difference between value
types and reference types is absolutely crucial to programming in .NET,
for a start.

 

[Jeff S.]

RE:
<< I *strongly* suggest that you learn more about .NET and C# before going
any further>>
I *certainly* agree with you that I should learn more about .NET - but your
recommendation is so vague as to be not helpful. My OP was specifically NOT
asking for code samples or otherwise for others to do my work BECAUSE I was
wanting high-level guidance that would help me to focus my learning in a way
that is relevant to the current project. That's how a lot of learning
happens - I'm sure you've likely done the same many times over your career.

The response by William Stacey was pretty much the sort of guidance I was
looking for - but I was just wanting a little bit more, like what a
Predicate delegate is. Before I asked him to clarify I googled it and found
nothing apparently relevant... then went to my 3.0 books and didn't find
anything helpful... thus my followup post. I know what a delegates is - just
not sure of the "Predicate" delegate part of his recommendation. I hope that
doesn't make me too dumb to be helped.

-Jeff

 

[Jon Skeet [C# MVP]]

<< I *strongly* suggest that you learn more about .NET and C# before going
any further>>
I *certainly* agree with you that I should learn more about .NET - but your
recommendation is so vague as to be not helpful.

Okay, here's a more concrete recommendation: read a book or tutorial
about C# and .NET which starts from a beginner's perspective. Pay close
attention to chapters which describe the differences between value
types and reference types, and parameter passing, too.

My OP was specifically NOT
asking for code samples or otherwise for others to do my work BECAUSE I was
wanting high-level guidance that would help me to focus my learning in a way
that is relevant to the current project. That's how a lot of learning
happens - I'm sure you've likely done the same many times over your career.

Well, I usually haven't tried to embark on a real-life project without
a reasonable understanding of the basics of what I'm using. It's fine
to use projects to learn, but I wouldn't try it with a real world
production project, which I assumed your question was about (given the
very specific nature of it). Threading is a relatively advanced topic,
for instance - so one would hope that someone asking a question
involving threading (as yours did) would have a good grounding in the
basics.

The response by William Stacey was pretty much the sort of guidance I was
looking for - but I was just wanting a little bit more, like what a
Predicate delegate is. Before I asked him to clarify I googled it and found
nothing apparently relevant... then went to my 3.0 books and didn't find
anything helpful... thus my followup post. I know what a delegates is - just
not sure of the "Predicate" delegate part of his recommendation. I hope that
doesn't make me too dumb to be helped.

You're not too dumb to be helped at all - but without a good
understanding of the fundamentals of the framework, I don't think it's
a good idea to continue with a real project.

Put it this way - asking about delegates without understanding value
types is a bit like someone asking for good examples of the subjunctive
mood without understanding the difference between a verb and a noun. I
*could* give you examples of implementing predicates using anonymous
methods etc, but the chances of you properly understanding those
examples without a sound knowledge of the basics are very slim. In
short, I don't think it would be helpful in the long run.

 

[William Stacey [MVP]]

Do you have the MSDN help installed? Look in the List<T>.Find method help.
What version of VS are you using?

 

[Nick Hounsome]

I agree with Jon for this reason - if you get an example of how to do the
sort you will be doing ONE thing right (and even then you could have done it
the hard way - it would just be slower) but if you if you continue to
misunderstand when it is appropriate to use a struct you will be doing MANY
things wrong and they will manifest themselves throughout your as they will
be used in multiple places whereas the sorting is only done in a single
method.

 

[Bruce Wood]

I was using structs simply because they are lighter weight than classes.

I will add my voice to the chorus: use classes not structs in this
case. There are occasions when it is appropriate to use structs instead
of classes "...because they are lighter weight..." but these occasions
are very, very rare indeed. The perception that structs are nothing
more than "classes lite" is just dead wrong. Fortunately, most new
programmers who insist on forging ahead with structs find this out "the
hard way." Unfortunately some of them then conclude that C# is junk,
rather than realizing that failing at pounding in a nail with a
screwdriver does not mean that screwdrivers are useless.

Users must be able to search for a specific person by any of the properties (e.g., LastName, FirstName, EmployeeID, HomeAddress, ZipCode, etc).

I would approach this as follows.

Check into the Comparer class and the IComparer interface that it
implements. These would allow you to write generic searching code that
takes a Comparer and a Person as its arguments and finds the Person or
Persons from the list that "compare equal" to the given Person based on
the results of your particular Comparer. This also allows you to search
based on any combination of the given properties in one simple
operation, simply by varying the Comparer.

You could also build more sophisticated Comparers that allow for
wildcard searches, "LIKE" searches, and other things like that.

Whatever you eventually decide to do, make Person a class. If you want
to know exactly why, try searching this newsgroup for "struct vs class"
or words to that effect. The topic comes up often here, frequently
raised by frustrated programmers who don't understand why C# is acting
so weird.

 

[John Parrish]

Just a quick thought, but have you looked at the ADO classes for
performance, vs. a struct that implement IComparable? With what you are
describing as a disconnected data source, the filter expressions should
make the overall task easier, but I don't know what if any implications
it would have as far as thread locking is concerned.

I have been impressed with ADO.NET's performance in scenarios like this.
Worth checking I supposed. Let us know what you find.

Regards

John Parrish

 

[John Parrish]

Careful on the attitude.. the line between berating and mentoring might
seem fine, but it never is to the recipient of either. While I agree
with your sentiments, I think as an MVP you might do a better job at
encouragement. Perhaps spend a little more time explaining, otherwise,
perhaps not say anything at all.

 

[Jon Skeet [C# MVP]]

Careful on the attitude.. the line between berating and mentoring might
seem fine, but it never is to the recipient of either. While I agree
with your sentiments, I think as an MVP you might do a better job at
encouragement. Perhaps spend a little more time explaining, otherwise,
perhaps not say anything at all.

If the OP shows some interest in really learning the differences
between value types and reference types, I'll be very happy to help.
However, I believe that explaining something advanced when we *know*
the basics are missing is a bad idea - in my experience it only leads
to more questions which could easily be avoided by learning those
basics first. I've seen it time and time again in newsgroups (it was
worse on the Java ones).

I dare say I could have expressed it better though...