Finding max element of an array using two heap-allocated arrays and a bubble sort
-
As seen on reddit: https://github.com/tangxunye/android_vendor_qcom_proprietary/blob/e0666c398903d38e72aeda7042ec2836cd3dba68/mm-camera/mm-camera2/media-controller/modules/isp/hw/modules/rolloff/mlro_to_plro/mlro_utils.c#L52
Its from Qualcomm so it must be good code, right?
There are plenty of WTFs to go around here. But I think my favorite part is that the function parameters are described in loving detail (
double *x ---> input one-dimensional array
) but the descriptions of what the functions actually do are either useless or missing entirely. I don't suppose you'd want to mention thatbubblesort
sorts the input in reverse order or anything.
-
What's worse is that the function returns the absolute value of the element with the largest absolute value, not the largest element. (If the array is { 0, -2, 1 }, it returns 2 and not 1.)
It's still the wrong way to do it, of course. There's no need for either of the malloc calls. (Even if you do it by sorting the malloc'ed array, you don't need the array of indices, since that's just used to find and take the absolute value of the original element with the largest absolute value, but you already have that in the zeroth element of the sorted copy.)
All in all, a mega , but there's also the of assuming anything about the quality of code produced by a large corporation. After all, I once worked at a large corporation whose production codebase included a file called
evildead.c
where all the variables and local functions had names related to Romero's film. Even stripped of that , the code was just awful for many other reasons, notably that it was clearly intended to demonstrate that Real Programmers can write Fortran code in any language, except that it had been written by a bad Real Programmer.
-
@jnz said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
Its from Qualcomm so it must be good code, right?
Good one
Just look at one of the monthly Android security bulletins and check how many of the critical vulnerabilities were found in one of the Qualcomm drivers. Also, since when do hardware companies hire competent developers?
-
@asdf I don't know, let's ask Realtek for example:
Best viewed at 800x600 with IE 6.0 or Netscape 7.02 or Mozilla Firefox 1.0.6 or higher.
Oh.
-
@deadfast said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
Realtek
I made the mistake of visiting their website once. Never again!
-
@steve_the_cynic The function is called absmax, so I guess returning the maximum absolute value is deliberate (making 2 the correct return value in your example). Seems like a really edge case, but why not. The implementation is a huge , though, on that we can agree.
-
@asdf said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@deadfast said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
Realtek
I made the mistake of visiting their website once. Never again!
I can see why:
Best viewed at 800x600 with IE 6.0 or Netscape 7.02 or Mozilla Firefox 1.0.6 or higher.
-
Error mem alloc for l
fuck you too
-
@jnz said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
As seen on reddit: https://github.com/tangxunye/android_vendor_qcom_proprietary/blob/e0666c398903d38e72aeda7042ec2836cd3dba68/mm-camera/mm-camera2/media-controller/modules/isp/hw/modules/rolloff/mlro_to_plro/mlro_utils.c#L52
Its from Qualcomm so it must be good code, right?
There are plenty of WTFs to go around here. But I think my favorite part is that the function parameters are described in loving detail (
double *x ---> input one-dimensional array
) but the descriptions of what the functions actually do are either useless or missing entirely. I don't suppose you'd want to mention thatbubblesort
sorts the input in reverse order or anything.Without reading the linked code:
double absmax(double *a, size_t n) { double max = 0; double *z = a + n; while( a < z ) { if( *a > max ) { max = *a; else if( -*a > max ) { max = -*a; } a++; } return max; }
-
@pleegwat said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
Without reading the linked code:
I'd use a temporary that holds the abs'd version of the value in the array, but would otherwise do pretty much the same. (It's probably also best to set max to -1 or some other reasonable sentinel initially.)
-
@dkf Yeah, I'd forgot that this function would never return negative on non-empty input, so that'd be sensible when passed an empty list.
And using an intermediate would've given me an opportunity to write
val = fabs(*a++)
and tick some people off.
-
@pleegwat said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
fabs
Fabulous!
-
@asdf said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
Qualcomm drivers
They're the ones responsible for Atheros, right? It's rather difficult to get their stuff orkng on Windows 7 because apparently I have to go to the OEM.
-
@pleegwat said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@jnz said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
As seen on reddit: https://github.com/tangxunye/android_vendor_qcom_proprietary/blob/e0666c398903d38e72aeda7042ec2836cd3dba68/mm-camera/mm-camera2/media-controller/modules/isp/hw/modules/rolloff/mlro_to_plro/mlro_utils.c#L52
Its from Qualcomm so it must be good code, right?
There are plenty of WTFs to go around here. But I think my favorite part is that the function parameters are described in loving detail (
double *x ---> input one-dimensional array
) but the descriptions of what the functions actually do are either useless or missing entirely. I don't suppose you'd want to mention thatbubblesort
sorts the input in reverse order or anything.Without reading the linked code:
double absmax(double *a, size_t n) { double max = 0; double *z = a + n; while( a < z ) { if( *a > max ) { max = *a; else if( -*a > max ) { max = -*a; } a++; } return max; }
First thought: oh wow that's evil
Second thought: wait, else can't be inside an if, it has to be after an if
Third thought: oh, there's an opening brace on the while. It's just a typo. :(
-
@tsaukpaetra said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@asdf said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
Qualcomm drivers
They're the ones responsible for Atheros, right? It's rather difficult to get their stuff orkng on Windows 7 because apparently I have to go to the OEM.
I remember having issues with them in the early days of running Ubuntu, as my laptop at the time had Atheros wifi and there were no drivers. Although I also had the fun choice of running Ubuntu and have non-working wifi or running Windows and have non-working keyboard. Keyboards ceasing to work properly on my laptops being a recurring theme it seems...
-
@ben_lubar said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@pleegwat said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@jnz said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
As seen on reddit: https://github.com/tangxunye/android_vendor_qcom_proprietary/blob/e0666c398903d38e72aeda7042ec2836cd3dba68/mm-camera/mm-camera2/media-controller/modules/isp/hw/modules/rolloff/mlro_to_plro/mlro_utils.c#L52
Its from Qualcomm so it must be good code, right?
There are plenty of WTFs to go around here. But I think my favorite part is that the function parameters are described in loving detail (
double *x ---> input one-dimensional array
) but the descriptions of what the functions actually do are either useless or missing entirely. I don't suppose you'd want to mention thatbubblesort
sorts the input in reverse order or anything.Without reading the linked code:
double absmax(double *a, size_t n) { double max = 0; double *z = a + n; while( a < z ) { if( *a > max ) { max = *a; else if( -*a > max ) { max = -*a; } a++; } return max; }
First thought: oh wow that's evil
Second thought: wait, else can't be inside an if, it has to be after an if
Third thought: oh, there's an opening brace on the while. It's just a typo. :(
Huh, yeah, I missed a brace. If you want compact and evil:
#define MAX(a,b) ((a)>(b)?(a):(b)) #define ABS(a) ((a)>0?(a):(-a)) double absmax(double *a, size_t n) { double max = -1.0; double *z = a + n; do max = MAX(max, ABS(*a)) while (++a<z); return max; }
Though that doesn't work on empty lists.
-
@pleegwat said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
Though that doesn't work on empty lists.
You get a nice sentinel
-1.0
from an empty list, which might be acceptable.
-
@dkf said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@pleegwat said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
Though that doesn't work on empty lists.
You get a nice sentinel
-1.0
from an empty list, which might be acceptable.No, you get a nice UB from dereferencing
a
. It'sdo while
, notwhile
.
-
@nedfodder Hmm, missed that. :(
-
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@steve_the_cynic The function is called absmax, so I guess returning the maximum absolute value is deliberate (making 2 the correct return value in your example). Seems like a really edge case, but why not. The implementation is a huge , though, on that we can agree.
I'm sure it is deliberate, but it's also ambiguous. Is it "the absolute value of the max" or the "max of the absolute values". (And could we end up with
absmax
andmaxabs
to cover those two cases? And the subsequent endless fun when people choose the wrong one...)I suppose it could be worse. They could have written it to return the unmodified value of the element with the largest absolute value. Ugh.
-
@steve_the_cynic said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
maxabs
Sounds like a name of a protein shake.
-
@steve_the_cynic said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
I'm sure it is deliberate, but it's also ambiguous. Is it "the absolute value of the max" or the "max of the absolute values"
Except you'd have to be possibly-even-insaner-than-this to write an entire new function to do
abs(max(arr,sz))
maxabs() is an insane implementation of a reasonable, potentially useful function.
absmax() is not worthy of being a separate functionAlso if you don't mind iterating over the array twice
maxabs(double *arr,size_t sz) {
double mn = min(arr,sz);
double mx = max(arr,sz);
return (mx > -mn) ? mx : mn;
}
-
@gwowen said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
return (mx > -mn) ? mx : mn;
return (mx > -mn) ? mx : -mn; // Obviously
-
@gwowen You can extract min and max in a single iteration with a dedicated function.
-
@khudzlin Yeah. OpenCV has one that does exactly that for its matrix type. I was assuming you had library functions for min() and max() [e.g. something like std::min_element() and std::max_element() that returns a value rather than an iterator, ]
-
@gwowen Nothing stops you from coding that function, even if you have access to library functions.
-
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
You can extract min and max in a single iteration with a dedicated function.
Yeah! Just bubblesort the data and pick off the values at either end of the array…
-
@dkf said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
You can extract min and max in a single iteration with a dedicated function.
Yeah! Just bubblesort the data and pick off the values at either end of the array…
You can do it in linear time, though.
-
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
You can do it in linear time, though.
-
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@dkf said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
You can extract min and max in a single iteration with a dedicated function.
Yeah! Just bubblesort the data and pick off the values at either end of the array…
You can do it in linear time, though.
thanks to quantum bogo sort i can do it in constant time!~
-
@jnz there is nothing special about this. I bet the original code was written by a scientist in MATLAB and an engineer was tasked to translate a large block of code (including this) to C for a device. He may have been required to not change any algorithm, being a lowly engineer to follow scientists. Scientists write shitty and unoptimized code, that is their jerb. The real is the mindless conversion. Any senior engineer with enough wits and leeway, will get their code and translate it while keeping the spirits of it only.
-
@pleegwat said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
double absmax(double *a, size_t n) { double max = 0; double *z = a + n; while( a < z ) { if( *a > max ) { max = *a; else if( -*a > max ) { max = -*a; } a++; } return max; }
This code is clear, straightforward, idiomatic C. We can't have that. We all know that Functional Programming is the future. It needs more Functional:
#include <math.h> #include <stdlib.h> static double reduce(const double *arr, size_t n, double (*f)(double, double), double acc) { for (size_t i = 0; i < n; i++) acc = f(acc, arr[i]); return acc; } static double max(double a, double b) { return (a > b) ? a : b; } static double absmax_step(double acc, double x) { return max(acc, fabs(x)); } double absmax(const double *arr, size_t n) { return reduce(arr, n, absmax_step, 0.0); }
That ought to do it.
-
@accalia said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@dkf said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
You can extract min and max in a single iteration with a dedicated function.
Yeah! Just bubblesort the data and pick off the values at either end of the array…
You can do it in linear time, though.
thanks to quantum bogo sort i can do it in constant time!~
Doesn't quantum bogo sort still take linear time because you have to look at the whole array before you decide whether to destroy the entire universe?
-
@ben_lubar said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@accalia said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@dkf said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
You can extract min and max in a single iteration with a dedicated function.
Yeah! Just bubblesort the data and pick off the values at either end of the array…
You can do it in linear time, though.
thanks to quantum bogo sort i can do it in constant time!~
Doesn't quantum bogo sort still take linear time because you have to look at the whole array before you decide whether to destroy the entire universe?
no. you use quantum processes to permutate the array and determine if the permutation is sorted. and quamtum takes constant time.
:-P
-
@accalia Sort of: you actually check all possible permutations simultaneously, which collapses the quantum waveform into the sorted state ;)
-
@raceprouk hey! iy's quantum it works however you want it to because it's quantum
:-P
-
@accalia but does it contain solace?
-
@arantor said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@accalia but does it contain solace?
yes, but only an infinitesimal amount.
-
@accalia That's always bugged me, how 'quantum leap' is used to mean 'massive improvement'. After all, a quantum is the smallest possible unit: you need billions of them just to get something miniscule.
-
@raceprouk said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
quantum leap
-
@accalia Oh, boy!
-
@gwowen said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@gwowen said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
return (mx > -mn) ? mx : mn;
return (mx > -mn) ? mx : -mn; // Obviously
Curiously, no, that doesn't work either. If all the values are the same positive value, it will return -mn, and that will be negative because mn is positive. And you can't just change the > to a >= because then it doesn't work if they are all the same negative value.
-
@raceprouk said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@accalia That's always bugged me, how 'quantum leap' is used to mean 'massive improvement'. After all, a quantum is the smallest possible unit: you need billions of them just to get something miniscule.
It means a jump in improvement as opposed to a continuous process.
-
-
@raceprouk Yes, that's what it's turned into.
And it makes sense. Except for people who can't grasp relative size and distances.
-
@raceprouk said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
And then the murders began.
Once again, your signature works wonderfully.
-
@gwowen said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
if you don't mind iterating over the array twice
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
You can extract min and max in a single iteration with a dedicated function.
Iterating it twice is still O(n). ¯\_(ツ)_/¯
/"Big-O is the only performance metric that anyone should need"
-
@raceprouk said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@accalia That's always bugged me, how 'quantum leap' is used to mean 'massive improvement'. After all, a quantum is the smallest possible unit: you need billions of them just to get something miniscule.
The leap from classical physics to quantum physics is hardly a minuscule leap, though.
-
@anotherusername said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
@gwowen said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
if you don't mind iterating over the array twice
@khudzlin said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
You can extract min and max in a single iteration with a dedicated function.
Iterating it twice is still O(n). ¯\_(ツ)_/¯
/"Big-O is the only performance metric that anyone should need"
And hash tables are pointless because they are only as efficient as the mechanism they use to resolve conflicts.
-
@pleegwat said in Finding max element of an array using two heap-allocated arrays and a bubble sort:
And hash tables are pointless because they are only as efficient as the mechanism they use to resolve conflicts.
I've just invented this amazing new hash table that resolves conflicts using ... another hash table! Its O(1) all the way down.