Changes between Initial Version and Version 1 of Ticket #18368, comment 3


Ignore:
Timestamp:
2019-11-30T10:24:14+01:00 (4 years ago)
Author:
GerdP

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #18368, comment 3

    initial v1  
    11The problem with the existing algorithm is that it does a brute force search for the best node to start with when there is no "terminal node" like in a c-shaped or d-shaped way.
    2 It starts with node 2684142672 and adds nodes in clockwise order until it detects a problem when it comes to node 176872704 for the 2nd time. This "problem detection" in `buildSpanningPath()` is a rather complex operation, I think it is at least O(n²) and it uses a synchronized Stack. Instead of starting a 2nd try with this problem node as start it uses the node 1740733337 and fails again at the same place after. This is done for thousands of nodes and each call takes very long as we have a O(n³) algo now.
     2It starts with node 2684142672 and adds nodes in clockwise order until it detects a problem when it comes to node 176872704 for the 2nd time. This "problem detection" in `buildSpanningPath()` is a rather complex operation, I think it is at least O(n²) and it uses a synchronized Stack. Instead of starting a 2nd try with this problem node as start it uses the node 1740733337 and fails again at the same place after almost the same time. This is done for thousands of nodes and each call takes very long as we have a O(n³) algo now.
    33I think it is obvious that we should start with a node that appears most often in the given edges when there is no "terminal node". The patch implements this.
    44The search for the start node is much faster than the problem detection. On my PC I see < 30 ms for the additional search and ~1500 to 3500 ms for the (single) call of `buildSpanningPath()` to compute the result.