Merge lp:~mhr3/unity-lens-applications/secondary-sorting into lp:unity-lens-applications

[Michal Hruby]

Cluster applications according to relevancy of the match when searching and if multiple applications fall into the same cluster sort them according to frequency of use.

Implements secondary sorting of applications based on frequency of use.

[Michal Hruby (mhr3)]

Note that there are pending changes to the lens view (it should display just 6 recent apps and these should be only filtered out on search), so currently this affects only the home view.

[lp:~mhr3/unity-lens-applications/secondary-sorting]

274. By Michal Hruby on 2012-03-12

Make sure we check the cancellable after updating popularities

[Mikkel Kamstrup Erlandsen (kamstrup)]

52 + if (popularities_dirty)
53 + yield update_popularities ();

Check for cancellation after here?

91 + popularity_map[uri] = relevancy--;

Should the decrement not be moved to the outermost for-loop? If one event has many apps they should all rank alike, no?

139 + results.results.sort_with_data ((a, b) =>
140 + {
141 + int rel_a = a.relevancy / 10;
142 + int rel_b = b.relevancy / 10;
        ...

Can you add a comment explaining the sorting please (also noting the rounding trick)? For the uninitiated this will look like dark magic.

I was wondering if it would be a significant speed increase if you simply iterated the results GSList but then inserted the hits sorted in a GSequence. I don't know the performance profile of sorting a GSList, but I'd assume it to be weak... But this prolly clashes with code elsewhere expecting the glist..?

184 + /* Make sure fresh install learns quickly */
185 + if (popularity_map.size <= 5) popularities_dirty = true;

Like this tweak. Clever you are!

review: Needs Information

[Mikkel Kamstrup Erlandsen (kamstrup)]

75 + // simulate a kind of frecency

Also - this is not "frecency", but rather "relequency" or "frelevancy" whatever you wanna clal it :-)

[Michal Hruby (mhr3)]

> kamstrup wrote 4 minutes ago:
> 52 + if (popularities_dirty)
> 53 + yield update_popularities ();
>
> Check for cancellation after here?

8 minutes ago
Make sure we check the cancellable after updating popularities

Received the tachyons ;)

> Should the decrement not be moved to the outermost for-loop? If one event has many apps they should all rank alike, no?

I suppose you're right, at least I don't have to use 256 event limit and magical 512 constant five lines later.

> Can you add a comment explaining the sorting please (also noting the rounding trick)? For the uninitiated this will look like dark magic.

Fixed.

> I was wondering if it would be a significant speed increase if you simply iterated the results GSList but then inserted the hits sorted in a GSequence. I don't know the performance profile of sorting a GSList, but I'd assume it to be weak... But this prolly clashes with code elsewhere expecting the glist..?

I was thinking about this as well, but since there are usually just a few hundred apps (and only a few dozen search hits), the time spent building a sequence and sorting it would probably be higher than just sorting the linked list. (moreover looking at glib's sources it seems to be using mergesort which is O(N logN) therefore a non-issue really).

[lp:~mhr3/unity-lens-applications/secondary-sorting]

275. By Michal Hruby on 2012-03-12

Explain the magical sorting

276. By Michal Hruby on 2012-03-12

Treat multi-subject events equally

[Michal Hruby (mhr3)]

> 75 + // simulate a kind of frecency
>
> Also - this is not "frecency", but rather "relequency" or "frelevancy"
> whatever you wanna clal it :-)

Actually that was a comment on the time range I'm using there (only last 3 weeks), so it indeed is frecency in this context. (so overall the sorting is "frecevancy" ;)

[Mikkel Kamstrup Erlandsen (kamstrup)]

Great! You have me sold!

review: Approve

=== modified file 'src/daemon.vala'
--- src/daemon.vala	2012-02-20 12:35:16 +0000
+++ src/daemon.vala	2012-03-12 11:46:18 +0000
@@ -33,7 +33,10 @@
     private Zeitgeist.Log log;
     private Zeitgeist.Index zg_index;
     private Zeitgeist.Monitor monitor;
-    
+
+    private Map<string, int> popularity_map;
+    private bool popularities_dirty;
+
     /* The searcher for online material may be null if it fails to load
      * the Xapian index from the Software Center */
     private Unity.Package.Searcher? pkgsearcher;
