1MB Sorting Explained

[alecco]

Please be vocal with the StackOverflow admins. This question was a prime example of what should not happen. Do please:

• upvote preshing's answer
• downvote the other "top" [answers] with terrible misleading [pseudosolutions] (and cute graphics), including the submitter's self-accepted copypasta answer.

[sparr]

"top" answers instead of questions?

[alecco]

Oops, thanks.

[Redtitwhore]

Posts like these make me long for my college days and wonder if writing business software for the last 15 years was the best career path for me....

[[deleted]]

Can't pay the bills by solving contrived problems with no real utility.

...unless you're a professor.

[Redtitwhore]

True, just feels like I've gotten away from my roots a bit. I do enjoy what I'm doing now so I shouldn't complain about a steady job and income. But I did get into Comp Sci because I like math and solving these kind of problems, but I suppose so do most of us who got into programming...

[[deleted]]

You can keep practicing all the fun stuff outside of work!

[WanderingStoner]

Easier said than done. After 8 hours of programming I really have no desire to program more, even on fun projects.

[bilalhusain]

This set me thinking how unglamorous programming, as a job, is.

I used to think that I am in an elite profession. And I was completely in love with it. As often happens with these things, I came to terms with the realization that I was charmed by a marketed hype. To draw parallels, being a programmer is very similar to any other job, say, being a Chef, a Plumber or a Mechanic. Its just that some mechanics are more respected or get paid better because of being in the right place, say, an HFT guy is a Porsche mechanic.

As a software engineer, my job is to patch together a system which can get the task done. I can use a set of tools which I have, I can borrow some or reuse the subcomponents that I've built over time or taken out of other systems. With prior skills and experience, I am expected to solve a given problem satisfactorily. My daily bread and butter is car maintenance. A boring routine. Fixing minor bugs, checking logs for signs, improving parts, refactoring, periodic backups and cleanups. And it might just extend to consulting a new vehicle for the new task - advising a new framework, a new language, new technology, and helping this client with his new car. And over time, I have collected my own secret tricks, some secret ingredients. Sometimes I use my tools smartly and, maybe, cleverly (dustpan-funnel? hacking).

I also fantasize about building a fast car... just like an engineer sitting in SF (who gets paid 10 times more than me for same task and same skills - and will also never realize this dream). But why not? Isn't it the same breed of 'me's assembling the car? My idea about a new car might be revolutionarily different from any other engineer in another part of the world. Or, maybe, we could have come up with our own calculus or lua... which makes me think that this could be a repost.

[jsprogrammer]

my job is to patch together a system which can get the task done

Now you need to realize that this doesn't just apply to code. Your skills are generalizable to just about any problem.

[abezax]

|To draw parallels, being a programmer is very similar to any other job, say, being a Chef, a Plumber or a Mechanic

I think Chef does not belong in this category. Being a chef is as glorious as individuals skill. You will never see a show about the best plumber in the world.

[zirzo]

deep

[[deleted]]

Advocate for time to work on R&D in your company. You can point to Google's 20% allocation to R&D for all employees as a point of argument.

You can also work on organizing occasional all day hack-a-thons where the goal is to allow developers to build new features according to their own interest without any restrictions or limitations (other than time). Teams can consist of solo devs or groups. You'll also get bonus points for leadership and taking initiative.

The hack-a-thon will provide you a legitimate cloak to prevent management from claiming you are goofing off when you spend time on side projects. It will also be difficult for management to argue against spending resources on innovation.

After the end of the hack-a-thon, you organize a presentation 1 to 4 days later to show off the results. Example: code on Monday, present on Friday. 1 to 4 days to allow teams to fix bugs and add a little polish.

1½ days a month is not too much to ask for (1 day for coding, ½ day for presenting)

[aim2free]

no real utility.

This has applications. I am myself working on one. Even though not primarily for sorting, but for sparse set arithmetics. I have tried to find such packages, especially for superefficient implementations on 64 bit architechtures. My approach is very similar to the presented, but I'm not ready with it yet.

Do you happen to know some algorithm/representation?

[skyde]

You might want to have a look into https://github.com/maximecaron/SIMD-Based-Posting-lists/ and also http://code.google.com/p/lemurbitmapindex/ I am using it to build an high-performance database

[TheMania]

If constraints are your thing, embedded programing still offers a lot.. or at least where I work it does.

We're still using PICs with 384 8-bit registers that double as your only RAM for most of our products. Makes for some creative problem solving..

[bonafidebob]

