Comment On The Quadrasort

Stephan Müeller was overjoyed to hear that his coworker, The Specialist, had finally left the company. His coworker earned that title because he had the strange power to turn anything he touched into an unmaintainable, barely-compilable heap of codefiles: methods would swell to thousands of lines of code, case statements would branch to over ten levels, and so on. While browsing through his inventions, Stephan discovered the Quadrasort: it would sort a list of filenames formatted like "YYYYMMDDHH.ext". Sure, using the built-in Collections.Sort() method would do the trick; the format is, after all, designed for lexicographical ordering. But you have to admit, The Specialist's Quadrasort is that much more ... special .... [expand full text]
« PrevPage 1 | Page 2 | Page 3Next »

Re: The Quadrasort

2005-12-22 15:10 • by dshiznit
First!

Re: The Quadrasort

2005-12-22 15:11 • by Mikademus
Now that's a lot of code for doing really very little...

Re: The Quadrasort

2005-12-22 15:11 • by xasperated
Is there any possible way of doing that worse?  Just in
performance with all the loop interations it must be a joy. And
debugging that monstrosity would be horrifying.



Re: The Quadrasort

2005-12-22 15:12 • by dshiznit
54398 in reply to 54394
dshiznit:
First!

Sorry. I was just so frickin excited to see there were no posts yet!

Re: The Quadrasort

2005-12-22 15:17 • by Sheco
Why didnt he just do a single loop with a custom comparison function?

Re: The Quadrasort

2005-12-22 15:19 • by Ytram
54400 in reply to 54398
dshiznit:
dshiznit:
First!

Sorry. I was just so frickin excited to see there were no posts yet!


I fully endorse the genocide of people like yourself that get excited by being the first to post, or think that such an accomplishment is worthy of any kind of kudos or acknowledgement.

Re: The Quadrasort

2005-12-22 15:21 • by Jeff R.
an unmaintainable, barley-compilable heap of codefiles



I'd probably want plenty of
whisky if I was working with this code, yes.  Let's not just do a
bubble sort but let's do it four times...


Re: The Quadrasort

2005-12-22 15:22 • by Noah
54402 in reply to 54397
I was thinking a randomized algorithm would work - something that provably gets your items close to sorted within some bound, and then you run it lots and lots of times :-)

Re: The Quadrasort

2005-12-22 15:24 • by Marc
Ah! I see the WTF - he's using a Vector...

Re: The Quadrasort

2005-12-22 15:27 • by Dweasil
You know what they say: When one bubblesort isn't enough, use four!

Re: The Quadrasort

2005-12-22 15:30 • by akrotkov
54406 in reply to 54405
I'm sure he just read about a Radix sort somewhere, and implemented it in the worst possible way ever.

It sort of looks like one... if you squint, anyway.

Re: The Quadrasort

2005-12-22 15:33 • by RevMike
Why not just use a SortedSet?

[ducks]

Re: The Quadrasort

2005-12-22 15:33 • by hash
I'm guessing the WTF is that he's using Java?

Re: The Quadrasort

2005-12-22 15:33 • by Fortran Slinger
54411 in reply to 54404
Anonymous:
Ah! I see the WTF - he's using a Vector...


Ah, Now I see...it's not thread safe

Re: The Quadrasort

2005-12-22 15:36 • by Djinn
54413 in reply to 54400
May I join this genocide?

Re: The Quadrasort

2005-12-22 15:38 • by kipthegreat
Alex Papadimoulis:

    String filesArray[] = new String[len];

for (i = 0; i < len; i++)
filesArray[i] = (String) filesVector.get(i);


At least in Java 5 code like this is no longer needed (just the snippet here, not whole wtf).  I've had to do it several times and always found it a little annoying.

Now (assuming filesVector is defined as Vector<String>), all that can be replaced with-

String[] filesArray = filesVector.toArray();

or something like that, I forget exact syntax

Re: The Quadrasort

2005-12-22 15:40 • by Nand
54416 in reply to 54404
Anonymous:
Ah! I see the WTF - he's using a Vector...


Of course. Vector fileVector. This is obviously a vector of files... no wait. Strings.

/not like naming it filenameVector would make the function justifyable..

Re: The Quadrasort

2005-12-22 15:40 • by jmroth
Yeah well Collections.Sort() might contain bugs so he goes and implements every critical operation himself... that can't be wrong :P

Re: The Quadrasort

