The "IT DOESN'T WORK!" thread

[Shivahn]

Thanks everyone! I'm unfortunately at work now, but I'm going to try to write up those alternate forms when I get home. I still don't fully get it, but the more I read over the posts explaining it the more I understand. I'm quite grateful to have a place where I can ask questions, since while the MIT OCW is great, and I understand almost everything I read, when I just can't get something there's nowhere to turn. Except here, apparently! So thanks again.

Edit for retrospective hilarity: I'm reading the readings before the lectures (like you're supposed to in formal classes) for the MIT stuff.

Function types, notation, and all that? Yeah, that's in the lecture for the reading I did that brought up the whole problem. Whoops >.>

[chridd]

The type of your repeat is then:
(A->A, N)->(A->A)
where A is some unknown type, and N is your "repeat count".

Better would be to parenthesize it as

Code: Select all

( (A->A), N ) -> (A->A)

Pairing binds tighter than function application in every typed functional language I know, so (A -> A, N) would be interpreted as a function of one argument that returns a pair. While there's nothing fundamentally wrong with doing the other thing, it goes against expectations heavily. At least for people who have the background to have expectations.

In Haskell, pairing binds looser than everything else:

Code: Select all

Prelude> :t (id, 1)
(id, 1) :: Num a1 => (a -> a, a1)
Prelude> :t (\x -> (x, 1))
(\x -> (x, 1)) :: Num a => t -> (t, a)
Prelude> (sqrt 2, 3)
(1.4142135623730951,3)


[sourmìlk]

So, I'm trying to compile a reasonably large project in Eclipse using MinGW, and I'm getting these bizarre and random "#include nested too deeply" errors. I checked, there aren't includes nested to deeply. And every time I alter an include tree to maybe eliminate some redundancy, the warnings jump to entirely different files, and then maybe back to the previous ones after another edit, but never disappear. What the hell is happening?

EDIT:

never mind, I think I found the loop. It's Face -> Material -> Texture -> Image -> PixelBuffer -> GLBuffer -> Face...

I need to find a way around that, though I'm not sure how.

[headprogrammingczar]

In Haskell, pairing binds looser than everything else:

Alternatively, tuples in Haskell always have to have parens around them.

Code: Select all

