5 ms·

I don't know. If you are struggling with A* search, and claiming to be a great programmer, it sound contradictory. I am assuming poster was familiar with graph

by irahul 15y ago

I don't know. If you are struggling with A* search, and claiming to be a great programmer, it sound contradictory. I am assuming poster was familiar with graphs and graph searches before he stumbled onto A* search. Recursive/Non-recursive dfs should be pretty much obvious to a comp sci student. Here is a sample non-recursive dfs: https://gist.github.com/1789807 https://gist.github.com/1789807 A* search is the same, except you change the $graph to include costs, and change the `queue` implementation to pop based on a heuristic function(cost from source till here + cost to dest). I am not saying a good computer programmer must know A* search - I am saying if you are a programmer, your thought process should be molded in a way you start finding these things obvious. I can't think of any programmers who I personally know, or otherwise, who aren't well versed in algorithms. Familiarity with algorithms serves 2 purpose: 1. It gives your mind general elasticity and agility. 2. Many times, it gives you foundations on which you build. I recently wrote this small python lib which converts xml to python dict and vice-versa https://github.com/thoughtnirvana/xmldict https://github.com/thoughtnirvana/xmldict. It came naturally to me as I was simply implementing a recursive-descent parser. I don't think had I not known about parsers, the solution would have come naturally to me. That is just one example. There are other examples involving dynamic programming, counting sort...which translates nicely to real world use cases, and if you don't know the basic algorithms, you end up re-implementing a second-class substitute badly.

ColdAsIce 15y ago
Yeah thats a nice xmldict you wrote there, except it doesnt do anything good at all. Try to parse this with it, <html>hello</lol>world</html>. So much for your A* search and algorithmic knowledge. I am no good with algorithms but would know to stop at such an idea as to make my own xmldict parser in that way. I would instead learn about parsing and the algorithms for successful parsing, instead of a half-assed approach.
- lutorm 15y ago
  I don't know a lot about XML, but that doesn't look like (legal) XML to me. Is it?
- irahul 15y ago
  > Try to parse this with it, <html>hello</lol>world</html>. Parsing invalid xml with a xml parser throws an error like it should. I am using cElementTree for parsing and this is what will happen with your input. In [1]: import xml.etree.cElementTree as ElementTree In [2]: ElementTree.XML('<html>hello</lol>world</html>') --------------------------------------------------------------------------- ParseError Traceback (most recent call last) /home/rahul/musings/python/<ipython-input-2-54e782b0af58> in <module>() ----> 1 ElementTree.XML('<html>hello</lol>world</html>') /home/rahul/musings/python/<string> in XML(text) ParseError: mismatched tag: line 1, column 13 > make my own xmldict parser in that way What is that way you are talking about? There isn't a xmldict implementation for Python(at least I can't google it), I needed one, so I wrote a recursive descent parser. A recursive descent parser is a popular choice provided your grammar is LL(k) - Python, Perl et al run on hand-coded recursive-descent parsers. Also, recursive-descent parsers are easiest to handroll. PS - There is a way to disagree. Your's isn't the right way.