2005-12-22 15:43 • by Djinn
54419 in reply to 54413
ugh. Meant to quote Ytram. The "edit time" timed out.

I've cleaned up behind so many "programmers" afraid or ignorant of recursion. And so many DIY-ers. This is a bad combonation of the two.

Re: The Quadrasort

2005-12-22 15:47 • by kipthegreat
54420 in reply to 54400
Ytram:
dshiznit:
dshiznit:
First!

Sorry. I was just so frickin excited to see there were no posts yet!


I fully endorse the genocide of people like yourself that get excited by being the first to post, or think that such an accomplishment is worthy of any kind of kudos or acknowledgement.


I also endorse the genocide of the people who add another ten stupid posts saying "I hate people who post 'first'".  And the people who make posts bitching about people who bitch about people who make 'first' posts.  And yes, I realize I am embracing my own genocide.  If that is how it must be then that is how it must be.  I will be remembered as a martyr!

Re: The Quadrasort

2005-12-22 15:47 • by Kalal
54421 in reply to 54414
kipthegreat:


At least in Java 5 code like this is no longer needed (just the snippet here, not whole wtf). I've had to do it several times and always found it a little annoying.

Now (assuming filesVector is defined as Vector), all that can be replaced with-

String[] filesArray = filesVector.toArray();

or something like that, I forget exact syntax




Yet another Java programmer who doesn't know what he is talking about. Vector#toArray() is there since ancient Java 1.2. Particular the version were you supply your own array as an argument works like a charm since ages when you need to get a special type of array.

Re: The Quadrasort

2005-12-22 15:47 • by FORTRAN slinger
54422 in reply to 54419
Djinn:
ugh. Meant to quote Ytram. The "edit time" timed out.

I've cleaned up behind so many "programmers" afraid or ignorant of recursion. And so many DIY-ers. This is a bad combonation of the two.



combonation - such a booutiful woord


Re: The Quadrasort

2005-12-22 15:47 • by anon
I'd be interested to know how many man hours went into this.  I'm
guessing probably not too many, since it looks like the result of 3
copy-n-pastes.

Re: The Quadrasort

2005-12-22 15:48 • by TankerJoe
54424 in reply to 54400
Ytram:
dshiznit:
dshiznit:
First!

Sorry. I was just so frickin excited to see there were no posts yet!


I
fully endorse the genocide of people like yourself that get excited by
being the first to post, or think that such an accomplishment is worthy
of any kind of kudos or acknowledgement.




(OT) At least he said he was sorry.... besides, I don't think genocide is the answer.  We need people like him.

Re: The Quadrasort

2005-12-22 15:50 • by cconroy
54425 in reply to 54419
Wow, just... wow.  The SpecialOlympicist really couldn't have done much worse with that, could he?



Re: The Quadrasort

2005-12-22 15:53 • by TankerJoe
54426 in reply to 54420
kipthegreat:


I also endorse the genocide of the
people who add another ten stupid posts saying "I hate people who post
'first'".  ...snip...  I will be remembered as a martyr!




All of the people who would remember you as a martyr would be subject to the genocide to.  Sorry.

Re: The Quadrasort

2005-12-22 15:55 • by cconroy
54427 in reply to 54422
FORTRAN slinger:
Djinn:
ugh. Meant to quote Ytram. The "edit time" timed out.



I've cleaned up behind so many "programmers" afraid or ignorant of
recursion. And so many DIY-ers. This is a bad combonation of the two.







combonation - such a booutiful woord









Well, he did combone several WTFs in creating this masterpiece.  It's a perfectly cromulent word.



Re: The Quadrasort

2005-12-22 15:56 • by magnus
54428 in reply to 54394
Second! Doh! not quite...oh well...maybe tomorrow

Re: The Quadrasort

2005-12-22 15:57 • by kipthegreat
54429 in reply to 54421
Anonymous:
kipthegreat:


At least in Java 5 code like this is no longer needed (just the snippet here, not whole wtf). I've had to do it several times and always found it a little annoying.

Now (assuming filesVector is defined as Vector), all that can be replaced with-

String[] filesArray = filesVector.toArray();

or something like that, I forget exact syntax




Yet another Java programmer who doesn't know what he is talking about. Vector#toArray() is there since ancient Java 1.2. Particular the version were you supply your own array as an argument works like a charm since ages when you need to get a special type of array.


Cool, I didn't realize that. I had tried casting the result to a special array   (String[])vector.toArray() ... which obviously doesn't work since Object[] can't be casted to String[].  I guess I stopped there since a loop was simple and I didn't catch that the one with the parameter would correctly handle a String[] argument.