@@ -92,6 +95,15 @@
       monitor.events_deleted.connect (mark_dirty);
       log.install_monitor (monitor);
       
+      popularity_map = new HashMap<string, int> ();
+      popularities_dirty = true;
+      // refresh the popularities every now and then
+      Timeout.add_seconds (30 * 60, () =>
+      {
+        popularities_dirty = true;
+        return true;
+      });
+
       this.gp_settings = new Settings ("com.canonical.Unity.ApplicationsLens");
       this.gp_settings.bind(DISPLAY_RECENT_APPS_KEY, this, "display_recent_apps", SettingsBindFlags.GET);
       this.gp_settings.bind(DISPLAY_AVAILABLE_APPS_KEY, this, "display_available_apps", SettingsBindFlags.GET);
@@ -143,10 +155,7 @@
       /* Listen for changes to the lens scope search */
       scope.search_changed.connect ((lens_search, search_type, cancellable) =>
       {
-        if (search_type == SearchType.DEFAULT)
-          update_scope_search.begin (lens_search, cancellable);
-        else
-          update_global_search.begin (lens_search, cancellable);
+        dispatch_search (lens_search, search_type, cancellable);
       });
       
       /* Re-do the search if the filters changed */
@@ -194,6 +203,22 @@
       lens.export ();
     }
 
+    private async void dispatch_search (LensSearch lens_search,
+                                        SearchType search_type,
+                                        Cancellable cancellable)
+    {
+      if (popularities_dirty)
+      {
+        yield update_popularities ();
+        if (cancellable.is_cancelled ()) return;
+      }
+
+      if (search_type == SearchType.DEFAULT)
+        yield update_scope_search (lens_search, cancellable);
+      else
+        yield update_global_search (lens_search, cancellable);
+    }
+
     /* Pre-populates the type queries so it's easier/faster to build our search */
     private void populate_type_queries ()
     {
@@ -376,6 +401,41 @@
         return s + " AND " + extract_type_query (options);
     }
 
+    private async void update_popularities ()
+    {
+      try
+      {
+        // simulate a kind of frecency
+        var end_ts = Timestamp.now ();
+        var start_ts = end_ts - Timestamp.WEEK * 3;
+        var rs = yield log.find_events (new TimeRange (start_ts, end_ts),
+                                        zg_templates,
+                                        StorageState.ANY,
+                                        256,
+                                        ResultType.MOST_POPULAR_SUBJECTS,
+                                        null);
+
+        // most popular apps must have high value, so unknown apps (where
+        // popularity_map[app] == 0 aren't considered super popular
+        int relevancy = 256;
+        foreach (unowned Event event in rs)
+        {
+          for (int i = 0; i < event.num_subjects (); i++)
+          {
+            unowned string uri = event.get_subject (i).get_uri ();
+            if (uri == null) continue;
+            popularity_map[uri] = relevancy;
+          }
+          relevancy--;
+        }
+      }
+      catch (GLib.Error err)
+      {
+        warning ("%s", err.message);
+      }
+      popularities_dirty = false;
+    }
+
     private async void update_scope_search (Unity.LensSearch search,
                                             Cancellable cancellable)
     {
@@ -701,6 +761,25 @@
       
       return icon;
     }