Prelude> 2, 3
<interactive>:1:2: parse error on input `,'
Prelude> (2, 3)
(2,3)


Incidentally, this is my least favorite quirk of Haskell, because it doesn't allow n-tuples to be defined as nested 2-tuples.

[EvanED]

Huh, that's interesting. I checked my memory for OCaml and thought that ML and Haskell agreed on that point. (In my defense, I've done very little in Haskell.)

Code: Select all

# let f (a,b) = a + b
  ;;q
val f : int * int -> int = <fun>

[sourmìlk]

W00t, more problems!

So, I have a project that exists solely to test whether GLEW is on my machine. The code, in it's entirety, is as follows:

Code: Select all

#include <iostream>

#define GLEW_STATIC

#include <GL/glew.h>
#include <GL/freeglut.h>

using namespace std;

int main(int argc, char **argv)
{
    glutInit(&argc, argv);

    glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE | GLUT_DEPTH);

    glutInitWindowPosition(0, 0);
    glutInitWindowSize(1920, 1080);
    glutCreateWindow("TEST");

    GLenum err = glewInit();

    if(err != GLEW_OK)
    {
        cout <<"ERROR: could not load GLEW. " <<glewGetErrorString(err) <<endl;
        return 0;
    }

    cout <<"GLEW loaded, running version " <<glewGetString(GLEW_VERSION) <<endl;

    return 0;
}
 

When I run it, it terminates immediately (before the first line of main) with a status of -(2 ^ 31) + 1. When I run it using the debugger, however, I find that the thread suspends itself on the opening bracket of main, and only continues when I tell the debugger to resume, at which point the program completes successfully, indicating that GLEW works.

However, in another project, all references to GLEW functions fail to compile, giving me the error "undefined reference to __glew[function]". I've verified that all the binaries and DLLs and such are in the right place and that I'm linking to it properly. Why does it (sort of) work in one project, and not the other? Why is the first project crashing outside the debugger?

And of course, it all works on Ubuntu.

[PM 2Ring]

never mind, I think I found the loop. It's Face -> Material -> Texture -> Image -> PixelBuffer -> GLBuffer -> Face...

I need to find a way around that, though I'm not sure how.

You should be using guard macros in your headers to prevent multiple inclusion.

[headprogrammingczar]

Or better, refactor your code so you aren't looping at all.

[Jplus]

Or better, refactor your code so you aren't looping at all.

I'm sorry but that doesn't seem realistic for any sufficiently large project. Imagine a project that uses <vector>, as well as a third-party library which also uses <vector>. Include guards were invented and are used by everyone for good reasons (in C and C++).

[Shivahn]

Ok, I'm having trouble with C++. The basic trouble is as follows:

I have a class who has a member that is another class (an image class). The image class has a constructor that takes a single std::string and then loads a picture from that string and processes it (e.g., Image sunglasses("art/sunglasses.png"); will make an image called sunglasses loaded from the path art/sunglasses.png and then do stuff to it.) I was having a lot of trouble getting anything to work (and trying to track down the problem, because the program segfaulted seemingly at random within a hundredth of a second) until I realized that what is happening is the first class is being created and trying to construct the member object of type Image, which isn't actually loading an image but is trying to use pointers on one anyway thus causing the segfault.

So I tried to overload the constructor so that if no arguments are passed it doesn't do anything (since the first class will end up loading the image on its own later anyway), but I keep getting told that the call to the member object's constructor is ambiguous. I don't really understand this: shouldn't it be obviously the one with no arguments?

And without it, I get that quick segfault. I guess I really broadly just want to know what's going on. I have questions but I'm not knowledgeable enough to really understand how to ask them.

[chridd]

I have a class who has a member that is another class (an image class).

To clarify, do you mean that it has a member variable of type image (as opposed to the image class itself being inside the class)?

So I tried to overload the constructor so that if no arguments are passed it doesn't do anything (since the first class will end up loading the image on its own later anyway), but I keep getting told that the call to the member object's constructor is ambiguous. I don't really understand this: shouldn't it be obviously the one with no arguments?

Do any of image's constructors have default arguments?

[Shivahn]

The first class has a member that is an instance of the image class, yeah. The image class as a whole is not a member of the first class.

I've only programmed one constructor into the image class, and it does have a default argument.

Something else that may be relevant is that there's also a static member of type image in the class. Also, it looks like I segfault even if I comment out my main loop. Like, all of it.

Edit: Actually, it looks like that is the main problem. If I cut that out it still segfaults, but it's much later. So I clearly have two bugs, but the static member is the biggest problem.

[Splanky222]

So I accidentally saved a blank program over my Java Binary Search Tree class for my Data Structures class, so I'm rewriting it. I'm getting a weird runtime error when I check my Insert method:

Code: Select all

class BST<T extends Comparable<? super T>>{
  BSTNode<T> root;
 
  BST() {
    root = null;
  }
//...//
private void Insert(T newEl, BSTNode<T> node) {
    if(node == null)
      node = new BSTNode<T>(newEl);
    else if(node.El() == newEl) //no repeats
      ;
    else if (newEl.compareTo(node.El()) > 0)
      Insert(newEl, node.Right());
    else
      Insert(newEl, node.Left());
  }
 
  public void Insert(T newEl) {
    Insert(newEl, root);
  }


I guess it's sort of weird having two Insert Methods like this anyways, but I forgot just quite how we did it in class and these seemed like a good way of doing it... Either way that's what I'm trying to check!:

Code: Select all

//...//
BST<Integer> tree = new BST<Integer>();
 Integer i = new Integer(7);
 tree.Insert(i);

Everything compiles perfectly happily, but when I run the program to check my class, I get this error:
java.lang.NoSuchMethodError: BST.Insert(Ljava/lang/Comparable;)V

I have the whole <T extends Comparable<? super T>> business in my node class as well, so if the generic type T has Comparable as a superclass (even though Comparable is an interface?) and the compiler recognizes that I am calling an existent method in my Binary Search Tree class, it still tells me that there's no such method taking a Comparable argument... I am thoroughly bamboozled.

[phlip]

Well, looking at your Insert method, I can't see how it would work... in the code path where it actually creates the new node, it doesn't store it anyway... it just creates it and returns, and it'll quickly get GCed. It looks like that when you're passing a value in for the second parameter of Insert, and then inside Insert you're assigning node a value, you're expecting that that assignment will flow back into whatever you passed in originally... which isn't going to happen, that's not how references work in Java.

That doesn't explain the error you're getting, though... it just means that when you fix that error, it's not going to work...

As for your actual error... try deleting any .class files you have, and recompiling from scratch, maybe? Something old and incompatible might be floating around, or something?

[Yakk]

Java references have pointer semantics. A = B means "A now refers to B".

To modify he actual object that A refers to, instead of changing what object A refers to, you need to do something like A.CopyFrom( B ).

Does that about describe it?

[EvanED]

So I accidentally saved a blank program over my Java Binary Search Tree class for my Data Structures class, so I'm rewriting it.

I cannot recommend learning version control enough. It will prevent problems like this. In my opinion, programming without it is ludicrous, and it's utterly unacceptable that (at least in my experience) VCS is almost never taught or even mentioned in class. It should be introduced very early in any CS class which is likely to be a first programming course.

I wrote up some notes for an upper division class I taught last semester, which I hope are generally useful. It aims to present a somewhat unified-ish view of three different choices for version control software: Subversion, Git, and Mercurial. There are probably a few better sources out there, but the stuff I was finding all focused on one of those in particular.

[Splanky222]

Java references have pointer semantics. A = B means "A now refers to B"

Yeah I thought it might not work because of that very reason, I was just trying to confirm that.

In fact, it was some loose junk hanging around from my old (erased... oops!) BST file. I now get exactly what I expected, a BST that doesn't work!
*Edit: forgot to quote. Thanks for the suggestion, phlip!

[sourmìlk]

For those worrying about my GLEW program (i.e. none of you) I decided to enable extensions manually. Yes, with the good old fashioned

Code: Select all

PFNGLFRAMEBUFFERTEXTURE2DPROC glFramebufferTexture2D = (PFNGLFRAMEBUFFERTEXTURE2DPROC) wglGetProcAddress("glFramebufferTexture2D");


Seriously, who the hell names these types? Windows type names are some of the ugliest and most useless I've seen From hWND to LPCSTR or whatever it is, it's stupid.

[Jplus]

The first class has a member that is an instance of the image class, yeah. The image class as a whole is not a member of the first class.

I've only programmed one constructor into the image class, and it does have a default argument.

Something else that may be relevant is that there's also a static member of type image in the class. Also, it looks like I segfault even if I comment out my main loop. Like, all of it.

Edit: Actually, it looks like that is the main problem. If I cut that out it still segfaults, but it's much later. So I clearly have two bugs, but the static member is the biggest problem.

I propose you show us some code, that might make things easier.

[Shivahn]

Ok. This is all a bit moot now since I am pretty quickly realizing that since I wrote this when I was terrible-er at coding it's better to start from the ground up. (Incidentally, if anyone has general advice for programming well besides "make things modular" "build and enforce abstraction barriers" and "document everything," I'd really appreciate you mentioning it).

Spoiler:

So the relevant bits of the image class is here:

Code: Select all

class Image { // This structure holds an image
    public:
    SDL_Surface * image;
    Image(std::string filename="Art/Default.png");
    void generateImage(int, int); // Generates a blank image with width and height of whatever's passed to it
    void load(std::string);
};

It's all public because of how I coded the main parts of stuff in the first place. I was going to make it private after I adjusted the drawing functions and stuff. It's one of the reasons I really realized how bad my coding was.

The constructor just calls the loading function.

The load function is here:

Code: Select all

SDL_Surface * load_alpha(std::string filename)
{
        // Creates a surface to load the image on, and a surface to optimize it on
        SDL_Surface * loadedImage=NULL;
        SDL_Surface * optimizedImage=NULL;

        loadedImage=IMG_Load(filename.c_str()); // Loads the image after typecasting the string to a constant character pointer

        if (loadedImage!=NULL)

        {
                optimizedImage=SDL_DisplayFormatAlpha(loadedImage); // Optimizes the loaded image and saves it as the optimized image
                SDL_FreeSurface(loadedImage);
        }

        // Checks for errors
        if(optimizedImage==NULL)
            printf("Error loading image: %s", IMG_GetError());

        return optimizedImage;
}

The ultimate source of the problem is the SDL_DisplayFormatAlpha. If that's the only thing commented out, the whole thing works. Well, obviously not entirely, but it doesn't segfault.

The member of the class who is causing the problem and its constructor are

Code: Select all

static Image tiles;

Image Chunk::tiles;

So, yeah. I'm going to reengineer everything (and again, would appreciate general ideas on how to not build things terribly again), but I'm still very interested in what's happening and why.

[phlip]

Does SDL need to be initialised before you use it? Being a static variable, the constructor for your Chunk::tiles variable is going to be run before anything in the main-line of your code is run...

[Shivahn]

Does SDL need to be initialised before you use it? Being a static variable, the constructor for your Chunk::tiles variable is going to be run before anything in the main-line of your code is run...

I believe so, that would make sense. How would I go about doing that?

And why does it segfault? I don't understand the technical reason. I feel like that's a weird error instead of.. I don't know, something about an undefined function or something.

[phlip]

Well, dealing with uninitialised stuff is highly unpredictable. It, along with keeping a pointer to something that doesn't exist any more (eg a dynamic object that's been deleted, or an object on the stack of a function that's returned)... they're cases where you're working with data that sometimes will be OK (especially in the deleted case, shortly afterwards... it won't be broken until later, when a new object overwrites it)... but can cause bizarre behavior later, in a completely different place to the actual bug.

This, naturally, makes them an absolute pain in the dick to debug.

[Jplus]

Ok. This is all a bit moot now since I am pretty quickly realizing that since I wrote this when I was terrible-er at coding it's better to start from the ground up. (Incidentally, if anyone has general advice for programming well besides "make things modular" "build and enforce abstraction barriers" and "document everything," I'd really appreciate you mentioning it).

Alright. Perhaps you already found out about these things, but I saw a few things in your code that could be done better and which you didn't mention by yourself yet.

Code: Select all

class Image { // This structure holds an image

This is a useless comment.

Code: Select all

    void generateImage(int, int); // Generates a blank image with width and height of whatever's passed to it

This is a better comment, because it adds information. There is, however, a more concise way to document your code:

Code: Select all

    void generateImage(int width, int height);

Code: Select all

        // Creates a surface to load the image on, and a surface to optimize it on
        SDL_Surface * loadedImage=NULL;
        SDL_Surface * optimizedImage=NULL;

This comment is noninformative, and besides, it's incorrect! You're not actually creating the surfaces, you're only initializing the pointers.
By the way, NULL has no special meaning in C++ (it's just the integer value 0) and in order to be portable you have to #include <cstdlib> for it, so usually we prefer to initialize and compare pointers simply with a literal 0.

Code: Select all

        loadedImage=IMG_Load(filename.c_str()); // Loads the image after typecasting the string to a constant character pointer

Again, a useless comment.

Code: Select all

        if (loadedImage!=NULL)
        {
                optimizedImage=SDL_DisplayFormatAlpha(loadedImage); // Optimizes the loaded image and saves it as the optimized image
                SDL_FreeSurface(loadedImage);
        }

        // Checks for errors
        if(optimizedImage==NULL)
            printf("Error loading image: %s", IMG_GetError());

The first check is good, but the second is ambiguous. There are two possible reasons why optimizedImage might be a null pointer: (1) because IMG_Load failed and the first if statement wasn't executed, or (2) because SDL_DisplyFormatAlpha failed. If you want to be able to distinguish the two cases and not treat failed optimizing as failed image loading, you should write something like below.
Also, again your comments don't add any information. Besides, why comment that the if statement is a check the second time but not the first time? Aim for consistency. Oh, and that applies to your code layout as well.

Code: Select all

        if (loadedImage != 0)
        {
                optimizedImage = SDL_DisplayFormatAlpha(loadedImage);
                if (optimizedImage == 0)
                        { /* handle error */ }
                else
                        SDL_FreeSurface(loadedImage);
        }
        else
                printf("Error loading image: %s", IMG_GetError());

In summary: documenting your code is not the same as repeating every statement in natural language in a comment. Your code should be as clear as possible without comments (we call that self-documenting code). Better reasons to add comments include: copyright and licensing information, description of the formal characteristics of an algorithm (but don't worry about that yet), type/value requirements on template/function arguments, rationale for choosing one approach over another, and clarification of complex blocks of code.
Apart from that, just keep writing programs and you'll get better with time.

Does SDL need to be initialised before you use it? Being a static variable, the constructor for your Chunk::tiles variable is going to be run before anything in the main-line of your code is run...

I believe so, that would make sense. How would I go about doing that?

Non-const static data members always have to be initialized outside the class, and exactly once. Have a look at StackOverflow.

And why does it segfault? I don't understand the technical reason. I feel like that's a weird error instead of.. I don't know, something about an undefined function or something.

If you don't initialize Chunk::tiles properly, I think that'll be your best bet. Unless there are other errors in your program that I don't know about.

[Steax]

(Incidentally, if anyone has general advice for programming well besides "make things modular" "build and enforce abstraction barriers" and "document everything," I'd really appreciate you mentioning it).

While he's a web programmer, I love Jeff Atwood's Coding Horror blog. Go back in time, there's a lot of fascinating stuff to read. He covers a lot of small/light topics which other people don't talk about, but continue to be interesting food for thought. For example, why normal sorting is bad (as opposed to natural sorting), properly encrypting stuff, things to think about when providing codes on paper, and workstation ergonomics. It's the little but useful tidbits of information, like you'd get from many a good blog, which I find myself calling upon as I work.

[Yakk]

[quote="Jplus"This comment is noninformative, and besides, it's incorrect! You're not actually creating the surfaces, you're only initializing the pointers.
By the way, NULL has no special meaning in C++ (it's just the integer value 0) and in order to be portable you have to #include <cstdlib> for it, so usually we prefer to initialize and compare pointers simply with a literal 0.[/quote]I'd also be tempted to start using nullptr if your compiler supports it.

(nullptr is the only instance of the nullptr_t, a type that can be converted to any pointer type as the nullpointer of that type (foo*)0).

It describes what is going on far better than zero does. And it deals with a few corner cases of multiply overloaded functions that you may one day run into and be really confused by, and/or get bugs from. (NULL is 0, so it prefers to be turned into an int than a pointer...)

The first check is good, but the second is ambiguous. There are two possible reasons why optimizedImage might be a null pointer: (1) because IMG_Load failed and the first if statement wasn't executed, or (2) because SDL_DisplyFormatAlpha failed. If you want to be able to distinguish the two cases and not treat failed optimizing as failed image loading, you should write something like below.

That if in "if you want to be able to distinguish" is important. Sometimes you really don't care why the image load fails.

Error-oblivious programming, that logs errors and proceeds along as if they never happened, can sometimes be a good idea. Having some method of tracking down the moment the error happened is also a good idea. So a mixture of asserts, error logs, error-oblivious robust code, and non-destructive operations is sometimes a good plan.

Ie, if you are loading an image, and that will involve loading the file, optimizing the file, and then injecting it into the application...

The oblivious way to code it would be to assert things are going well, carry along an error log describing what problems you ran into as you did it, as best you can generating an image (even if it isn't a valid image), notifying the user if there where problems, and having the ability to easily "roll back" the application of the image into the application if the user didn't like what compromise you came up with.

As another example, if an optimizedImage is another kind of image (and an image that isn't optimized would work, but not be optimal), your "if loaded image is not null" code could fall back on the loaded image if the optimization failed.

Other methods would include backing out the first time a problem occurs and saying you can't do it (and why), query the user whenever a problem occurs and have the user make a decision with each problem, or segfaulting whenever anything unexpected happens. I advise against the last option.

[EvanED]

Code: Select all

    void generateImage(int, int); // Generates a blank image with width and height of whatever's passed to it

This is a better comment, because it adds information. There is, however, a more concise way to document your code:

Code: Select all

    void generateImage(int width, int height);

Agreed, though the original comment still has one piece of information: it will create a blank image. (As opposed to, say, an uninitialized image with random colors.)

However, that's only a little bit more informative. What's "blank"? Solid white? Solid black? Solid (some global "current color" setting)?

By the way, NULL has no special meaning in C++ (it's just the integer value 0) and in order to be portable you have to #include <cstdlib> for it, so usually we prefer to initialize and compare pointers simply with a literal 0.

I've heard this advice, and while I don't feel strongly about it, I do disagree. Especially in comparisons, I think NULL is clearer. It also gives the complier (at least GCC) the ability to give warnings about misuses of NULL, which double-checks your beliefs. (This is more important if you're using typedefs to pointers.) For instance, int x; if (x == NULL) .. and void foo(bool x); foo(NULL); will both produce a warning.

Yakk's suggestion about nullptr is a good one if you can swing the complier support. But IMO it's not widely-supported enough now that it's a good idea to rely on it. (Though apparently you can emulate it -- see the first answer.)

[Yakk]

gcc 4.6 supports it. MSVC 10 supports it.

If your compiler doesn't support it, install gcc.

Or use:

Code: Select all

const                        // this is a const object...
class {
public:
  template<class T>          // convertible to any type
    operator T*() const      // of null non-member
    { return 0; }            // pointer...
  template<class C, class T> // or any type of null
    operator T C::*() const  // member pointer...
    { return 0; }
private:
  void operator&() const;    // whose address can't be taken
} nullptr = {};              // and whose name is nullptr

(from the stackoverflow link above, which gets it from the C++0x proposal, who got it from yet an earlier source, etc).

I'd be tempted to do this:

Code: Select all

const                        // this is a const object...
class nullptr_t {                // of type nullptr_t
public:
  template<class T>          // convertible to any type
    operator T*() const      // of null non-member
    { return 0; }            // pointer...
  template<class C, class T> // or any type of null
    operator T C::*() const  // member pointer...
    { return 0; }
private:
  void operator&() const;    // whose address can't be taken
} nullptr = {};              // and whose name is nullptr

but there might be a reason why not.

[EvanED]

gcc 4.6 supports it. MSVC 10 supports it.

And both of those are the latest stable versions. Want it to be compilable on RHEL? RHEL 6 ships with 4.4. RHEL 5 ships with 4.1. Edit: And just to emphasize, RHEL 5 isn't even out of the first support phase (of 3 phases of regular support) until the end of this year. Even RHEL 4 is still in phase 3 of regular support, and doesn't enter extended support until the end of this month.

How much burden you want to place on your users is up to you of course, but there is plenty of reason that you might want to support older compilers.

[Shivahn]

Thanks everyone! That's a lot of stuff to mull over. The documentation in particular, I know that's a weak point of mine. I'll be reading over all this for a while.

One simple way to fix the problem, by the way, was to just make a default Image constructor that was empty, rather than trying to load a default image. That way tiles doesn't try to load an image before the SDL library is initialized. I feel kind of silly, since that was such a simple solution.

[Jplus]

It happens to everyone. Keep it up!

[Malconstant]

I'm trying to develop an Android app, and I'd like to be able to get it on my phone without bothering to put it up on the Android Marketplace. So I made the appropriate .apk file from Eclipse, and tested it with an emulator, so I'm sure the file's fine.

I mounted my phone to my computer, where it gave two removable disks (HTC Rezound, apparently one of them corresponds to phone storage and the other corresponds to the SD card). The HTC Rezound user guide suggests that copying a file to the root directory to either of these removable disks will suffice to place a file on the phone.

I've since copied my .apk to both directories, and for kicks made an APK folder to put another copy in because some tutorial suggested it. I've also e-mailed the file to myself and downloaded it on my phone from there. From the e-mailed version I get the error message: "Parse error. There is a problem parsing the package".

I've downloaded ASTRO, AndExplorer, and AppInstaller to try and find the files on the phone, and so far only AndExplorer seems able to find the file, and when I try to access it from there it gives me the same parsing error.

So I feel this problem is getting a little silly. Does anyone have experience with this part of Android app development?

[gametaku]

Method 1

1. Enable usb debugging.
2. Connect your phone via usb to to the computer.
3. Run the program in eclipse, and it should send to your phone.

Method 2

1. Open the command prompt
2. Navigate to the android tools directory (skip if you have the path added)
3. type: adb install <path_to_apk>

[Breakfast]

Well, my code does work but I'm trying to make it more efficient. It's written in C# and here is my original code:

Spoiler:

Code: Select all

        private static List<int> QuickSort(List<int> listOfNumbers)
        {
            if (listOfNumbers.Count <= 1)
            {
                return listOfNumbers;
            }
            else
            {
                List<int> _partitionValue = new List<int>() { listOfNumbers[listOfNumbers.Count / 2] };

                listOfNumbers.Remove(_partitionValue.First());

                List<int> _lessThanPartition = listOfNumbers.Where(x => x <= _partitionValue.First()).ToList();
                List<int> _greaterThanPartition = listOfNumbers.Where(x => x > _partitionValue.First()).ToList();

                return QuickSort(_lessThanPartition).Concat(_partitionValue).Concat(QuickSort(_greaterThanPartition)).ToList();
            }
        }

This took ~51 seconds to sort a list of 10 million integers. Microsoft's built in Sort() for Lists takes ~1.5 seconds. Where I'm at currently with my code takes ~8.5 seconds. It does an Insertion Sort if the list is <= 45 elements, otherwise it's doing an inplace Quicksort. I apologize for somewhat poor readability. Putting the Insertion Sort, Swap and Partition functions inline shaved ~4 seconds off the runtime. Here is where I'm at now:

Spoiler:

Code: Select all

       
        private static void QuickSort(List<int> listOfNumbers, int leftBound, int rightBound)
        {
            if (leftBound < rightBound)
            {
                if ((rightBound - leftBound) <= 45)
                {
                    #region Insertion Sort

                    for (int i = leftBound; i <= rightBound - 1; i++)
                    {
                        int _insertionValue = listOfNumbers[i];

                        int j = i - 1;

                        while (j >= 0 && listOfNumbers[j] > _insertionValue)
                        {
                            listOfNumbers[j + 1] = listOfNumbers[j];
                            --j;
                        }

                        listOfNumbers[j + 1] = _insertionValue;
                    }

                    #endregion
                }
                else
                {
                    #region Quicksort

                    int _partition = leftBound + (rightBound - leftBound) / 2;

                    #region Partition

                    int _pivotValue = listOfNumbers[_partition];

                    int _temp = listOfNumbers[_partition];
                    listOfNumbers[_partition] = listOfNumbers[rightBound];
                    listOfNumbers[rightBound] = _temp;

                    int _storeIndex = leftBound;

                    for (int i = leftBound; i <= rightBound - 1; i++)
                    {
                        if (listOfNumbers[i] < _pivotValue)
                        {
                            _temp = listOfNumbers[i];
                            listOfNumbers[i] = listOfNumbers[_storeIndex];
                            listOfNumbers[_storeIndex] = _temp;

                            _storeIndex += 1;
                        }
                    }

                    _temp = listOfNumbers[_storeIndex];
                    listOfNumbers[_storeIndex] = listOfNumbers[rightBound];
                    listOfNumbers[rightBound] = _temp;

                    _partition = _storeIndex;

                    #endregion

                    QuickSort(listOfNumbers, leftBound, _partition - 1);
                    QuickSort(listOfNumbers, _partition + 1, rightBound);

                    #endregion
                }
            }
        }

The options I'm looking into include a dual pivot, trying to run parts of it in parallel, and possibly doing away with recursion and making it iterative (although I don't think this option would help all that much). Wikipedia gives a big O analysis of a parallel quicksort but I'm not sure what parts could safely run in parallel.

[PM 2Ring]

Sorry, I don't know C#, but your code looks readable enough to me.

In Ancient Times, we'd recurse on the smaller sub-partition and loop on the larger sub-partition. Modern compilers can automatically eliminate tail recursion (I assume C# can do that), so all you need to do is ensure that you sort the smaller sub-partition with the first recursive call.

Why did you choose 45 for the cut-off point? You might be able to make that a bit smaller; I generally make it around 20 or so, but I haven't written my own quicksort() for at least a decade when machines were somewhat smaller (and slower) than they are today. If you want to use this quicksort for a specific application, testing is required to determine an optimal cut-off point. If you're just sorting smallish lists of integers or tables of strings, and lots of your data can fit into your CPU's cache, you can probably make the cut-off fairly high.

Another optimization to consider is to use a sorting network for very small sub-partitions (around 10 elements or less) instead of insertion sort.

[Breakfast]

On a cursory glance it appears C# .NET 4.0 does handle tail recursion although previous versions do not. I am using 4.0

I was planning to mention why I decided on 45 in my last post but forgot. 45 was picked from experimental test runs because it appeared to give the most optimal times (~8 - ~9 seconds) when compared to number of quicksorts / insertion sorts being performed. Numbers < 40 or > 50 would consistently give me > ~9 seconds runtime. With a dual pivot method I would probably choose a smaller number.

As for readability, I only meant that it's one large function instead of being broken up into several, more compact ones.

[Jplus]

I suspect the Microsoft implementation you're comparing your code with isn't parallel, which would indicate you can still do it much faster without parallelising your code. After reading your code, I have a few suggestions in addition to those from PM 2Ring.

First of all, you're currently doing more swaps than strictly needed. There is no need to move the pivot to the end of the array, and you could be more efficient if you moved indices from both ends of the list. Let the left index go up until it meets a value that is not smaller than the pivot, let the right index go down until it meets a value that is not larger, break the loop if the left index and the right index have met or swap and repeat otherwise.

Secondly, you could do slightly better by choosing the pivot more cleverly. The most common approach is to take the median of the first, middle and last elements of the array. I never heard about a "dual pivot".

Thirdly, you could greatly reduce the number of comparisons in the insertion sort by first checking whether the element to be inserted is smaller than the front element or not. If it is, move it to the front straight away without comparing it to all the intermediate elements. If it isn't, do an unguarded insert: it's the same as your current inner loop, but without the check that prevents you from walking off the array.

Finally, you can improve a little by delaying the insertion sort until the end. If the subrange is shorter than your insertion sort treshold, just return directly from the quicksort function. When the topmost quicksort has returned, do a single insertion sort pass over the entire array. This requires you to "outline" the insertion sort function again, but you save yourself O(log n) function calls. You can also switch to unguarded insertions entirely when you've inserted more elements than the treshold, which lets you shave off even more comparisons.

EDIT: small but very important erratum.

[Malconstant]

@ gametaku

You are a beautiful human being. the USB debugging was the trick and it's working just fine. Turns out I was using a much higher API on Eclipse than my phone could handle. I was hoping fixing that would let me e-mail them but no dice, but just running through Eclipse does the trick.

Thanks again!

[Breakfast]

Thanks for all of the suggestions Jplus. I'll get to trying those as soon as I can.

I also doubt that Microsoft is using parallel processing techniques. However, if I can figure out a good way to implement it, it might help. .Net's built in function Parallel.Invoke() actually slowed the runtime down to ~12 seconds because of overhead.

Code: Select all

Parallel.Invoke(() => QuickSortFast(listOfNumbers, leftBound, _partition - 1), () => QuickSortFast(listOfNumbers, _partition + 1, rightBound));

Here's a link to the dual pivot method:
http://gdtoolbox.com/DualPivotQuicksort.pdf

It did become Java's sort of choice at some point but I'm not sure if it's still being used.

[PM 2Ring]

Finally, you can improve a little by delaying the insertion sort until the end. If the subrange is shorter than your insertion sort threshold, just return directly from the quicksort function. When the topmost quicksort has returned, do a single insertion sort pass over the entire array.

Nice trick, Julian!

I must confess I didn't look closely at Breakfast's code, since I'm unfamiliar with C#, so I didn't notice those other inefficiencies you mentioned.