At least I know I'm not the only one that doesn't know this..  I've seen a loop like this in other people's code many times, but I've never seen the toArray(Object[]) method used.

Re: The Quadrasort

2005-12-22 16:01 • by Flu Blighter
54430 in reply to 54400
Don't reply, you're only encouraging it!

Re: The Quadrasort

2005-12-22 16:10 • by RevMike
54431 in reply to 54429
kipthegreat:
Anonymous:
kipthegreat:


At least in Java 5 code like this is no longer needed (just the snippet here, not whole wtf). I've had to do it several times and always found it a little annoying.

Now (assuming filesVector is defined as Vector), all that can be replaced with-

String[] filesArray = filesVector.toArray();

or something like that, I forget exact syntax




Yet another Java programmer who doesn't know what he is talking about. Vector#toArray() is there since ancient Java 1.2. Particular the version were you supply your own array as an argument works like a charm since ages when you need to get a special type of array.


Cool, I didn't realize that. I had tried casting the result to a special array   (String[])vector.toArray() ... which obviously doesn't work since Object[] can't be casted to String[].  I guess I stopped there since a loop was simple and I didn't catch that the one with the parameter would correctly handle a String[] argument.

At least I know I'm not the only one that doesn't know this..  I've seen a loop like this in other people's code many times, but I've never seen the toArray(Object[]) method used.

The toArray(Object[]) method is available in everything that implements java.util.Collection.

The first time I tried to use this method, I struggled to get the syntax correct.  Here is an example to keep handy...

import java.util.Collection;
import java.util.Vector;

