The Daily WTF: Curious Perversions in Information Technology

Julia · 2013-11-11 Reply Admin

ffrriisstt!!

More seriously, isn't that O(n^2 log n) as he's also re-sorting the arrays on every iteration?

2013-11-11 Reply Admin

I love the ku klux klan var named there, makes me want to use also SS and CCCP and _666 as var names

2013-11-11 Reply Admin

That code is really racist.

2013-11-11 Reply Admin

Hey, at least it uses the minimal amount of memory for the array :)

2013-11-11 Reply Admin

This has also been refactored to remove the inefficient jjj loop, so it could have been worse.

2013-11-11 Reply Admin

Julia:
More seriously, isn't that O(n^2 log n) as he's also re-sorting the arrays on every iteration?

Hm. I don't think so. Should still be O(n^2 + n*log(n)) = O(n^2), shouldn't it?

2013-11-11 Reply Admin

Looks like a piece of some Ku Klux Klan submarine firmware. You need to understand that the Klan doesn't have a concept of efficiency - if you have slaves to do your bidding there's no point in optimizing to do less work. On the contrary - you need to make sure your slaves are slaving enough - and I think they don't distinguish between people and computers.

I hope snoofle secretly switched their torpedo launch calls to autodestruct!

Btw, it seems that Akismet may be a klan member.. so be careful.

2013-11-11 Reply Admin

I didn't study it closely enough to figure out exactly what the code is doing, but I don't think I've ever had the need to resize an array since I started programming C# 13 years ago so I'd be surprised if it couldn't be done better with List<t> and/or IDictionary<t>

2013-11-11 Reply Admin

Oh my, there is so much wrong with this gem, you could have filled a whole week with it.

Proves again: real obfuscaters need no stinking GOTO to make code harmful.

2013-11-11 Reply Admin

MightyM:
Hey, at least it uses the minimal amount of memory for the array :)

And no memory wasted on variable names either.

2013-11-11 Reply Admin

Julia:
ffrriisstt!!
More seriously, isn't that O(n^2 log n) as he's also re-sorting the arrays on every iteration?

There are sorting implementations that run significantly faster than O (n log n) if the array is already sorted. For example, the MacOS X implementation checks for a sequence of items in either ascending or descending order both at the begin and the end of the array, and if there is not much else then the sort is in O (n). So adding one item at the end and sorting, or changing a random item and sorting, is O (n).

Still horrible.

ubersoldat · 2013-11-11 Reply Admin

On the plus side, at least the kid read the documentation and didn't reinvent the wheel with custom Sort, Resize, etc.

Auction_God · 2013-11-11 Reply Admin

Tim:
I didn't study it closely enough to figure out exactly what the code is doing, but I don't think I've ever had the need to resize an array since I started programming C# 13 years ago so I'd be surprised if it couldn't be done better with List<t> and/or IDictionary<t>

Sure you have. You just didn't do it yourself. You let C# do it for you. And since you obviously don't understand that, your code may be more inefficient than you realize. Each of those collections has a parameter on the constructor to specify the initial size. You can also specify how many entries to add when they are expanded.

2013-11-11 Reply Admin

Tim:
I didn't study it closely enough to figure out exactly what the code is doing, but I don't think I've ever had the need to resize an array since I started programming C# 13 years ago so I'd be surprised if it couldn't be done better with List<t> and/or IDictionary<t>

Or even better, using Linq...

Nutster · 2013-11-11 Reply Admin

just me:
MightyM:
Hey, at least it uses the minimal amount of memory for the array :)

And no memory wasted on variable names either.

Well, no imagination, anyway. Mind you, non-descriptive variable names are the least of the concerns with this hunk of code.

2013-11-11 Reply Admin

If there are variables ii, xx, yy, and kkk... does that mean there is jj - ww, zz, and aaa - jjj as well? Scary...

Oh wait, there is a dm variable as well - maybe there is ia-iz, etc. Somehow though I think that one is supposed to be more descriptive then the others, rather than an iteration.

2013-11-11 Reply Admin

I'm guessing that the author simply found it easier to read 3 identical letters in a row than the character on it's own.

So, maybe its a some sort of coping mechanism for some kind of dyslexia.

That doesn't excuse the fact that the code is also terrible in every other way.

2013-11-11 Reply Admin

TRWTF is...:
I'm guessing that the author simply found it easier to read 3 identical letters in a row than the character on it's own.

I'd say he read somewhere that single-letter variable names are Bad Practice.

