7 ms·

I'm confused, so the comparison function can modify the list? I thought most sorting algorithms assumed the contents of the list was constant. Why would I want

I'm confused, so the comparison function can modify the list? I thought most sorting algorithms assumed the contents of the list was constant. Why would I want my comparator to ever modify the list under sort?

danlark 4y ago
You don't, it's just not disallowed :)
- infogulch 4y ago
  "because it prevents the user from writing a comparison function that modifies the list while sorting" is not a reason I would expect to prefer rust, and yet here we are.
  - mbrubeck 4y ago
    It's possible in Rust too, but only for a subset of element types: those that support shared mutation (also known as "internal mutation"). For example, a type containing an `AtomicU32` or a `Mutex<T>` or a `Cell<T>` could have an `Ord::cmp` implementation that alters its value, and the compiler will not prevent this.
    - orlp 4y ago
      Yes, I had a nasty bug in an initial version of glidesort where I (naively) assumed that I could create a temporary copy of an element by doing a memcpy and call the comparison function on this temporary copy a bunch of times before throwing it away, since I assumed the comparison function would not mutate the copy. Unfortunately interior mutability means this would lead to potential double drops, and it was just not sound.
  - account42 4y ago
    The comparison operator is not actually mutating the list, which would not be allowed in C++ either. Instead it is dynamically generating the < comparison operator for the elements in the list based on the order for which elements it is evaluated. The order for two elements remains fixed once examined and in the end it always ends up with a valid totally ordered comparison operator. The only thing required for this to work is that the comparison operator can have mutable state and that the same shared state is used for all comparisons in the sorting algorithm (asided from thread-safety so you'd need adjustments for a parallel sort).
deleted 4y ago
[deleted]
slavboj 4y ago
An "accessed at" field is a trivial use case.
jmalicki 4y ago
If you examine the modification more closely, it is just finding the list that would exhibit worst case performance - once created, that list would always exhibit the worst case as a constant list. Once you have the resulting list, the indices are sorted, then assigning each num_solid value to that index would result in the list being constant, and then could be sorted to give such worst case behavior. I wish the article was more clear on this.
account42 4y ago
Technically the list is not being modified but the comparison operator is dynamically determining the order of elements when the sorting algorithm checks them. This is done in a way so that the order of pairs that have already been checked previously remains fixed and it results in a valid totally ordered comparison operator in the end - but the order it ends up with depends on the sorting algorithm.

danlark 4y ago

You don't, it's just not disallowed :)

infogulch 4y ago
"because it prevents the user from writing a comparison function that modifies the list while sorting" is not a reason I would expect to prefer rust, and yet here we are.
- mbrubeck 4y ago
  It's possible in Rust too, but only for a subset of element types: those that support shared mutation (also known as "internal mutation"). For example, a type containing an `AtomicU32` or a `Mutex<T>` or a `Cell<T>` could have an `Ord::cmp` implementation that alters its value, and the compiler will not prevent this.
  - orlp 4y ago
    Yes, I had a nasty bug in an initial version of glidesort where I (naively) assumed that I could create a temporary copy of an element by doing a memcpy and call the comparison function on this temporary copy a bunch of times before throwing it away, since I assumed the comparison function would not mutate the copy. Unfortunately interior mutability means this would lead to potential double drops, and it was just not sound.
- account42 4y ago
  The comparison operator is not actually mutating the list, which would not be allowed in C++ either. Instead it is dynamically generating the < comparison operator for the elements in the list based on the order for which elements it is evaluated. The order for two elements remains fixed once examined and in the end it always ends up with a valid totally ordered comparison operator. The only thing required for this to work is that the comparison operator can have mutable state and that the same shared state is used for all comparisons in the sorting algorithm (asided from thread-safety so you'd need adjustments for a parallel sort).

deleted 4y ago

[deleted]

slavboj 4y ago

An "accessed at" field is a trivial use case.

jmalicki 4y ago

If you examine the modification more closely, it is just finding the list that would exhibit worst case performance - once created, that list would always exhibit the worst case as a constant list. Once you have the resulting list, the indices are sorted, then assigning each num_solid value to that index would result in the list being constant, and then could be sorted to give such worst case behavior. I wish the article was more clear on this.

account42 4y ago

Technically the list is not being modified but the comparison operator is dynamically determining the order of elements when the sorting algorithm checks them. This is done in a way so that the order of pairs that have already been checked previously remains fixed and it results in a valid totally ordered comparison operator in the end - but the order it ends up with depends on the sorting algorithm.