Go Back   Freethought Forum > The Amphitheater > The Atrium

Reply
 
Thread Tools Display Modes
  #1176  
Old 12-01-2023, 05:01 PM
-FX-'s Avatar
-FX- -FX- is offline
Forum gadfly
 
Join Date: Feb 2011
Location: In your head
Gender: Male
Posts: MMXIII
Blog Entries: 1
Default 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
Reply With Quote
  #1177  
Old 12-01-2023, 09:38 PM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is offline
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXXI
Images: 66
Default Re: In Which We Brag About Our Petty Accomplishments

Quote:
Originally Posted by seebs View Post
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.

:mindblow:

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?
__________________
:kiwf::smurf:
Reply With Quote
Thanks, from:
JoeP (12-01-2023)
  #1178  
Old 12-02-2023, 07:54 AM
seebs seebs is online now
God Made Me A Skeptic
 
Join Date: Jul 2004
Location: Minnesota
Posts: VMMCMLXVII
Images: 1
Default 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
Reply With Quote
Thanks, from:
BrotherMan (12-03-2023), Crumb (12-04-2023), Ensign Steve (12-02-2023), viscousmemories (12-02-2023)
  #1179  
Old 12-02-2023, 12:51 PM
viscousmemories's Avatar
viscousmemories viscousmemories is offline
Admin
 
Join Date: Apr 2004
Location: Ypsilanti, Mi
Gender: Male
Posts: XXXDCCXLVI
Blog Entries: 1
Images: 9
Default 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.

:homdrool:
Reply With Quote
Thanks, from:
Ensign Steve (12-02-2023), JoeP (12-03-2023), Sock Puppet (12-04-2023)
  #1180  
Old 12-02-2023, 03:44 PM
-FX-'s Avatar
-FX- -FX- is offline
Forum gadfly
 
Join Date: Feb 2011
Location: In your head
Gender: Male
Posts: MMXIII
Blog Entries: 1
Default Re: In Which We Brag About Our Petty Accomplishments

Quote:
Originally Posted by seebs View Post
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
Reply With Quote
  #1181  
Old 12-03-2023, 01:38 AM
Kamilah Hauptmann's Avatar
Kamilah Hauptmann Kamilah Hauptmann is online now
Shitpost Sommelier
 
Join Date: Mar 2016
Posts: XVMCMXXIII
Default 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

:AB: :canada:
Reply With Quote
Thanks, from:
BrotherMan (12-03-2023), ceptimus (12-03-2023), JoeP (12-03-2023), LarsMac (12-04-2023), ShottleBop (12-03-2023), Sock Puppet (12-04-2023)
  #1182  
Old 12-03-2023, 05:56 PM
Miss Shelby's Avatar
Miss Shelby Miss Shelby is offline
angry white woman
 
Join Date: Feb 2005
Gender: Female
Posts: MMMCDLI
Default Re: In Which We Brag About Our Petty Accomplishments

Quote:
Originally Posted by seebs View Post
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
Reply With Quote
  #1183  
Old 12-03-2023, 08:10 PM
seebs seebs is online now
God Made Me A Skeptic
 
Join Date: Jul 2004
Location: Minnesota
Posts: VMMCMLXVII
Images: 1
Default 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
Reply With Quote
Thanks, from:
Ensign Steve (12-04-2023)
Reply

  Freethought Forum > The Amphitheater > The Atrium


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

 

All times are GMT +1. The time now is 05:41 AM.


Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Page generated in 0.73018 seconds with 15 queries