Comment On And We Got Sheena

I think you need to learn big-O notation again...

Well... Yeah that's pretty terrible

ITYM O(n^4)

It's a constant time algorithm? Awesome!!

But you kept her around because we all know "Sheena is a punk rocker," and who doesn't want a punk rocker girl working in the next cube over?

Wow. Thats the worst WTF so far this year.

I laughed, I cried, it moved me.

You might say that writing an algorithm with an unreasonable run-time complexity is a failure. But calling it O(4) (which is equivalent to O(1) and also the best possible) when you really mean O(n^4) (which is a whole world different), that is worse than failure.

Did Sheena put out? Because that's the only reason I'd have to even let her continue to touch code. Seriously, if she's going to write incredibly horrible stuff like this, maybe it's best to just give her a job filing papers or something.

Matthew W. S. Bell:

ITYM O(n^4)

O(n^2 * m^2) by my estimation, where n is the number of lines and m is the length of a line.

Basically it's O(s^2) where s is the number of characters in the file.

So depending on how you think about files it's either of quadratic or quartic complexity.

Not everybody has the brain capacity to understand the ramifications of one's design decisions...

This code looks like Pascal to me, but then I am not quite sure. As far as my distanced Turbo Pascal knowledge goes, this code has a number of problems, although they could be due to 'anonymization'. Especially undeclared variables or variables used out of scope. "CurPos" and "i", for example, are never declared. Assuming they might have been declared at file level (i.e. outside of these procedures), then, of course, ReadC is the greatest WTF of all, with its side-effect influence on CurPos -- besides the runtime problems.

Nice functional decomposition. It could have been all in one procedure with nested loops. Even the loveliest code can hide horrific algorithms.

Pascal would not be surprising, considering that it was an early Mac program.

we won't have noticed that in the modern days with modern processors =p

