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

Applying Textbook Data Structures for Real Life Wins

heap.io

Post reply on HN
Print view View original

21–30 of 33 posts

Re: Applying Textbook Data Structures for Real Life Wins

#21

Post by itissid »

nraynaud wrote: post #19

A few years back I had a traveling salesperson problem, I googled a bit, and somehow didn't find anything interesting, so I just created a random loop, and randomly mutated it until it got better. A few months ago I discovered a neat little heuristic: the best loop never self-intersect. And a few days ago, I found that there is a definite algorithm that gives a result whose worst case is bounded WRT to the optimal. M…

I think that most of the times they are particular to a domain to solve particular problem. For example Some researcher would have a grant for developing an optical inspection of a circuit board using a camera moving on the 2d euclidean space efficiently is a TSP. You can develop a Polynomial Time approximation scehne(PTAS) to solve it.

At first it's novel then st some point it appears in a book specific to polynomial time approximation schems in books dedicated to the cause. Look at the references in wikipedia. They often point to a larger body of work than what the wiki can possibly hope to cover.

Re: Applying Textbook Data Structures for Real Life Wins

#22

Post by eutectic »

KMag wrote: post #15
eutectic wrote: post #12

Earlier quoted context omitted.

I think there's a paper somewhere claiming that completely random linking is just as good as union-by-rank (in expectation).

Isn't that expected (within a constant factor of optimal depth, a.k.a. O(log N) tree height)? They're essentially building a treap, minus the in-order traversal of keys restriction. [0] https://en.wikipedia.org/wiki/Treap

Optimal depth for union-find is O(1); every node points directly to the root. It's a very different case than building a binary search tree.

Re: Applying Textbook Data Structures for Real Life Wins

#24

Post by nraynaud »

dlkf wrote: post #20
nraynaud wrote: post #19

A few years back I had a traveling salesperson problem, I googled a bit, and somehow didn't find anything interesting, so I just created a random loop, and randomly mutated it until it got better. A few months ago I discovered a neat little heuristic: the best loop never self-intersect. And a few days ago, I found that there is a definite algorithm that gives a result whose worst case is bounded WRT to the optimal. M…

OOC: how did you create your initial random loop? This was a Kaggle problem about seven years ago. The competitive solutions found a good initial guess by breaking up the domain into a grid. They would solve TSP in each grid cell, and then stitch these solutions together to get a reasonable initial global solution. If you created your initial loop greedily (as I did) you got a garbage solution, and also wasted a lot…

sorry, I misremembered, I used a Z-order path in the end:

https://github.com/nraynaud/webgcode/blob/gh-pages/webapp/cn...

I guess I decided that some order was better than random.

Re: Applying Textbook Data Structures for Real Life Wins

#25

Post by vivekseth »

nraynaud wrote: post #19

A few years back I had a traveling salesperson problem, I googled a bit, and somehow didn't find anything interesting, so I just created a random loop, and randomly mutated it until it got better. A few months ago I discovered a neat little heuristic: the best loop never self-intersect. And a few days ago, I found that there is a definite algorithm that gives a result whose worst case is bounded WRT to the optimal. M…

I would try to look for academic papers on the topic. Even if you can’t find an exact match, papers typically have a section that describes other related work. You can also scan through the citations to see if anything might be a match. If there’s some relevant paper, you’ll probably find it after searching through a few papers.

When reading a paper I would just scan the abstract, conclusion, introduction, related work section (possibly in that order) to see if it’s relevant.

For finding papers I like semantic scholar and Google scholar.

Re: Applying Textbook Data Structures for Real Life Wins

#26

Post by egberts1 »

Biggest and most challenging trend is to properly devise a data design schema for:

1. an appropriate privacy and deanonymization level to each data item in a structure (corporate privacy, trade secret, account ID)

2. an appropriate privacy level to a tuple of data items (i.e., PII; name, ID, birthdate)

3. And a security context for each class of end-users (support, engineering team, marketing) to use what amount of and degree of deanonymized data items.

Re: Applying Textbook Data Structures for Real Life Wins

#27

Post by lowdanie »

nraynaud wrote: post #19

A few years back I had a traveling salesperson problem, I googled a bit, and somehow didn't find anything interesting, so I just created a random loop, and randomly mutated it until it got better. A few months ago I discovered a neat little heuristic: the best loop never self-intersect. And a few days ago, I found that there is a definite algorithm that gives a result whose worst case is bounded WRT to the optimal. M…

Your method is similar to a popular probabilistic technique called simulated annealing [1].

The general setting for this type of algorithm is that you have a large number of states and you want to find the state that maximizes a particular score. In the TSP, the states are paths and the score is the (negative of the) path length. The idea is to define a Markov Chain whose stationary distribution is proportional to the score. This means that if you jump from state to state according to the probabilities defined by the MC, eventually the probability of ending up at a given state is proportional to that states score.

In the case of TSP the states can be represented as permutations of the cities and the neighbors of a state are given by swapping the positions of two cities. The probability of moving to a neighbor is high if the length of the neighbor is shorter than the current path.

[1] https://en.wikipedia.org/wiki/Simulated_annealing

Re: Applying Textbook Data Structures for Real Life Wins

#28

Post by whycombagator »

nraynaud wrote: post #19

A few years back I had a traveling salesperson problem, I googled a bit, and somehow didn't find anything interesting, so I just created a random loop, and randomly mutated it until it got better. A few months ago I discovered a neat little heuristic: the best loop never self-intersect. And a few days ago, I found that there is a definite algorithm that gives a result whose worst case is bounded WRT to the optimal. M…

> My question is how do you find all those algorithms? Wikipedia never really feel like a good introductory nor discovery place.

I know a place.

From the Github repo Coding Interview University[0] there is a link to a Jupyter notebook[1] on various ways to solve the traveling salesman problem - it is a very good, detailed, resource.

[0] https://github.com/jwasham/coding-interview-university

[1] https://nbviewer.jupyter.org/url/norvig.com/ipython/TSP.ipyn...

Re: Applying Textbook Data Structures for Real Life Wins

#29

Post by bpicolo »

nraynaud wrote: post #19

A few years back I had a traveling salesperson problem, I googled a bit, and somehow didn't find anything interesting, so I just created a random loop, and randomly mutated it until it got better. A few months ago I discovered a neat little heuristic: the best loop never self-intersect. And a few days ago, I found that there is a definite algorithm that gives a result whose worst case is bounded WRT to the optimal. M…

> you have not found the keywords

Knowing the right keywords and roughly how they fit together is a huge component of domain expertise. Building general background knowledge through experience and readings goes a long way for this reason.

Re: Applying Textbook Data Structures for Real Life Wins

#30

Post by commandlinefan »

I feel like, 25 years post-undergrad and over 10 years post grad school, I should go back and re-read some data structures classics: I spend all of my time running database queries and debugging web service calls and only rarely dipping into real algorithmic optimization. I wonder how much performance optimization I'm leaving on the table because my data structures are so rusty.
Post reply on HN