2013-11-11 Reply Admin

just me:
TRWTF is...:
I'm guessing that the author simply found it easier to read 3 identical letters in a row than the character on it's own.

I'd say he read somewhere that single-letter variable names are Bad Practice.

so indexing through a jagged array, you should use, "column" and "row" as your variable names, unless you already used them for something else, then you use "column2"...

For indexing loops, you use a single letter, and stick to a convention so the variable names are always available in that scope, then you can tell how many levels deep you are.

And if the code inside the loop is too big to track what level deep you are, then it's doing too much.

2013-11-11 Reply Admin

The algorithm is way nasty. Since it goes round n times sorting each time the cost is as follows

order N^2/2 for the resizing worst case order N(NlogN) for the sorting but assuming a non-clever sort algorithm order N^2 or with a clever sort actually NlogN for working out where to insert but N^2/4 for the insertion step (because we copy half the array again).

even worse the memory cost is order N^2/2 since you are unlikely to have had a garbage collection during the entire process. A very popular memory mistake.

2013-11-11 Reply Admin

Tom:
Or even better, using Linq...

Troll? I'll assume you know what you're talking about and fill in the rest:

...Linq IEnumerable/IQueryable

There is much more to Linq than most people surmise. Tell someone about compiling a DSL using the Linq Expression library and they still seem to think:

1  From item In items
2  Where item.IsQuux
3  Select item.Bazz

DrPepper · 2013-11-11 Reply Admin

Paul Neumann:
There is much more to Linq than most people surmise.

I once wrote a program to produce a list of prime numbers in a single linq statement:

var mx=1000000;
var query = (from two in Enumerable.Range(2,1) select two)
             .Union (from candidate in Enumerable.Range(3, mx-2).Where(p => p % 2 != 0) select candidate).AsParallel()
                      .Except ((from candidate in Enumerable.Range(3, mx-2).Where(p => p % 2 != 0).AsParallel()
                                from q1 in Enumerable.Range(3, (int)Math.Sqrt(candidate)).Where(p => p % 2 != 0).AsParallel()
                                where q1 < candidate && candidate % q1 == 0
                                select candidate)
             .Distinct()).OrderBy(x => x);
 
 
foreach (int i in query)
      Console.WriteLine(i);

Coyne · 2013-11-11 Reply Admin

belzebub:
Looks like a piece of some Ku Klux Klan submarine firmware. You need to understand that the Klan doesn't have a concept of efficiency - if you have slaves to do your bidding there's no point in optimizing to do less work. On the contrary - you need to make sure your slaves are slaving enough - and I think they don't distinguish between people and computers.
I hope snoofle secretly switched their torpedo launch calls to autodestruct!

Btw, it seems that Akismet may be a klan member.. so be careful.

I suspect the kkk really stands for "Katzenjammer Kids Kludge". There's missing definitions here, but my best guess is that it doesn't even work...after wasting all that CPU.

chubertdev · 2013-11-11 Reply Admin

Probably a similar situation to this:

http://thedailywtf.com/Articles/Coded-to-the-Letter.aspx

2013-11-11 Reply Admin

Judging from the code alone there is no way to judge whether the if statement could indicate a rare event.

The damn code is unreadable at the least, such code typically translate from research paper directly and that could explain why.

chubertdev · 2013-11-11 Reply Admin

Quick way to fix the code:

/*
...
*/

2013-11-11 Reply Admin

DrPepper:
Paul Neumann:
There is much more to Linq than most people surmise.
I once wrote a program to produce a list of prime numbers in a single linq statement:[...]

Good job.

2013-11-11 Reply Admin

DrPepper:
Paul Neumann:
There is much more to Linq than most people surmise.
I once wrote a program to produce a list of prime numbers in a single linq statement:[...]

Good job.

Clicked wrong preview, and Fuck You akismet!

2013-11-11 Reply Admin

DrPepper:
Paul Neumann:
There is much more to Linq than most people surmise.
I once wrote a program to produce a list of prime numbers in a single linq statement:[...]

Good job.Die akismet, die.

2013-11-11 Reply Admin

Andrew Au:
Judging from the code alone there is no way to judge whether the if statement could indicate a rare event.
The damn code is unreadable at the least, such code typically translate from research paper directly and that could explain why.

Just wondering, which kinds of research journals do you normally read that contain code like this? The ones I know rather don't deal with such trivialities like array resizing at all and focus on the higher level picture.

Oh, you don't read any? Just some unfounded academia bashing? Thought so.

