Ordering by sum of difference

Question

I have a model that has one attribute with a list of floats:

values = ArrayField(models.FloatField(default=0), default=list, size=64, verbose_name=_('Values'))

Currently, I'm getting my entries and order them according to the sum of all diffs with another list:

def diff(l1, l2):
    return sum([abs(v1-v2) for v1, v2 in zip(l1, l2)])

list2 = [0.3, 0, 1, 0.5]
entries = Model.objects.all()
entries.sort(key=lambda t: diff(t.values, list2))

This works fast if my numer of entries is very slow small. But I'm afraid with a large number of entries, the comparison and sorting of all the entries will get slow since they have to be loaded from the database. Is there a way to make this more efficient?

Answer 1

best way is to write it yourself, right now you are iterating over a list over 4 times!

although this approach looks pretty but it's not good.

one thing that you can do is:

1. have a variable called last_diff and set it to 0

2. iterate through all entries.

3. iterate though each entry.values

4. from i = 0 to the end of list, calculate abs(entry.values[i]-list2[i])

5. sum over these values in a variable called new_diff

6. if new_diff > last_diff break from inner loop and push the entry into its right place (it's called Insertion Sort, check it out!)

in this way, in average scenario, time complexity is much lower than what you are doing now!

and maybe you must be creative too. I'm gonna share some ideas, check them for yourself to make sure that they are fine.

assuming that:

1. values list elements are always positive floats.
2. list2 is always the same for all entries.

then you may be able to say, the bigger the sum over the elements in values, the bigger the diff value is gonna be, no matter what are the elements in list2.

then you might be able to just forget about whole diff function. (test this!)

Answer 2

The only way to makes this really go faster, is to move as much work as possible to the database, i.e. the calculations and the sorting. It wasn't easy, but with the help of this answer I managed to actually write a query for that in almost pure Django:

class Unnest(models.Func):
    function = 'UNNEST'

class Abs(models.Func):
    function = 'ABS'

class SubquerySum(models.Subquery):
    template = '(SELECT sum(%(field)s) FROM (%(subquery)s) _sum)'    

x = [0.3, 0, 1, 0.5]
pairdiffs = Model.objects.filter(pk=models.OuterRef('pk')).annotate(
    pairdiff=Abs(Unnest('values')-Unnest(models.Value(x, ArrayField(models.FloatField())))), 
).values('pairdiff')
entries = Model.objects.all().annotate(
    diff=SubquerySum(pairdiffs, field='pairdiff')
).order_by('diff')

The unnest function turns each element of the values into a row. In this case it happens twice, but the two resulting columns are instantly subtracted and made positive. Still, there are as many rows per pk as there are values. These need to be summed, but that's not as easy as it sounds. The column can't be simply be aggregated. This was by far the most tricky part—even after fiddling with it for so long, I still don't quite understand why Postgres needs this indirection. Of the few options there are to make it work, I believe a subquery is the single one expressible in Django (and only as of 1.11).

Note that the above behaves exactly the same as with zip, i.e. the when one array is longer than the other, the remainder is ignored.

Further improvements

While it will be a lot faster already when you don't have to retrieve all rows anymore and loop over them in Python, it doesn't change yet that it results in a full table scan. All rows will have to be processed, every single time. You can do better, though. Have a look into the cube extension. Use it to calculate the L₁ distance—at least, that seems what you're calculating—directly with the <#> operator. That will require the use of RawSQL or a custom Expression. Then add a GiST index on the SQL expression cube("values"), or directly on the field if you're able to change the type from float[] to cube. In case of the latter, you might have to implement your own CubeField too—I haven't found any package yet that provides it. In any case, with all that in place, top-N queries on the lowest distance will be fully indexed hence blazing fast.