|
|
12-01-2023, 05:01 PM
|
|
Forum gadfly
|
|
Join Date: Feb 2011
Location: In your head
Gender: Male
|
|
Re: In Which We Brag About Our Petty Accomplishments
That is so petty it's goddamn comedy gold. Gold, Jerry, that's gold.
__________________
"Have no respect whatsoever for authority; forget who said it and instead look what he starts with, where he ends up, and ask yourself, "Is it reasonable?""
- Richard P. Feynman
|
12-01-2023, 09:38 PM
|
|
California Sober
|
|
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
|
|
Re: In Which We Brag About Our Petty Accomplishments
Quote:
Originally Posted by seebs
okay, i did this nearly 30 years ago, but i only found out recently
The ISO programming language standard for the C programming language has a sentence in it that I'm pretty sure is there to tell me, personally, to stop.
Quote:
When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another.
|
What this sentence does is say that, if you are specifying a comparison function to be used to compare two items in an array to sort them, your comparison function must make the same decision no matter where they are in the array.
Why would you say that?
Because, a few years before this language showed up, someone used the fact that this wasn't specified to write a program which attempted to sort an array by position-in-this-array. And there was debate over whether this was permissible or valid. And as a result, the language spec was modified to state specifically that you were not allowed to do that.
I've been smug for some time about the fact that several programming communities have acquired a :seebsno: emoji, but this is a whole different tier.
|
If you had a comparison function that did that, you could make every sort a stable sort. Was that the idea? Why didn't they like it, just too impractical to do?
|
12-02-2023, 07:54 AM
|
God Made Me A Skeptic
|
|
Join Date: Jul 2004
Location: Minnesota
|
|
Re: In Which We Brag About Our Petty Accomplishments
The rationale for "we don't think this is allowed" is that a common implementation for sorts is basically to copy the current "pivot" element you're comparing things to out of the array, at which point, the comparison-by-address is undefined behavior. (Curiously, the C99 spec actually prohibits this also!)
The deeper problem, though, is that sorting algorithms are not always exactly just the simplest possible quicksort, and if you moved an item to a new position, "sort by its position in the array" will now be sorting it by that new position. It's not "sort by the position it started in", but "sort by the position it's in now". More subtly, some algorithms can involve repeating a comparison in some contexts, and if you get different results comparing two elements depending on their positions, you can end up with the algorithm just entirely breaking.
So the basic issue is: If you can't trust that the comparison function really is comparing the values, you can't trust that arbitrary sort algorithms will work without blowing up.
__________________
Hear me / and if I close my mind in fear / please pry it open
See me / and if my face becomes sincere / beware
Hold me / and when I start to come undone / stitch me together
Save me / and when you see me strut / remind me of what left this outlaw torn
|
12-02-2023, 12:51 PM
|
|
Admin
|
|
Join Date: Apr 2004
Location: Ypsilanti, Mi
Gender: Male
|
|
Re: In Which We Brag About Our Petty Accomplishments
Thanking that post to mask what was really happening in my brain when I read it.
|
12-02-2023, 03:44 PM
|
|
Forum gadfly
|
|
Join Date: Feb 2011
Location: In your head
Gender: Male
|
|
Re: In Which We Brag About Our Petty Accomplishments
Quote:
Originally Posted by seebs
So the basic issue is: If you can't trust that the comparison function really is comparing the values, you can't trust that arbitrary sort algorithms will work without blowing up.
|
I would read this sort of post every day if I could.
__________________
"Have no respect whatsoever for authority; forget who said it and instead look what he starts with, where he ends up, and ask yourself, "Is it reasonable?""
- Richard P. Feynman
|
12-03-2023, 01:38 AM
|
|
Shitpost Sommelier
|
|
|
|
Re: In Which We Brag About Our Petty Accomplishments
I got two sets of drill bits out of clamshells without cutting myself.
__________________
Peering from the top of Mount Stupid
|
12-03-2023, 05:56 PM
|
|
angry white woman
|
|
Join Date: Feb 2005
Gender: Female
|
|
Re: In Which We Brag About Our Petty Accomplishments
Quote:
Originally Posted by seebs
The rationale for "we don't think this is allowed" is that a common implementation for sorts is basically to copy the current "pivot" element you're comparing things to out of the array, at which point, the comparison-by-address is undefined behavior. (Curiously, the C99 spec actually prohibits this also!)
The deeper problem, though, is that sorting algorithms are not always exactly just the simplest possible quicksort, and if you moved an item to a new position, "sort by its position in the array" will now be sorting it by that new position. It's not "sort by the position it started in", but "sort by the position it's in now". More subtly, some algorithms can involve repeating a comparison in some contexts, and if you get different results comparing two elements depending on their positions, you can end up with the algorithm just entirely breaking.
So the basic issue is: If you can't trust that the comparison function really is comparing the values, you can't trust that arbitrary sort algorithms will work without blowing up.
|
I have no idea what it is you do for a living but equal kudos to it YOU ROCK MY EXISTENCE!! for making me feel inferior and fuck you too for making me feel inferior.
__________________
What are sleeping dreams but so much garbage?~ Glen’s homophobic newsletter
|
12-03-2023, 08:10 PM
|
God Made Me A Skeptic
|
|
Join Date: Jul 2004
Location: Minnesota
|
|
Re: In Which We Brag About Our Petty Accomplishments
i am a programmer, mostly in the "weird high-performance shit" category. i currently do database internals, which is A Lot Of Weird Bullshit.
__________________
Hear me / and if I close my mind in fear / please pry it open
See me / and if my face becomes sincere / beware
Hold me / and when I start to come undone / stitch me together
Save me / and when you see me strut / remind me of what left this outlaw torn
|
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
|
|
Thread Tools |
|
Display Modes |
Linear Mode
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
All times are GMT +1. The time now is 05:41 AM.
|
|
|
|