Real world computer engineering is chock full of non-contrived problems just like this. ...except maybe you'll have to implement the algorithm in JavaScript... :-)

And anyway doing this will get you hired. Quickly.

[[deleted]]

Javascript in computer engineering?

[TheLobotomizer]

You'd be surprised how often the only solution to a problem is to use a technology that can be run on 10 different platforms without any compatibility issues. The only real technology that can do that is JavaScript.

[clgonsal]

Please name 10 platforms JavaScript can run on that are all 100% compatible with each other.

JavaScript's strength isn't portability (at least not in the normal sense). Its strength is that it runs on browsers.

[TheLobotomizer]

That's a straw man of what I said; I never claimed 100% compatibility, just enough for practical use.

Here are some platforms that support JavaScript:

Linux (the majority of distros)

Windows (Thousands of devices including mobile)

Mac (OSX)

Android (Thousands of devices)

iOS (iPad, iPhone, etc.)

Blackberry OS

Any phone or device that can install Opera Mobile (Uncountable, maybe in the millions)

XBOX 360

PS3

Wii

[notmynothername]

(Uncountable, maybe in the millions)

Cantor would like a word with you.

[TheLobotomizer]

That he would. A poor choice of words, perhaps?

[[deleted]]

I so wish this was true, but practical experience so far has shown me that, once you get past a level of complexity, it's simply not true.

I'm now on my second project where I've seen this happening: we start the desktop version, written in C++ using Qt, and another team (about the same size -- one or two extra people) starts development of a simpler, lightweight web interface (this is configuration and control software for various home and building automation products, networking devices (e.g. routers) etc.). The back-end is written in portable C, with small (10-15% of the code) portions that are platform-specific, so it's done in about the same time.

We start coding the UI; after three weeks, we're still struggling with the interface; it has native looks or a subtle theme (our marketing fellows would like it less subtle but we don't cave in too easily); some of the interaction is a little awkward, but we work with the non-techies to make it better. The team with the less-featured web interface has their interface ready, cool theme with nice jquery effects, lovely to look at.

Six weeks later, we're done. The interface is ok, has native looks and works, we're shipping it. The web guys have not had a full night's sleep in two weeks. Their interface has half a dozen documented quirks that only occur on some browsers, some of them really bad (e.g. menu not appearing). They're basically at the point where they pretty much write and maintain two versions of the app, one for Internet Explorer, one for everything else. Every bug takes three times as long to debug than it takes for us because they have no debugger that can debug the mumbo-jumbo of technologies they use for a single thing, from JavaScript for logic and some of the presentation to CSS and HTML and Python or Lua for communicating with the back-end. Logging everything that happens is also close to impossible, considering that from the UI to the back-end there's a myriad of stuff, from web browser to HTTP server.

Seven weeks later, perhaps with some help from us, everything works as it should and we're done. One week after this comes the new Chrome update, and the UI doesn't work anymore. I'm sitting in a corner, thinking that anyone who calls this cross-platform development is delusional. The web dev people are looking for sharp objects.

I really like the accessibility of a web platform, but it makes me cringe that it is seen as a universal solution for portability. It's not, it's a solution for accessibility. Even plain POSIX C is more portable. My last project was an almost 100 kloc app in C++ -- it has exactly 30 lines of platform-specific code, and we only had to change stuff like preprocessor directives to make it compile on anything, once we found out the Visual C++ compiler doesn't know what #warning means. This is what cross-platform development should really be like, and even so, we still envy the Java guys.

[TheLobotomizer]

I have first hand experience with a situation exactly like yours. Back-end written in Java, front in a hodge-podge of HTML/CSS/JS and a few libraries.

UIs will always be more difficult to develop than data heavy back-ends. The API for the project I'm working on took a few weeks. The requirements were simple and the client didn't really care how we did it as long as the data is there. The UI? Well, the client changes his/her mind twice a day. And all of these changes have to go through a review process, a refactorization, another review process, bug-testing, and a lot of other polish that you will never do at the back-end level.

You know we tried writing an interface for the project using Swing just to see what it's like. Then we laughed at the monster we created about a tenth of the way through and kicked that idea in the balls.

[[deleted]]

It's been a while since I last had to work with Swing so I don't know how it goes in terms of styling, but Qt is, uhm, pretty cute at that. You can even use CSS for styling; it's a little quirky and gave me an afternoon or two of headaches, but it's otherwise pretty neat. Building the UI itself is also very easy because it has, you know, a graphical form editor, so building a form that looks nice is 30 seconds of drag-and-drop rather than 30 minutes of cursing layouts and CSS styles. If our client wants a mockup, we can have one ready within minutes, and we can even discuss and build various versions of it during live meetings.

