hexomancer

Nope. We only have to read the parent of the last changed folder. Plus, any filesystem worth its salts already caches the frequently used parts.

> where are you storing the amount each file was changed since the last parent folder update

The same place we store the rest of the file attributes?

I think my design does make a lot of sense but you are actively trying to not understand it.

> So you have a log file inside a folder. Because it just keeps growing line by line then the folder's size is never updated. Now you have many Gb's of log file in that folder, and the folder says it is using "4Kbytes".

You misunderstood what I meant. I didn't mean we should only update if a single change is significant. I meant we only update when the cumulative changes since last update is significant. An example:

Let's say we create a 1mb file. The next time the file is changed, we only update the parent if the change is more than 10% (the new size is greater than 1.1mb or less than 0.9mb). For example if it is a log file and each line is 100 bytes, we update the parent after 1000 new lines (even though the 1000th line is still only 100 bytes). (of course the number of lines before the update depends on the size of the file, so if we had a 1GB log file, we would update after 1000000 new lines).

It is trivial to prove that the estimate is never off by a factor of more than 10% (even for the parent folders). So this is not a "half-assed broken-by-design feature" since it provides strong guarantees in bounds and at least in my personal day-to-day usage, I almost never care about the exact size of a folder but want to have a rough idea of how large it is.

First of all, most files are nowhere near 10 levels deep, let alone hundreds of levels.

Second, we don't have to do a naive update every single time a file is changed. We can amortize the cost by updating the parent folder sizes only when the file size is changed by a significant amount since last update (say, 10%). And we can do this process recursively is the parent directories. This was it only takes O(1) time to update folder metadata for each file operation and all the metadata are accurate within 10%.

Also I don't see how drives and hard linked files are any different than regular files in this context.

Can you elaborate on this?

Do you have a source for that?

Is it alzheimer’s?

You say that as if there are not millions of developers using multi-monitor setups already.

I don't get why having multiple optimal paths would falsify my algorithm. Can you provide an explicit counter-example?

Here is why I think the algorithm is correct:

At each step the edge that we are considering is either contained in all the optimal solutions or only some of them. If the edge is contained in all the solutions, increasing its weight to infinity would change the optimal solution and we pick that edge in our solution. Otherwise (if the edge is contained in only some of the solutions) increasing the weight would not change the solution because there is another optimal solution that does not contain that edge so we do not pick that edge.

So we can prove this theorem: At every step of the algorithm if an edge is picked, it is contained in all the optimal solutions.

So the algorithm does not pick any extra edges. Now we have to prove that it includes all the necessary edges. But that is easy because each time that we choose not to including an edge, we are sure that there is an optimal solution in the remaining graph so we are never left with a graph with no optimal solution.

I think you assumed that I meant we change the edge weights from infinity back to their original value at each step but that is not what I meant.

Do you have a reference to a reputable source that proves the optimization version is cook-reducable to decision version?

I didn't say there is anything wrong with reducing the optimization to decision in general. But I feel this specific application to the TSP problem may be flawed. (for the reasons i mentioned before. i.e wikipedia being very specific about the decision version) For another resource see: https://www.ibm.com/developerworks/community/blogs/jfp/entry...

note: I am not implying that the above source is reputable. But it does hint that the solution to this problem probably is not this trivial.

Thanks for the answer, I have edited my post and I have basically the same solution. (Only instead of removing the edges I increase their weight to infinity because I think the TSP problem is defined only on complete graphs) But as I have mentioned in my comment I feel like this solution is flawed.

How?

edit: The wikipedia mentions that the TSP problem is NP-hard and explicitly says that the decision version of this problem is NP-complete. My assumption is that if the optimization version was proven to be NP-hard there would be no need to explicitly mention the decision version.

I can think of a way to use the decision version to find a solution to the optimization version but i feel like it must be flawed:

First we do a binary search on `L` (the length of the tour- input to the decision version) so we can find the optimal L within a factor of epsilon (maybe this epsilon is the flaw? But I don't think that is the case.) Now we pick an edge and increase its weight to infinity. Now we do the binary search again on the new graph. If the value of the optimal solution has changed it means that the edge must be in the optimal optimization solution. By doing the same process on all the edges we can find the optimal solution.

As I said there must be a flaw in the above algorithm but I can't find it.

Are these supposed to make Israel sound good? Because to me, it sounds like Israel is doing the dirty, inhumane works for the US.

I mean it is cool but how is it cooler than VR? VR can achieve the exact same effect as this and more.

What?! A constant in logarithmic scale is still a constant.