View Issue Details
ID | Project | Category | View Status | Date Submitted | Last Update |
---|---|---|---|---|---|
0011403 | Open CASCADE | OCCT:Foundation Classes | public | 2006-01-27 14:18 | 2012-01-13 18:32 |
Reporter | Assigned To | ||||
Priority | normal | Severity | feature | ||
Status | closed | Resolution | fixed | ||
OS | All | ||||
Fixed in Version | 6.1.0 | ||||
Summary | 0011403: NCollection_UBTreeFiller is too slow | ||||
Description | The complexity of NCollection_UBTreeFiller is O(n**2) because of the randomization algorithm using sequence collection. This is important when the number of objects becomes greater than 100,000, the delays are too long. | ||||
Additional information and documentation updates | Documentation remark, added by AGV 2006-01-27 13:03:20: New features: 1. Performance of tree filling operation increased. On PentiumIV(2.4GHz), with a model of 1,000,000 triangles the tree is filled: - before: in 554sec, - now: in 21sec. 2. New method is added to UBFiller class: CheckTree. This method outputs the size of the tree and the balance factor. The latter is the mean square length of all tree branches divided by the minimal theoretical length. The greater the factor, the less balanced is the tree. Improvements: 1. INTERNAL: In UBFiller class Vector collection is used instead of Sequence, with the relevant algorithm of randomization 2. INTERNAL: In UBTree class the method Add() was slightly modified to avoid extra data copying. The additional gain of performance is ~10%. Changes: The previous public API of the modified classes has not been changed, but for one point: In UBTreeFiller constructor the parameter is added: isFullRandom, True as default. The value True ensures the correct randomization of large tree sizes (50,000 or more) ; with False - the randomization proceeds in a window RAND_MAX wide (32767 values). In my test with 1,000,000 triangles I obtained: isFullRandom == True: filling time 21sec, balance 3.3 isFullRandom == False: filling time 15sec, balance 9.0 Modified entities: NCollection_UBTree NCollection_UBTreeFiller | ||||
Tags | No tags attached. | ||||
Test case number | |||||
Date Modified | Username | Field | Change |
---|---|---|---|
2006-01-27 14:31 | bugmaster | Assigned To | bugmaster => agv |
2006-01-27 14:31 | bugmaster | Status | new => assigned |
2006-01-27 15:05 |
|
CC | => msv |
2006-01-27 15:05 |
|
Status | assigned => resolved |
2006-02-20 16:49 |
|
Status | resolved => tested |
2006-02-20 16:51 | bugmaster | CC | => imv |
2006-02-28 11:21 | bugmaster | OtherBugsDependingOnThis | => 11768 |
2006-04-06 15:55 | bugmaster | Status | tested => closed |
2006-04-06 15:55 | bugmaster | Resolution | @0@ => fixed |
2011-08-02 11:23 | bugmaster | Category | OCCT:FDC => OCCT:Foundation Classes |
2012-01-13 18:32 |
|
Description Updated | |
2012-01-13 18:32 |
|
Additional Information Updated |