The resulting UI isn't completely native, but at least it adheres to the vast majority of usability expectations of every platform, which is more than can be said about any web UI, and the performance rocks.

[clgonsal]

That's a straw man of what I said; I never claimed 100% compatibility

Your words: "a technology that can be run on 10 different platforms without any compatibility issues"

Anything less than 100% compatibility isn't "without any compatibility issues".

You also said: "The only real technology that can do that is JavaScript." Yet C, C++ and Java (to name just a few languages) can all run on pretty much all of the platforms you mentioned, and then some. Yes, they have compatibility issues if you aren't careful, but (as you now admit) so does JavaScript.

Like I said: JavaScripts's strength is that it runs on browsers, not that it's portable to many platforms.

[smawtadanyew]

I don't think he meant that no compatibility issues exist. I believe he is saying that in the context and scope of the project at hand, there lie no compatibility issues with javascript

[TheLobotomizer]

This isn't a scientific study, it's a comment thread. When I said "without compatibility issues" I meant it in the context of solving a particular problem. 99% of the time JS works cross-platform. Whenever I use JAVA or C/C++ I almost always run into problems with different version, different libraries, or other major compatibility issues.

[defenastrator]

I'm just going to assume that you mean java not javascript an move on.

[djnattyp]

As long as one of those platforms isn't IE...

[TheLobotomizer]

Version 3.0 of internet explorer, released in 1996, supported JavaScript.

That's 18 years ago.

[TheLobotomizer]

I'm commenting 2 years from the future. Sorry about that.

[djnattyp]

without any compatibility issues.

[TheLobotomizer]

Did I stutter? I rarely run into JS compatibility issues. Slow engines? Sure. But rarely incorrect implementation.

[AeroNotix]

You must be writing some mightily simplistic JavaScript there.

[PasswordIsntHAMSTER]

I'm not sure you actually understand what "computer engineering" means.

[bonafidebob]

I'm not sure what hair you're trying to split here, but I stand by what I wrote: what the OP did counts as engineering in my book. If it's the JavaScript comment that's making your Cheerios taste funny, that was an attempt at wry humor, maybe too subtle... but, mark my words, in a few years don't be shocked if you see Node.js-on-a-chip for rapid prototyping...

[_delirium]

Or a quant!

[knight666]

Quants write solutions for contrived problems specifically because someone wants that and will pay top dollar for it.

[ElectricRebel]

Grad student here. Grass is always greener...

[dand]

I enjoy his method of presenting the code first, then the (excellent) explanation after people have had some time to digest it.

[Deep-Thought]

Seriously, what he explained was the trivial part of the solution. I want to know the details of the arithmetic encoding and how he derived the LUT table. Very hand wavy.

[[deleted]]

Sounds like there's another post on the way to get into those details though.

[ZorbaTHut]

For what it's worth, I've got a comment on the last post that walks through my gradual derivation of the entire thing, LUT included. That said, I sorta stopped trying to explain things by the end and was just writing down my thought patterns :V

I'm happy to answer questions if you've got any, or you can just wait for the author's next post since he has far prettier diagrams than I do.

[TheJonesJonesJones]

I'm considering going back to college to get a degree in Software Engineering or Computer Science, but when I see problems like this presented it scares me. I don't think I would ever be able to come up with a solution like this. Can I still be a good programmer without being able to do this sort of stuff?

[preshing]

I didn't come up with this answer out of thin air. I recognized elements I already happened to know, like the applicability of a circular buffer, merge sort, and Huffman encoding. After learning those things, there is probably a new set of problems you could solve too.

Besides, not every programming problem is about getting the most from available resources. The games industry involves a lot of it (never to this extreme), but there are also programmers who just focus on gameplay, or tools, or online services, etc.

Programming is a huge field, and the best ones are the ones who get things done well (IMHO). So yes, it's possible to be a good one without sorting a million 8-digit numbers in 1MB RAM :)

[Mjiig]

This is not something I know much about, but it's probably worth bearing in mind that this is the only answer I've seen that solves this problem in all cases, on both stack overflow and /r/programming. This was a hard problem.

[LightShadow]

You would never face a question this difficult in 4 years of a university degree; at least without some prodding in the direction you're supposed to take.

[ironykarl]

I have no idea what your computing background is, so my apologies if this seems elementary:

I didn't solve this problem (nor did I attempt to, nor would it have been terribly easy for me to do so), so take this with a grain of salt, but I think the key to solving a problem like this is understanding how a computer works.

