This week's book giveaway is in the Jython/Python forum.
We're giving away four copies of Murach's Python Programming and have Michael Urban and Joel Murach on-line!
See this thread for details.
Win a copy of Murach's Python Programming this week in the Jython/Python forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Algorithms v. "The Real World"  RSS feed

 
Stevens Miller
Bartender
Posts: 1443
30
C++ Java Netbeans IDE Windows
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As a CS student, I loved learning algorithms. They seemed like mystical spells and my textbooks were my grimoires. But, upon entering the actual profession, I found that any attempt to use them was criticized by my co-workers as confusing and dangerous. In particular, anything that made use of dynamic memory allocation (as though automatics weren't dynamic) was condemned as risky and unpredictable. Linked lists, for example, earned me a long lecture about how, "in the real world," one should use arrays and, "just get on with it."

So my question is this: while algorithms are important to the study of computer science, do you feel they are of much practical use in the "real world" of computer programming and, if so, why?
 
Stephan van Hulst
Saloon Keeper
Posts: 6980
110
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes. While I've never had reason to implement a linked list or a heap in the "real world", practicing with them made it faster to recognize their use in existing software, which makes reasoning about your code and tracking down bugs much easier. I also think that while many of the things you learn from your textbooks you won't apply in practice directly, you will mix and match those concepts to create solutions to real world problems.

For instance, I never thought I'd use the stuff I learned in my Compilers class in anything other than hobby projects, but at my current job we're building and dealing with structures that look an awful lot like abstract syntax trees, and I've applied algorithms I learned from my class to them that solved some problems very elegantly.

I think anybody who says dynamic memory allocation is risky and unpredictable should not be in the profession of software engineering.
 
Stevens Miller
Bartender
Posts: 1443
30
C++ Java Netbeans IDE Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:While I've never had reason to implement a linked list or a heap in the "real world", practicing with them made it faster to recognize their use in existing software, which makes reasoning about your code and tracking down bugs much easier.

That's a good, valid point, Stephan, but I think it somewhat evades the question. Knowing enough to understand what other programmers might have done is valuable, but it's not an endorsement of the methods those other programmers used. What I'm asking is whether or not the sorts of algorithms we studied in school can be defended for use in commercial code. (I think the answer is "yes," but I'm curious about the author's--and your--answer).

I think anybody who says dynamic memory allocation is risky and unpredictable should not be in the profession of software engineering.

For most things, I agree. But maybe not always. The topic reminds me of something we used to say to each other back when I was learning how to program Windows 3.0: "Would you fly in a plane that depended on a Windows application? One you wrote yourself?"

As a "real world" example, I once wrote code for a company that developed automation software that ran blood-testing machines. We wrote in C. The chief programmer declared that anyone who called malloc() in their code would be fired. Wherever we would otherwise have called malloc(), we allocated a fixed-size array in global address space (so we couldn't overflow the stack by creating it automatically). If we needed memory, that's where we got it. Most of the time, that worked pretty well, though some of us kind of dodged his prohibition by creating our own application-level memory managers, allocating chunks from that global array and then "returning" them as needed. The chief's feeling was that, assuming the customer's machine had as much memory as ours did, it would be a compile-time error to ask for an array that was too big, as opposed to a run-time error to try to malloc() a block of memory that was too big. When you're writing code for the medical profession, you don't want anything that looks like this:


I actually did write a production program once that used a linked list to queue up commands for a remote server. If I ever ran out of memory, I had it block on the request for a while and, if it timed out, it asked the user if they wanted to wait some more, or give up. My co-workers pointed out that, if the server ever got more than a few commands behind, we had a bigger problem to solve on the server side and that a small array would have been easier to use and maintain. I agreed and that's what we did, though I did give up the more "elegant" list with some regret.
 
Stephan van Hulst
Saloon Keeper
Posts: 6980
110
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stevens Miller wrote:What I'm asking is whether or not the sorts of algorithms we studied in school can be defended for use in commercial code.

If by use, you mean writing them yourself, then PROBABLY NO. If I caught you writing a linked list, I would also raise my eyebrow at you, because you're likely not using what your language is already giving you. For instance, in my algorithms class I learned about linked lists, red-black trees, heaps, and sorting. Java provides LinkedList, TreeSet, PriorityQueue and Collections.sort. If by use, you mean use these kinds of algorithms that others have already written, then YES. Case in point, the aforementioned types in the Java standard library.

For most things, I agree. But maybe not always. The topic reminds me of something we used to say to each other back when I was learning how to program Windows 3.0: "Would you fly in a plane that depended on a Windows application? One you wrote yourself?"

Building professional software that lives depend on is a team effort that requires extensive testing and a mature set of tools. This has little to do with whether or not we should avoid "difficult" programming techniques. Some things are inherently difficult, and saying we should avoid them at all costs is a sure sign that you don't know what you're doing. We all know that concurrent programming is hard, but I don't want to fly in an airplane that uses software that can't handle concurrent processes.

That reminds me, at uni I learned about using mutexes, semaphores and object monitors. Would I write them? NO. Would I trust anybody that did? NO, because they're not using the tools given to them.

The chief programmer declared that anyone who called malloc() in their code would be fired. Wherever we would otherwise have called malloc(), we allocated a fixed-size array in global address space (so we couldn't overflow the stack by creating it automatically).

Your chief programmer was a moron. A person like that has no business designing software.

If we needed memory, that's where we got it. Most of the time, that worked pretty well, though some of us kind of dodged his prohibition by creating our own application-level memory managers, allocating chunks from that global array and then "returning" them as needed.

And this is exactly the reason. The way people are going to get around this restriction is WAY more brittle and error prone than using malloc() in the first place.

The chief's feeling was that, assuming the customer's machine had as much memory as ours did, it would be a compile-time error to ask for an array that was too big, as opposed to a run-time error to try to malloc() a block of memory that was too big. When you're writing code for the medical profession, you don't want anything that looks like this:

And what would you do when your application level memory manager tells you that the globally accessible array (that by the way, doesn't protect against illegal addressing by throwing segmentation faults) is full? And what if your stack memory runs out?

I actually did write a production program once that used a linked list to queue up commands for a remote server. If I ever ran out of memory, I had it block on the request for a while and, if it timed out, it asked the user if they wanted to wait some more, or give up. My co-workers pointed out that, if the server ever got more than a few commands behind, we had a bigger problem to solve on the server side and that a small array would have been easier to use and maintain. I agreed and that's what we did, though I did give up the more "elegant" list with some regret.

Let's assume for a moment that the application should be able to recover from a temporary lag, by processing the backlog of commands it's built up in the mean time. Your instinct to use a linked list is correct, but you should then immediately follow up with the question "Does my language or environment provide me with an existing implementation?".

Here's the kicker: After looking for a standard implementation of linked lists in C, I can't find one. It turns out that learning about linked lists from your textbooks has ACTUAL real world use. The conclusion that I draw from that is that C is a horribly outdated language, and nowhere near suitable to use for applications that lives depend on.
 
Stephan van Hulst
Saloon Keeper
Posts: 6980
110
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To condense my thoughts in a short answer: The type of things you would learn in an algorithms class has actual real world use, but ONLY if you're implementing a standard library.
 
Stephan van Hulst
Saloon Keeper
Posts: 6980
110
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stevens Miller wrote:In particular, anything that made use of dynamic memory allocation (as though automatics weren't dynamic) was condemned as risky and unpredictable.

I want to revisit this remark, because I now understand better what you mean.

There is nothing wrong with dynamic memory allocation, but having to do it to implement types that really should have been a standard part of the language is a sign that the language is unsuitable. I understand your coworkers' reluctance to implement a linked list, because you shouldn't have to. Having to resort to fixed arrays instead just means that you're using the wrong tools for the job, in this case, the language C.
 
Stevens Miller
Bartender
Posts: 1443
30
C++ Java Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
Stevens Miller wrote:In particular, anything that made use of dynamic memory allocation (as though automatics weren't dynamic) was condemned as risky and unpredictable.

I want to revisit this remark, because I now understand better what you mean.

There is nothing wrong with dynamic memory allocation, but having to do it to implement types that really should have been a standard part of the language is a sign that the language is unsuitable. I understand your coworkers' reluctance to implement a linked list, because you shouldn't have to. Having to resort to fixed arrays instead just means that you're using the wrong tools for the job, in this case, the language C.

That summarizes a lot of powerful points, Stephan. When I wrote my command-queue, the year was 1998 (and I was writing in Visual Basic). There were no available implementations for me to use. Today, particularly in Java, there's no arguing with your observation that the existing library provides robust, reliable implementations of all kinds of things no one should be writing on their own anymore. (Although, maybe I've missed my own point, as it appears we are talking more about data structures than we are about algorithms; the question still applies, however.)

Now, to know what those implementations offer, and being able to choose among them wisely, requires some knowledge of their underlying mechanisms. For that, nothing replaces what we learned in school. Further, computer science (as opposed to computer science, if I may be so vulgar as to use typography to make my distinction) investigates algorithms in their own right. Orders of computation, computability, and so on, are the actual subject matter of that science. They don't need justification in the context of some application. If you are going to study computer science, you are going to be studying algorithms. As the world seems ever to be in the throes of a shortage of computer scientists, a book that helps more people see the intrinsic appeal of the study of algorithms might be just what we need, even if none of us ever writes our own linked list again.
 
Stephan van Hulst
Saloon Keeper
Posts: 6980
110
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My first taste of programming came when I got my graphing calculator in high school, and read through the programming section in the manual. I tried out some of the samples, and from there started making very small games.

A friend introduced me to an online challenge where one of the assignments was to write a Pascal program that reads a maze from a text file, and assigns a 'distance' to each square in relation to the maze's starting square. After the concept of recursion and backtracking clicked with me, I fell in love with computer science. It's these fundamental algorithms that can definitely spark our interest, even if nowadays most of my work consists of wiring libraries and frameworks together.
 
Imtiaz Ahmad
Greenhorn
Posts: 2
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knowledge of the algorithms is crucial to be a well rounded engineer. But practically, it would be rare that you would need to create a linked list or a red-black tree. These structures are already being used under the hood in most cases. Under the hood of the language and various frameworks. But understanding them will and practicing them every now and then will improve your engineering abilities!
 
Jeremy Kubica
Author
Greenhorn
Posts: 18
5
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is already a lot of good discussion on this thread. So I will just reiterate some of the points I have seen.

Stephan van Hulst wrote:While I've never had reason to implement a linked list or a heap in the "real world", practicing with them made it faster to recognize their use in existing software, which makes reasoning about your code and tracking down bugs much easier. I also think that while many of the things you learn from your textbooks you won't apply in practice directly, you will mix and match those concepts to create solutions to real world problems.


There's two really important points here. #1 Understanding the basic data structures and algorithms is critical to understanding (and thus correctly using) other people's code, including standard libraries. #2 A lot of interesting challenges come up where a single standard algorithm won't apply, but you have to mix components of two or more.

That being said, I have had to implement algorithms and data structures. In those cases it is almost always because I have needed to adapt them to a problem that is almost, but not quite, what you find in the textbook. For example in my graduate work, I ended up adapting spatial data structures like KD-trees and Quad-Trees to work on spherical coordinates, because I was working with astronomy data.
 
Stephan van Hulst
Saloon Keeper
Posts: 6980
110
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Very good example Jeremy, I think that creating or reinventing these types of algorithms and data structures is mostly done in the academic world. Outside the academia such algorithms will mostly be provided in tried and tested libraries.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stevens Miller wrote:So my question is this: while algorithms are important to the study of computer science, do you feel they are of much practical use in the "real world" of computer programming and, if so, why?

My late entry into this discussion:
1. Absolutely, for all the reasons mentioned by Stephan and others.
2. With regard to "rolling your own", my take is: Make sure you have your justification ready before you write your first line of code.

I have actually written my own linked list class, called Ring (which kind of describes the difference between it and a regular one), and I find it extremely useful. It's also single-linked, which makes it highly concurrent with minimal synchronisation.

But as between it and an array (or ArrayList)? I'll use the latter 95% of the time, and twice on Sundays, because they're generally (a) faster, (b) more compact, (c) have better cache characteristics, and (d) (perhaps most important) I don't have to write or test a darn thing.

My 2¢.

Winston
 
Damon McNeill
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stevens Miller wrote:As a CS student, I loved learning algorithms. They seemed like mystical spells and my textbooks were my grimoires. But, upon entering the actual profession, I found that any attempt to use them was criticized by my co-workers as confusing and dangerous. In particular, anything that made use of dynamic memory allocation (as though automatics weren't dynamic) was condemned as risky and unpredictable. Linked lists, for example, earned me a long lecture about how, "in the real world," one should use arrays and, "just get on with it."

So my question is this: while algorithms are important to the study of computer science, do you feel they are of much practical use in the "real world" of computer programming and, if so, why?


Have you considered that maybe you're co-workers are wrong? Linked lists and arrays are optimized for different use-cases, and the decision to use one or another is not based on tripe, but on real-world use cases and performance requirements.

I find it hard to believe that anyone can write a real world program without using dynamic memory allocation ("new" or "malloc").
 
Damon McNeill
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stevens Miller wrote:
Stephan van Hulst wrote:
As a "real world" example, I once wrote code for a company that developed automation software that ran blood-testing machines. We wrote in C. The chief programmer declared that anyone who called malloc() in their code would be fired. Wherever we would otherwise have called malloc(), we allocated a fixed-size array in global address space (so we couldn't overflow the stack by creating it automatically). If we needed memory, that's where we got it. Most of the time, that worked pretty well, though some of us kind of dodged his prohibition by creating our own application-level memory managers, allocating chunks from that global array and then "returning" them as needed. The chief's feeling was that, assuming the customer's machine had as much memory as ours did, it would be a compile-time error to ask for an array that was too big, as opposed to a run-time error to try to malloc() a block of memory that was too big. When you're writing code for the medical profession, you don't want anything that looks like this:



I'm sure I read this on the Daily WTF. It does seem ridiculous to ban "malloc()". Maybe we should be paranoid that 1+1 might not =2 as well? Assuming the customer's machine had as much memory as the developer's test systems, I don't see any problem.
 
Damon McNeill
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would add that, behind real-world languages such as Java, are based on implementation techniques that were derived in a purely-academic setting. That's how things work... the smart guys figure out the best algorithms, and the real-world guys implement it. Seems to work OK.
 
Campbell Ritchie
Sheriff
Posts: 53750
127
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Damon McNeill wrote:. . . I find it hard to believe that anyone can write a real world program without using dynamic memory allocation ("new" or "malloc").
Why are you mentioning new and malloc as if there were some sort of synonymy to them?
 
Damon McNeill
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oh, I guess it's bad to post C code on the Java forum ... ooop!
 
Damon McNeill
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Of course, "new" and "malloc" are totally different beasts.. they don't even do the same thing at all.
 
Henry Wong
author
Sheriff
Posts: 22840
119
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Damon McNeill wrote:Oh, I guess it's bad to post C code on the Java forum ... ooop!


IMHO, I see nothing wrong with it, as long as it is in the context of the discussion.  And also, it is ridiculously rare to see anyone that hasn't coded in C before...

Henry
 
Damon McNeill
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, it's like the "lingua franca" of programming.
 
Henry Wong
author
Sheriff
Posts: 22840
119
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Damon McNeill wrote:
I find it hard to believe that anyone can write a real world program without using dynamic memory allocation ("new" or "malloc").


The real world is pretty big, so, you will be surprised...

For example, in finance, algo trading, high frequency trading, etc. this is actually common. Yes, the application do malloc() to get the memory to run (ie. to start up) -- but that is it. Once the market opens, no malloc(), no free(), period. The application is written in a way that it has the memory it needs at the start, and that is it -- any buffers must go through some sort of recycling system, etc.

Why? Well, malloc/free has jitter. Sometimes, arguably, it can go as high as a microsecond. And in the world of algo trading, even 200 nanoseconds can mean the difference between getting the trade (and making money) vs not getting the trade (and losing money).

Henry
 
Damon McNeill
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's a very interesting use case, thank you for that.
 
Stevens Miller
Bartender
Posts: 1443
30
C++ Java Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong wrote:200 nanoseconds can mean the difference between getting the trade (and making money) vs not getting the trade (and losing money).


Well, that's what the traders say. My own observation is that getting the trade and losing money go together about half the time themselves.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!