2013-11-11 Reply Admin

foo:
The ones I know rather don't deal with such trivialities like array resizing at all and focus on the higher level picture.

And for that matter, so do I when I just use "push_back" (in C++) which does automatic resizing in amortized constant time. That's what made me wonder when the article said "Sometimes [...] you need to explicitly resize the target", doesn't C# have "push_back" or something similar?

DrPepper · 2013-11-11 Reply Admin

Paul Neumann:
DrPepper:
Paul Neumann:
There is much more to Linq than most people surmise.
I once wrote a program to produce a list of prime numbers in a single linq statement:[...]
Good job.Die akismet, die.

That's truly amazing. When people really grasp the beauty and conciseness of linq, nirvana results. Good trick with the 'let' statments. How does the linq perform when compared to just writing it out in c#? And, did you consider parallelizing it?

2013-11-11 Reply Admin

gnasher729:
Julia:
ffrriisstt!!
More seriously, isn't that O(n^2 log n) as he's also re-sorting the arrays on every iteration?

There are sorting implementations that run significantly faster than O (n log n) if the array is already sorted. For example, the MacOS X implementation checks for a sequence of items in either ascending or descending order both at the begin and the end of the array, and if there is not much else then the sort is in O (n). So adding one item at the end and sorting, or changing a random item and sorting, is O (n).

Still horrible.

The O(n^2) was the two loops, the O(log n) was the sort. So, it is actually somewhere between O(n^3) and O(n^2 log n) depending on the sort algorithm. Given this "gem", I wouldn't be surprised if the nephew re-wrote the built-in sort to a bubble sort.

Ragnax · 2013-11-11 Reply Admin

gnasher729:
For example, the MacOS X implementation checks for a sequence of items in either ascending or descending order both at the begin and the end of the array, and if there is not much else then the sort is in O (n). So adding one item at the end and sorting, or changing a random item and sorting, is O (n).
Still horrible.

That means spending O(n) up front to determine if the desired Θ(n) best case complexity of insertion sort is viable. If it is; you apply it and have spent O(2n) in total. If it is not, you can apply a proven optimal worst-case O(n log n) sorting algorithm and you'll have spent O(2n log n) in total.

Seems to me that just going for the simple O(n log n) approach directly will be faster so much more consistently that the additional overhead is simply not worth it for a general purpose sort. Am I missing something here, or is this indeed an example of Apple producing code that is "still horrible" ?

2013-11-11 Reply Admin

Ragnax:
gnasher729:
For example, the MacOS X implementation checks for a sequence of items in either ascending or descending order both at the begin and the end of the array, and if there is not much else then the sort is in O (n). So adding one item at the end and sorting, or changing a random item and sorting, is O (n).
Still horrible.

That means spending O(n) up front to determine if the desired Θ(n) best case complexity of insertion sort is viable. If it is; you apply it and have spent O(2n) in total. If it is not, you can apply a proven optimal worst-case O(n log n) sorting algorithm and you'll have spent O(2n log n) in total.

Seems to me that just going for the simple O(n log n) approach directly will be faster so much more consistently that the additional overhead is simply not worth it for a general purpose sort. Am I missing something here

Quite a bit, like how O notation works. E.g. O(2n) = O(n) and O(n) + O(n log n) = O(n log n).

2013-11-11 Reply Admin

Ragnax:
That means spending O(n) up front to determine if the desired Θ(n) best case complexity of insertion sort is viable. If it is; you apply it and have spent O(2n) in total. If it is not, you can apply a proven optimal worst-case O(n log n) sorting algorithm and you'll have spent O(2n log n) in total.
Seems to me that just going for the simple O(n log n) approach directly will be faster so much more consistently that the additional overhead is simply not worth it for a general purpose sort. Am I missing something here, or is this indeed an example of Apple producing code that is "still horrible" ?

Sure you are missing something. What you are missing is that for random data, the check whether there is a long sequence of ascending or descending elements will finish very quickly. The chance that even just five random numbers are in ascending or descending order is only on in 60. So for randomly arranged arrays, the cost is practically zero.

Now assume that the first k elements are in ascending or descending order. In that case you can sort the remaining n - k elements, then do a merge. The merge is n operations. Sorting the remaining elements takes (n - k) log (n - k) instead of n log n, so you save about k log n + n log (n / (n - k)) operations. If k is relatively small compared to n, that's about k log n + k operations. You win if n < k (log n + 1) or k < n / (log n + 1). But in the cases where you don't win, you only checked n / (log n + 1) elements to see if they were sorted.

