Archived issue #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.
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
Documentation remark, added by Author 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
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
Public activity
No public notes
Participants are labeled by their role within this record.