Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Optimizing a breadth-first search

snellman.net

Post reply on HN
Print view View original

11–20 of 40 posts

Re: Optimizing a breadth-first search

#11

Post by frankmcsherry »

jsnell wrote: post #7
rrobukef wrote: post #4

Earlier quoted context omitted.

This was my thought too, but I don't want to assume: he cites enough standard but specific sources that he should know the general search algorithms. Also I think that since he doesn't mention standard depth first search at all it perhaps wasn't relevant?

As mentioned briefly in the introduction, I didn't have good heuristics to use for a scoring function. A totally undirected DFS didn't seem like a great option. The readme links to an existing Python-based solver for the same game [0], which had both BFS and DFS modes. The DFS one was considerably slower on large puzzles even when given the optimal target depth. Totally happy to believe I'm wrong about that, though :…

It's a super interesting post, and I've no reason to think that iterative deepening would be better, just that it is designed to deal with exactly this problem. The lack of growth in novel states may invalidate its main hypothesis though (tree-like growth).

The Python version seems to do DFS using function calls, and I could imagine this isn't the most performant way to do it. Also, the description implies that their DFS implementation retains state; not sure what to make of it, and not a Python reader:

> Depth-First should be a bit kinder to system memory, though it'll still chew up quite a bit remembering which game states we've seen before.

Re: Optimizing a breadth-first search

#12

Post by jsnell »

frankmcsherry wrote: post #11
jsnell wrote: post #7

Earlier quoted context omitted.

As mentioned briefly in the introduction, I didn't have good heuristics to use for a scoring function. A totally undirected DFS didn't seem like a great option. The readme links to an existing Python-based solver for the same game [0], which had both BFS and DFS modes. The DFS one was considerably slower on large puzzles even when given the optimal target depth. Totally happy to believe I'm wrong about that, though :…

It's a super interesting post, and I've no reason to think that iterative deepening would be better, just that it is designed to deal with exactly this problem. The lack of growth in novel states may invalidate its main hypothesis though (tree-like growth). The Python version seems to do DFS using function calls, and I could imagine this isn't the most performant way to do it. Also, the description implies that their…

Fair enough, and it's easy to test :)

I made a non-iterative DFS, but hardcoded the maximum depth to the optimal solution. On a trivial puzzle that should take This is obviously not fully optimized code (whee, std::unordered_set). But fixing that won't help when we're off by 3-4 orders of magnitude. I think the shape of the search graph of this game just isn't well suited to any form of DFS, there are far too many alternate paths to each state.

Re: Optimizing a breadth-first search

#13

Post by OskarS »

jsnell wrote: post #7
rrobukef wrote: post #4

Earlier quoted context omitted.

This was my thought too, but I don't want to assume: he cites enough standard but specific sources that he should know the general search algorithms. Also I think that since he doesn't mention standard depth first search at all it perhaps wasn't relevant?

As mentioned briefly in the introduction, I didn't have good heuristics to use for a scoring function. A totally undirected DFS didn't seem like a great option. The readme links to an existing Python-based solver for the same game [0], which had both BFS and DFS modes. The DFS one was considerably slower on large puzzles even when given the optimal target depth. Totally happy to believe I'm wrong about that, though :…

The linked solver doesn't use iterative deepening, and it saves all states that the DFS solver encounters (negating the advantage of using DFS).

I think IDDFS might work really well here, even without a good heuristic. It's worth trying, at the very least.

EDIT: read your reply to the other user. Fair enough :)

Re: Optimizing a breadth-first search

#14

Post by ball_of_lint »

hinkley wrote: post #8
rrobukef wrote: post #4

Earlier quoted context omitted.

This was my thought too, but I don't want to assume: he cites enough standard but specific sources that he should know the general search algorithms. Also I think that since he doesn't mention standard depth first search at all it perhaps wasn't relevant?

I think it warrants an explanation though. Why not DFS? Too hard to dedupe? What’s the branching factor and the duplication rate? If the algorithm is 50x faster due to lower overhead it might be worth it.

It would probably end up with similar memory requirements because it has to dedupe. Naively you would need to store all the visited states anyway just like with BFS.

You might see some interesting effects using a bloom filter and an IDDFS. It would turn the whole search probabilistic but might be fast enough that you could run it enough times to remove reasonable doubt.

Re: Optimizing a breadth-first search

#15

Post by stcredzero »

Something has happened to Comp Sci programs over the past 3 decades. Based on what's too small a sample size (the graduates I've been interviewing in SF) it seems like a very large number of graduates from CS programs with 3.75 GPAs or above, can't do much more than glue together libraries, can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name-drop algorithms, and fall far short of being able to implement those algorithms.

