roboforum.ru

Технический форум по робототехнике.

Найти вторую координату точки принадлежащей отрезку

Раздел создан специально для людей которым интересна робототехника, но в силу разных причин они не знают с чего начать.
Задавайте ваши вопросы, какими бы простыми они не казались, постоянные посетители форума постараются ответить на них по мере своих сил.
Робот своими руками. Самодельный робот.

Сообщение SSG » 27 авг 2007, 15:24

Не, я спорить не хочу.  :) Просто не понимаю почему тормознутее будет?  :(  Тормознутее будет умножение выполнять? Мне почему-то кажется, что при достаточно большом массиве полином невысокой степени посчитать быстрее будет чем лопатить массив. А по поводу косяков за пределами интервала возражение не принимаю, да они могут быть, но чаще их нет, а вот при использовании массива, прогнозируемые значения функции в точках, не входящих в интервал, низя получить вообще (если, конечно, опять же не прибегнуть к интерполированию).
Вообще эта тема интересна и я бы хотел попросить поделиться табличкой исходных данных. Я бы поэкспериментировал.  8)
Аватара пользователя
SSG
 
Сообщения: 1058
Зарегистрирован: 15 янв 2007, 19:23
Откуда: Беларусь, Барановичи
прог. языки: С для МК, Delphi для ПК

Сообщение Digit » 28 авг 2007, 14:51

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

Сообщение SSG » 28 авг 2007, 15:19

Короче чуть-чуть примитивно потесил в 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)
А вообще прикольная темка - реализация численных методов на контроллере. Тока надо ли это кому?  :)
Последний раз редактировалось SSG 29 авг 2007, 09:34, всего редактировалось 1 раз.
Аватара пользователя
SSG
 
Сообщения: 1058
Зарегистрирован: 15 янв 2007, 19:23
Откуда: Беларусь, Барановичи
прог. языки: С для МК, Delphi для ПК

Сообщение lebaon » 28 авг 2007, 17:59

а нафига нам перебирать весь массив  :shock: ?
мы знаем y и хотим узнать x(y)
x(y)=massiv[y]
вот, тут нам нужно 1 косвенное обращение к памяти и все :twisted:
Аватара пользователя
lebaon
Безбашенный Теоретик
 
Сообщения: 1137
Зарегистрирован: 07 янв 2006, 18:30
Откуда: Подмосковье

Сообщение SSG » 28 авг 2007, 18:33

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

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

Сообщение Digit » 28 авг 2007, 21:21

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


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

2 SSG
Про индексы массива типа float: можно например умножить этот флоат на... на 10, 100 или на 1000 (в зависимости от задачи), и забить на оставшуюся дробную часть - смотря какая точность нужна.
Кстати, ты не написал, сколько у тебя прямой перебор массива идет? :) Полином за 1.4мс, а перебор?
Про прямой перебор: найти можно в разы быстрее. Поищи книжку Д.Кнут в инете на скач - где-то выкладывали - не пожалеешь! :) Там столько изящных методов разбирается!!!  :roll:
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Сообщение SSG » 29 авг 2007, 10:17

Исправился. 1.6 мс.
Книжку поищу, спасибо.  :)
Аватара пользователя
SSG
 
Сообщения: 1058
Зарегистрирован: 15 янв 2007, 19:23
Откуда: Беларусь, Барановичи
прог. языки: С для МК, Delphi для ПК

Сообщение lebaon » 29 авг 2007, 16:15

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

именно это и имеется в виду :twisted:
массив может иметь такие размеры, какие надо, в ущерб точности конечно :wink:  например на 16 значений
y=massiv[x/16] где x - byte
это будет сдвиг+обращение к памяти :twisted:
почему то все привыкли, что в массиве найти значение можно только перебором, а это не так  :wink:
а задача эта сводится к вечному компромиссу скорость или память  :x
Аватара пользователя
lebaon
Безбашенный Теоретик
 
Сообщения: 1137
Зарегистрирован: 07 янв 2006, 18:30
Откуда: Подмосковье

Пред.

Вернуться в Новичкам или основы основ роботостроения.

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 20