weavejester 15y ago
In defence of the poster, I think it depends on how much experience you have solving a certain class of problems, and perhaps more importantly, how you were taught. I don't recall having studying the A* algorithm before, so I first looked it up on Wikipedia for a few minutes, and then came back to the comments. It's worth me saying that 30 seconds of reading your comment and linked gist did more to aid my comprehension than a few minutes looking through the Wikipedia article. This is the case because you described the algorithm in terms of building blocks I was already familiar with. It's a depth-first search with a weighted queue; as you say, pretty obvious! But it wasn't immediately obvious from the Wikipedia article, because Wikipedia articles are designed to impart information, not necessarily to teach. If the poster was taught by a professor who was teaching more like the Wikipedia article (and I've known a lot of lecturers who do this!), I can understand the confusion.
- irahul 15y ago
  I see where you are coming from. I was arguing more on the side of "familiarity with algorithms" is like "hitting the gym" irrespective of what game/sport you play. It either helps you directly, or gives you general skill. I was mostly taking exception to conflating "great programmers - no algorithmic knowledge". It's great that you figured out A* search in under 30 seconds, but that's because you had the foundation. As I said, I am not claiming A* search(or any other algorithm) is the baseline, but there is a baseline(I won't bother enumerating algorithms - there is no agreed upon list), and a good programmer should strive to be above that baseline. Simply putting your hands up and claiming I can develop large systems fine and hence algorithmic knowledge is not really helpful - it is counter productive. Again, if it's working fine for the poster, that's great. But the poster might be missing "unknown unknowns."
  - fjellfras 15y ago
    Something I have found is that with learning algorithms a sideways approach is sometimes better if you find yourself struggling. I initially had some trouble visualizing the process of algorithm development if I simply followed a book and did exercises (self-taught), so I would pick a complicated looking algorithm and just read about it, then think about it for a while, and try to find somewhere it had been used in code and how it solved some problem. After a while I would go back to the book and it would sink in and I was able to better understand the mathematical model and intuition. Several such algorithms later and I am able to pick up new algorithms relatively quicker.
feralchimp 15y ago
> if you are a programmer, your thought process should be molded in a way you start finding these things obvious > had I not known about parsers, the solution would have come naturally to me Your use of "obvious" and "come naturally" fit together, and match the template of someone who is naturally more inclined to understand this stuff than the OP might be, or (for that matter) I might be. But rather than abandon algos as irrelevant, the OP should put more effort in.
- NinetyNine 15y ago
  I disagree that anyone is "naturally-inclined" to be better at algorithms, or coding, or abstract thinking. Rather, approach it as if we've been a blank slate that has picked up techniques and patterns of thinking, as throughout our lives we've been confronted with problems that required a new way of thinking. I'd reckon that someone you see as "naturally inclined" has simply encountered problems before that lend themselves to abstract in a similar way as these new problems they face (algorithms, architecture, speaking Japanese). If you believe my paradigm, then you start to realize that not only is your mind extremely flexible, but that by focusing on a varied set of similar problems, you can start developing a framework to pick up more skills faster, and thus develop that "natural inclination" in the field you practice.
haberman 15y ago
> Here is a sample non-recursive dfs: I'm pretty sure that's a BFS, not a DFS. A DFS uses a stack, not a queue.
- jules 15y ago
  Despite the name, he is using the array as a stack, not as a queue.
- irahul 15y ago
  > I'm pretty sure that's a BFS, not a DFS. A DFS uses a stack, not a queue. In the gist, queue.push adds element to the tail end, and queue.pop removes from the tail end. For it to be behave as BFS, you will have to change queue.pop to queue.shift which will remove elements from the front. An ideal graph search implementation will take queue as a parameter, and will use queue.enqueue and queue.dequeue. And then the injection -> implementation mapping will be: LIFOQueue(stacks) -> DFS FIFOQueue(regular queues) -> BFS PriorityQueue -> Some sort of Best First Search PriorityQueue with A* heuristics -> A* search(duh) But I didn't want to go through all that trouble to demonstrate a simple snippet.
  - haberman 15y ago
    Interesting, I had never seen this formulation where DFS and BFS can be expressed by a single algorithm that differs only in the behavior of the "queue." It's still a bit misleading to call it "queue" since it might be a stack, but I see the intention. This formulation of DFS (which tracks a stack of nodes to visit) is less efficient than one that tracks a stack of iterators, because the size of your stack is O(vertices) instead of O(graph depth). On the other hand, it's simpler in some ways, so I can see why it would be preferable in some situations.
    - justinhj 15y ago
      Norvig's practical ai programming has a great chapter on search which also shows how similarly different algorithms can be expressed if you have the right abstraction

by irahul 15y ago

ColdAsIce 15y ago

Yeah thats a nice xmldict you wrote there, except it doesnt do anything good at all. Try to parse this with it, <html>hello</lol>world</html>. So much for your A* search and algorithmic knowledge. I am no good with algorithms but would know to stop at such an idea as to make my own xmldict parser in that way. I would instead learn about parsing and the algorithms for successful parsing, instead of a half-assed approach.

lutorm 15y ago
I don't know a lot about XML, but that doesn't look like (legal) XML to me. Is it?
irahul 15y ago
> Try to parse this with it, <html>hello</lol>world</html>. Parsing invalid xml with a xml parser throws an error like it should. I am using cElementTree for parsing and this is what will happen with your input. In [1]: import xml.etree.cElementTree as ElementTree In [2]: ElementTree.XML('<html>hello</lol>world</html>') --------------------------------------------------------------------------- ParseError Traceback (most recent call last) /home/rahul/musings/python/<ipython-input-2-54e782b0af58> in <module>() ----> 1 ElementTree.XML('<html>hello</lol>world</html>') /home/rahul/musings/python/<string> in XML(text) ParseError: mismatched tag: line 1, column 13 > make my own xmldict parser in that way What is that way you are talking about? There isn't a xmldict implementation for Python(at least I can't google it), I needed one, so I wrote a recursive descent parser. A recursive descent parser is a popular choice provided your grammar is LL(k) - Python, Perl et al run on hand-coded recursive-descent parsers. Also, recursive-descent parsers are easiest to handroll. PS - There is a way to disagree. Your's isn't the right way.

weavejester 15y ago

In defence of the poster, I think it depends on how much experience you have solving a certain class of problems, and perhaps more importantly, how you were taught. I don't recall having studying the A* algorithm before, so I first looked it up on Wikipedia for a few minutes, and then came back to the comments. It's worth me saying that 30 seconds of reading your comment and linked gist did more to aid my comprehension than a few minutes looking through the Wikipedia article. This is the case because you described the algorithm in terms of building blocks I was already familiar with. It's a depth-first search with a weighted queue; as you say, pretty obvious! But it wasn't immediately obvious from the Wikipedia article, because Wikipedia articles are designed to impart information, not necessarily to teach. If the poster was taught by a professor who was teaching more like the Wikipedia article (and I've known a lot of lecturers who do this!), I can understand the confusion.

irahul 15y ago
I see where you are coming from. I was arguing more on the side of "familiarity with algorithms" is like "hitting the gym" irrespective of what game/sport you play. It either helps you directly, or gives you general skill. I was mostly taking exception to conflating "great programmers - no algorithmic knowledge". It's great that you figured out A* search in under 30 seconds, but that's because you had the foundation. As I said, I am not claiming A* search(or any other algorithm) is the baseline, but there is a baseline(I won't bother enumerating algorithms - there is no agreed upon list), and a good programmer should strive to be above that baseline. Simply putting your hands up and claiming I can develop large systems fine and hence algorithmic knowledge is not really helpful - it is counter productive. Again, if it's working fine for the poster, that's great. But the poster might be missing "unknown unknowns."
- fjellfras 15y ago
  Something I have found is that with learning algorithms a sideways approach is sometimes better if you find yourself struggling. I initially had some trouble visualizing the process of algorithm development if I simply followed a book and did exercises (self-taught), so I would pick a complicated looking algorithm and just read about it, then think about it for a while, and try to find somewhere it had been used in code and how it solved some problem. After a while I would go back to the book and it would sink in and I was able to better understand the mathematical model and intuition. Several such algorithms later and I am able to pick up new algorithms relatively quicker.

feralchimp 15y ago

> if you are a programmer, your thought process should be molded in a way you start finding these things obvious > had I not known about parsers, the solution would have come naturally to me Your use of "obvious" and "come naturally" fit together, and match the template of someone who is naturally more inclined to understand this stuff than the OP might be, or (for that matter) I might be. But rather than abandon algos as irrelevant, the OP should put more effort in.

NinetyNine 15y ago
I disagree that anyone is "naturally-inclined" to be better at algorithms, or coding, or abstract thinking. Rather, approach it as if we've been a blank slate that has picked up techniques and patterns of thinking, as throughout our lives we've been confronted with problems that required a new way of thinking. I'd reckon that someone you see as "naturally inclined" has simply encountered problems before that lend themselves to abstract in a similar way as these new problems they face (algorithms, architecture, speaking Japanese). If you believe my paradigm, then you start to realize that not only is your mind extremely flexible, but that by focusing on a varied set of similar problems, you can start developing a framework to pick up more skills faster, and thus develop that "natural inclination" in the field you practice.

haberman 15y ago

> Here is a sample non-recursive dfs: I'm pretty sure that's a BFS, not a DFS. A DFS uses a stack, not a queue.

jules 15y ago
Despite the name, he is using the array as a stack, not as a queue.
irahul 15y ago
> I'm pretty sure that's a BFS, not a DFS. A DFS uses a stack, not a queue. In the gist, queue.push adds element to the tail end, and queue.pop removes from the tail end. For it to be behave as BFS, you will have to change queue.pop to queue.shift which will remove elements from the front. An ideal graph search implementation will take queue as a parameter, and will use queue.enqueue and queue.dequeue. And then the injection -> implementation mapping will be: LIFOQueue(stacks) -> DFS FIFOQueue(regular queues) -> BFS PriorityQueue -> Some sort of Best First Search PriorityQueue with A* heuristics -> A* search(duh) But I didn't want to go through all that trouble to demonstrate a simple snippet.
- haberman 15y ago
  Interesting, I had never seen this formulation where DFS and BFS can be expressed by a single algorithm that differs only in the behavior of the "queue." It's still a bit misleading to call it "queue" since it might be a stack, but I see the intention. This formulation of DFS (which tracks a stack of nodes to visit) is less efficient than one that tracks a stack of iterators, because the size of your stack is O(vertices) instead of O(graph depth). On the other hand, it's simpler in some ways, so I can see why it would be preferable in some situations.
  - justinhj 15y ago
    Norvig's practical ai programming has a great chapter on search which also shows how similarly different algorithms can be expressed if you have the right abstraction