Merge lp:~mhr3/unity-lens-applications/secondary-sorting into lp:unity-lens-applications
- secondary-sorting
- Merge into trunk
Status: | Merged |
---|---|
Approved by: | Mikkel Kamstrup Erlandsen |
Approved revision: | 276 |
Merged at revision: | 276 |
Proposed branch: | lp:~mhr3/unity-lens-applications/secondary-sorting |
Merge into: | lp:unity-lens-applications |
Diff against target: |
256 lines (+120/-20) 4 files modified
src/daemon.vala (+115/-18) src/unity-package-search.cc (+3/-1) src/unity-package-search.h (+1/-0) vapi/unity-package-search.vapi (+1/-1) |
To merge this branch: | bzr merge lp:~mhr3/unity-lens-applications/secondary-sorting |
Related bugs: |
Reviewer | Review Type | Date Requested | Status |
---|---|---|---|
Mikkel Kamstrup Erlandsen (community) | Approve | ||
Review via email: mp+96993@code.launchpad.net |
Commit message
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.
Description of the change
Implements secondary sorting of applications based on frequency of use.
Michal Hruby (mhr3) wrote : | # |
- 274. By Michal Hruby
-
Make sure we check the cancellable after updating popularities
Mikkel Kamstrup Erlandsen (kamstrup) wrote : | # |
52 + if (popularities_
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.
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_
Like this tweak. Clever you are!
Mikkel Kamstrup Erlandsen (kamstrup) wrote : | # |
75 + // simulate a kind of frecency
Also - this is not "frecency", but rather "relequency" or "frelevancy" whatever you wanna clal it :-)
Michal Hruby (mhr3) wrote : | # |
> kamstrup wrote 4 minutes ago:
> 52 + if (popularities_
> 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).
- 275. By Michal Hruby
-
Explain the magical sorting
- 276. By Michal Hruby
-
Treat multi-subject events equally
Michal Hruby (mhr3) wrote : | # |
> 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) wrote : | # |
Great! You have me sold!
Preview Diff
1 | === modified file 'src/daemon.vala' | |||
2 | --- src/daemon.vala 2012-02-20 12:35:16 +0000 | |||
3 | +++ src/daemon.vala 2012-03-12 11:46:18 +0000 | |||
4 | @@ -33,7 +33,10 @@ | |||
5 | 33 | private Zeitgeist.Log log; | 33 | private Zeitgeist.Log log; |
6 | 34 | private Zeitgeist.Index zg_index; | 34 | private Zeitgeist.Index zg_index; |
7 | 35 | private Zeitgeist.Monitor monitor; | 35 | private Zeitgeist.Monitor monitor; |
9 | 36 | 36 | ||
10 | 37 | private Map<string, int> popularity_map; | ||
11 | 38 | private bool popularities_dirty; | ||
12 | 39 | |||
13 | 37 | /* The searcher for online material may be null if it fails to load | 40 | /* The searcher for online material may be null if it fails to load |
14 | 38 | * the Xapian index from the Software Center */ | 41 | * the Xapian index from the Software Center */ |
15 | 39 | private Unity.Package.Searcher? pkgsearcher; | 42 | private Unity.Package.Searcher? pkgsearcher; |
16 | @@ -92,6 +95,15 @@ | |||
17 | 92 | monitor.events_deleted.connect (mark_dirty); | 95 | monitor.events_deleted.connect (mark_dirty); |
18 | 93 | log.install_monitor (monitor); | 96 | log.install_monitor (monitor); |
19 | 94 | 97 | ||
20 | 98 | popularity_map = new HashMap<string, int> (); | ||
21 | 99 | popularities_dirty = true; | ||
22 | 100 | // refresh the popularities every now and then | ||
23 | 101 | Timeout.add_seconds (30 * 60, () => | ||
24 | 102 | { | ||
25 | 103 | popularities_dirty = true; | ||
26 | 104 | return true; | ||
27 | 105 | }); | ||
28 | 106 | |||
29 | 95 | this.gp_settings = new Settings ("com.canonical.Unity.ApplicationsLens"); | 107 | this.gp_settings = new Settings ("com.canonical.Unity.ApplicationsLens"); |
30 | 96 | this.gp_settings.bind(DISPLAY_RECENT_APPS_KEY, this, "display_recent_apps", SettingsBindFlags.GET); | 108 | this.gp_settings.bind(DISPLAY_RECENT_APPS_KEY, this, "display_recent_apps", SettingsBindFlags.GET); |
31 | 97 | this.gp_settings.bind(DISPLAY_AVAILABLE_APPS_KEY, this, "display_available_apps", SettingsBindFlags.GET); | 109 | this.gp_settings.bind(DISPLAY_AVAILABLE_APPS_KEY, this, "display_available_apps", SettingsBindFlags.GET); |
32 | @@ -143,10 +155,7 @@ | |||
33 | 143 | /* Listen for changes to the lens scope search */ | 155 | /* Listen for changes to the lens scope search */ |
34 | 144 | scope.search_changed.connect ((lens_search, search_type, cancellable) => | 156 | scope.search_changed.connect ((lens_search, search_type, cancellable) => |
35 | 145 | { | 157 | { |
40 | 146 | if (search_type == SearchType.DEFAULT) | 158 | dispatch_search (lens_search, search_type, cancellable); |
37 | 147 | update_scope_search.begin (lens_search, cancellable); | ||
38 | 148 | else | ||
39 | 149 | update_global_search.begin (lens_search, cancellable); | ||
41 | 150 | }); | 159 | }); |
42 | 151 | 160 | ||
43 | 152 | /* Re-do the search if the filters changed */ | 161 | /* Re-do the search if the filters changed */ |
44 | @@ -194,6 +203,22 @@ | |||
45 | 194 | lens.export (); | 203 | lens.export (); |
46 | 195 | } | 204 | } |
47 | 196 | 205 | ||
48 | 206 | private async void dispatch_search (LensSearch lens_search, | ||
49 | 207 | SearchType search_type, | ||
50 | 208 | Cancellable cancellable) | ||
51 | 209 | { | ||
52 | 210 | if (popularities_dirty) | ||
53 | 211 | { | ||
54 | 212 | yield update_popularities (); | ||
55 | 213 | if (cancellable.is_cancelled ()) return; | ||
56 | 214 | } | ||
57 | 215 | |||
58 | 216 | if (search_type == SearchType.DEFAULT) | ||
59 | 217 | yield update_scope_search (lens_search, cancellable); | ||
60 | 218 | else | ||
61 | 219 | yield update_global_search (lens_search, cancellable); | ||
62 | 220 | } | ||
63 | 221 | |||
64 | 197 | /* Pre-populates the type queries so it's easier/faster to build our search */ | 222 | /* Pre-populates the type queries so it's easier/faster to build our search */ |
65 | 198 | private void populate_type_queries () | 223 | private void populate_type_queries () |
66 | 199 | { | 224 | { |
67 | @@ -376,6 +401,41 @@ | |||
68 | 376 | return s + " AND " + extract_type_query (options); | 401 | return s + " AND " + extract_type_query (options); |
69 | 377 | } | 402 | } |
70 | 378 | 403 | ||
71 | 404 | private async void update_popularities () | ||
72 | 405 | { | ||
73 | 406 | try | ||
74 | 407 | { | ||
75 | 408 | // simulate a kind of frecency | ||
76 | 409 | var end_ts = Timestamp.now (); | ||
77 | 410 | var start_ts = end_ts - Timestamp.WEEK * 3; | ||
78 | 411 | var rs = yield log.find_events (new TimeRange (start_ts, end_ts), | ||
79 | 412 | zg_templates, | ||
80 | 413 | StorageState.ANY, | ||
81 | 414 | 256, | ||
82 | 415 | ResultType.MOST_POPULAR_SUBJECTS, | ||
83 | 416 | null); | ||
84 | 417 | |||
85 | 418 | // most popular apps must have high value, so unknown apps (where | ||
86 | 419 | // popularity_map[app] == 0 aren't considered super popular | ||
87 | 420 | int relevancy = 256; | ||
88 | 421 | foreach (unowned Event event in rs) | ||
89 | 422 | { | ||
90 | 423 | for (int i = 0; i < event.num_subjects (); i++) | ||
91 | 424 | { | ||
92 | 425 | unowned string uri = event.get_subject (i).get_uri (); | ||
93 | 426 | if (uri == null) continue; | ||
94 | 427 | popularity_map[uri] = relevancy; | ||
95 | 428 | } | ||
96 | 429 | relevancy--; | ||
97 | 430 | } | ||
98 | 431 | } | ||
99 | 432 | catch (GLib.Error err) | ||
100 | 433 | { | ||
101 | 434 | warning ("%s", err.message); | ||
102 | 435 | } | ||
103 | 436 | popularities_dirty = false; | ||
104 | 437 | } | ||
105 | 438 | |||
106 | 379 | private async void update_scope_search (Unity.LensSearch search, | 439 | private async void update_scope_search (Unity.LensSearch search, |
107 | 380 | Cancellable cancellable) | 440 | Cancellable cancellable) |
108 | 381 | { | 441 | { |
109 | @@ -701,6 +761,25 @@ | |||
110 | 701 | 761 | ||
111 | 702 | return icon; | 762 | return icon; |
112 | 703 | } | 763 | } |
113 | 764 | |||
114 | 765 | private string extract_desktop_id (string? desktop_file, | ||
115 | 766 | bool unmangle = false) | ||
116 | 767 | { | ||
117 | 768 | if (desktop_file == null) return ""; | ||
118 | 769 | |||
119 | 770 | string desktop_id = Path.get_basename (desktop_file); | ||
120 | 771 | /* S-C uses "app_name:desktop_id.desktop", get rid of the prefix */ | ||
121 | 772 | int colon_pos = desktop_id.index_of (":"); | ||
122 | 773 | if (unmangle && colon_pos > 0) | ||
123 | 774 | { | ||
124 | 775 | desktop_id = desktop_id[colon_pos+1:desktop_id.length]; | ||
125 | 776 | /* well it's still not real desktop_id, S-C converts slashes to "__" | ||
126 | 777 | * if the desktop file is in /usr/share/applications */ | ||
127 | 778 | desktop_id = desktop_id.replace ("__", "-"); | ||
128 | 779 | } | ||
129 | 780 | |||
130 | 781 | return desktop_id; | ||
131 | 782 | } | ||
132 | 704 | 783 | ||
133 | 705 | private void add_pkg_search_result (Unity.Package.SearchResult results, | 784 | private void add_pkg_search_result (Unity.Package.SearchResult results, |
134 | 706 | Set<string> installed_uris, | 785 | Set<string> installed_uris, |
135 | @@ -712,25 +791,39 @@ | |||
136 | 712 | var appmanager = AppInfoManager.get_default(); | 791 | var appmanager = AppInfoManager.get_default(); |
137 | 713 | var ratings_filter = scope.get_filter ("rating") as RatingsFilter; | 792 | var ratings_filter = scope.get_filter ("rating") as RatingsFilter; |
138 | 714 | uint n_added = 0; | 793 | uint n_added = 0; |
140 | 715 | 794 | ||
141 | 795 | if (category != Category.AVAILABLE) | ||
142 | 796 | { | ||
143 | 797 | results.results.sort_with_data ((a, b) => | ||
144 | 798 | { | ||
145 | 799 | /* We'll cluster the relevancies into a couple of bins, because | ||
146 | 800 | * there can be multiple terms adding to the relevancy (especially | ||
147 | 801 | * when doing one/two character prefix searches - ie a "f*" search | ||
148 | 802 | * will have slightly higher relevancy for item with name "Search | ||
149 | 803 | * _f_or _f_iles" than "_F_irefox", and that's not what we want) | ||
150 | 804 | */ | ||
151 | 805 | int rel_a = a.relevancy / 10; | ||
152 | 806 | int rel_b = b.relevancy / 10; | ||
153 | 807 | if (rel_a == rel_b) | ||
154 | 808 | { | ||
155 | 809 | string id_a = extract_desktop_id (a.desktop_file); | ||
156 | 810 | string id_b = extract_desktop_id (b.desktop_file); | ||
157 | 811 | rel_a = popularity_map["application://" + id_a]; | ||
158 | 812 | rel_b = popularity_map["application://" + id_b]; | ||
159 | 813 | } | ||
160 | 814 | return rel_b - rel_a; // we want higher relevancy first | ||
161 | 815 | }); | ||
162 | 816 | } | ||
163 | 817 | |||
164 | 716 | foreach (var pkginfo in results.results) | 818 | foreach (var pkginfo in results.results) |
165 | 717 | { | 819 | { |
166 | 718 | if (pkginfo.desktop_file == null) | 820 | if (pkginfo.desktop_file == null) |
167 | 719 | continue; | 821 | continue; |
168 | 720 | 822 | ||
170 | 721 | string desktop_id = Path.get_basename (pkginfo.desktop_file); | 823 | string desktop_id = extract_desktop_id (pkginfo.desktop_file, |
171 | 824 | category == Category.AVAILABLE); | ||
172 | 722 | string full_path; | 825 | string full_path; |
173 | 723 | 826 | ||
174 | 724 | /* S-C uses "app_name:desktop_id.desktop", get rid of the prefix */ | ||
175 | 725 | int colon_pos = desktop_id.index_of (":"); | ||
176 | 726 | if (category == Category.AVAILABLE && colon_pos > 0) | ||
177 | 727 | { | ||
178 | 728 | desktop_id = desktop_id[colon_pos+1:desktop_id.length]; | ||
179 | 729 | /* well it's still not real desktop_id, S-C converts slashes to "__" | ||
180 | 730 | * if the desktop file is in /usr/share/applications */ | ||
181 | 731 | desktop_id = desktop_id.replace ("__", "-"); | ||
182 | 732 | } | ||
183 | 733 | |||
184 | 734 | AppInfo? app = appmanager.lookup (desktop_id); | 827 | AppInfo? app = appmanager.lookup (desktop_id); |
185 | 735 | full_path = appmanager.get_path (desktop_id); | 828 | full_path = appmanager.get_path (desktop_id); |
186 | 736 | 829 | ||
187 | @@ -852,7 +945,11 @@ | |||
188 | 852 | } | 945 | } |
189 | 853 | else | 946 | else |
190 | 854 | { | 947 | { |
192 | 855 | debug ("Declined activation of URI '%s': Expected URI scheme unity-install:// or unity-runner://", uri); | 948 | /* Activation of standard application:// uris */ |
193 | 949 | |||
194 | 950 | /* Make sure fresh install learns quickly */ | ||
195 | 951 | if (popularity_map.size <= 5) popularities_dirty = true; | ||
196 | 952 | |||
197 | 856 | return new Unity.ActivationResponse(Unity.HandledType.NOT_HANDLED); | 953 | return new Unity.ActivationResponse(Unity.HandledType.NOT_HANDLED); |
198 | 857 | } | 954 | } |
199 | 858 | 955 | ||
200 | 859 | 956 | ||
201 | === modified file 'src/unity-package-search.cc' | |||
202 | --- src/unity-package-search.cc 2012-02-20 11:08:48 +0000 | |||
203 | +++ src/unity-package-search.cc 2012-03-12 11:46:18 +0000 | |||
204 | @@ -437,10 +437,11 @@ | |||
205 | 437 | try | 437 | try |
206 | 438 | { | 438 | { |
207 | 439 | // Perform search | 439 | // Perform search |
208 | 440 | searcher->enquire->set_collapse_key(XAPIAN_VALUE_DESKTOP_FILE); | ||
209 | 440 | max_hits = (max_hits != 0 ? max_hits : searcher->db->get_doccount ()); | 441 | max_hits = (max_hits != 0 ? max_hits : searcher->db->get_doccount ()); |
210 | 441 | searcher->enquire->set_query(query); | 442 | searcher->enquire->set_query(query); |
211 | 442 | Xapian::MSet matches = | 443 | Xapian::MSet matches = |
213 | 443 | searcher->enquire->get_mset(0, max_hits); | 444 | searcher->enquire->get_mset(0, max_hits); |
214 | 444 | 445 | ||
215 | 445 | // Retrieve the results, note that we build the result->results | 446 | // Retrieve the results, note that we build the result->results |
216 | 446 | // list in reverse order and then reverse it before we return it | 447 | // list in reverse order and then reverse it before we return it |
217 | @@ -453,6 +454,7 @@ | |||
218 | 453 | { | 454 | { |
219 | 454 | Xapian::Document doc = i.get_document(); | 455 | Xapian::Document doc = i.get_document(); |
220 | 455 | UnityPackageInfo *pkginfo = _pkginfo_from_document (doc); | 456 | UnityPackageInfo *pkginfo = _pkginfo_from_document (doc); |
221 | 457 | pkginfo->relevancy = i.get_percent (); | ||
222 | 456 | result->results = g_slist_prepend (result->results, pkginfo); | 458 | result->results = g_slist_prepend (result->results, pkginfo); |
223 | 457 | } | 459 | } |
224 | 458 | catch (Xapian::Error e) | 460 | catch (Xapian::Error e) |
225 | 459 | 461 | ||
226 | === modified file 'src/unity-package-search.h' | |||
227 | --- src/unity-package-search.h 2011-03-09 14:50:33 +0000 | |||
228 | +++ src/unity-package-search.h 2012-03-12 11:46:18 +0000 | |||
229 | @@ -46,6 +46,7 @@ | |||
230 | 46 | gchar *application_name; | 46 | gchar *application_name; |
231 | 47 | gchar *desktop_file; | 47 | gchar *desktop_file; |
232 | 48 | gchar *icon; | 48 | gchar *icon; |
233 | 49 | gint relevancy; | ||
234 | 49 | } UnityPackageInfo; | 50 | } UnityPackageInfo; |
235 | 50 | 51 | ||
236 | 51 | #ifdef __cplusplus | 52 | #ifdef __cplusplus |
237 | 52 | 53 | ||
238 | === modified file 'vapi/unity-package-search.vapi' | |||
239 | --- vapi/unity-package-search.vapi 2011-03-09 14:50:33 +0000 | |||
240 | +++ vapi/unity-package-search.vapi 2012-03-12 11:46:18 +0000 | |||
241 | @@ -34,7 +34,6 @@ | |||
242 | 34 | public class SearchResult { | 34 | public class SearchResult { |
243 | 35 | public GLib.SList<unowned PackageInfo> results; | 35 | public GLib.SList<unowned PackageInfo> results; |
244 | 36 | public int num_hits; | 36 | public int num_hits; |
245 | 37 | |||
246 | 38 | } | 37 | } |
247 | 39 | 38 | ||
248 | 40 | [Compact] | 39 | [Compact] |
249 | @@ -44,6 +43,7 @@ | |||
250 | 44 | public string application_name; | 43 | public string application_name; |
251 | 45 | public string desktop_file; | 44 | public string desktop_file; |
252 | 46 | public string icon; | 45 | public string icon; |
253 | 46 | public int relevancy; | ||
254 | 47 | } | 47 | } |
255 | 48 | } | 48 | } |
256 | 49 | } | 49 | } |
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.