python: Speed up get_package_list()

This patch replaces the quadratic monstrosity with an approximately linear
equivalent.

On my system (40297 installed+available packages) this gets the time spent in
get_package_list to 1.3 s from the initial ~600 s. In other words, pkcon
refresh now spends just about 20 s CPU time instead of 8 minutes.

Signed-off-by: Richard Hughes <richard@hughsie.com>

1 files changed, 9 insertions, 4 deletions

diff --git a/lib/python/packagekit/filter.py b/lib/python/packagekit/filter.py
index 99d2de85..e99cfef1 100644
--- a/lib/python/packagekit/filter.py
+++ b/lib/python/packagekit/filter.py
@@ -21,6 +21,7 @@
 # imports
 from .enums import *
 from .package import PackagekitPackage
+import collections
 
 class PackagekitFilter(object, PackagekitPackage):
 
@@ -83,17 +84,21 @@ class PackagekitFilter(object, PackagekitPackage):
             if self._filter_base(pkg):
                 self.package_list.append((pkg, state))
 
+        # prepare lookup table of installed packages
+        installed_dict = collections.defaultdict(list)
+        for pkg, state in self.package_list:
+            if state is INFO_INSTALLED:
+                installed_dict[self._pkg_get_name(pkg)].append(pkg)
+
         # check there are not available versions in the package list
         # that are older than the installed version
         package_list = self.package_list
         self.package_list = []
         for pkg, state in package_list:
 
-            add = True;
+            add = True
             if state is INFO_AVAILABLE:
-                for pkg_tmp, state_tmp in self.package_list:
-                    if state_tmp is not INFO_INSTALLED:
-                        continue
+                for pkg_tmp in installed_dict[self._pkg_get_name(pkg)]:
                     rc = self._pkg_compare(pkg, pkg_tmp)
 
                     # don't add if the same as the installed package