Кольцевой буфер FIFO
- Войдите на сайт для отправки комментариев
Сб, 20/05/2017 - 10:52
При использовании кольцевого буфера FIFO, если не хочу переполнять его (при переполнении буду выставлять флаг) из физического размера буфера SIZE два элемента всегда остаются неиспользуемыми? Те максимальная загрузка =(SIZE-2) или я чего-то не додумал?
1.Для именно FIFO указатели делаются на первую занятую клетку и первую свободную, а нет так, как вы написали. Тогда никакой херни не происходит.
2. длину нужно делать только степенью двойки, тогда инкремент/декремент естественным образом максИруестя через AND.
3. если Ваш код требует учета каждого такта, то нужно взять камень побыстрее, сейчас не 80-е годы. Они даже по цене не будут особо различаться ;).
Я чего-то не понимаю или ТС запутался в своем незнании.
struct date { int D1; int D2; }; struct date *start_buffer=NULL; //указатель на начало буфера void setup() { start_buffer = new struct date[10];// создание буфера start_buffer[0].D1 = 5; start_buffer[0].D2 = 6; start_buffer[1].D1 = 5; start_buffer[1].D2 = 6; } void loop() { // put your main code here, to run repeatedly: }Квон, дорогой! Вы - очень неплохой программист-самоучка. За год, который я наблюдаю Вас на форуме, Ваш код стал сильно лучше.
Примите как совет, прошу Вас, пора приступить к системному профильному образованию. Нужно спокойно и планомерно освоить Кнута. Все три тома. И задачки порешать, хотя бы те, что не очевидны.
если все так, как я предполагаю, это пустое ожидание можно прерывать прерываниями и реальная загрузка процессора окажется в несколько раз меньше.
Перейти на быстрый Due ARM пока не получается - ее драйверы творят гемор , после загрузки программы отваливается USB компорт, через который только что загружена программа. Причем, для разных версий IDE и драйвера платы ведет себя по разному. Итого - на некоторых версиях IDE удается скомпилировать и загрузить программу в Due, но она не работает - не могу даже помигать светодиодом. Проблема или с версией IDE или с операц. системой. Может быть есть ошибки в ARM - большой раздел Errata у производителя огорчает. В общем, с Due , о/c и версиями IDE головная боль и с ней буду разбираться отдельно, а пока использую 2560.
По п.1 осмыслю и спрошу позже, если согласитесь ответить.
http://mexalib.com/search/?q=%D0%98%D1%81%D0%BA%D1%83%D1%81%D1%81%D1%82%...
wdrakula. Спасибо. Кнут мне не поможет. Я просто уже приблизился к тому что бы понять свое НЕПОНИМАНИЕ ОПП , а так же языка Си , который повыше С++. Причем не вообще-то в теории ,а в практике. Так что практика и практика, раз книжек по этой теме нет.
С этих
Джефф Элджер - C++ Библиотека программиста
Дейтел Х., Дейтел П - Как программировать на C++
А так же закиньте в закладки это http://document.saraff.ru/ http://cpp.com.ru/kr_cbook/index.html#content http://netlib.narod.ru/library/book0003/toc.htm
Обоим:
1. Неважно, какие "версии" Кнута читать,
2. во времена Кнута еще не было ООП. Это просто алгоритмы и их теория.
3. Кстати сказать, я тоже не люблю ООП. Я старый Сишник, реально не молодой :(. Но иногда ООП сильно нагляднее.
Если поставить указатель для чтения (начало буфера) на первый занятый элемент, а конец на первую свободную, по моим подсчетам максимальная заполненность без переполнения буфера все равно будет не SIZE, а (SIZE-1) ?
подумайте еще раз.. что мешает заполнить его до конца?
До состояния, когда оба указателя равны. В этом случае писать некуда.
Просто проверка на неравенство указателей делается ДО записи.
Перед записью байта делаем проверку, ферштейн зи? Вакаримас ка?
1.Это Вам решать. Видит Б..г, странный вопрос! Как Вы программу пишите, так она и работает, в ней нет "маленьких зеленых человечков".
2. Вы там выше, какую-то ересь про указатель и степень 2 написали.
Я имел ввиду ТОЛЬКО то, приращение указателя кольцевого буфера записыватся математически так:
p = (p + 1) % <длина буфера>;
операция "%" - взятия остатка от деления - долгая, но в случае, когда длина равно степени 2, остаток от деления равен соответствующему к-ву младших разрядов, которые можно получить просто обнулением старших.
Например для <длина буфера> = 1024:
p = (p + 1) & 0x03ff; или p = (p + 1) & 1023;
В откомпилированном коде добавится две инструкции по одному такту... не жалко.
А если брать буфер 256, ни and ни указателей не нужно, адресация байтовым индексом, сравнения и инкримент самые быстрые. Если скорость так важна как Вы о ней думаете - байт лучший.
Практически имеет смысл заполнять его до конца?
В таком виде вопрос лишен смысла.
Для чего заполнять до конца (с какой целью)?
Да уже в общем и не для чего. См. http://arduino.ru/forum/programmirovanie/inline-eto-prinuditelnyi-modifikator-ili-neobyazatelnaya-rekomendatsiya-kompi#comment-284443 Обычная история, попадает челу в руки ардуино - он начинает творит. Творит чего попало, в основном херню. Не нужен ему буфер. Никакой, циклический - особенно не нужен.
Logik, вопрос не в том, для чего нужен кольцевой буфер, а в том, для чего его запонять до конца.
Этот вопрос не имеет смысла без контекста задачи. А в контексте этой задачи буфер вобще не нужен.
Чисто абстрактно - да может требоватся полное заполнение. Например в протоколе первый блок данных 256 байт, и буфер 256. Если не заполнять полностю, то либо дробить блок либо увеличивать буфер, причем сразу в 2 раза. Оба пути - плохо. Проще обеспечить полное заполнение.
wdrakula. Спасибо. Кнут мне не поможет. Я просто уже приблизился к тому что бы понять свое НЕПОНИМАНИЕ ОПП , а так же языка Си , который повыше С++. Причем не вообще-то в теории ,а в практике. Так что практика и практика, раз книжек по этой теме нет.
В таком разе посоветую найти и почитать Пратт "языки программирования разработка и реализация" очень помогает понять "С" и многие иные языки, что называется "изнутри". Ещё можно почитать Ахо, Ульман "Алгоритмы и Структуры данных" или как-то наоборот, уж не помню.. Неплохо почитать книжки Гленфорда Майерса, Баррона, Касьянова и мн. др. Но, это все на сейчас "древности" и описываемые языки уже по большей части исчезли из жизни, разве что "С" остался.
Хотя, Касьянов (оптимизационные преобразования программ) хоть и несколько заумен, но вчитавшись сильно оцените прояснение простой истины: все подходы красивого кода используют те или иные способы оптимизации, что называется "в пальцах"... Очень хорошо у предпоследнего описаны рекурсивные алгоритмы .. ну, в общем по мне - это та классика, которая никогда не бывает бесполезной.
Arhat109-2, похоже вы меня не поняли. Что такое математика и ход ее развития. Обычно считается что математика это появление знаков 1-9,0. И все . Дальше идет опрерирование этими знаками. Но скорее всего чем больше развивается математика, чем больше проблем она решает, там больше математика обогащается знаками математической нотации (+,-,х ,/ = > < ~ ну и так далее) . Разумеется многие знаки проникли в программирование. Ведь Керниган и Ритчи не придумали язык программирования. Они банально предложили сбалансированую систему программой нотации, которая помогла компактно записать объемные коды на ассемблере. Эта же система оказалась расширяемой в разные стороны. Страуструп предложил сделать еще надстройку, которая еще компактнее записывать код и кусками заимствовать в других программах. Но появилось ООП. Все знают что это хорошо, но где нотация под эту систему. Нет ее. Похоже ООП , как феншуй- все надо делать по феньшую, но у каждого свое представление о феншуе. А алгоритмы - так они больше как математические задачи. Нужны научить думать головой, но на практике малоприменимы, или применимы только как общее направление.
Знаете, при попытках решения задач, одна из типовых ошибок - черезмерное ожидание сложности. Так у Вас и с ООП, оно всего только - наследование+инкапсуляция+полиморфиз. Но вмести они позволяют разрабу думать по другому. Вы ж когда на Си пишите не думаете о том как оно в машинном коде выйдет (ну мало кто о таком думает, есть конешно люди, но мало). И уж точно никто не думает как происходит пересылка данных между регистрами МК, все знают, происходит, есть какие-то шины и стробы там внутри, чтото гдето переключается,,, ну и хрен с ним. А насамом жеж деле там меняются електромагнитные поля, электроны движутся вдали. Тоже нафиг. Этот мой бред к чему был - у того же процесса есть разные уровни описания и абстракции. И ООП - только один из них, требующий еще меньше вдаватся в детали о потоках електронов чем Си. А на самом деле и электрони и машкод и синтаксис действительно тот же.
Может так оно Вам понятней будет. Не ждите от ООП многого. В каком то смысле он - электроотвертка. Делает то же что и обычная, зачастую хуже, но быстрей и меньше усилий требует.
При написании программы можно следовать как минимум двумя путями: методом муравья и методом бога. Методом муравья - пишешь по кусочку и потом смотришь куда кривая выведет. Методом бога -начало проектируешь все на бумаге , раскидывешь на куски , куски поменьше и в конце приступаешь к программе. Второй метод медленее, так человек не бог все предусмотреть не может.
Все же почему лучше второй метод . Для меня программа не то что запустилось и можно дальше забить на нее и заказчика, а так же кривая работа этой программы. Жизнь все же не сказка. Программа после запуска должна "жить дальше", проходить различные мелкие средние и крупные изменения и наконец , если повится еще один заказчик, то после некоторого измения втюхать и ему эту программу. Вот поэтому и надо пытаться программировать в режиме бога, так как менять программу приходится все же после взгляда на нее сверху. Вот по этой причине ООП и лучше. Но это если у вас очень конкретные представления об конкретной ООП и ее структуре, включая названия классов и методов входящих в нее.
Чисто абстрактно - да может требоватся полное заполнение. Например в протоколе первый блок данных 256 байт, и буфер 256. Если не заполнять полностю, то либо дробить блок либо увеличивать буфер, причем сразу в 2 раза. Оба пути - плохо. Проще обеспечить полное заполнение.
Вы уверены, что написали сейчас именно про кольцевой буфер?
Если Вы не хотите заводить счетчик количества заполненных мест в буфере, то Вы не сможете использовать все места, чтобы полностью заполненный буфер отличался от пустого.
Если Вы готовы использовать счетчик и потерять немного в быстродействии, то Вы можете использовать буфер полностью.
Если Вы хотите максимального быстродействия, то надо использовать два индекса, никаких счетчиков и уменьшение указателей при продвижении (либо увеличение при размере буфера 256)- за счет уменьшения емкости буфера на единицу хранения.
Если Вы не хотите заводить счетчик количества заполненных мест в буфере, то Вы не сможете использовать все места, чтобы полностью заполненный буфер отличался от пустого.
А если смогу? ;)
Но суть проблемы верно замечена. У полностью полного и у полностю пустого указатели (или индексы) указывают на один и тот же элемент. Потому отличит просто так не получится. Но достаточно завести флажок который устанавливается если после добавления данных указатель записи догнал указатель чтения и сравнялся с ним и сбрасывается после любой выборки данных. Все, проблема решена этот флажок позволит отличить пустой от полного. Очевидно его надо проверять при каждой попытке записи. Издержки мизерные. И даже наоборот, может даже ускорится работа т.к. перед добавлением данных будет только флажок проверятся, а не указатели сравниватся.
Перед каждой записью все равно нужно проверять указатели не неравенство. Какой смысл выставлять флажок, если такая проверка и есть флажок, а больше он никому не нужен?
Столько штампов в одном абзаце встречаю только у хохлосрачников .. как Вам это удалось?
1. Видиом я (и многие мои коллеги) - явно "не все", ибо знают насколько ООП - плохо во всех смыслах.
2.Алгоритмы не равно "метаематические задачи". Почто так - задачка на дом.
3. На практике Кнут - это сборище шикарных ПРАКТИЧЕСКИХ алгоритмов. Также как и алгоритмы разных "ахо-карасиков".. они потому и зовутся "классикой", что сделать иначе можно только через *опу. №все украдено до вас" (как правило программистами нашего и старше поколений)
4.феншуи придуманы для вас, чтобы вам не засорять головешки разного рода обоснованиями, выводами и прочим опытом старших товарищей, которые своих собак уже съели.
Вот, к сожалению .. как раз непонимание почто вам рекомендуют то да это и приводит к тому, что у каждой программы остается только ДВА состояния:
первое - "Вау, как круто! Щас мы тут такую шикарную фигню забабахаем!"
и второе: -"Какой дебил это писал?!?"
Не в обиду, а так к слову.. :)
Arhat109-2. Я вас услышал. Забабахать программу аналогичную моим вам не удастся, код я не прячу, по многим причинам 1- зачем вам это надо, у вас и так есть много задач для решения, 2- зачем писать по другому если и так замечательно выходит, 3- вы не понимаете полностью причины почему я так пишу, а значит видите много "лишнего и ненужного", 4- как ни странно код с моей точки не оптимален, ему есть куда развиваться. Как в ширину - надо еще много написать кирпичиков-классов. Как в глубину - написать полноценую ОС или программный движок. Вот их я пока не наблюдаю в среде Ардуино. В крайнем случае в открытом коде. Или у вас он завалялся??
Как хотите. Вашего п.1 - действительно "за глаза" достаточно. Я лишь посоветовал "что почитать" из классики и для лучшего понимания, за которые Вы вроде сетовали.
Перед каждой записью все равно нужно проверять указатели не неравенство. Какой смысл выставлять флажок, если такая проверка и есть флажок, а больше он никому не нужен?
Значит Вы ниче так и не поняли. Нет перед записю проверять указатели на неравенство не нужно. Только флаг проверять. А он установлен или сброшен при предыдущей операции. Там делался инкремент, указатели проверялись и в зависимости от результата флаг устанавливался или нет. Если бы Вы внимательно читали то наверно догадались бы что у флажка этого очевидное название - чтото типа "Буфер заполнен целиком, места нет". Зачем еще дополнительные проверки?