public class ToArrayDemo {
    public static void main(String[] args) {
        Collection c = new Vector();
       
        c.add("Foo");
        c.add("Bar");
        c.add("Baz");

        String[] a = (String[]) c.toArray(new String[]{});

        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

Re: The Quadrasort

2005-12-22 16:44 • by MasterMalvin
It would be fun to have whole contests made up of Rube Goldbergs like
this where teams have to figure out what it actually *does* the
quickest, and with the least amount of violence.  And the winners
get the author's personal e-mail address :D

Re: The Quadrasort

2005-12-22 16:44 • by TankerJoe
54437 in reply to 54431
RevMike:


The first time I tried to use this method, I struggled to get the syntax correct.  Here is an example to keep handy...

import java.util.Collection;
import java.util.Vector;

public class ToArrayDemo {
    public static void main(String[] args) {
        Collection c = new Vector();
       
        c.add("Foo");
        c.add("Bar");
        c.add("Baz");

        String[] a = (String[]) c.toArray(new String[]{});

        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}





I agree that it is far from intuitive to use this method as I
originally struggled with it also.  I came up with a slightly
different take that works fine, and I think is a little bit clearer.



        Collection c = new Vector();

        c.add("Foo");
        c.add("Bar");
        c.add("Baz");


        String[] a = new String[c.size()];

        c.toArray(a);


        for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}



So, to bring it back to the WTF, this:





String filesArray[] = new String[len];
for (i = 0; i < len; i++)
filesArray[i] = (String) filesVector.get(i);




Could have easily been done like this, no loopy looping needed:

	String filesArray[] = new String[len];
filesVector.toArray(filesArray);











Re: The Quadrasort

2005-12-22 16:47 • by Rank Amateur

Heh, I see. Year has four characters to it, so how can this possibly work? And Month and Day and HH have 2 a piece. This calls for my patented decasort(), with 10 while loops. It's 150% better than quadrasort!


No wait, don't you have to bubblesort each bit separately? What's 80 in Latin?


No wait, is this Unicode?


--Rank

Re: The Quadrasort

2005-12-22 17:00 • by TankerJoe
This all makes so much sense!!!!  Brillant!!!  I fully expect
a new API to result from this.  It should implement:



Name of sort         File name pattern

==========       ============

UnarySort          -  YYYY.ext

BinarySort         -  
YYYYMM.ext    (who cares if this name is already taken.)

TernarySort       -   YYYYMMDD.ext

QuadraSort       -   YYYYMMDDHH.ext

QuinarySort      -    YYYYMMDDHHMM.ext

SenarySort        -    YYYYMMDDHHMMSS.ext

SeptenarySort   -    YYYYMMDDHHMMSSMMM.ext

OctalSort          -    YYYYMMDDHHMMSSMMMNNN.ext



Bah!





Re: The Quadrasort

2005-12-22 17:05 • by Suck My Lisp
54440 in reply to 54439
And for records of arbitrary length, "ChampagneSort".

Re: The Quadrasort

2005-12-22 17:37 • by I Agree
54441 in reply to 54439
<
SenarySort        -    YYYYMMDDHHMMSS.ext>

I would have called it:


SexySort        -    YYYYMMDDHHMMSS.ext


It has a nicer ring to it.

Thanks

Re: The Quadrasort

2005-12-22 17:42 • by olddog
Okay... there's quick-sort, and bubble-sort, and now!.... safety-sort.  - 'Cause you can never be sure that items won't magically change during the sort. Hey- at least the bad dates were 'logged' ( for some reason ).

Re: The Quadrasort

2005-12-22 17:43 • by whoisfred
54443 in reply to 54437
TankerJoe:
RevMike:


The first time I tried to use this method, I struggled to get the syntax correct.  Here is an example to keep handy...

import java.util.Collection;
import java.util.Vector;

public class ToArrayDemo {
    public static void main(String[] args) {
        Collection c = new Vector();
       
        c.add("Foo");
        c.add("Bar");
        c.add("Baz");

        String[] a = (String[]) c.toArray(new String[]{});

        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}





I agree that it is far from intuitive to use this method as I
originally struggled with it also.  I came up with a slightly
different take that works fine, and I think is a little bit clearer.



        Collection c = new Vector();

        c.add("Foo");
        c.add("Bar");
        c.add("Baz");


        String[] a = new String[c.size()];

        c.toArray(a);


        for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}



So, to bring it back to the WTF, this:





String filesArray[] = new String[len];
for (i = 0; i < len; i++)
filesArray[i] = (String) filesVector.get(i);




Could have easily been done like this, no loopy looping needed:

	String filesArray[] = new String[len];
filesVector.toArray(filesArray);












Personally, I prefer this:
        String[] a = (String[]) c.toArray(new String[c.size]);

All one line without having to create an extraneous empty String array.

Re: The Quadrasort

2005-12-22 17:44 • by whoisfred
54444 in reply to 54443
whoisfred:


Personally, I prefer this:
        String[] a = (String[]) c.toArray(new String[c.size]);

All one line without having to create an extraneous empty String array.


of course I meant:

        String[] a = (String[]) c.toArray(new String[c.size()]);

Re: The Quadrasort

2005-12-22 18:09 • by TankerJoe
54449 in reply to 54444
whoisfred:
whoisfred:


Personally, I prefer this:
        String[] a = (String[]) c.toArray(new String[c.size]);

All one line without having to create an extraneous empty String array.


of course I meant:

        String[] a = (String[]) c.toArray(new String[c.size()]);







TankerJoe:





	String[] a = new String[c.size()];
        c.toArray(a);






I see/agree with the "all-on-one-line" argument,but  where is my
extraneous empty String array?  I'm pretty sure that both way are:



1) Creating a string array with the exact capacity needed to fill it with the String objects in the collection

2) Fill up the String array

3) Keep a reference to the String array ... called "a" in this case.



The only difference is that I keep the reference from when I created
the array, whereas you get the reference by casting the return object
from the toArray method.  Maybe we can chalk this up to programmer
preference/style?  Programming is an art form after all.





Re: The Quadrasort

2005-12-22 18:15 • by BlueEagle
Alex Papadimoulis:

try {
countYearA = Integer.parseInt(valA.substring(0, 4));
countYearB = Integer.parseInt(valB.substring(0, 4));
countA = Integer.parseInt(valA.substring(4, 6));
countB = Integer.parseInt(valB.substring(4, 6));
if (countYearA < countYearB)
continue;
if (countA <= countB)
continue;
filesArray[i] = valB;
filesArray[i + 1] = valA;
} catch (NumberFormatException nfe) {
Log.log( ERROR1+nfe.getMessage() , NPSLOGGER );
}


Atleast he is doing exception handling...

Re: The Quadrasort

2005-12-22 18:37 • by TankerJoe
54452 in reply to 54450
Anonymous:


Atleast he is doing exception handling...




Well thank dog for that.

Re: The Quadrasort

2005-12-22 18:52 • by John V.
54454 in reply to 54416

Nand:
Anonymous:
Ah! I see the WTF - he's using a Vector...


Of course. Vector fileVector. This is obviously a vector of files... no wait. Strings.

