views:

336

answers:

6

Hi I class Car it has a property: string Code and 10 other.

common codes is list of strings(string[] ) cars a list of cars(Car[]) filteredListOfCars is List.

for (int index = 0; index < cars.Length; index++)
{
    Car car = cars[index];
    if (commonCodes.Contains(car.Code))
    {
         filteredListOfCars.Add(car);
    }
}

Unfortunately this piece of methodexecutes too long.

I have about 50k records

How can I lower execution time??

+20  A: 

The easiest optimization isto convert commonCodes from a string[] to a faster lookup structure such as a Dictionary<string,object> or a HashSet<string> if you are using .Net 3.5 or above. This will reduce the big O complexity of this loop and depending on the size of commonCodes should make this loop execute faster.

JaredPar
+1 for beating me to it by 30 seconds ;p
Jake
+17  A: 

Jared has correctly pointed out that you can optimize this with a HashSet, but I would also like to point out that the entire method is unnecessary, wasting memory for the output list and making the code less clear.

You could write the entire method as:

var commonCodesLookup = new HashSet<int>(commonCodes);
var filteredCars = cars.Where(c => commonCodesLookup.Contains(c.Code));

Execution of the filteredCars filtering operation will be deferred, so that if the consumer of it only wants the first 10 elements, i.e. by using filteredCars.Take(10), then this doesn't need to build the entire list (or any list at all).

Aaronaught
The Linq Join method does the lookup logic for you so that you do not have to specify the HashSet. cars.Join(commonCodes, car=>car.Code, code => code, (car, code) => car)
DRBlaise
@DRBlaise: It is true that `Join` uses a hash table, but it is also an implementation detail, and it is risky to rely on such things as they are subject to change (even if change is unlikely). If you want to guarantee a certain level of performance, then you should be explicit about the semantics.
Aaronaught
Why int? new Hash<string> isn't correct??
@phenevo: Yes, it is correct, I just didn't notice the part of your question where you said that the codes was a `string[]` and assumed it was an `int[]`. Obviously the `T` should be whatever type your `Code` is (in this case `string`).
Aaronaught
A: 

you could use the linq join command, like

var filteredListOfCars = cars.Join(commonCodes, c => c.Code, cC => cC, (car, code) => car).ToArray();
A: 

Here's an alternative to the linq options (which are also good ideas): If you're trying to do filtering quickly, I would suggest taking advantage of built in types. You could create a DataTable that has two fields, the id of the car in your array, and the code (you can add the other 10 things if they matter as well). Then you can create a DataView around it and use the filter property of that. It uses some really fast indexing internally (B-trees I believe) so you probably won't be able to beat its performance manually unless you're an algorithms whiz, which if you were, you wouldn't be asking here. It depends what you're doing and how much performance matters.

Tesserex
+1  A: 

To do what you want, I would use the Linq ToLookup method to create an ILookup instead of using a dictionary. ToLookup was made especially for this type of scenario. It is basically an indexed look up on groups. You want to group your cars by Code.

var carCodeLookup = cars.ToLookup(car => car.Code);

The creation of the carCodeLookup would be slow but then you can use it for fast lookup of cars based on Code. To get your list of cars that are in your list of common codes you can do a fast lookup.

var filteredCarsQuery = commonCodes.SelectMany(code => carCodeLookup[code]);

This assumes that your list of cars does not change very often and it is your commonCodes that are dynamic between queries.

DRBlaise
A: 

It looks like what you're really checking is whether the "code" is common, not the car. You could consider a fly weight pattern, where cars share common instances of Code objects. The code object can then have an IsCommon property and a Value property. You can then do something to the effect of updating the used Code objects whenever the commoncodes list changes. Now when you do your filtering you only need to check each car code's IsCommon property

joboy