Repository for a great number of the suspected function runs must often be organized during the realization of numerical global optimization method or program modules testing methods. In this connection the problem of a fastaccess search of required element arises. A way to solve the problem can be found through the organization of an effective data repository, which allows for rapid implementation of the search and insertion of new elements. The binary and ternary trees storage options are considered in the paper, their comparison is made, recommendations for use of analyzed data models are reported.
Considerable volume of function "runs" must be stored during application of
numerical global optimization method (GO) [
Let us agree, that by the test we mean function f (x) calculation at the point
specified by optimization algorithm or function testing algorithm. Optimization methods
complexity is the total number of algorithm steps [
At the same time, each function call may require significant computing time depending on the complexity of the test function.
This article deals with the problem of data repository organizing for GO algorithm
based on the modified bisection method (BM) [
In order to avoid repeated calculations, it is expedient to store the point coordinates
and function values at them in a separate data repository. Thus the data array may
have considerable size. In this case there is the problem of finding an element in the
array. For example, the average complexity of sequential search in an unordered and
in an ordered array is O(n) [
Practically, binary trees (b-trees) are generally used to increase the efficiency of the
search algorithm [
Figure 2 shows the balanced binary tree built for the regular grid (see. Fig. 1) using one of the rational methods of construction of the balanced binary tree. In addition, computational experiment must comply with the sequence shown in Figure 1. The calculations start from a point with coordinates (2, 2). A binary tree shown in Figure 2 corresponds to this plan. However, the gradual detalization of the search area is peculiar for BM, and it starts from a large sample spacing with a gradual decrease in specific fragments in the searching range. The range of search "densifies" nonuniformly here. In this case, it's impractical to achieve the balance of the binary tree, and this leads to efficiency loss of search algorithms. Figure 3 shows a binary tree corresponding to the experiment shown in Figure 4. As can be seen from the figure binary tree becomes not balanced for irregular grid. One way to improve the efficiency of the search algorithm is to use more complex data structures, such as ternary trees (t-trees). 2
Two ordering relationships ("<" and "> =" or "<=" and ">") are used to build a binary tree that allow to implement a procedure of binary division of the ordered set. Three conditions are required for the ternary tree construction which allow to split an ordered set into three parts. As such, will be the following conditions "<", "=" and ">". Points of the experiment will be organized by the following criterion z x y , i.e. by the sum of the experimental points coordinates. In general, points with coordinates that correspond to the condition of equality, not often encountered; in this case, a ternary tree is converted into binary. However, there is a fair amount of such points for regular grids. Points that satisfy the condition of equality are located on the diagonals ( x y const ) for 5 * 5 grid in figure 5. The result is a t-tree, shown in Figure 6.
The comparison between an average efficiency of search for b- and t-trees for different regular grids of partitioning the search space is of some interest.
Let n be a number of nodes of a regular grid for each coordinate, N n2 - the total
number of grid nodes, k - the depth of a complete binary tree [
The total number of nodes for a "complete" (balanced) b-tree can be calculated from
the formula [
log2 N, if log2 N log2 N, k log2 N1, else.
On the assumption of equally probable binary tree filling with the information in the grid nodes we calculate the average complexity of the search on the "complete" btree. For a grid with the number of elements N n 2 , the elements of the "complete" tree up to the depth k 1 will be completely filled. 2k elements are located on each k level of the binary tree. It is easy to show that for equally probable distribution of nodes of a regular grid in a binary tree the average complexity of search can be calculated using the following formula:
1 B(N ) 2 (k n2 (k 1) 2k ).
n Unfortunately, "complete" balanced b-tree is generated only when the inclusion of grid elements into a binary tree has a certain order. In general, the search process can form linear structure with greater depth than the "complete" b-tree.
Knuth [
The ternary tree depth is almost the same as the dimension of the grid, as the tree depth cannot be less than the number of nodes on the grid diagonal because of the equality operation. It is much more difficult to calculate the average complexity of the search T(N) for a ternary tree. Figure 7 shows a graph of behavior T(N) of the number of grid elements resulted from the computing experiment for quasioptimal t-trees. As can be seen from the figure a ternary tree has disadvantages in the description of the regular grid of the experiment in comparison with optimal binary tree. However, a margin of free branches in the tree that can be filled with new grid nodes is very important in the nonlinear search space partitioning method when changing the sample spacing of the search space. In this regard, the binary tree loses much to t-tree, since b-tree branches are located at the last level of the tree.
The reservation availability for new experimental points occurs in the t-tree, which do not increase the depth of search long enough. The latter happens because the operation of the equality "=" implements the partition of the grid points set into equivalence classes. All classes are comparable to operations "<" and ">" and form "branches" of equivalence.
Grid densifying in separate squares leads to the appearance of new branches, that quickly find an empty place on a tree. The upper levels of binary trees tend to be already completed by this time and further development is possible only by increasing the depth of the tree.
It is inappropriate to sort b-tree in order to improve its structure when the operations
of element inserting and searching for an item in the tree are made at the same time.
The fastest sorting algorithms require N log2 N operations to improve the tree
structure [
Thus, ternary tree can be used as the data model of experimental points placement during software module testing. 3
The efficiency of the search algorithm in ternary tree depends on the properties of the
test function. We used 6 test functions with different topologies in the computational
experiments and, therefore, different computational complexity in terms of solving
the problem of GO. The functions are different: from relatively simple rational
functions, more complex ravine functions, multiextremal functions (including
discontinuous functions) to ROOT standard test functions offered on the site [
As can be seen from the figure, in most cases, the efficiency of the search on the t-tree is comparable with the average complexity of the search at the optimal binary tree. The latter is achieved due to the large number of ternary tree free connections, located on the upper levels. In general, the average search length of t-tree has an acceptable value for large volumes of stored data. In comparison it should be noted that t-tree was discussed in unsorted form, while b-tree, for the same amount of information was optimal and balanced. The latter means the high efficiency of the search on t-trees. If we consider the relative average search length (ratio of the average search length to the total number of elements of the tree), then with increasing of the size of t-tree search efficiency only increases (see Fig. 9).
In this article, we considered the problem of data repository organization and data search algorithm on ternary trees, designed to serve the global optimization methods and function tests that require processing of large volumes of information. Using of ternary trees gives a number of advantages in comparison with traditional binary trees, as it does not require to perform a sort operation or balance the tree in order to improve the efficiency of the search on ternary trees, and the average complexity of the search is comparable to the efficiency of search on the binary optimal balanced tree.
This work was supported by the state Ministry of Education and Science of the Russian Federation as part of the activities of the Program of competitiveness improving of SSAU among the world's leading research and education centers for 2013-2020.