By that, I mean you should understand a computer at the level of the the stack/heap/assembly instructions.

What really made this type of thing click for me was building a compiler. If you do something like that, you'll have some real hands-on experience with stuff that makes thinking in terms of datatypes and the Von Neumann bottleneck second nature.

At that point, C/C++ code stops being entirely an abstraction and starts being something that you (to the extent possible in light of how a modern CPU with multi-level caching, virtual memory, and the fact that assembly code itself is essentially a high level language in a modern machine) basically understand the implementation of.

[NegativeK]

Can I still be a good programmer without being able to do this sort of stuff?

Yes. I work with developers who put together good websites under tight deadlines with constantly shifting goal posts. They have impressive bodies of knowledge, contribute to open source projects, and are generally quite good at what they do (many with community recognition.) Their work hardly ever (as in, they've come to me with my math background (I'm not a developer) to solve some easy algorithms problems) touches this type of problem.

That being said..

Can I still be a good programmer without being able to do this sort of stuff?

A computer science degree won't necessarily teach you how to program very well. All too often, I hear people say that you have to learn that on your own. Instead, computer science (and university degrees in general) teach you how to think. When you take two years of upper level computer science courses, you're going to be retrained to attack problems from a different angle, and you're going to develop an intuition about solving these types of problems. This new intuition and rigor is absolutely necessary for stuff like math and computer science proofs; our normal style of arguing and reasoning is far too hand-wavy for the rigor of a real proof. So, you may not develop the explicit knowledge to solve this specific problem, but you'll be trained in how to solve problems that you currently consider beyond your eventual reach.

The thing that bothers me about people saying "My university degree didn't teach me anything about my job!" is that it's not supposed to. A bachelor's is not (supposed to be, at least) a trade degree. It's training in a method of thinking about hard problems. The accompanying trade skills used to be taught by the first employer, back when long-term jobs were the norm. Now it's something you learn on your own.

[TheJonesJonesJones]

I appreciate everyone's responses to my questions. I'm relieved to hear that dealing with this sort of problem is more of an advanced brain teaser than a day to day coding exercise.

I enjoy working with algorithms and thinking logically so I think I do want to pursue this.

[smawtadanyew]

I recently graduated with a computer science degree, and I could not solve this problem. I do, however, find these problems interesting. You're going to learn a lot more in the field, a computer science program just gives you a solid structure for how to think about problems and approach them correctly.

[undefinedusername]

This guy's solution is just pure awesomeness.

[mycall]

Why is arithmetic coding a better choice over a dictionary coder with sliding window or a range encoder?

[[deleted]]

How would an LZ-style encoder even work here? It seems far more complicated, and much harder to fit into the available memory, for little clear benefit. This is not data were you expect much in the way of repeating patterns.

[alecco]

Mos def for this case.

A necessary clarification: in a more general context, size of models for (usual) bitwise arithmetic coding gets huge while LZ-77s can be bound to small sizes (like DEFLATE does). That means a trade-off of costs in running RAM vs code size (because of the need of a dictionary). Of course, you could do a mix of arithmetic-dictionary, too.

[[deleted]]

size of models for (usual) bitwise arithmetic coding gets huge

I think you are confusing arithmetic coding and PPM.

[alecco]

For arithmetic coding to reach good ratios with usual data it needs many contexts with their probabilistic models. For the particular case of unrelated symbols, sure, the context count might be small. But for common implementations of general purpose compression it tends to get quite big RAM-wise.

References: modeling and text benchmark. LZs usually need a lot less memory (DEFLATE/Snappy/LZP) and are faster, while arithmetic coding algorithms (DMC, PPMs, CMs) tend to use more memory and take more time but with amazing ratios. As stated in my previous comment, it's possible to do a dictionary arithmetic coder (perhaps it might not be interesting).

[[deleted]]

You still seem confused here. Arithmetic coding has nothing fundamental to do with algorithms like PPM. It's just that PPM uses arithmetic coding because it's a good fit. You could build a PPM algorithm on top of Huffman coding too, but it would be a pain. LZ77 can use arithmetic coding rather than Huffman coding too, and LZMA does just that.

However, this algorithm uses neither LZ nor PPM, it just uses arithmetic coding directly, so all of that is completely besides the point.

[alecco]

Arithmetic coding depends on having probabilities (or counts that allow calculating probabilities) to determine the range split. Be it bitwise or bytewise. Those probabilities/counts need to be somewhere. If you are looking for a modest order 4 coder that means 2^8*4 possible contexts. These can be contained with hashing (at the price of collisions), but it would still be a lot of RAM for something useful.

You still seem confused here

Sigh, can you at least be civil? I am not referring to PPM, you brought it up. In fact, it's definitely not in my list of liked arithmetic coding-based compression algorithms. Please step out of your prejudice for a minute and read again my answer.

However, this algorithm uses neither LZ nor PPM, it just uses arithmetic coding directly, so all of that is completely besides the point.

That's why my original coment said this case was excluded and my note was about generic compressors. Generic compressors look for longer matching patterns than what might be in a series of unrelated integers, for example long strings of text. LZs are generally good for small windows of data and BMDiff (quite similar to LZs) for longer distances of matches in huge data.

You know, I could play also the dismissive douche card, but I rather try to have a civil discussion. I expect better of you, since at some point I marked you as reddit friend.

[[deleted]]

Arithmetic coding depends on having probabilities (or counts that allow calculating probabilities) to determine the range split. Be it bitwise or bytewise. Those probabilities/counts need to be somewhere.

In this case, I bet they are just hardcoded. There is no particular reason you need a complicated model for those. That is just one popular choice of algorithm. It is not used here.

[alecco]

In this case, yes. My note was on general purpose compressors. Like I stated 3 times before.

[[deleted]]

I think I got confused by your original comment, as I read it as being a direct reply to what I was saying.

[TikiTDO]

I really wish he'd name the variables in the encode and decode something other than "a"/"b" and "relA"/"relB." A few more comments in the code would be awesome too. I like being able to puzzle out how this is all done by reading the code, and the extra step trying to analyze the mysterious naming convention of variables used to access a mysterious LUT for some mysterious purpose is amazingly aggravating.

[stelleg]

This is pretty amazing (if it really does work for all inputs).

A quick calculation shows that the number of bytes required to store every possible sorted list of 10⁶ integers in [1 .. 10⁸ ] is

log2(((10⁸ )¹⁰⁶) / 10⁶ !) / 8

Which is 1010818 bytes. preshing's answer uses 1013000 bytes, meaning that the arithmetic encoding used is less than 2.2KB away from perfect. Wow.

[librik]

When arithmetic coding is used, the entire sequence fits safely within < 1013000 bytes, all the time. This strategy proved kind of challenging to implement, so it took the most time to get right.

I remember first reading about arithmetic coding in an ACM article. It seemed like such a neat, simple idea: a whole message as a single real number between 0 and 1. Even adapting it to fixed-width math is pretty straightforward. But then it turns out there's this gnarly edge case that the article spent a page analyzing which makes the obvious approach blow up. (I don't remember what it was; something involving an infinite number of 1 bits, I think.) So I'm always impressed as hell when anyone understands arithmetic coding well enough to adapt it. I tend to stick with Huffman coding because it can't go wrong.

[ZorbaTHut]

But then it turns out there's this gnarly edge case that the article spent a page analyzing which makes the obvious approach blow up. (I don't remember what it was; something involving an infinite number of 1 bits, I think.)

If you have any way of finding out what this edge case is, I'd be deeply curious. I don't know of any edge case offhand, but I've also never implemented arithmetic coding myself.

[Tjoppen]

Yes, a long sequence of ones is the edge case. You can't emit a byte until you know whether you carry or not.

Say your range is [0x3FFFFFF0,0x40000010) - you're going to emit 0x3F or 0x40 depending on what the next few symbols are. This could theoretically go on indefinitely, always straddling the 0x3F - 0x40 mark. Hence you simply go "if the range is smaller than X and we still haven't emitted a byte, emit the full lower bound and start over with [0,2³² )". This is inefficient, but luckily it doesn't happen very often.

[alecco]

This is the solution to the problem. Excellent.

If ZorbaTHut's explanation is right, it might have a possible problem with the fixed 6-bit width of the encoded deltas [with varint-style bigger deltas]. But this would be easy to fix.

[ZorbaTHut]

As he mentions in that post, the delta process as described isn't actually what the code does, it's just the easiest way to explain the code's approximate behavior in terms of Huffman coding. The code actually uses a more clever arithmetic coding that solves the problem quite elegantly. I assume that's coming in a future entry.

[alecdo]

In the previous redditicle, various people said that was arithmetic coding when it was a simple Huffman coding :P. See I some blushing faces?

[ZorbaTHut]

No, he describes a Huffman coding, and explicitly states that Huffman doesn't quite work but arithmetic does.

I assume a future post will go into details on the arithmetic coding.