4 ms·

Here's a list of all the algorithms and data structures I've actually needed to implement by hand so far:

douche 11y ago
For whatever reason, there isn't a nice priority queue out of the box in the .NET framework, so that is about the only one that I've had to implement
SamReidHughes 11y ago
Fascinating. Taking the restricted definition of "algorithm" you seem to be using, here's the first few I can think of that I've had to implement (for money): - Converting a dollar/cents value into text, e.g. 67.33 -> "sixty-seven dollars and thirty-three cents", in XSLT of all things. I wrote the first version in Emacs Lisp, then translated that to XSLT. I was working on manually translating a bunch of .doc files to a new layout for the automatic generation of contracts, and the vendor had supplied a version that, after reading its source code, I realized was broken on certain inputs, like 10001 or something. I guess it was made by some people that thought they'd never need to write algorithms when working as a software developer. - I was asked to combine the information in a few spreadsheets with several thousand rows into a new one. I ended up needing to compute some statistics on certain ranges of a set of rows, so in my short Perl program I sorted the data by the relevant key and used binary search to find the ranges. That's not a list for my whole career, that's just what I can remember from my first summer internship as a data entry/IT hob-job monkey when I was a teenager.
tripzilch 11y ago
Fisher-Yates shuffle may be the one "book" algorithm that I literally implemented a handful of times. But there are a couple of more generic algorithms that I occasionally can't really help but implement in some variation or other. Usually because the "book" version of the algorithm that is already in the standard library of your language of choice doesn't quite fit your problem. Many classic algorithms are simple enough to code for your problem, than to write an adapter for the standard library version of the algorithm. For instance binary search. It's a tool. Prefer not to implement it by hand (because less chance of bugs) if I know there's a library call that does it fast, but if need be, easy enough. Sometimes you may not realize you're implementing a classic algorithm, say when writing certain recursive functions that are actually equivalent to a tree-traversal algorithm of a datastructure. Sometimes you do realize, coding up a class definition for something, and then you notice "hey these fields actually make this data sort of equivalent to a doubly-linked list". That's when your algorithms-knowledge comes in handy, because it allows you to stop and consider, is a doubly-linked list really the most suitable datastructure for this problem? Do I know other clever "book" algorithms that fulfill this need? Are they better? More performant? Without the knowledge of the first algorithm you wouldn't even know to ask this question. So the point is, you don't know what you don't know. Apparently you never needed to implement a "book" algorithm or datastructure by hand in order to get your programming task done. But do you know those tasks couldn't have been done better, faster, more performant, elegant, easier, if only you had the knowledge about the right algorithm for the job? Whether you would end up implementing it by hand or not, it's having that knowledge at the ready, that makes algorithms and data structures knowledge something that distinguishes one programmer from the other. Then there's a bunch of domain-specific algorithms. Various types of numerical integration methods I've implemented by hand many times because you can almost always do better than naive Euler. And since they're in the inner loop, tangled up with the particular equations of your problem, calling them as a library function is just going to drain performance.

For whatever reason, there isn't a nice priority queue out of the box in the .NET framework, so that is about the only one that I've had to implement

SamReidHughes 11y ago

Fascinating. Taking the restricted definition of "algorithm" you seem to be using, here's the first few I can think of that I've had to implement (for money): - Converting a dollar/cents value into text, e.g. 67.33 -> "sixty-seven dollars and thirty-three cents", in XSLT of all things. I wrote the first version in Emacs Lisp, then translated that to XSLT. I was working on manually translating a bunch of .doc files to a new layout for the automatic generation of contracts, and the vendor had supplied a version that, after reading its source code, I realized was broken on certain inputs, like 10001 or something. I guess it was made by some people that thought they'd never need to write algorithms when working as a software developer. - I was asked to combine the information in a few spreadsheets with several thousand rows into a new one. I ended up needing to compute some statistics on certain ranges of a set of rows, so in my short Perl program I sorted the data by the relevant key and used binary search to find the ranges. That's not a list for my whole career, that's just what I can remember from my first summer internship as a data entry/IT hob-job monkey when I was a teenager.

tripzilch 11y ago

Fisher-Yates shuffle may be the one "book" algorithm that I literally implemented a handful of times. But there are a couple of more generic algorithms that I occasionally can't really help but implement in some variation or other. Usually because the "book" version of the algorithm that is already in the standard library of your language of choice doesn't quite fit your problem. Many classic algorithms are simple enough to code for your problem, than to write an adapter for the standard library version of the algorithm. For instance binary search. It's a tool. Prefer not to implement it by hand (because less chance of bugs) if I know there's a library call that does it fast, but if need be, easy enough. Sometimes you may not realize you're implementing a classic algorithm, say when writing certain recursive functions that are actually equivalent to a tree-traversal algorithm of a datastructure. Sometimes you do realize, coding up a class definition for something, and then you notice "hey these fields actually make this data sort of equivalent to a doubly-linked list". That's when your algorithms-knowledge comes in handy, because it allows you to stop and consider, is a doubly-linked list really the most suitable datastructure for this problem? Do I know other clever "book" algorithms that fulfill this need? Are they better? More performant? Without the knowledge of the first algorithm you wouldn't even know to ask this question. So the point is, you don't know what you don't know. Apparently you never needed to implement a "book" algorithm or datastructure by hand in order to get your programming task done. But do you know those tasks couldn't have been done better, faster, more performant, elegant, easier, if only you had the knowledge about the right algorithm for the job? Whether you would end up implementing it by hand or not, it's having that knowledge at the ready, that makes algorithms and data structures knowledge something that distinguishes one programmer from the other. Then there's a bunch of domain-specific algorithms. Various types of numerical integration methods I've implemented by hand many times because you can almost always do better than naive Euler. And since they're in the inner loop, tangled up with the particular equations of your problem, calling them as a library function is just going to drain performance.