4 ms·

> I can't help but think this mentality is what lead to the recent left-pad debacle It borders on category error to compare homebrewing argument parsing with a

by p4wnc6 11y ago

> I can't help but think this mentality is what lead to the recent left-pad debacle It borders on category error to compare homebrewing argument parsing with an overreliance on microframeworks extending all the way down to leftpad. Argument parsing is almost always supported directly by the language implementers in a standard library. And even if it wasn't, it's such a critical task with huge overhead for handling corner cases, cross-platform details, etc., that the value of a central implementation is obvious. A left pad operation ought to be part of the standard language (which is actually what the leftpad debacle was about, Javascript's incredible failures as a language), but it's too trivial to compare it to something like argument parsing. > The pseudo-code of BFS is all of 20 lines, ... If it's only 20 lines, that's great because it means it was easy for the other 500 library writers to write it, write tests, and observe and fix issues over time. So, whew, that's 20 lines I totally shouldn't waste my time on, plus unit tests and routine maintenance I don't have to commit to. And also, given the wide acknowledgement that a good programmer should be writing at most a few hundred lines of code per day (otherwise it's probably mostly junk), 20 lines of code is not trivial. Probably most programmers write a whole lot more than that per day (especially if counting copy/pasted code), but this is in part a sign of a bad programmer, or perhaps more so a sign of the anti-quality constraints placed on them by most employers.

lawrjone 10y ago
What the hell sort of library would you crack out to do a breadth first search traversal? This is my main problem with the OP, BFS isn't some arcane complex cryptic algorithm, it's a way of moving through a data structure that becomes natural and very obvious when you think about how you can effectively traverse it for some tasks. If I were ever to want to traverse something in a breadth first search manner, then I would just write it. It would take longer to search for another library and read how it's somehow implemented this search than it would to write it, test it, get it reviewed, and we've still avoided adding another potentially crappy dependency to our project. It's not category error to compare this to leftpad. leftpad actually makes more sense imo, as it's a common microfunction that may be used more than once. BFS is typically far more coupled with the underlying data and is more naturally written inline.
- microtherion 10y ago
  There is, for instance, the Boost Graph library in C++: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/table_of_contents.html http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/table_of...
- ljw1001 10y ago
  I would use one of the tree implementations in java.util. You may have heard of it.
- p4wnc6 10y ago
  > we've still avoided adding another potentially crappy dependency to our project. No, you've just added the crappy dependency == your off the cuff implementation (which is even more work since you have to handle issues and unit testing for it too). > What the hell sort of library would you crack out to do a breadth first search traversal? In Python I would use networkx probably, unless there was a good reason I couldn't (such as working in an embedded environment where I couldn't install large libraries). It ought to require an exceptional circumstance to stoop to implementing it myself. Tell me, if we switched from talking about breadth first search to, say, inverting a matrix with Gaussian elimination and pivoting, do you feel the same? Are you going to trust your implementation over something you can get from netlib?
  - lawrjone 10y ago
    In the case where you'd require a bfs to traverse a graph, you're already doing something that is algorithmic, and will otherwise be prohibitively costly if explored in a dfs manner. The most complicated part of this algorithm is highly unlikely to be the bfs itself, with it's highly likely 10 lines of code in total. In this case, someone who didn't have the time to visualise exactly how the bfs is operating shouldn't be writing the algorithm. Pretending like you don't need to know the details of how it traverses the tree when you needed to choose the specific implementation for this algorithm to be performant is a lie. It's not like Guassian elimination, where the concept is far more abstract, this is a concrete idea of how you're moving through the graph and shouldn't be some black magic. On top of this, who writes this code and doesn't test that it does what you expected it to do on sample data. If you bfs implementation was bust, then you'd miss nodes or revisit them, which becomes immediately apparent from testing the algorithm you're writing. > It ought to require an exceptional circumstance to stoop to implementing it myself. Maybe the problem here is that I see a bfs as a fundamentally simple algorithm. Saying writing it yourself must be an exceptional circumstance sounds about as crazy to me as saying no-one should ever use for loops, they expose you to making mistakes with an index you may forget is zero-based, please use anonymous iterators instead. When something takes 5m to write, is heavily tested by default (as it will be a feature under test anyway and possible flaws will be highly obvious) and is at the same level of abstraction as the code you'll be writing around it, then just write the damn thing. EDIT - Try writing a BFS that operates on an acyclic graph that outputs the value of each node, that compiles and runs and prints at least two node values that has a bug. Try writing bugs into this, it's actually difficult to screw up.

by p4wnc6 11y ago

lawrjone 10y ago

What the hell sort of library would you crack out to do a breadth first search traversal? This is my main problem with the OP, BFS isn't some arcane complex cryptic algorithm, it's a way of moving through a data structure that becomes natural and very obvious when you think about how you can effectively traverse it for some tasks. If I were ever to want to traverse something in a breadth first search manner, then I would just write it. It would take longer to search for another library and read how it's somehow implemented this search than it would to write it, test it, get it reviewed, and we've still avoided adding another potentially crappy dependency to our project. It's not category error to compare this to leftpad. leftpad actually makes more sense imo, as it's a common microfunction that may be used more than once. BFS is typically far more coupled with the underlying data and is more naturally written inline.

microtherion 10y ago
There is, for instance, the Boost Graph library in C++: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/table_of_contents.html http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/table_of...
ljw1001 10y ago
I would use one of the tree implementations in java.util. You may have heard of it.
p4wnc6 10y ago
> we've still avoided adding another potentially crappy dependency to our project. No, you've just added the crappy dependency == your off the cuff implementation (which is even more work since you have to handle issues and unit testing for it too). > What the hell sort of library would you crack out to do a breadth first search traversal? In Python I would use networkx probably, unless there was a good reason I couldn't (such as working in an embedded environment where I couldn't install large libraries). It ought to require an exceptional circumstance to stoop to implementing it myself. Tell me, if we switched from talking about breadth first search to, say, inverting a matrix with Gaussian elimination and pivoting, do you feel the same? Are you going to trust your implementation over something you can get from netlib?
- lawrjone 10y ago
  In the case where you'd require a bfs to traverse a graph, you're already doing something that is algorithmic, and will otherwise be prohibitively costly if explored in a dfs manner. The most complicated part of this algorithm is highly unlikely to be the bfs itself, with it's highly likely 10 lines of code in total. In this case, someone who didn't have the time to visualise exactly how the bfs is operating shouldn't be writing the algorithm. Pretending like you don't need to know the details of how it traverses the tree when you needed to choose the specific implementation for this algorithm to be performant is a lie. It's not like Guassian elimination, where the concept is far more abstract, this is a concrete idea of how you're moving through the graph and shouldn't be some black magic. On top of this, who writes this code and doesn't test that it does what you expected it to do on sample data. If you bfs implementation was bust, then you'd miss nodes or revisit them, which becomes immediately apparent from testing the algorithm you're writing. > It ought to require an exceptional circumstance to stoop to implementing it myself. Maybe the problem here is that I see a bfs as a fundamentally simple algorithm. Saying writing it yourself must be an exceptional circumstance sounds about as crazy to me as saying no-one should ever use for loops, they expose you to making mistakes with an index you may forget is zero-based, please use anonymous iterators instead. When something takes 5m to write, is heavily tested by default (as it will be a feature under test anyway and possible flaws will be highly obvious) and is at the same level of abstraction as the code you'll be writing around it, then just write the damn thing. EDIT - Try writing a BFS that operates on an acyclic graph that outputs the value of each node, that compiles and runs and prints at least two node values that has a bug. Try writing bugs into this, it's actually difficult to screw up.