There are literally problems that were 1) once covered in freshman year, 2) could once be recognized and solved by CS grads in seconds, 3) stump recent CS graduates, 4) prompt HN commenters to say how they could solve it if given a few days, and 5) come up in conversation if you go to meetups and talk to people doing actual work.

How does this relate to BFS? It used to be that someone trained as a computer scientist would look at a data structure or a graph and start running some quick gedankenexperiments: What would happen if I tried to find that with DFS? What would happen if I tried to find that with BFS? Those aren't going to be suitable solutions for all problems, but it's a good place to start thinking. There seem to be a large number of recent grads who can't even get that far.

Re: Optimizing a breadth-first search

#17

Post by hashkb »

stcredzero wrote: post #15

Something has happened to Comp Sci programs over the past 3 decades. Based on what's too small a sample size (the graduates I've been interviewing in SF) it seems like a very large number of graduates from CS programs with 3.75 GPAs or above, can't do much more than glue together libraries, can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name…

I clicked on this thread to make a sure-to-be-downvoted ironic comment along the lines of "this isn't appropriate content for HN based on community sentiment regarding whiteboard interviews and what kind of work we actually do at our jobs."

There's a serious problem in the industry being driven by coding bootcamps; it's really sad to see universities being forced to stoop to compete.

Re: Optimizing a breadth-first search

#18

Post by taeric »

stcredzero wrote: post #15

Something has happened to Comp Sci programs over the past 3 decades. Based on what's too small a sample size (the graduates I've been interviewing in SF) it seems like a very large number of graduates from CS programs with 3.75 GPAs or above, can't do much more than glue together libraries, can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name…

I think you are using very rose colored glasses looking at the past. The best of the best could do that, likely. However, few could ever do things in seconds. Nor is there really any benefit in being able to solve something in seconds.

Interestingly, to me, it seems our industry was dominated by people that got good at gluing things together. To a very large degree. We bemoan this when we talk about how much more responsive machines used to be, but I think there can be very little denying that computers do more.

Granted, I suspect I am at best one of the bad graduates you are referencing. :(

Re: Optimizing a breadth-first search

#19

Post by hashkb »

taeric wrote: post #18
stcredzero wrote: post #15

Something has happened to Comp Sci programs over the past 3 decades. Based on what's too small a sample size (the graduates I've been interviewing in SF) it seems like a very large number of graduates from CS programs with 3.75 GPAs or above, can't do much more than glue together libraries, can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name…

I think you are using very rose colored glasses looking at the past. The best of the best could do that, likely. However, few could ever do things in seconds. Nor is there really any benefit in being able to solve something in seconds. Interestingly, to me, it seems our industry was dominated by people that got good at gluing things together. To a very large degree. We bemoan this when we talk about how much more res…

Nobody here would deny the business value of gluing APIs together. We're not asking for your empathy, either; but we are telling you the truth about the difference between where the bar was and where it is now.

The idea that "computers are fast, my code just needs to work" is a really really horrible way to treat your users' devices. A whole host of similar ideas are now popular, and it's pretty obvious that it's because the industry is now dominated by people that are (just) good at gluing things together. This is a bad thing.

Re: Optimizing a breadth-first search

#20

Post by spike021 »

stcredzero wrote: post #15

Something has happened to Comp Sci programs over the past 3 decades. Based on what's too small a sample size (the graduates I've been interviewing in SF) it seems like a very large number of graduates from CS programs with 3.75 GPAs or above, can't do much more than glue together libraries, can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name…

>Something has happened to Comp Sci programs over the past 3 decades. Based on what's too small a sample size (the graduates I've been interviewing in SF) it seems like a very large number of graduates from CS programs with 3.75 GPAs or above, can't do much more than glue together libraries, can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name-drop algorithms, and fall far short of being able to implement those algorithms.

Ah, one of the pain points with companies in the Bay Area.

For the longest time one obvious, if not necessarily exclusive, problem with students who can achieve a 3.75 or higher GPA is that they tend to be much better at the rote memorization of concepts, but because they didn't necessarily "slog" through stuff, have some troubles, not try to just memorize formulas and algorithms, they don't have the ability to think through problems.

What about students in the 3.0 to 3.75 GPA range? Or are they considered "too dumb" to pass the resume filter you're using?

I think recruiting around here is targeted at "best and brightest" too much, and over-simplifies just the kind of people fit that qualifier.

I remember applying for internships while I was going to SJSU and many of the top companies in the area would have a drop down selection list of "which university did you attend?" and the list would only consist of the usual top UC's and top private schools.

I'm not saying actually smart people can't come from those universities, but when you're doing things like limiting a candidate search to 3.75 or greater GPAs, or filtering based on only "top" schools, then I think the issues you're describing are going to be much more immediate than otherwise.

Post reply on HN