So worst case, you do about n / (log n + 1) unnecessary operations. That's less than the usual n log n by a factor (log n)^2, so the worst case is only a tiny bit worse. The best case is incredibly much better. In practice, even sorting fully sorted arrays is not at all uncommon, while sorting arrays that were originally sorted except for a few number of changed or added elements is very common. And the worst case would be highly unusual. For example, an array of 100,000 elements where the first 9,000 elements are sorted, but not the first 10,000.

2013-11-11 Reply Admin

I once wrote an O(n**3) sorting subroutine. There is a reason why I used Fortran exponentiation syntax in this expression ^_^

It was not the first time I wrote a subroutine, but it was the first time I did sorting, and I had not heard of Knuth at the time. I was someone's nephew. I was 16 years old in first year of university.

THRWTF (the hypothetically real WTF) would have been if I had an aunt or uncle running a business, and if said relative had taken a copy of my code, and if said relative had used it unchanged. This did not happen.

By the way though, my code worked ^_^

2013-11-11 Reply Admin

There's always work to be done. Once your slaves insist that they've finished writing code, move them onto doing the dishes. One scrubs while the other dries, in the following order:

Drinking glasses first. These need to be rinsed in scalding hot water immediately after they're scrubbed and should be drip dried in order to give a clean and shiny appearance for your dinner parties.
Cutlery next. If the drying slave notices that a piece of cutlery has even one speck of dirt (say, between the prongs of a fork), it must go back in the sink to be done again.
Drinking mugs.
Plates and bowls, chopping boards and knives. At this point, the drying slave should probably start sweeping the carpet furthest from hard surfaces towards hard surfaces. If the water starts to look murky, the scrubbing slave should use it to scrub any remaining dishes that look dirtier than the water and put them back on the dirty pile before replacing the water and resuming.
Pots and pans, etc.
The benches, onto the hard surface to be swept up at a later point. At this point, the scrubbing slave should take over drying anything that isn't glassware, followed by vacuuming the areas of the carpet that the sweeping slave has swept.

By thinking of two easy jobs and two hard jobs, and alternating the two slaves so that at all times they're either doing an easy job or a hard job in the most efficient way, you're teaching them about algorithms (and hopefully a bit of multithreading). While they're doing these tasks, you'll have time to identify areas where your slaves need to refactor code. Reward the slaves who improve over time by giving them less and less hard work (eg. constantly writing/maintaining code because they're good at it, hanging clothes to dry and planting/watering for the veggie garden), and the slaves who don't improve over time by giving them more and more hard, physical work (eg. washing and drying clothes with an old-fashioned hand washing mechanism, mowing the lawn, digging holes for the veggie garden and spreading large mounds of mulch or gravel).

dkf · 2013-11-12 Reply Admin

n_slash_a:
the O(log n) was the sort

No.

OK, I'll explain. Sort is limited to O(n logn) at best; the logarithmic part actually comes from the ability to recursively decompose the problem into smaller, simpler pieces. (There are linear sorts, but they're very specialised.) The principal O(logn) algorithm is binary search on a sorted array.

Anonymouse · 2013-11-12 Reply Admin

TRWTF is...:
That code is really racist.

Actually, I think it's probably rather crawlist.

2013-11-12 Reply Admin

gnasher729:
There are sorting implementations that run significantly faster than O (n log n) if the array is already sorted. For example, the MacOS X implementation checks for a sequence of items in either ascending or descending order both at the begin and the end of the array, and if there is not much else then the sort is in O (n). So adding one item at the end and sorting, or changing a random item and sorting, is O (n).

a) So you pay the price of that test on every sort operation?

b) If you're building a sorted list by inserting/deleting items randomly the cost per item should be O(log n) whether the list is already sorted or not (eg. std::set)

2013-11-12 Reply Admin

gnasher729:
Julia:
More seriously, isn't that O(n^2 log n) as he's also re-sorting the arrays on every iteration?
There are sorting implementations that run significantly faster than O(n log n) if the array is already sorted. For example, the MacOS X implementation checks for a sequence of items in either ascending or descending order both at the begin and the end of the array, and if there is not much else then the sort is in O(n).

On the other hand, Thunderbird used to have an internal "enhanced" quicksort algorithm that decided to switch to bubble sort if it didn't move any elements when partitioning the array.

2013-11-12 Reply Admin

