How to optimize this code

Question

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??

Answer 1

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.

Answer 2

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).

Answer 3

you could use the linq join command, like

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

Answer 4

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.

Answer 5

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.

Answer 6

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