Глупый вопрос про один алгоритм
выглядит как две прямые
нет он не линейный. как раз таки раньше был линейный и можно было тупо делить число на расстояние и попадать в нужный индекс
хочется лучше, чем бинарный поиск?
ps
можно использовать бинарный поиск, но делить не пополам, а пропорционально разнице между предыдущим и текущим
ps
можно использовать бинарный поиск, но делить не пополам, а пропорционально разнице между предыдущим и текущим
можно вычислить примерный индекс а потом проверить что там и поправить на единичку если не угадал
можно вычислить примерный индекс а потом проверить что там и поправить на единичку если не угадалвот я так и сделал. считаем среднее расстояние между целями, находим приблизительный индекс, и потом идем от этого индекса либо вверх либо вниз.
быстрее реально ?
принципиальных улучшений я тут не вижу. как вариант можно подогнать примерный индекс так чтоб двигать нужно было только в одну сторону, или вычислить его без условных переходов, или всунуть в массив в середину чисел чтоб индекс вычилялся проще и точнее.
число это время до милисекунд 
и это юзается в расчете графики
и это юзается в расчете графикиi = (x < 1650) ? x - 33) / 100) : x - 1896) / 100 + 15)
Дальше выбираешь между a[i] и a[i+1].
Дальше выбираешь между a[i] и a[i+1].
а поясни плиз происхождение магический чисел ?
Как уже говорил , две прямые.
99 100 99 100 100 100 100 100 100 99 100 100 100 100
466
100 100 100 100 100 100 100 100 100 100 100 100 100
99 100 99 100 100 100 100 100 100 99 100 100 100 100
466
100 100 100 100 100 100 100 100 100 100 100 100 100
Можно после первого шага не двигать на единички, а применять тот же приём. Получится interpolation search, он же false position method.
я бы завел индексный массив:
duration_index[64] = {0, 1, 1, 2...}, где i-ый элемент хранит в себе индекс элемента в исходном массиве. Нужный индекс берется как индекс самого ближайшего значения из исходного массива к значению некоторой функции от i
в данном случае в качестве функции я выбрал линейную (f(x) = 50 * x)
после подготовки такого индексного массива попадание в цель вообще имеет сложность O(1):
nearestValue = duration[duration_index[round(1065 / 1030)]];
duration_index[64] = {0, 1, 1, 2...}, где i-ый элемент хранит в себе индекс элемента в исходном массиве. Нужный индекс берется как индекс самого ближайшего значения из исходного массива к значению некоторой функции от i
в данном случае в качестве функции я выбрал линейную (f(x) = 50 * x)
после подготовки такого индексного массива попадание в цель вообще имеет сложность O(1):
nearestValue = duration[duration_index[round(1065 / 1030)]];
но опять же, после удаления/добавления значений в исходный массив придется перестраивать индесный
и возникает сложность в виде подбора нужной функции
и возникает сложность в виде подбора нужной функции
i = (x < 1650) ? x - 33) / 100) : x - 1896) / 100 + 15)во, про это я и говорил, но самому считать было лень
Дальше выбираешь между a[i] и a[i+1].
ещё тут наверно можно придумать битхак в духе кармаковского корня, но уже совсем хардкор
как быстро найти индексподходящий алгоритм : метод секущих
http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_...
подходящий алгоритм : метод секущихиллюстрация: берем код с вики, допиливаем, любуемся:
#include <iostream>
int durations[] = {33,132,232,331,431,531,631,731,831,931,1030,1130,1230,1330,1430,1896,1996,2096,2196,2296,2396,2496,2596,2696,2796,2896,2996,3096,3196};
int durations_last_index = sizeof(durations) / sizeof(durations[0]) - 1;
int f(int x)
{
return durations[x];
}
template <typename F>
int findRoot(int a, int b, F f)
{
int iterations = 0;
while (a < b)
{
++iterations;
a = b - (b - a) * f(b)/(f(b) - f(a;
b = a - (a - b) * f(a)/(f(a) - f(b;
}
std::cout << "iterations : " << iterations << std::endl;
return b;
}
int main
{
const int y = 1065;
int x = findRoot(0, durations_last_index, [] (int x) { return f(x) - y; });
std::cout << "x = " << x << ", y = " << y << ", f(x) = " << f(x) << std::endl;
}
выхлоп:
iterations : 1борьбу с делением на ноль, округлениями и тд доверяю читателю
x = 10, y = 1065, f(x) = 1030
ссылка : http://ideone.com/6fqZLJ
думаешь быстрее однострочника что написал?
думаешь быстрее однострочника что написал?не думаю
решение слишком завязано на входные данные, поэтому работает шустрее
предложил более общий подход (хотя и не универсальный). может, пригодится ТС
надо помнить, что скорость сходимости зависит от входных данных. в частности, данные должны образовывать монотонную последовательность. чем более похоже на прямую, тем шустрее сходиться будет
хмм
а где факап чето не могу понять ?
http://ideone.com/MMmlBQ
поменял массив и время а находит неправильно
а где факап чето не могу понять ?
http://ideone.com/MMmlBQ
поменял массив и время а находит неправильно
а где факап чето не могу понять ?надо запиливать поддержку дискретного случая
например, так: http://ideone.com/NSOYV9
Оставить комментарий
bav46
Есть вот такой массивdurations[29](33,132,232,331,431,531,631,731,831,931,1030,1130,1230,1330,1430,1896,1996,2096,2196,2296,2396,2496,2596,2696,2796,2896,2996,3096,3196)
есть число, например 1065
как быстро найти индекс для элемента 1030, попадание в цель в общем