Jibble:
gnasher729:
There are sorting implementations that run significantly faster than O (n log n) if the array is already sorted. For example, the MacOS X implementation checks for a sequence of items in either ascending or descending order both at the begin and the end of the array, and if there is not much else then the sort is in O (n). So adding one item at the end and sorting, or changing a random item and sorting, is O (n).

a) So you pay the price of that test on every sort operation?

b) If you're building a sorted list by inserting/deleting items randomly the cost per item should be O(log n) whether the list is already sorted or not (eg. std::set)

The price is very little, and the possible benefits are huge. More important, the average benefit in real-life scenarios is huge. For example, in the "nephew" case it improves things from O (nnlog n) to O (n*n). It simplifies code: Instead of writing code that inserts a few items into a sorted array, just append the items and sort. It also helps with the notorious case of arrays that are already sorted but in reverse order. It really accelerates the case of concatenating two sorted arrays and sorting the concatenation. It really simplifies the case where some items may have been changed and you want to make sure the array is still sorted - calling the sort function is as fast as checking that it is sorted.

Inserting into an array has linear cost for moving items around. Inserting into a sorted linked list has linear cost for finding where to insert.

2013-11-12 Reply Admin

In the usual "stretchy array" container classes the growth is by a constant factor, maybe 1.5. I have seen a one off implementation of a growing byte array with a constant increment of 100 bytes. Not very efficient when it has to grow from 100B to 500kB. This was in an application server sold by a very large corporation.

2013-11-12 Reply Admin

The "Nephew" way is all the way up in the government.

It seems like the Obamacare website was build by a company whos executive was friends with Michelle Obama: http://dailycaller.com/2013/10/25/michelle-obamas-princeton-classmate-is-executive-at-company-that-built-obamacare-website/

2013-11-12 Reply Admin

gnasher729:
Jibble:
gnasher729:
There are sorting implementations that run significantly faster than O (n log n) if the array is already sorted. For example, the MacOS X implementation checks for a sequence of items in either ascending or descending order both at the begin and the end of the array, and if there is not much else then the sort is in O (n). So adding one item at the end and sorting, or changing a random item and sorting, is O (n).

a) So you pay the price of that test on every sort operation?

b) If you're building a sorted list by inserting/deleting items randomly the cost per item should be O(log n) whether the list is already sorted or not (eg. std::set)

The price is very little, and the possible benefits are huge. More important, the average benefit in real-life scenarios is huge. For example, in the "nephew" case it improves things from O (nnlog n) to O (n*n). It simplifies code: Instead of writing code that inserts a few items into a sorted array, just append the items and sort. It also helps with the notorious case of arrays that are already sorted but in reverse order. It really accelerates the case of concatenating two sorted arrays and sorting the concatenation. It really simplifies the case where some items may have been changed and you want to make sure the array is still sorted - calling the sort function is as fast as checking that it is sorted.

Inserting into an array has linear cost for moving items around. Inserting into a sorted linked list has linear cost for finding where to insert.

That's why there are other data structures for these purposes which allow O(log n) (e.g. std::set, like Jibble said).

2013-11-13 Reply Admin

TRWTF is...:
I'm guessing that the author simply found it easier to read 3 identical letters in a row than the character on it's own.

I can actually think of a good reason to do that... try using your text editor's "Find" command to find all instances of a single-letter variable (e.g. "i"), and see how many false positives you end up wasting your time skipping over. With the variable named "iii" instead, you can scan much faster.

2013-11-13 Reply Admin

Jeremy:
TRWTF is...:
I'm guessing that the author simply found it easier to read 3 identical letters in a row than the character on it's own.

I can actually think of a good reason to do that... try using your text editor's "Find" command to find all instances of a single-letter variable (e.g. "i"), and see how many false positives you end up wasting your time skipping over. With the variable named "iii" instead, you can scan much faster.

That's why I search for \bi\b or use the whole word option.

2013-11-13 Reply Admin

chubertdev:
Quick way to fix the code:
/*
...
*/

Nah! This really should be a /* ... --- ... */

chubertdev · 2013-11-13 Reply Admin

Jeremy:
TRWTF is...:
I'm guessing that the author simply found it easier to read 3 identical letters in a row than the character on it's own.

I can actually think of a good reason to do that... try using your text editor's "Find" command to find all instances of a single-letter variable (e.g. "i"), and see how many false positives you end up wasting your time skipping over. With the variable named "iii" instead, you can scan much faster.

VB to the rescue!!!! Search for Dim space letter space.

The Nephew Way

Leave a comment on “The Nephew Way”