[gnome-software: 3/7] gs-app-list: Make randomising a list a lot more efficient

[Philip Withnall <pwithnall src gnome org>]

commit 5d9af0c29a8ee510369dd84e9db1b661166e9928
Author: Philip Withnall <pwithnall endlessos org>
Date:   Tue May 24 16:10:25 2022 +0100

    gs-app-list: Make randomising a list a lot more efficient
    
    The previous implementation iterated over the list generating a
    3-character randomisation key for each app, and storing it in a per-app
    hash table. Then it did a quicksort (O(n log(n))) of the list. Then it
    iterated over the list again and removed the randomisation key from each
    app.
    
    This took O(n log(n)) time with a heavy constant factor and a lot of
    string and hash table allocations. It used O(3n) calls to the `GRand`.
    
    Shuffling an array only needs to take O(n) time, though. This commit
    achieves that by using a Fisher–Yates shuffle, with N calls to `GRand`
    and N swaps of elements in the array. No allocations are needed apart
    from to set up the `GRand`.
    
    I haven’t measured the performance improvement with this change, but it
    should be a positive one even if it’s not significant.
    
    Signed-off-by: Philip Withnall <pwithnall endlessos org>

 lib/gs-app-list.c | 42 +++++++++++-------------------------------
 1 file changed, 11 insertions(+), 31 deletions(-)
---
diff --git a/lib/gs-app-list.c b/lib/gs-app-list.c
index 404d1b91e..961f2bb2a 100644
--- a/lib/gs-app-list.c
+++ b/lib/gs-app-list.c
@@ -702,21 +702,6 @@ gs_app_list_truncate (GsAppList *list, guint length)
        g_ptr_array_set_size (list->array, length);
 }
 
-static gint
-gs_app_list_randomize_cb (gconstpointer a, gconstpointer b, gpointer user_data)
-{
-       GsApp *app1 = GS_APP (*(GsApp **) a);
-       GsApp *app2 = GS_APP (*(GsApp **) b);
-       const gchar *k1;
-       const gchar *k2;
-       g_autofree gchar *key = NULL;
-
-       key = g_strdup_printf ("Plugin::sort-key[%p]", user_data);
-       k1 = gs_app_get_metadata_item (app1, key);
-       k2 = gs_app_get_metadata_item (app2, key);
-       return g_strcmp0 (k1, k2);
-}
-
 /**
  * gs_app_list_randomize:
  * @list: A #GsAppList
@@ -729,34 +714,29 @@ gs_app_list_randomize_cb (gconstpointer a, gconstpointer b, gpointer user_data)
 void
 gs_app_list_randomize (GsAppList *list)
 {
-       guint i;
        GRand *rand;
-       GsApp *app;
-       gchar sort_key[] = { '\0', '\0', '\0', '\0' };
        g_autoptr(GDateTime) date = NULL;
-       g_autofree gchar *key = NULL;
        g_autoptr(GMutexLocker) locker = NULL;
 
        g_return_if_fail (GS_IS_APP_LIST (list));
 
        locker = g_mutex_locker_new (&list->mutex);
 
-       key = g_strdup_printf ("Plugin::sort-key[%p]", list);
        rand = g_rand_new ();
        date = g_date_time_new_now_utc ();
        g_rand_set_seed (rand, (guint32) g_date_time_get_day_of_year (date));
-       for (i = 0; i < gs_app_list_length (list); i++) {
-               app = gs_app_list_index (list, i);
-               sort_key[0] = (gchar) g_rand_int_range (rand, (gint32) 'A', (gint32) 'Z');
-               sort_key[1] = (gchar) g_rand_int_range (rand, (gint32) 'A', (gint32) 'Z');
-               sort_key[2] = (gchar) g_rand_int_range (rand, (gint32) 'A', (gint32) 'Z');
-               gs_app_set_metadata (app, key, sort_key);
-       }
-       g_ptr_array_sort_with_data (list->array, gs_app_list_randomize_cb, list);
-       for (i = 0; i < gs_app_list_length (list); i++) {
-               app = gs_app_list_index (list, i);
-               gs_app_set_metadata (app, key, NULL);
+
+       /* Fisher–Yates shuffle of the array.
+        * See https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle */
+       for (guint i = gs_app_list_length (list) - 1; i >= 1; i--) {
+               gpointer tmp;
+               guint j = g_rand_int_range (rand, 0, i + 1);
+
+               tmp = list->array->pdata[i];
+               list->array->pdata[i] = list->array->pdata[j];
+               list->array->pdata[j] = tmp;
        }
+
        g_rand_free (rand);
 }