StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I thought of this this morning, then found that @Alexey Kukanov had similar thoughts. But mine is more fleshed out and has some more optimization, so I'll post it anyways.</p> <p>This algorithm is <code>O(n * (1 + generations))</code>, and will work for any dataset. For realistic data this is <code>O(n)</code>.</p> <ol> <li>Run through all records and generate objects representing people which include date of birth, links to parents, and links to children, and several more uninitialized fields. (Time of last death between self and ancestors, and an array of dates that they had 0, 1, 2, ... surviving generations.)</li> <li>Go through all people and recursively find and store the time of last death. If you call the person again, return the memoized record. For each person you can encounter the person (needing to calculate it), and can generate 2 more calls to each parent the first time you calculate it. This gives a total of <code>O(n)</code> work to initialize this data.</li> <li>Go through all people and recursively generate a record of when they first added a generation. These records only need go to the maximum of when the person or their last ancestor died. It is <code>O(1)</code> to calculate when you had 0 generations. Then for each recursive call to a child you need to do <code>O(generations)</code> work to merge that child's data in to yours. Each person gets called when you encounter them in the data structure, and can be called once from each parent for <code>O(n)</code> calls and total expense <code>O(n * (generations + 1))</code>.</li> <li>Go through all people and figure out how many generations were alive at their death. This is again <code>O(n * (generations + 1))</code> if implemented with a linear scan.</li> </ol> <p>The sum total of all of these operations is <code>O(n * (generations + 1))</code>.</p> <p>For realistic data sets, this will be <code>O(n)</code> with a fairly small constant.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload