search

petrelharp / ftprime_ms

4 stars 2 forks source link

Issues with "Estimates of run time complexity section" #66

Closed jeromekelleher closed 6 years ago

jeromekelleher commented 6 years ago

I'm not fully comfortable with this section at the moment. At a high-level, I think it's moving a bit too quickly at the moment, and could use a little more explanation. Perhaps a few more full equations would help break things up a bit?

Specific problems:

  1. The paragraph starting "To get an idea of how required space depends on the length of time between simplification steps.". This isn't what the paragraph is about though, is it? I though the result in (1) gives us the upper bound on the number of edges in the simplified TS.
  2. We don't ever actually explicitly show the O(N log N + M) space result from the abstract. We definitely need to make this clear.

That's it really. I think we just need to slow it down a bit and explain the results that are derived. These are cool results, it'd be a shame if people didn't understand them!

petrelharp commented 6 years ago

re: (1) Oh, good point. That calculation is related to the question of how much memory is used given a certain simulation interval, because it tells you how much you cut back down to, but that's not the required space. We could change the title sentence here to "What if we simplify more frequently?" This suggests, as Kevin's empirical results do also, that the speed advantage to waiting longer decreases. From these calculations, I would have thought that waiting longer than about 4N generations to simplify wouldn't help things any; but in Fig C2 with N=10,000, we've got optimal speed already simplifying every 1,000 generations.

petrelharp commented 6 years ago

The section is clearly about both time and space complexity. Need to change the title.

And, you're right, this should lead off with a short paragraph explaining the O(N log N + M) thing.

I'll have a go at this.

petrelharp commented 6 years ago

Hopefully the changes I made over there addressed this. I didn't lead off with the O(N log N + M) thing because it was already there, effectively, but I added a paragraph saying this explicitly (although I didn't say "as we said in the abstract").