News for hackers. Stuff that matters.
Re:Khan Academy: Algorithms by symlinkk on Sunday March 15, 2015 @03:12AM (#9205678)
I'm in college right now and I've been wondering...do professional programmers actually think about sorting algorithms on a day-to-day basis? How relevant is this knowledge when it comes to actually making something?
Re:Khan Academy: Algorithms by patio11 on Sunday March 15, 2015 @03:22AM (#9205694)
Ask a simple question, get a simple answer: no. While there are some programmers who develop libraries, the majority will just consume well-understood sorting algorithms which are baked into their languages/standard libraries/etc of choice. If you find yourself coding mergesort and you are not in a job interview, a nightmare, or a nightmare of a job interview, you are probably doing something wrong.

That said, most of the reason we teach sorting algorithms is to teach algorithms in general, and particularly the consequential lesson that "There are often many methods to doing something that work; these methods are often different in extraordinarily consequential ways; the right method for certain problems -- even ones which look trivial on the outside! --may require literally years of R&D to develop."

Re:Khan Academy: Algorithms by drcode on Sunday March 15, 2015 @10:24AM (#9206590)
I personally think distributed networks with smart contracts are going to be "a thing" soon, and in that kind of environment virtual cpu cycles are constrained to a level where an Intel 8080 processor looks like a speed demon.

In that type of environment, you need to do a lot of thinking about basic algorithm science, including exploring the many types of sorting algos.

(Here's some code I'm working on right now in that vein, which helps to perform efficient percentile calculations in a smart contract https://github.com/drcode/ethereum-order-statistic-tree)

Re:Khan Academy: Algorithms by aninhumer on Sunday March 15, 2015 @05:21AM (#9205918)
Even ones that look trivial on the inside might take years of R&D to develop.
Re:Khan Academy: Algorithms by throwaway43 on Sunday March 15, 2015 @05:40AM (#9205945)
Any examples ?
Re:Khan Academy: Algorithms by dhotson on Sunday March 15, 2015 @08:52AM (#9206301)
Boyer-Moore (finding a string in another string) is a good example: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sear...
Re:Khan Academy: Algorithms by danieldk on Sunday March 15, 2015 @07:11AM (#9206093)
Re:Khan Academy: Algorithms by CoreDumpling on Sunday March 15, 2015 @06:17AM (#9206000)
Re:Khan Academy: Algorithms by gleenn on Sunday March 15, 2015 @03:46AM (#9205745)
I had a professor who told the class that if they ever wrote a sorting algorithm professionally, they should be fired. Depending on where you go, college is some cross between academia and training to get a job, and usually biased towards academia. While not directly relevant to daily programming, understanding time complexity and whats going on under the hood are very useful for understanding many things that I do use on a regular basis.

For instance, adding an index to a database table is something I regularly do for performance, and the reason is based on principles I learned in college. The runtime complexity of an indexed table is way better. Any monkey coder can add the index too, the difference is that I know what's going on under the hood (finding things in a ordered tree data structure are way faster than scanning through the whole table).

I was grumpy learning some things in college early on, and the more I advance my career, the more I appreciate the things I learned even if I don't code them up, or even use them, on a regular basis.

Re:Khan Academy: Algorithms by eru on Sunday March 15, 2015 @07:04AM (#9206081)
> I had a professor who told the class that if they ever wrote a sorting algorithm professionally, they should be fired.

For straight up sorting, yes.

But, some other algorithms have exactly the same structure as sorting.

As a toy example, take the famous skyline problem. See https://briangordon.github.io/2014/08/the-skyline-problem.ht... for the details:

"You are given a set of n rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each rectangle, you’re given the x position of the left edge, the x position of the right edge, and the height. Your task is to draw an outline around the set of rectangles so that you can see what the skyline would look like when silhouetted at night."

One approach to solving the problem is equivalent to merge sort: you write a merge function that merges two lists of in-order non-overlapping rectangles, and go from there.

Re:Khan Academy: Algorithms by jameshart on Sunday March 15, 2015 @01:39PM (#9207281)
Which turns out not to be a toy problem at all - with the x axis representing time, and the y axis representing things like 'resource utilization' or 'seat reservations' or 'room bookings', all of a sudden you've got the basis for any number of resource optimization or allocation problems.

A related problem (not the same problem, but amenable to the same sort of approaches), for example, comes up when displaying overlapping appointments in a calendar timeline view.

Re:Khan Academy: Algorithms by eru on Sunday March 15, 2015 @08:14PM (#9208857)
Indeed. And the merge sort approach to solving these intervall-as-a-datastructure problems parallelize nicely.
Re:Khan Academy: Algorithms by xxs on Sunday March 15, 2015 @08:26AM (#9206247)
>>I had a professor who told the class that if they ever wrote a sorting algorithm professionally, they should be fired.

Not many out of the box libraries would have find N min out of a stream/iterator...draw the moving median, moving min/max and so on. You won't find a red/black tree with linked next nodes to do the task efficiently. So sometimes there is that.

Re:Khan Academy: Algorithms by karmacondon on Sunday March 15, 2015 @06:22AM (#9206008)
I realize that you chose one example off the top of your head, but it seems like an incredibly rare case. The majority of developers can understand "Queries involving this column are slow, it needs an index". Slightly more sophisticated developers can use an EXPLAIN statement (or it's equivalent) to see how many rows are being scanned and apply indexes where necessary. How many hours of coursework is it worth to obtain the knowledge "finding things in a ordered tree data structure are way faster than scanning through the whole table"?

I'm not sure if I've ever run into anyone who said "The things I learned in college have turned out to be pretty much worthless in my professional career. I wasted a lot of time learning irrelevant information." It's interesting that the majority of every CS education is always valuable, to every person, with no exceptions.

Re:Khan Academy: Algorithms by MichaelGG on Sunday March 15, 2015 @11:16AM (#9206742)
Eh, you'd be surprised by the number of devs that simply don't know what indexes are, other than magic-go-fast-juice. I've seen people put a separate index on every column, so that "it'd be fast for all queries"...without thinking that most of their queries used at least two predicates. I've seen people go on to spend tons of time and money on things that fundamentally cannot work because they simply are incapable of thinking through the complexity of what their asking. The fact that modern systems are so fast can let someone get pretty far before hitting a brick wall.

OTOH, I'm not sure full coursework is needed for that. Just make your way through Sedgwick's algorithms book in a month or two and you're in the top 1% probably.

Re:Khan Academy: Algorithms by NDizzle on Sunday March 15, 2015 @01:23PM (#9207227)
Most places where I have worked, this is simply not the case. N in this case is somewhere between 100 and 300. Database indexing SPECIFICALLY is something that very few people grasp. Even Senior-Senior people.
Re:Khan Academy: Algorithms by jagbolanos on Sunday March 15, 2015 @09:54AM (#9206483)
You make a good point and I think it's because sometimes the objective is not clear.

When you study sorting you really do it because:

1) It's a simple, frequent and clear problem that everybody understands

2) People just need to think about it for a while to figure out a correct algorithm normally O(n^2) and think about optimizations from there (that will probably still make it O(n^2)).

3) You can study different techniques to solve that problem: like divide-and-conquer (mergesort), using a data structure (heapsort), divide-and-conquer+randomization (quicksort), not going for comparisons but using the structure of the data (radixsort).

4) You can learn to apply big-O notation for efficiency and compare different algorithms

5) You can study the limits of a problem (not an algorithm) like the omega(n log(n)) limit of comparison sorts and the omega(n) limit of sorting in general).

This also happens with the less clear but also rich problem of the Minimum Spanning Tree that has 2 famous algorithm (Prim and Kruskal) that can be implemented with different data structures having a great impact in efficiency.

So the real problem is that sometimes teachers just focus on teaching sorting but don't explain (and sometimes they don't have it clear either) that it's not sorting but a framework of mind what you want to give them. Sorting is normally already implemented in the popular and not so popular programming languages libraries.

Re:Khan Academy: Algorithms by delish on Sunday March 15, 2015 @10:14AM (#9206553)
I agree with the reasons the parent provided, especially that teachers teach the content without providing a "why?"

What I suspect generally that I cannot prove (yet): When teachers teach things that are easy to teach but not directly important to learn, students are distracted by the surface irrelevance.

Of course the underlying concepts and designs of sorting are important to understand. But, that the GP asked, "Do professional programmers actually think about this? Is this relevant?" means the curriculum has a problem. The problem is: students are asking meta-questions that should've been answered by the "why?" mentioned above.

In sum, I agree with the parent, especially with:

> So the real problem is that sometimes teachers just focus on teaching sorting but don't explain (and sometimes they don't have it clear either) that it's not sorting but a framework of mind what you want to give them.

It's easy (possibly... lazy? Again, this is what I suspect that I cannot prove) for a CS department to declare "Students will learn [list of topics] by examining and implementing sorting algorithms."

By contrast, it's a hard to 1. interest students by presenting them with problems not fossilized exercises. 2. ensure to students' parents and taxpayers and employers that they know the "basics|fundamentals|theory"

Re:Khan Academy: Algorithms by cbd1984 on Sunday March 15, 2015 @03:42AM (#9205734)
In most complex jobs (that is, jobs with a theoretical component someone writes books about), the theory part mostly comes to the fore when something goes wrong, and you have to diagnose and fix the problem.

So, in this case, programmers would use this stuff when a sort takes up too much time or too much RAM for what it's meant to do. Then you need to know what big-O is and how to fix it.

It seems a bit odd to spend all this time preparing for things that don't happen every day, but, really, that's what people pay the big bucks for: Someone who can smooth over life's little difficulties, at least in that specific realm.

Re:Khan Academy: Algorithms by dbecker on Sunday March 15, 2015 @09:17AM (#9206372)
This blog post by Joel Spolsky makes a case for teaching low-level stuff that I find very compelling.

http://www.joelonsoftware.com/articles/fog0000000319.html

Someone who hasn't thought about sorting algorithms is likely to implement a "Shlemiel the painter" solution without even realizing that their problem is fundamentally sorting related.

Re:Khan Academy: Algorithms by dools on Sunday March 15, 2015 @06:12AM (#9205991)
In most universities there is a distinction between software engineering and computer science. Computer science deals more with things like writing and optimising compilers, and the interface between hardware and software, and writing an optimised sorting algorithm is a good introduction to that kind of thinking.

Software engineers (like engineers in other fields) are in the business of taking stuff made by scientists and building things out of it that businesses and consumers use (like spotify and bridges and dialysis machines). They wouldn't do much in the realm of specific algorithm design, it's mostly about research and system architecture.

Re:Khan Academy: Algorithms by Everhusk on Sunday March 15, 2015 @12:44PM (#9207093)
So I come from the other end of the spectrum. Studied non-CS in college, and after graduating I became a self-taught developer and am now working as a "professional programmer".

I had always believed that I wouldn't need to know the CS theory because I was able to write code that worked and didn't find it too complicated. When I decided to become a developer I learned by launching a few websites, which performed horribly, but I didn't realize until I got a few users. It took me a while to even figure out what was wrong, but eventually I learned about Big-O and realized my algorithms were far from optimal. Started scrambling to teach myself all CS theory I could find online, just so I could build things properly. Then there is a phase where you are constantly worried there is something else from CS school you are missing which will cause your software to blow up, but eventually you get more confident (with shipped code/and a better understanding of CS theory).

So in the end, I think the CS theory in school saves you from a lot of head banging and ignorance after you graduate. However, you will probably do a lot of this in your undergrad, so I guess it all balances out in the end!

Re:Khan Academy: Algorithms by ilovecomputers on Sunday March 15, 2015 @03:23AM (#9205695)
No, but we do think about efficient computational solutions to our problems. These sorting algorithms are simply starting points for you to start thinking how algorithms solve problems, how to optimize them, how to construct data structures, and how to apply asymptotic analysis on your computational solutions. If all goes well with these algo courses, you should end up thinking like a computer scientist ;)
Re:Khan Academy: Algorithms by plinkplonk on Sunday March 15, 2015 @04:37AM (#9205846)
no, but you need the type of thinking that goes into predicting/implementing/evaluating/debugging the performance of a sorting algorithm (unless you are doing some kind of simple CRUD app for years, which is a perfectly fine way to make a living)
Re:Khan Academy: Algorithms by stevebot on Sunday March 15, 2015 @10:31AM (#9206615)
Yes it does matter, though its not usually very grand. Think about it this way, most of those algorithms you learned in college took someone in academia years to write. The algorithms I write in my day-job are usually MUCH more simple.

For example, I remember one developer (who know works at Amazon funny enough), who used dual for loops to iterate through data and find values in multiple places in our application. This caused a noticeable UI slow down. I ended up just loading this data in a Hashmap and it became instantaneous.

Re:Khan Academy: Algorithms by Shivetya on Sunday March 15, 2015 @08:40AM (#9206280)
The majority of my data work for the last dozen or so years has been via SQL and I am only concerned with sorting from a performance perspective, larger hardware (read minis and mainframes) usually have fully developed databases so the real work is done by the OS/db engine.

It then becomes a game of ensuring adequate access paths and the like and using a query analyzer to see if what you put in executes as you like. I am more than amazed at the tricks a good query engine can pull but readily take advice it offers when a new index/access path is required.

Since this covers the sorting the next issue is, making sure the project requests are asking for the right data. A lot of time we gain efficiency by analyzing what they want and making their request better fit that (see Bob, you really didn't need that million record request when all you wanted were this set here)

Re:Khan Academy: Algorithms by kryptiskt on Sunday March 15, 2015 @08:45AM (#9206287)
In the same way that mathematicians seldom solve quadratic equations, programmers seldom implement sorting algorithms. They are still a hugely important building block, and if you don't know how they work you will have little hope of creating good algorithms for situations when the off-the-shelf libraries can't help you anymore. Loads of programmers don't aspire to technically challenging work though and they will likely do fine, every now and then littering with accidentally quadratic code.
Re:Khan Academy: Algorithms by kmfrk on Sunday March 15, 2015 @07:56AM (#9206185)
You can generally use them to model a situation or improve it. For instance, if you're doing a dictionary, you'll be looking into a trie or Bloom filter, and it's generally like that I'm using it.

Skiena's Algorithm Design Manual is great for the former approach, and has a cookbook feel to it, since most of it is just an index of different algorithms to use for different situations.

Re:Khan Academy: Algorithms by jonkiddy on Monday March 16, 2015 @10:13AM (#9211494)
On a typical day, no I do not think about sorting algorithms in particular.

Generally speaking though, I do think about Big-O notation when writing something that isn't trivial. If I do have to implement some particular known algorithm, then I typically look to the language itself for a solution. Failing that I look for a suitable library, and only after exhausting those potential solutions do I write my own.

Re:Khan Academy: Algorithms by evanmoran on Sunday March 15, 2015 @02:25PM (#9207445)
We don't think about sorting specifically, but we do think about performance and the structure of data all the time. How data is stored very much effects how quickly it can be retrieved. This is pretty universal – Twitter needs different storage then Google – you'll be surprised how often you think in these terms.
Re:Khan Academy: Algorithms by mattxxx on Sunday March 15, 2015 @11:13AM (#9206724)
It's very important, but I wouldn't implement a sort; I would be making sure that I'm using the right one for the moment.

The same goes for data-structures. For example, I might need a set of unique values, but, when I code, I would choose an enum-set or a hash-set based on what problem I'm solving.

Re:Khan Academy: Algorithms by GFK_of_xmaspast on Sunday March 15, 2015 @07:21AM (#9206112)
I've been doing this for a living for about 15 years now and have had to implement a sorting algorithm from scratch a couple times for special-case scenarios.

Graph algorithms, and linear algebra complexities, on the other hand, I've had to worry about a bunch.

Re:Khan Academy: Algorithms by afarrell on Sunday March 15, 2015 @08:59AM (#9206321)
I will occasionally think "okay, so this bit is obviously going to cause O(n^2) database queries. Lets fix that." and add in a select_related(). But most of my performance-improving comes after gathering actual data.
Re:Khan Academy: Algorithms by atmosx on Sunday March 15, 2015 @04:47AM (#9205864)
Nope, there are ready-made libraries for every fairly common language out there.