а вот ArrayBsearch - страница 2
Вы упускаете торговые возможности:
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Регистрация
Вход
Вы принимаете политику сайта и условия использования
Если у вас нет учетной записи, зарегистрируйтесь
(Вы фактически говорите: "мы писали на стандартном языке программирования, как работает - так и правильно").
Т.к. логика функции должна соответствовать спецификации, а не сама себе...
Повторяю
Функция задумывалась прежде всего для таймсерии Time[], поэтому такое поведение.
Добавлю
В примере к функции ArrayBsearch приведён пример именно с таймсерией Time[].
Поэтому
Поведение функции изменено не будет. Будет уточнено описание.
В общем, вот функция бинарного поиска ближайшего значения из массива double. Написано может и не очень красиво (ну не люблю я си), но работает вроде.
Если разработчики пожелают её в каком то виде использовать с МТ, буду только рад, дарю. Но её подрихтовать надо, для эффективности. Для целочисленных массивов примерно так же можно решить задачу поиска. Нужно только следить, что бы середина диапазона между соседними значениями правильно интерпретировалась. Если подменить функции сравнения значений, то можно искать и даты и строки и прочее.
PS. блин! что за коварный движок у форума. Эта сволочь сожрала все ведущии пробелы в коде. Исправлять не буду.
int start()
{
int pos;
double val;
double buf[] = { 1.45, 1.46, 1.47, 1.48, 1.49, 1.50 };
val = 1.44; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.45; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.454; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.457; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.4749; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.475; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.479; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.48; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.484; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.485; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.499; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.50; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
val = 1.56; pos = NearestBsearch( buf, val, 0, ArraySize(buf) - 1);
Print( "для значения: ", val, " нашел индекс: ", pos," и его значение в массиве: ", buf[pos]);
//----
return(0);
}
//+------------------------------------------------------------------+
// array[] - массив
// value - искомое значение
// start - начальный индекс массива, в котором происходит поиск
// last - конечный индекс массива, в котором происходит поиск
// возвращается найденный индекс или -1, если была ошибка в задание start и last
// массив должен быть отсортирован по возрастанию.
//+------------------------------------------------------------------+
int NearestBsearch( double array[], double value, int start, int last)
{
int center;
if( start > last) { return( -1); }
if( start == last) { return( start); }
if( value <= array[start]) { return( start); }
if( value >= array[last]) { return( last); }
while( start < last - 1) {
center =( start + last) / 2;
if( array[center] <= value) { start = center; }
else { last = center; }
}
if( value < (( array[start] + array[last]) / 2)) { last = start; }
return( last);
}
stringo:
---------
Там, где я работаю, ошибки так и фиксятся временами - просто вносятся изменения в документацию.
При этом сам код остается тем же.
Иногда достаточно доказать, что какое-то требование уже обсуждалось
(с такими аргументами, такие письма, такое подтверждение в bug-tracking),
чтобы изменили техническое задание.
Тест-инженеры изменяют тесты, ошибка исчезает.
И абсолютно рабочий проверенный код, несоответствующий документации -
это такой же дефект, как, например, ошибка инициализации приложения,
когда пользователь вообще ничего на экране не увидит (просто приоритет другой).
.
Я критиковал исключительно стиль Вашей аргументации.
.
HideYourRichess:
---------------------
Не поверил я Вашему коду. Какой-то он слишком сложный.
.
Проверьте, пожалуйста, такой вызов:
double buf[]={ 10, 30, 50, 70 };
double val= 20;
int pos=NearestBsearch(buf,val,0,ArraySize(buf)-1);
.
Результатом поиска будет будет не совсем ожидаемое число 30,
если, конечно, Вы все именно так все и не задумывали...
А все из-за того, что не была проведена проверка граничного условия -
когда искомое значение оказывается точно посередине двух элементов массива.
Мне повезло ;-) и (10+30)/2 оказалось точно равно 20 :-).
.
А всего-то нужно откорректировать условие
if( value < (( array[start] + array[last]) / 2)) { last = start; }
и сделать его таким:
if( value <= (( array[start] + array[last]) / 2)) { last = start; }
.
Возможно, есть еще ошибки.
.
А почему нельзя было просто перебрать все элементы массива, запоминая позицию с наименьшим
расстоянием от образца? Ведь, в частности, уйдет требование насчет сортировки.
Для 20 алгоритм выдаёт законные индекс 1 и значение 30. 30 - это и есть правильный результат. Там нет ни каких ошибок. Не нужно менять "<" на "<=" - только испортите. Всё проводится по правилам классического арифметического округления.
Перебирать нельзя потому что скорость работы, в массе своей, станет гораздо хуже чем есть. Сейчас она примерно log2 (размер_массива). Вообще, это классический бинарный поиск, немного подправленный под текущии нужды. Для задач общего вида, не специальных, это один из самых быстрых алгоритмов. Его бы ещё под потоковые операции переписать и на ассемблере - было бы вообще прекрасно.
Если вы считаете этот код сложным - напишите свой, более простой и более быстрый. На всякий случай скажу, человечество (всё человечество, не кто то конкретный) шло к созданию этого алгоритма почти 20 лет. Лучшие умы в программировании и математике. "сложный код" - ахренеть. Вы вообще понимаете, о чём вы тут вальяжно пытаетесь рассуждать? Всего одиннадцать значимых операторов! Напишите лучше.
Для 20 алгоритм выдаёт законные индекс 1 и значение 30. 30 - это и есть правильный результат. Там нет ни каких ошибок. Не нужно менять "<" на "<=" - только испортите. Всё проводится по правилам классического арифметического округления.
Добро. Но законные - "для кого"?
Первое в списке ближайшее значение не возвращается? Не возвращается.
Возвращается следующее.
Я со своей стороны допустил возможность, что Вы так все и задумывали.
Уровень протеста с Вашей стороны - это намек на то, что пост мой Вы не прочитали.
Перебирать - можно.
Не знаю, правда, какие у Вас объемы и насколько часто используется поиск,
оптимизацией математики не занимаюсь - просто не нужно
(на всякий случай уточню - результата нет ;-) ).
А если так принципиальна скорость - то можно еще быстрее сделать.
.
(правил) Если массив уровней будет содержать даже 100 значений,
то разница алгоритмов - это даже не 1% загрузки процессора.
Без тестов не верю. (правил: без тестов на валидность работы, естественно)
.
Лучше? Легко.
.
Вы там что-то типа уровней - цен искали, я видел.
1.45, 1.46, 1.47, 1.48, 1.49
.
Формируется массив с адресацией 0 - 15000. По индексу сразу закладывается ответ.
Тогда поиск ближайшего значения выглядит так:
otvet = massiv[cena * 10000]
Под конкретную задачу - в конкретных случаях - так - делать можно.
.
Или - если у Вас именно те данные, которые Вы привели в первом посте, то так:
int a = (сena + 0.005) * 100;
double b = a / 100.0;
Для cena = 1.469 ответ будет 1.47
.
Никакого мошенничества.
Если вы считаете этот код сложным - напишите свой, более простой и более быстрый. На всякий случай скажу, человечество (всё человечество, не кто то конкретный) шло к созданию этого алгоритма почти 20 лет. Лучшие умы в программировании и математике. "сложный код" - ахренеть. Вы вообще понимаете, о чём вы тут вальяжно пытаетесь рассуждать? Всего одиннадцать значимых операторов! Напишите лучше.
Знаком с отдельными представителями. Что-то указанные Вами 20 лет - маловато.
Укажите, пожалуйста, Ваш источник?
Добро. Но законные - "для кого"?
Первое в списке ближайшее значение не возвращается? Не возвращается.
Возвращается следующее.
Вы что, не понимаете? По правилам арифметического округления (которое проходят в средних классах школы) середина диапазона между двух чисел относится к большему числу. Объясняю на примере: число 1.5 округляется до 2. Это понятно? Это общее правило, проходят в школе. Другие методы округления, специальные, мы не рассматриваем. Операция округления - это и есть поиск ближайшего числа между двух.
Ещё раз, на пальцах. Середина диапазона между двух чисел 10 и 30, равна 20. Таким образом, алгоритм должен вернуть 30, что он и делает.
Все ваши последующие рассуждения о поиске показывают вашу полную неосведомленность в этой проблеме. Идея которую вы предложили - никуда не годится.
Вот вам массив, можете попробовать с помощью своей идеи поискать там числа. { 1, 1.1, 2, 45, 45.999, 50.1, 200, 201, 203 } У вас ничего не получится. Кроме того, речь идет о больших массивах. Маленькие массивы выгоднее перебирать линейным поиском.
И последнее. Вместо того что бы напрасно тратить время, напишите свой алгоритм, выложите, мы его сравним с классикой.
Знаком с отдельными представителями. Что-то указанные Вами 20 лет - маловато.
Укажите, пожалуйста, Ваш источник?
Учитесь хорошо, читайте книжки - они источник знаний.