/not like naming it filenameVector would make the function justifyable..


"What's your vector, Victor?"

Re: The Quadrasort

2005-12-22 18:53 • by KraGiE

dunno why, but I just thought of something..


For all the developers that talk about genocide of dumb developers, I wonder if any of you guys are the ones that are making these types of manslaughter to coding.  It was definitely off topic, but yeah. 

Re: The Quadrasort

2005-12-22 19:28 • by RevMike
54459 in reply to 54449
TankerJoe:
whoisfred:
whoisfred:


Personally, I prefer this:
        String[] a = (String[]) c.toArray(new String[c.size]);

All one line without having to create an extraneous empty String array.


of course I meant:

        String[] a = (String[]) c.toArray(new String[c.size()]);







TankerJoe:





	String[] a = new String[c.size()];
        c.toArray(a);






I see/agree with the "all-on-one-line" argument,but  where is my
extraneous empty String array?  I'm pretty sure that both way are:



1) Creating a string array with the exact capacity needed to fill it with the String objects in the collection

2) Fill up the String array

3) Keep a reference to the String array ... called "a" in this case.



The only difference is that I keep the reference from when I created
the array, whereas you get the reference by casting the return object
from the toArray method.  Maybe we can chalk this up to programmer
preference/style?  Programming is an art form after all.






TankerJoe's two line method is slightly faster.  It evaluates to...

   35:  aload_1
   36:  invokeinterface #8,  1; //InterfaceMethod java/util/Collection.size:()I
   41:  anewarray       #9; //class String
   44:  astore_2
   45:  aload_1
   46:  aload_2
   47:  invokeinterface #10,  2; //InterfaceMethod java/util/Collection.toArray:([Ljava/lang/Object;)[Ljava/lang/Object;
   52:  pop

While whoisfred's works out to...

   35:  aload_1
   36:  aload_1
   37:  invokeinterface #8,  1; //InterfaceMethod java/util/Collection.size:()I
   42:  anewarray       #9; //class String
   45:  invokeinterface #10,  2; //InterfaceMethod java/util/Collection.toArray:([Ljava/lang/Object;)[Ljava/lang/Object;
   50:  checkcast       #11; //class String;"
   53:  astore_2


Re: The Quadrasort

2005-12-22 20:17 • by bailey
54463 in reply to 54444
whoisfred:
whoisfred:


Personally, I prefer this:
        String[] a = (String[]) c.toArray(new String[c.size]);

All one line without having to create an extraneous empty String array.


of course I meant:

        String[] a = (String[]) c.toArray(new String[c.size()]);



Just to join the fun.. I'm assuming this isn't in Java 5 since in 5.0 you don't need to cast if you've declared the collection a container of Strings.

inefficient sort

2005-12-22 20:22 • by Nfol
54464 in reply to 54402
Noah:
I was thinking a randomized algorithm would work


I was thinking of writing something like this - keep trying random combinations until it was sorted. I wanted to make sure it was an algorithm, though (that is, finish in a finite amount of time), so I had to come up with a randomizer that wouldn't give me the same (dis)order twice, and would guarantee I would hit every permutation.

I didn't have time to mess with that, though. (It was for a programming competency test; the problem was: write your own sorting function. (Yes, this is quite simple; the test was meant to weed out such "programmers" as the ones who have unintentionally contributed to this site.))

I ended up writing a sort that tried every possibility until it was sorted. For example, if given DABC, it would do:

[list]
[*]DABC
[*]DACB
[*]DBAC
[*]DBCA
[*]DCAB
[*]DCBA
[*]ADBC
[*]ADCB
[*]ABDC
[*]ABCD
[/list]

Alas, the testers didn't make a comment. (I wonder if they even read the code.)

P.S. First Post! (For me, at least.)

P.P.S. But I've been lurking here a while.

P.P.P.S. And yes, I do usually tend to ramble on and on and on ...

Re: The Quadrasort

2005-12-22 20:34 • by ferrengi
OK,


So does anyone want to take a stab at why he had to do the exact same sort 4 times?


He could've done it just once and accomplish the exact same thing so what is special about the number 4?


I could not come up with any theory about this.


Any ideas?

Re: The Quadrasort

2005-12-22 20:55 • by olddog
54470 in reply to 54468
hmm... looks like each episode checks a specific date ( fragment ) for errors.  looks like the programmer is mining for date-syntax-error trends?
« PrevPage 1 | Page 2 | Page 3Next »

Add Comment