Changes between Initial Version and Version 1 of Ticket #8643


Ignore:
Timestamp:
2013-04-27T23:15:17+02:00 (12 years ago)
Author:
bilbo
Comment:

Note: there seems to be one still some O(n2) part in the Purge command, though not that bad one:

The while loop, with comment: 

 // Add referrer, unless the object to purge is not new
 // and the parent is a relation

When purging 176000 ways: needs 20 secs When purging 550000 ways: needs 260 secs (in both cases the purged ways are about 99% of the loaded dataset, i.e. not much is left afterwards

and the characteristics of the data is the same - OSM extracts with only buildings in them)

Now I see the reason for this is the same (iteration restarted after every removal, so effectively O(n2) part too), I guess I'll make another patch to fix this one too.

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #8643 – Description

    initial v1  
    1 There is bad algorithm used in Purge command, with complexity O(N^2), causing purge with about 176000 ways to take over 15 minutes.
     1There is bad algorithm used in Purge command, with complexity O(N^2^), causing purge with about 176000 ways to take over 15 minutes.
    22
    33Problem is in toposort, where the algorithm restart iteration over the hashset after every deleted way, but in Javaadoc for HashMap it says: