Hacker News Reader

Comment by misja111 | Hacker News Reader

Impressive, but I wonder what the practical benefit will be. How often do you need to sort an array of numbers? In practice you almost always want to sort an array of objects based on one of their properties.

View on HN

> How often do you need to sort an array of numbers? In practice you almost always want to sort an array of objects based on one of their properties.

And? If your objects are immovable then one level of indirection (pointers or indices) solves that. If your objects are moveable, then there's many (!) times where having your container sorted will improve performance.

I don't see how you can add that level of indirection if you can only sort an array of numbers. Let's say you have a Person object with property 'age' which is an Int. I can put the Person's ages into an Int Array and sort that. Where to add this indirection to get to the sorted array of Person objects?

1. Have an immutable container of Persons named `persons`

2. Have another container named `indices` representing the index or iterator into your Persons container

In C++:

3. `std::sort(begin(indices), end(indices), [&](int lhs, int rhs)->bool{ return persons[lhs].age() < persons[rhs].age(); });`

I don't know Java but I am sure there are many ways to do it in Java.

Eh yes, this works, but you are not using Arrays.intSort here. Which means that the optimizations that the article is about won't apply. intSort (or any other of the sorts in the article) works purely on an Array of Ints, moving them around and comparing them to each other.

It's quite hard to come up with something that we could use in every day programming that will benefit from the new optimizations.

Hash their properties

And... then? You would essentially need a homomorphic hash function for that to work.

I.e.: [ a, b, c ].map(hash) produces the same order.

where hash: A -> B, where p, q in A. p < q => x, y in B. x < y.

True and even then, you would only have a sorted list of the object's properties. But not a sorted list of the objects themselves.

`ord` is a hash function which preserves alphabetical ordering, etc.

It's not that hard, in many cases, to find an `f : DataDomain -> Int` st. `f(x1) < f(x2)` where `hash(x1) < hash(x2)`

sorting arrays of numbers is very often ultimately used under the hood of all the nice abstractions

Sorting an array of pointers is sorting by numbers.

Sure, but what use is that? You will have your objects sorted by the absolute value of their pointer. I guess this means you'll have your objects sorted by the order in which they are allocated in the heap. Cool, but not very useful.

You can do a sorted array of pointers and later check if a specific pointer is in it with binary search, etc.

Not in Java you can't.

Reply on news.ycombinator.com