2
$\begingroup$

I have a scenario where I want to sort a list of objects where the process of comparing two a <= b is very slow, and so I wish to minimise comparisons. My research suggests that would lead me to something like Merge Sort. However I noticed one thing, which is that rather than outputting a<b, a>b, a=b in the comparison, I can get another piece of info which I'll call a magnitude hint to say approximately how much greater or less than each value is - $a \approx 2b$ or $a \approx b/100$ etc.

This magnitude hint is an estimate, it will always have the correct sign $sign(log(a/b))$ is constant +, - or = if you repeatedly compare a & b, there is no chance of similar items being compared differently on 2 occasions. But the magnitude can vary - I suppose a truncated normal distribution centred on an unknown rank value of log(a/b) might represent it best, other solutions welcome.

I was wondering if there is a sorting algorithm that takes advantage of this property to speed up sorting, e.g. knowing something is 100 times greater, I can assume the two items are more likely to be at the extremes of the list than in the centre?

I had an idea to use a heuristic quicksort where you identify items significantly smaller, significantly larger or slightly smaller/larger than the pivot and treat them differently, although it was not entirely clear how. Alternatively algorithms that work well with partially sorted data like insertion sort might work well, since although the list is not partially sorted, the relative size can be used to speed up sorting.

So I'm thinking about something like with this list:

c,d,b,a

I measure a << d and a < b, therefore b < d can be inferred without another comparison.


I have already considered:

  • Looking for a sort algorithm with as few as possible compare operations. In fact it is the same scenario with a human sorting a list, except here I want to leverage the degree of similarity between 2 items to speed up sorting by reducing slow manual comparisons, which that question does not cover.

  • Minimal k-way comparison sorting algorithm? except again it soesn't explicitly leverage the relative difference property, and in my scenario there is an objective ranking, whereas in that example comparing movies there is not. Imagine putting coloured pencils in rainbow order, the comparisons would be done by a human and they can say "this is similar but slightly redder", or "these are opposite ends of the spectrum". But there is a definite correct final ordering, unlike in that question.

$\endgroup$
3
  • $\begingroup$ The obvious solution is to figure out why “a<b” is slow, and make it faster. Why is it slow? $\endgroup$
    – gnasher729
    Commented Jul 6 at 21:49
  • $\begingroup$ It is carried out by a human. The example could be you have some pencils labelled A-Z and you need to sort the list A-Z according to the colour of the pencil in rainbow order. A human could just as quickly say this pencil is close but a little bit redder, as they could say this pencil is opposite end of the spectrum to that pencil. Something like that $\endgroup$
    – Greedo
    Commented Jul 6 at 21:52
  • $\begingroup$ @D.W. I read your answer on this qu cs.stackexchange.com/questions/16775 and suppose that $a/b$ cannot be computed exactly so maybe a modified Bradley Terrey model that lets you say a beats b but it was close or comprehensive would work. IIUC B-T only takes Win/Loss/Draw as input. I would like a model that takes $\hat{d}$ as an estimate of Alice's hidden strength / Bob's hidden strength and use that to predict the Maximum Likelihood ranking. I'm not sure this approach guarantees fewest comparisons in the expected or worse case. $\endgroup$
    – Greedo
    Commented Jul 7 at 9:58

2 Answers 2

2
$\begingroup$

If you have the exact $a/b$ when comparing two elements $a$ and $b$, you can easily sort in $n-1$ comparisions by finding all the $k_i$ values where $k_i \cdot a_0 = a_i$ and sorting that by any number sorting algorithm.

I am assuming we don't have that, then we get $a/b$ with some probability distribution, which I am assuming to be a normal distribution on $\log a/b$. Then a bucket like approach on what you mentioned might be suitable, but take care that if two $a_i$ and $a_j$ are very close together, comparing them might gives us an inverse relation $a_i>a_j$ when in reality $a_i<a_j$

$\endgroup$
3
  • $\begingroup$ Sorry I should have clarified (and have now edited question), the a/b is an estimate. I agree with your assumption of the distribution though. Would you be able to expand a little on the bucket approach - is there any algorithm like it? $\endgroup$
    – Greedo
    Commented Jul 7 at 10:08
  • $\begingroup$ Actually I don't agree with the distribution, in my scenario the inverse will never happen. If I compare 2 items several times the sign (>, =,<) will never change, only the magnitude. A normal distribution centred at $log(a/b) = +5$ could still return b < a with some probability which in this case is not realistic. That is why I'm looking for a modification of a classical algorithm that is fast and can be sped up with a heuristic, rather than a maximum likelihood estimate approach, since there is a single valid ordering ultimately $\endgroup$
    – Greedo
    Commented Jul 7 at 16:10
  • $\begingroup$ @Greedo You'll have to decide on the distribution of a comparision's magnitude, before you can go towards an algorithm. You say if $a/b > 1$, We will never get $k\le 1$ when comparing $a$ to $b$, but then how exactly is $k$ distributed? $\endgroup$
    – EnEm
    Commented Jul 7 at 18:13
1
$\begingroup$

I'll assume you believe that the right model is that you observe a "truncated normal distribution" centered at $\log(a/b)$. Then a reasonable approach might be to combine maximum likelihood inference together with active learning.

Let $\theta_1,\dots,\theta_n$ denote the unknown values associated with the $n$ objects. Let $\Theta=(\theta_1,\dots,\theta_n)$. When you compare $i,j$, you obtain a sample from the distribution $\mathcal{D}(\log(\theta_i/\theta_j))$ where $\mathcal{D}(\mu)$ is some truncated normal distribution centered at $\mu$. Let $p(x|\mu)$ denote the pdf for $D(\mu)$, i.e., the probability density associated with observing $x$ as a sample from $\mathcal{D}(\mu)$.

With this setup, we can formulate the inference problem as a maximum likelihood inference problem. We'll assume we've observed the result of comparing a bunch of pairs of objects. In other words, we have a bunch of observations $x_{i,j}$, where each $x_{i,j}$ is a sample from $\mathcal{D}(\log(\theta_i/\theta_j))$ (i.e., a result of comparing $i$ and $j$). Then the likelihood of $\Theta$, given these observations, is given by

$$L(\Theta) = \prod p(x_{i,j}|\log(\theta_i/\theta_j)),$$

where $p(\cdot|\cdot)$ is the pdf mentioned above, and the product is taken over all pairs you have compared. Now find $\Theta$ that maximizes $L(\Theta)$. This can be done using any mathematical optimization algorithm, etc., gradient descent. The result will be a "good guess" at the $\theta$'s. Given $\Theta$, you can then sort the objects, based on their $\theta$ values.

How to choose which pairs of objects to compare? One plausible approach might be to pick pairs whose $\theta$-values are close to each other. e.g., in each round, you sort the $n$ objects by $\theta$-values, for each object find the distance to its nearest other object (which will be either the object immediately before it or after it), pick the $0.2n$ of them that have the lowest distances, and perform those $\le 0.2n$ comparisons. After each round, re-apply the inference algorithm to infer new $\theta$-values, and then repeat.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.