roboforum.ru

Не, я спорить не хочу.  :) Просто не понимаю почему тормознутее будет?  :(  Тормознутее будет умножение выполнять? Мне почему-то кажется, что при достаточно большом массиве полином невысокой степени посчитать быстрее будет чем лопатить массив. А по поводу косяков за пределами интервала возражение не принимаю, да они могут быть, но чаще их нет, а вот при использовании массива, прогнозируемые значения функции в точках, не входящих в интервал, низя получить вообще (если, конечно, опять же не прибегнуть к интерполированию).
Вообще эта тема интересна и я бы хотел попросить поделиться табличкой исходных данных. Я бы поэкспериментировал.  8)

Да, потестить было бы интересно
Мои высказывания базируются на опыте программинга под РС в игровой сфере. Анализ всяких таких вещей, если не ошибаюсь, есть в книжке: Дональд Кнут "Искусство программирования". В каком из томов - не помню. К сожалению, от меня сейчас эта книженция на расстоянии 1500 км, поэтому посмотреть не могу В ней анализируются алгоритмы по 1скорости. И табличность тоже обсуждалась. (Если там нет, буду валить все на склероз  :roll:  )
Думаю, независимо от того, под компом все считать или под AVR, скорость будет зависеть от сложности функции: для простой функции проще посчитать, а для сложной - найти в таблице. Лопатить в таблице тоже можно по-разному - можно двоичное дерево построить, можно массив завести, в котором номер ячейки равен известной переменной, а значение в ячейке - искомое число... Масса есть вариантов ускоренного поиска элемента в массиве (Тот же Д.Кнут в книжке описывает). Все опять же от задачи зависит.

Короче чуть-чуть примитивно потесил в VMlab. Выполнение такого куска, где выполняется вычисление полинома пятой степени, коэффициенты которого храняться в массиве:

Код: Выделить всё

PORTB.0=1;
f=a[0]+a[1]*x+a[2]*x*x+a[3]*x*x*x+a[4]*x*x*x*x+a[5]*x*x*x*x*x;
PORTB.0=0;


на Меге8 4 МГц заняло 1.4мс, а вот такого, в котором просто последовательно просматриваются 20 элементов массива:

Код: Выделить всё

PORTB.1=1;
for (i=0;i<20;i++) {
if (b[i][0]==x) {
    f=b[i][1];  
};
};  
PORTB.1=0;


1.6 мс.
Может где и ошибся. Все переменные (кроме i) типа float. Т.е. если массив большой, а полином, который хорошо (с достаточной точностью) описывает поведение функции - маленький, то можно и полином заюзать.
Кстати да, доступ к массиву можно оптимизировать, и самое простое, что приходит на ум - разместить в начале элементы, котрые будут всречаться чаще всего.  8)
А вообще прикольная темка - реализация численных методов на контроллере. Тока надо ли это кому?  :)

а нафига нам перебирать весь массив  :shock: ?
мы знаем y и хотим узнать x(y)
x(y)=massiv[y]
вот, тут нам нужно 1 косвенное обращение к памяти и все

lebaon писал(а):а нафига нам перебирать весь массив  :shock: ?
мы знаем y и хотим узнать x(y)
x(y)=massiv[y]
вот, тут нам нужно 1 косвенное обращение к памяти и все

Не догнал, простите. Разве имеется в виду что значения аргумента это и есть индексы массива, в котором хранятся соответствующие значения функции? Я предполагал, что аргумент и функция - величины типа float.  Кроме того, если аргумент - величина измеряемая, например АЦП, и может принимать 256 значений, то такой массив, как-то некрасиво в контроллер загонять (кодвижн, например, дает 256 байт под стек данных по умолчанию) - нужна внешняя память. Если я не прав, аргументированно ткниет мордой в то место, где я не прав - буду благодарен.  :)

lebaon писал(а):а нафига нам перебирать весь массив  :shock: ?
мы знаем y и хотим узнать x(y)
x(y)=massiv[y]
вот, тут нам нужно 1 косвенное обращение к памяти и все

Я нечто такое упоминал выше.

2 SSG
Про индексы массива типа float: можно например умножить этот флоат на... на 10, 100 или на 1000 (в зависимости от задачи), и забить на оставшуюся дробную часть - смотря какая точность нужна.
Кстати, ты не написал, сколько у тебя прямой перебор массива идет? Полином за 1.4мс, а перебор?
Про прямой перебор: найти можно в разы быстрее. Поищи книжку Д.Кнут в инете на скач - где-то выкладывали - не пожалеешь! Там столько изящных методов разбирается!!!  :roll:

Исправился. 1.6 мс.
Книжку поищу, спасибо.  :)

Разве имеется в виду что значения аргумента это и есть индексы массива, в котором хранятся соответствующие значения функции?

именно это и имеется в виду
массив может иметь такие размеры, какие надо, в ущерб точности конечно  например на 16 значений
y=massiv[x/16] где x - byte
это будет сдвиг+обращение к памяти
почему то все привыкли, что в массиве найти значение можно только перебором, а это не так  :wink:
а задача эта сводится к вечному компромиссу скорость или память  :x