Dear readers, in the Forex Magazine 2004 number 6 in the article "Programming in MQL II: Sort method of the bubble, continued" was made a small mistake. Please note that when adding a new variable is_sorted initially it must be attributable to the value "true", not "false". Error permitted only in the description of the code, the code is correct. Thus, the revised proposal will look like this: "Every time, before once again look over and compare the elements of the array, we assign this variable the value true. If we ever change the value of the array, then assign it to false."
In the last issue we examined the sorting method of the bubble (Forex Magazine 2004 number 5 - ? 6, Programming in MQL II: Sort method of the bubble). Now discuss how to find specific information in sorted arrays.
Assume that we have a sorted array, and the challenge: to find in this array is an element which is closest in meaning to a given number (hereinafter we call it "X").
The first thing that comes to mind - this is Classified and all elements of the array to calculate the difference between each of them and the number of "X". The one whose difference will be the smallest in magnitude, and will be the next element of the array to the "X". If in sorted array of the small number of elements (up to 5), this method is quite appropriate, but let's think, how many operations a computer must perform, if the sorted array is composed of 100 elements. We need to do almost the same operations of comparison, the number of elements in the array before the desired number. Thus, in the worst case where the required element of the array is at the end, we need to do a hundred and compare operations. This is a very laborious exercise.
Can I speed up the process of a search of assorted array? So far we have not used the fact that the array is sorted. To speed up the search, it is proposed to use the bisection method - the method of dichotomy.
The method of dichotomy is this: find out how many elements in the sorted array, we compare the number of "X" with the middle element of the array. If the middle element of the array more than the "X" - means all the elements of the array after the middle element of the array is also greater than the number of "X", because we are working with a sorted array. Therefore, we should continue to search for the remainder of the array, located to the middle element. Find out how much of the remainder of the array, we again choose the middle element and compare them with the number "X". So, to find the desired item is only a quarter of the array. Then, the border search narrowed even more - until the eighth part of the array, and so on, until there is an element of the array equal to the number of "X" or until it left the array of two elements, a greater number of "X", and another less.
Fig. 1 shows a reduced space, we find the desired element. Seeking element marked a red dot, the middle of the remaining parts of the array - green tags, discarded part of the array - in gray.
In the last issue we examined the sorting method of the bubble (Forex Magazine 2004 number 5 - ? 6, Programming in MQL II: Sort method of the bubble). Now discuss how to find specific information in sorted arrays.
Assume that we have a sorted array, and the challenge: to find in this array is an element which is closest in meaning to a given number (hereinafter we call it "X").
The first thing that comes to mind - this is Classified and all elements of the array to calculate the difference between each of them and the number of "X". The one whose difference will be the smallest in magnitude, and will be the next element of the array to the "X". If in sorted array of the small number of elements (up to 5), this method is quite appropriate, but let's think, how many operations a computer must perform, if the sorted array is composed of 100 elements. We need to do almost the same operations of comparison, the number of elements in the array before the desired number. Thus, in the worst case where the required element of the array is at the end, we need to do a hundred and compare operations. This is a very laborious exercise.
Can I speed up the process of a search of assorted array? So far we have not used the fact that the array is sorted. To speed up the search, it is proposed to use the bisection method - the method of dichotomy.
The method of dichotomy is this: find out how many elements in the sorted array, we compare the number of "X" with the middle element of the array. If the middle element of the array more than the "X" - means all the elements of the array after the middle element of the array is also greater than the number of "X", because we are working with a sorted array. Therefore, we should continue to search for the remainder of the array, located to the middle element. Find out how much of the remainder of the array, we again choose the middle element and compare them with the number "X". So, to find the desired item is only a quarter of the array. Then, the border search narrowed even more - until the eighth part of the array, and so on, until there is an element of the array equal to the number of "X" or until it left the array of two elements, a greater number of "X", and another less.
Fig. 1 shows a reduced space, we find the desired element. Seeking element marked a red dot, the middle of the remaining parts of the array - green tags, discarded part of the array - in gray.
(Fig. 1)For visibility, we did not put all the elements of the array on the hatch, but if you look at the lower leg and, given that he, at 32 times smaller than the original, contains 2 elements, it is clear that initially, we had an array of about 60 items. As a result of application of the dichotomy, completing only 6 of comparison operations, we were able to complete the search. If the search for direct bust, we would require approximately 30 operations comparison. The gain in the face.
Now we will try to implement this method of searching for MQL II. We will need some time to carry out similar acts, then we will need to design "cycle." Because we did not know how long we will have to perform a search, we take the cycle "while". The rest will become clear from the code and its comments.
Now we will try to implement this method of searching for MQL II. We will need some time to carry out similar acts, then we will need to design "cycle." Because we did not know how long we will have to perform a search, we take the cycle "while". The rest will become clear from the code and its comments.
In the next article we will learn to practice the method of sorting.
array: values [100] (0);
/ / original array to the left edge
/ / search coincides with the beginning of the array values
var: left (0);
/ / initially the right edge of the array for
/ / search coincides with the end of the array values
var: right (99);
/ / Middle element
var: middle (50);
/ / fill an array of values Fibonacci numbers
var: ix (0);
values [0] = 1;
values [1] = 1;
for ix = 2 to 99 (
values [ix] = values [ix-1] + values [ix-2];
);
/ / will go to the numbers Fibonnachi
/ / near to our "X"
var: X (123);
/ / variable "found" will contain the value "false"
/ / until we can not finish the search
var: found (false);
/ / continue to search until the variable
/ / "Found" not accept the value "true"
while is not found (
/ / calculate the middle of the array to search
/ / if (right - left) / 2 is not an integer, then
/ / should be rounded to the nearest whole
middle = left + round ((right - left) / 2);
/ / if the middle is the right of our element
/ / and the edge of the array to search are not yet two
/ / neighboring elements that ...
if ((values [middle]> X) and (right - left> 1)) then (
/ / ... I am the right end of the array to search
/ /, They are ours, now former, mid -
right = middle;
) Else
/ / otherwise, if the middle is left of our item
/ / and the edge of the array to search are not yet two
/ / neighboring elements that ...
if ((values [middle]
/ / ... Then change the left end of the array to search
/ /, They are ours, now former, mid -
left = middle;
) Else if (values [middle] == X) then (
/ / otherwise the middle of the same value on our part.
/ / this means that we should assign the variable
/ / Found the value "true" and thus stop the search,
/ / out of the cycle, "while"
found = true;
) Else (
/ / border for the search narrowed to the point
/ / and now the neighboring elements - this means
/ / that we should stop looking, out of the cycle, "while"
break;
);
);
/ / however, that the search has not been completed
if is found then (
/ / we got out of the cycle "while" looking for an element of the array
/ / closest to the value of a claim
print ( "Item number" + middle + "with value" + values [middle] + "matches the search");
) Else (
/ / we got out of the cycle "while" due to the fact that
/ / border for the search narrowed to the point that
/ / become neighboring elements - this means
/ / we should still compare the desired element
/ / in the subject to which the remaining elements
/ / close it
if ((values [right] - X) - (X - values [left])> 0) then (
print ( "Item number" + left + "with value" + values [left] + "closest to the required");
) Else if ((values [right] - X) - (X - values [left]) <0) then (print ( "Item number" + right + "with value" + values [right] + "closest to the Motion "); ) Else (print ( "Iskomyoe number is located exactly between the element with the number" + left + "with value" + values [left] + "and the element with the number" + right + "with value" + values [right]); ) )
No comments:
Post a Comment