WTF like these annoy me.
Crappy programmer I understand.
Idiots (superior co-workers) laughing at her code I understand.
Not firing her, I cannot understand. Why keep someone who is that laughable? Have them move on, the team morale will improve, the workload on the other devs will go down (no more re-writing their code, trying to figure out what they've done, no more of the other developers wondering how the crappy ones can even get paid.)

KattMan:

But you kept her around because we all know "Sheena is a punk rocker," and who doesn't want a punk rocker girl working in the next cube over?

I wanted to write a witty followup, invoking more of the lyrics of the song. But after thinking hard, as far as I remember those were the only words in the whole song.

Ah, the Ramones. We miss you. Maybe they can have a Ramones-drummer reunion tour.

This reminds me of a lady I used to work with. She did our financials, which consisted of going to a webpage once a month, right clicking a table, and exporting to an MS Excel table. The second part of her job was doing collections. She was a junkyard dog when she went after someone who forgot to pay us. The funniest quote was when I overheard her on the phone: "You don't pay up and my kids don't eat. Mike Tyson eats your kids. You don't want to know what I'm going to do to your kids." The funny part was all of our billing was internal to our company and it was basically just "funny money" that we transferred between different budgets.

The company established a centralized accounting group and they took over billing. They couldn't fire her so they told me to "teach her programming" so she could be my backup. Two years later I think she could figured out how to italicize text in FrontPage.

Billy:

WTF like these annoy me.
Crappy programmer I understand.
Idiots (superior co-workers) laughing at her code I understand.
Not firing her, I cannot understand. Why keep someone who is that laughable? Have them move on, the team morale will improve, the workload on the other devs will go down (no more re-writing their code, trying to figure out what they've done, no more of the other developers wondering how the crappy ones can even get paid.)

But you need someone to make your work look good.

Welbog:

Matthew W. S. Bell:

ITYM O(n^4)

O(n^2 * m^2) by my estimation, where n is the number of lines and m is the length of a line.

Lines consist of a roughly constant number of characters, so it's fully legal to consider them the same input variable (number of lines * some constant factor = number of chars. so O(<numlines>) == O(<numchars>))

Now, ReadC is obviously O(N).
ReadL repeats ReadC a constant number of times (from the start of the line until eol, assuming that's what #13 means), so that's also O(N).
Finally, ReadLine calls ReadL N times, so that's O(N^2). But the constant overhead is pretty damn huge :)

It only becomes O(N^4) if we consider number of lines and number of characters as independent inputs, which isn't true.

Tessseract:

Pascal would not be surprising, considering that it was an early Mac program.

They should've tried Javascript...

SuperousOxide:

KattMan:

But you kept her around because we all know "Sheena is a punk rocker," and who doesn't want a punk rocker girl working in the next cube over?

I wanted to write a witty followup, invoking more of the lyrics of the song. But after thinking hard, as far as I remember those were the only words in the whole song.

Ah, the Ramones. We miss you. Maybe they can have a Ramones-drummer reunion tour.

Well you know the team was ready to go.
They had their keyboards and
they were going to the demonstration.
But she couldn't code,
Because the help file had it all.

Yeah Sheena was a punk Rocker.

Welbog:

Matthew W. S. Bell:

ITYM O(n^4)

O(n^2 * m^2) by my estimation, where n is the number of lines and m is the length of a line.

Basically it's O(s^2) where s is the number of characters in the file.

So depending on how you think about files it's either of quadratic or quartic complexity.

So, forget slurping the whole file at once and caching it. Forget reading entire lines at a clip. Even just reading one character at a time, all she had to do was not reset the file, and read from curPos to the next CR. Doh!

I have no idea what language that is, but it seems to have some bizarre scope rules.

Tessseract:

Pascal would not be surprising, considering that it was an early Mac program.

You say that like it was originated for Macs. I remember using Knight's Wee Pascal on Sharp MZ-80Ks long before even the Lisa was created...

Oh, and it blew goats, but it was better than Sharp's nasty BASIC (or even Xtal BASIC)

I'm assuming the O(4) is a typo, but man I wish someone would fix it. It's driving me insane.

dkfal:

we won't have noticed that in the modern days with modern processors =p

Yes, which is a reason we have some developers writing horrible code on slow platforms because "The CPUs are fast enough!!!!1111eleven1111"

*sigh*

Sheena - for when your help file absolutely, positively has to be parsed overnight.

Im guessing sheena was Indian and all code copied of the internet.

Wasn't SHEENA A PUNK ROCKER ???

Boyaa:

Im guessing sheena was Indian and all code copied of the internet.

I can't place a good date on either, but the series of tubes that make our Internets was hardly in place back when there were 8 MHz Macs. Maybe she just got it out of computer magazines or on the back of cereal boxes.

How is this a WTF? Sheena's specialty was 'Cinema'. What did you expect her to write? How was she hired in the first place?

Billy:

WTF like these annoy me.
Crappy programmer I understand.
Idiots (superior co-workers) laughing at her code I understand.
Not firing her, I cannot understand. Why keep someone who is that laughable? Have them move on, the team morale will improve, the workload on the other devs will go down (no more re-writing their code, trying to figure out what they've done, no more of the other developers wondering how the crappy ones can even get paid.)

The manager who can fire her is unaware of the poor job she's doing and not interested in listening to the whining of her back-stabbing colleagues. Besides, she's a VP's niece.

dkfal:

we won't have noticed that in the modern days with modern processors =p

I have the sneaking suspicion that it would be noticeable on any file larger than a few MB.

If a modern computer can do file access 10000 times faster than the old Mac in question, the file only needs to be about 10 times bigger to see the same performance degradation.

Addendum (2007-04-20 11:21):
I should say about 21 times bigger if it's an O(n^3) algorithm.

In other news, Paramount Pictures today hired industry-renowned software developer Erich Gamma to direct their planned $200m blockbuster which has a working title of "How the f### did I get this job?".

I've estimated what the performance would be, and I think this excel formula represents it fairly accurately:
=POWER(FACT(A4);1.6)/30
That means that the complexity is about O(n!^1.6)

Strangely O(n!*log n!) didn't fit that well, but that's probably Sheena didn't use binary partitioning to speed up. (Like, discarding the first (Index - 1) * (avg line length) / 2 characters.)

MrBester:

Tessseract:

Pascal would not be surprising, considering that it was an early Mac program.

You say that like it was originated for Macs. I remember using Knight's Wee Pascal on Sharp MZ-80Ks long before even the Lisa was created...

No, he's saying it like it's common knowledge that a lot of early Mac software was written in Pascal. Which it is, and was.

And what is WTF?
Lack of experience?
Or hiring someone with cinema degree to work as a programmer?

Poor Sheena.

CAPTCHA: muhahaha. No. IMO this WTF is not funny. I've seen a lot of code like this in school and high school.

grumpy:

Lines consist of a roughly constant number of characters, so it's fully legal to consider them the same input variable (number of lines * some constant factor = number of chars. so O(<numlines>) == O(<numchars>))

Now, ReadC is obviously O(N).

Where N is the number of characters from the beginning of the file. Then the program calls ReadC for each character up to the end of the line that you want. Occasionally execution leaves ReadL and starts in it again, but that doesn't really affect the amount of work the program does very much. Therefore the algorithm is O(N^2) where N is the size of the file in characters, irrespective of how many lines it is split into.

I haven't factored in anything like the time taken for the line "Ans := Ans + Ch;" - if that's any worse than linear then it would be worse. And of course, this is just to fetch one particular row. Fetching all the rows one by one would of course be O(N^3).

The ReadC function parses the entire file up to the character, so calling it once is O(n) on filesize.

ReadL calls ReadC for every character in a line (say of average length m), so we have O(mn).

ReadLine calls ReadL for every line up to the requested one.
So if the file has l lines, the expected runtime is O(lmn). But n = lm, so the runtime of a single call to ReadLine is O(n^2), and parsing a whole file is O(n^3).

Have I made a terrible mistake somewhere, or does that sound about right?

Addendum (2007-04-20 11:22):
Errr... parsing a whole file is O(ln^2)

probably would've been faster to print it out, place it on a wooden table.....

captcha: quake ?

As bad as it might be i'll give her one thing...it works...which is more than i can say on the work done by others i have worked with :)

bobday:

The ReadC function parses the entire file up to the character, so calling it once is O(n) on filesize.

ReadL calls ReadC for every character in a line (say of average length m), so we have O(mn).

ReadLine calls ReadL for every line up to the requested one.
So if the file has l lines, the expected runtime is O(lmn). But n = lm, so the runtime of a single call to ReadLine is O(n^2), and parsing a whole file is O(n^3).

Have I made a terrible mistake somewhere, or does that sound about right?

Addendum (2007-04-20 11:22):
Errr... parsing a whole file is O(ln^2)

I agree with your logic except that in practice l is going to be linearly dependent on n. Thus this is an O(n^3) algorithm.

Since she can't be fired, put her paycheck on line 20.

anon:

I've estimated what the performance would be, and I think this excel formula represents it fairly accurately:
=POWER(FACT(A4);1.6)/30
That means that the complexity is about O(n!^1.6)

Unfortunately that is not how big-O notation works. You don't estimate the complexity by measuring the cycles needed to perform tasks of various sizes. The complexity is a measure of how the algorithm performs as the size of the problem approaches infinity, which in this case is O(n^2). You are very unlikely to ever see an example of code that has a complexity of a power of N that isn't an integer, and such code will usually have a very big clue in it to indicate why it isn't an integer. The standard dumb prime number generator is one example:

for (int i = 2; i< n; i++) {

   boolean isPrime = true;

   for (int o = 2; o < sqrt(i); o++) {

      if (i % o == 0) {

         isPrime = false;

      }

   }

   if (isPrime) {

      print out i;

   }

}

This has a complexity of O(n^1.5). The ".5" part comes from the sqrt operation - that is the big clue.

I come up with O(n^3):

ReadC calls Read n times, making it an O(n) algorithm (n being CurPos in this case).

ReadL calls ReadC n times. The loop is linear (O(n)) but calls another linear time function, making ReadL O(n^2).

ReadLine calls ReadL n times, making it on O(n^3) algorithm.

So it'd be O(n^3).

Assuming, of course, that all the I/O functions were O(1).

She got the code out of a film she watched in her cinema degree.

Volmarias:

Did Sheena put out? Because that's the only reason I'd have to even let her continue to touch code. Seriously, if she's going to write incredibly horrible stuff like this, maybe it's best to just give her a job filing papers or something.

What do you mean by "put out"?

Jonh Robo:

Volmarias:

Did Sheena put out? Because that's the only reason I'd have to even let her continue to touch code. Seriously, if she's going to write incredibly horrible stuff like this, maybe it's best to just give her a job filing papers or something.

What do you mean by "put out"?

At the end of the day, while the program was running, Sheena would put out:

- the lights
- the cat
- the flames coming out of the disk drive from the massive I/O
- that other thing was promised only after the program finished running

There is a joke which perfectly sums up this WTF. I think I even read it here first:

A worker is hired to paint the lines on the road. On the first day he paints ten miles, and his employers are amazed. But, the second day he paints just five, and on only the third day, he paints only a mile of the road. Disappointed his boss asks what the problem was. The worker replies, "Well sir, every day I have to walk farther and farther to get back to the paint bucket!"

Sheena puts Schlemiel to shame.

A bit more info:

Sheena we had to hire, as our organization wanted to hire Sheena's husband, a real hot-shot engineer. He managed to get Sheena's employment put into his employment contract.

Why it was slower than even the really bad O(n^3 ):

This was on the Original Mac with 128K of RAM. In case you didnt know:

With only 128K, there could be no OS disk cache of recently used disk blocks.

I'm not even sure there was a OS cache of what blocks were needed for the currently open files.

The disk drive was a 400K 3.5 inch floppy, with variable number of blocks per track. This made disk seeks really slow, as not only did the head have to seek, but the drive motor had to seek to the required speed for the destination track.

So there was considerable overhead in reading a file repeatedly from the first byte!

BTW the story does have a happy ending for everybody concerned-- after about eight years, Sheena's husband left for another job, and Sheena, on her own, got a job directing TV commercials, a job she loves and does very very well at.

LuCarD:

Billy:

WTF like these annoy me.
Crappy programmer I understand.
Idiots (superior co-workers) laughing at her code I understand.
Not firing her, I cannot understand. Why keep someone who is that laughable? Have them move on, the team morale will improve, the workload on the other devs will go down (no more re-writing their code, trying to figure out what they've done, no more of the other developers wondering how the crappy ones can even get paid.)

But you need someone to make your work look good.

Please. My work looks good all on its own.