+
+    private string extract_desktop_id (string? desktop_file,
+                                       bool unmangle = false)
+    {
+      if (desktop_file == null) return "";
+
+      string desktop_id = Path.get_basename (desktop_file);
+      /* S-C uses "app_name:desktop_id.desktop", get rid of the prefix */
+      int colon_pos = desktop_id.index_of (":");
+      if (unmangle && colon_pos > 0)
+      {
+        desktop_id = desktop_id[colon_pos+1:desktop_id.length];
+        /* well it's still not real desktop_id, S-C converts slashes to "__"
+         * if the desktop file is in /usr/share/applications */
+        desktop_id = desktop_id.replace ("__", "-");
+      }
+
+      return desktop_id;
+    }
     
     private void add_pkg_search_result (Unity.Package.SearchResult results,
                                         Set<string> installed_uris,
@@ -712,25 +791,39 @@
       var appmanager = AppInfoManager.get_default();
       var ratings_filter = scope.get_filter ("rating") as RatingsFilter;
       uint n_added = 0;
-    
+
+      if (category != Category.AVAILABLE)
+      {
+        results.results.sort_with_data ((a, b) =>
+        {
+          /* We'll cluster the relevancies into a couple of bins, because
+           * there can be multiple terms adding to the relevancy (especially
+           * when doing one/two character prefix searches - ie a "f*" search
+           * will have slightly higher relevancy for item with name "Search
+           * _f_or _f_iles" than "_F_irefox", and that's not what we want)
+           */
+          int rel_a = a.relevancy / 10;
+          int rel_b = b.relevancy / 10;
+          if (rel_a == rel_b)
+          {
+            string id_a = extract_desktop_id (a.desktop_file);
+            string id_b = extract_desktop_id (b.desktop_file);
+            rel_a = popularity_map["application://" + id_a];
+            rel_b = popularity_map["application://" + id_b];
+          }
+          return rel_b - rel_a; // we want higher relevancy first
+        });
+      }
+
       foreach (var pkginfo in results.results)
       {
       	if (pkginfo.desktop_file == null)
           continue;
         
-        string desktop_id = Path.get_basename (pkginfo.desktop_file);
+        string desktop_id = extract_desktop_id (pkginfo.desktop_file,
+          category == Category.AVAILABLE);
         string full_path;
 
-        /* S-C uses "app_name:desktop_id.desktop", get rid of the prefix */
-        int colon_pos = desktop_id.index_of (":");
-        if (category == Category.AVAILABLE && colon_pos > 0)
-        {
-          desktop_id = desktop_id[colon_pos+1:desktop_id.length];
-          /* well it's still not real desktop_id, S-C converts slashes to "__"
-           * if the desktop file is in /usr/share/applications */
-          desktop_id = desktop_id.replace ("__", "-");
-        }
-
         AppInfo? app = appmanager.lookup (desktop_id);
         full_path = appmanager.get_path (desktop_id);
         
@@ -852,7 +945,11 @@
         }
       else
         {
-          debug ("Declined activation of URI '%s': Expected URI scheme unity-install:// or unity-runner://", uri);
+          /* Activation of standard application:// uris */
+
+          /* Make sure fresh install learns quickly */
+          if (popularity_map.size <= 5) popularities_dirty = true;
+
           return new Unity.ActivationResponse(Unity.HandledType.NOT_HANDLED);
         }
 

=== modified file 'src/unity-package-search.cc'
--- src/unity-package-search.cc	2012-02-20 11:08:48 +0000
+++ src/unity-package-search.cc	2012-03-12 11:46:18 +0000
@@ -437,10 +437,11 @@
   try
   {
     // Perform search
+    searcher->enquire->set_collapse_key(XAPIAN_VALUE_DESKTOP_FILE);
     max_hits = (max_hits != 0 ? max_hits : searcher->db->get_doccount ());
     searcher->enquire->set_query(query);
     Xapian::MSet matches =
-      searcher->enquire->get_mset(0, max_hits);	
+      searcher->enquire->get_mset(0, max_hits);
 
     // Retrieve the results, note that we build the result->results
     // list in reverse order and then reverse it before we return it
@@ -453,6 +454,7 @@
           {
             Xapian::Document doc = i.get_document();
             UnityPackageInfo *pkginfo = _pkginfo_from_document (doc);
+            pkginfo->relevancy = i.get_percent ();
             result->results = g_slist_prepend (result->results, pkginfo);
           }
         catch (Xapian::Error e)

=== modified file 'src/unity-package-search.h'
--- src/unity-package-search.h	2011-03-09 14:50:33 +0000
+++ src/unity-package-search.h	2012-03-12 11:46:18 +0000
@@ -46,6 +46,7 @@
 	gchar    *application_name;
 	gchar    *desktop_file;
 	gchar    *icon;
+	gint      relevancy;
 } UnityPackageInfo;
 
 #ifdef __cplusplus

=== modified file 'vapi/unity-package-search.vapi'
--- vapi/unity-package-search.vapi	2011-03-09 14:50:33 +0000
+++ vapi/unity-package-search.vapi	2012-03-12 11:46:18 +0000
@@ -34,7 +34,6 @@
     public class SearchResult {
       public GLib.SList<unowned PackageInfo> results;
       public int num_hits;
-      
     }
     
     [Compact]
@@ -44,6 +43,7 @@
 	    public string application_name;
 	    public string desktop_file;
 	    public string icon;
+	    public int relevancy;
     }
   }
 }