1. 23

    1. 2

      Found at FrugalMap.cs:

      // If we’re unsorted and we have entries to sort, do a simple // bubble sort. Sort the pairs, 0..5, and then again until we no // longer do any swapping.

      Dying to know what the rationale was here. Does Bubblesort have really good performance on really small lists?

      1. 3

        Bubblesort is in place and requires no setup as most other potentially faster sorting algorithms does.

        You’re also bounded to at most 15 comparisons and an early bailout if nothing was swapped.

        So it’s probably good enough that the main time is spent elsewhere

        1. 2

          Yup! Bubblesort is much faster at small lists because the constant factor overhead is almost negligible (for exactly the reasons that @jeb mentioned). Usually you see insertion sort instead of bubble sort, which has the same O(N^2)-but-almost-zero-overhead time complexity, because insertion sort ends up doing fewer swaps, but the general idea (solve small sorting problems with O(N^2) algorithms) is the same. This is a weird property of asymptotic complexity analysis: the idea behind expressing complexity as O(f(n)) is to give you an idea of how some kind of resource usage (time, memory) grows as the problem grows. It really tells you very little about how the algorithm will perform on smaller instances of the problem.

          In fact, one of the more popular sorting algorithms today, Timsort, often boils down to “split into small lists of length N, run insertion sort on those, and then do a merge-sort-like merging until the whole thing is sorted”. Most production-grade quicksort implementations also do this: break the list down into small chunks, insertion-sort those, and then do the quicksort magic back up the stack. Many sorting algorithms do exactly what FrugalMap is doing as well: you can unroll the loop in the insertion sort step, since insertion sort on 5 elements ends up being a relatively small chunk of code, and you avoid conditional jumps in the common case that your short array is exactly the maximum length allowed by your algorithm.

        2. 1

          I wonder if it isn’t too little, too late.

          On the other hand I’d like to have reasonyably compatible WinForms on Windows/OSX/Linux/… as it is a very handy tool to create throwaway rudimentary UIs for some simple tasks. I have yet to see anything comparable in terms of productivity for small simple tasks (it does not scale well in my experience, neither in dpi sense, neither in UI complexity vs. productivity sense)

          With the Mono implementation I have experienced various issues which eventually made it unsuitable for my usecases. I hope it will eventually get it better, if it will still be used by anyone.

          But I have created simple “debug” GUI for simple image processing pipeline for example in less than a hour for example.

          1. 1

            Great news, esp for ReactOS. Still gotta ask:

            Did they put this into that patent, protection scheme for FOSS? Or is the MIT code still potentially patent encumbered?