CODEWITHSUNDEEP
c#linqlistviewwindows-runtime
Arn Vanhoutte
Arn Vanhoutte

Reputation: 1927

Performant search in listview

I am using Linq to search and show a specific string in a ListView on WinRT (Windows Phone 8.1). This is my current method:

string value = (string) sender.Text.ToLower();
if (value == "")
{
    AirportsList.ItemsSource = _airports.CountryList;
}
else
{
    List<Airport> queryList = _airports.AirportList
        .Where(airport => airport.IcaoId.ToLower().Contains(value) 
                      || airport.IcaoName.ToLower().Contains(value) 
                      || airport.City.ToLower().Contains(value) 
                      || airport.Country.ToLower().Contains(value)).ToList();
    AirportsList.ItemsSource = queryList.ToList();
}

This is quite slow and laggy since it has to create the itemssource each time. Is there a more performant way of doing it?

Upvotes: 0

Views: 174

Answers (1)

Adam Kewley
Adam Kewley

Reputation: 1234

I imagine creating the queryList isn't necessarily the slow part. That's just a List<Airport>, a class any hardware will capably instantiate with minimal overhead. I imagine the slow part is having to check your value against four different properties on all possible airports, of which there might be many. Further, for each property, you're searching if it Contains the string, rather than it just being at the beginning (via StartsWith). This means that each property has to be linearly searched for your result.

Luckily, searching through items is a pretty common computing issue; consequently, there's many solutions developers cleverer than myself have devised for speeding searches up, or at least making them seem snappy. I'd suggest you look pick a combination of the items listed below (and search for more!). I can't provide implementations them without writing an epically long answer (maybe another SO'er will oblige) but hopefully they'll help your search!

  • Return results to the UI as they're gathered - This one requires no fundamental change to your approach, nor does it make it faster, but immediate UI feedback is psychologically speaking very important and keeps the user's attention.
  • Narrow down the query - Are they searching for LHR, TPE, or any three-lettered phrase? It's likely that they are searching for an ICAO id. Perform your search through the ICAO ID's first and echo them to the UI asap. Checking their IP, are they seaching from a computer based in England? If they are, you could prioritize airports in England, etc. For many cases, this will complete most people's searches without having to go through all possible permutatitons. Of course, step to full-permutation searches after these shortcuts incase they're doing non-standard searches.
  • Subset previous query answers - If they searched for Lon and the search retrieved London Heathrow, London Gatwick, and Londrina, then a follow-up search for Londo is only ever going to return a subset of those responses. This requires that you hold the state of previous requests (and responses), and could be complicated to implement in practice.
  • Presort and index _airports.AirportList and use a different search algorythm - At the moment, you're linearly searching through the airports, which has O(n) complexity. Provided you're OK with initially searching with StartsWith rather than Contains, using a binary search would nock the algorythm down to O(log n) which, if there's alot of airports, will end up faster. Presort your _airports.AirportList by IcaoId, IcaoName, City, Country into separate indexes / lists (if you have the memory to spare) and binary search against those.
  • If that doesn't work, take up drinking (and micro-optimize) - You could pre-emptively ToLower your _airports.AirportList so that you're not having to constantly lowercaps them when searching. You could take advantage of cache optimization and flatten _airports.AirportList into parallel List<IcaoId>, List<IcaoName>, etc. You could statistically analyze your clients' search habits and optimize your searches around them (e.g 90 % are using two airports, always have those airports top of the search pile). You could offload the search onto a 3rd party service that does have the computing power to do it almost instantaneously (I'D SERIOUSLY CONSIDER THIS ONE). You could multithread the entire process. You could rewrite it in C++ and get annoyed when that one class you wrote 2 months ago memory leaked all over your phone. You could find evidence that implicates your boss in a sex scandal and blackmail him/her, avoiding this problem all over, etc.

Upvotes: 1

Related Questions