Модераторы: Snowy, MetalFan, bems, Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Как сделать кольцевой буфер? 
:(
    Опции темы
ivan219
  Дата 10.5.2011, 16:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1121
Регистрация: 19.11.2005
Где: Планета земля

Репутация: 5
Всего: 12
Как сделать кольцевой буфер?

На ум приходить только это:

Код

var
  A: Array[0..2] of Integer;
for I := 0 to n do
 A[I mod 3] := I;


Может есть другие варианты?


--------------------
Мой первый сайт и моя первая программа!!!!!
PM MAIL ICQ   Вверх
1000000dollars
Дата 10.5.2011, 16:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 231
Регистрация: 6.10.2007

Репутация: нет
Всего: 8
Есть. Например кольцевой список. Всё зависит от специфики задачи.
PM MAIL   Вверх
ivan219
Дата 10.5.2011, 22:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1121
Регистрация: 19.11.2005
Где: Планета земля

Репутация: 5
Всего: 12
Цитата(1000000dollars @  10.5.2011,  16:47 Найти цитируемый пост)
Есть. Например кольцевой список. Всё зависит от специфики задачи.


Специфика в том, что бы заполнять массив числами по кругу. Т.е. дошли мы до последней ячейки массива, следующие значение у же запишем в начало массива.
И так как это будет происходить в цикле и постоянно то операция
Код

I mod 3

мне не нравится. 
Возможно, есть менее ресурсоёмкий алгоритм.


--------------------
Мой первый сайт и моя первая программа!!!!!
PM MAIL ICQ   Вверх
northener
Дата 11.5.2011, 01:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1361
Регистрация: 2.9.2010

Репутация: 12
Всего: 20
Цитата(ivan219 @  10.5.2011,  22:19 Найти цитируемый пост)
И так как это будет происходить в цикле и постоянно то операция
Выделить всёкод Pascal/Delphi
1:
    
I mod 3

мне не нравится. 
Возможно, есть менее ресурсоёмкий алгоритм.


"Навскидку". 
Не проверяя все возможные реализации "кольцевого буфера" не смог придумать ничего лучше операции mod.

Блин! Ну что может быть менее ресурсоёмкой операцией, чем ассемблерная инструкция MOD?


--------------------
Но только лошади летают вдохновенно.
Иначе лошади разбились бы мгновенно!
PM MAIL   Вверх
cemick
Дата 11.5.2011, 09:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 416
Регистрация: 6.7.2006
Где: Санкт-Петербург

Репутация: нет
Всего: 6
Цитата(northener @  11.5.2011,  01:56 Найти цитируемый пост)
"Навскидку". 
Не проверяя все возможные реализации "кольцевого буфера" не смог придумать ничего лучше операции mod.

Блин! Ну что может быть менее ресурсоёмкой операцией, чем ассемблерная инструкция MOD? 


Mod это как минимум деление и далеко не факт что на большом количестве N это будет быстрее чем inc(i); if i = arrayLength then  i := 0;
PM MAIL WWW   Вверх
1000000dollars
Дата 11.5.2011, 09:29 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 231
Регистрация: 6.10.2007

Репутация: нет
Всего: 8
Цитата(ivan219 @  10.5.2011,  22:19 Найти цитируемый пост)
Специфика в том, что бы заполнять массив числами по кругу. Т.е. дошли мы до последней ячейки массива, следующие значение у же запишем в начало массива.И так как это будет происходить в цикле и постоянно то операциякод Pascal/Delphi1:I mod 3highlightSyntax('delphi_1YzA1Y','delphi');мне не нравится. Возможно, есть менее ресурсоёмкий алгоритм.


Ну если задача полностью описывается приведённым в первом посте кодом, то можно записывать только последние числа последовательности. 

Код

var
  A: Array[0..2] of Integer;
  nat,at : integer;

at = n mod 3; // хвост, который надо писать с начала массива
for I := 0 to at do
 A[I] := n-3+I;

at = 3- at; // остаток, который надо дописывать
nat = n div 3; // с какого числа его дописывать
for I := at to 3 do
 A[I] := nat-3+I;


Этот код очень плохой, но идею иллюстрирует. При больших n и малых размерах массива должен работать чертовски быстро. Ну и всего один mod и один div.
PM MAIL   Вверх
ivan219
Дата 11.5.2011, 11:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1121
Регистрация: 19.11.2005
Где: Планета земля

Репутация: 5
Всего: 12
Цитата(1000000dollars @  11.5.2011,  09:29 Найти цитируемый пост)
Ну если задача полностью описывается приведённым в первом посте кодом, то можно записывать только последние числа последовательности. 

Нет, код был приведён для примера. Массив является буфером промежуточных вычислений.


--------------------
Мой первый сайт и моя первая программа!!!!!
PM MAIL ICQ   Вверх
1000000dollars
Дата 11.5.2011, 15:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 231
Регистрация: 6.10.2007

Репутация: нет
Всего: 8
Цитата(ivan219 @  11.5.2011,  11:31 Найти цитируемый пост)
Массив является буфером промежуточных вычислений.


Тогда не думаю, что будут более хорошие решения с циклическим буфером, видимо придётся довольствоваться mod на каждой итерации, либо смотреть другие структуры данных.
PM MAIL   Вверх
ivan219
Дата 11.5.2011, 21:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1121
Регистрация: 19.11.2005
Где: Планета земля

Репутация: 5
Всего: 12
Реализовал код с 3 переменными шустрее получилось. Но идея шустрого кольцевого буфера ещё актуальна. Так как иногда бывает и с 1000 ячеек нужно работать и да же больше.


--------------------
Мой первый сайт и моя первая программа!!!!!
PM MAIL ICQ   Вверх
northener
Дата 12.5.2011, 01:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1361
Регистрация: 2.9.2010

Репутация: 12
Всего: 20
Цитата(cemick @  11.5.2011,  09:16 Найти цитируемый пост)
Mod это как минимум деление и далеко не факт что на большом количестве N это будет быстрее чем inc(i); if i = arrayLength then  i := 0; 

А проверить?
MOD - это не столько "деление" сколько ассемблерная инструкция. Так же как и INC.

Это сообщение отредактировал(а) northener - 12.5.2011, 01:56


--------------------
Но только лошади летают вдохновенно.
Иначе лошади разбились бы мгновенно!
PM MAIL   Вверх
1000000dollars
Дата 12.5.2011, 08:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 231
Регистрация: 6.10.2007

Репутация: нет
Всего: 8
Не знаю насколько это применимо к решаемой задаче, но для одной из моих задач нужно было хитро обработать поток данных. Специфика была такова, что было надо "помнить" последние 8 килобайт обработанного потока. Я делал примерно так:

Код

WP : Cardinal; // индекс для записи
Buffer : Array of byte; // буфер

SetLength (Buffer, $A00000); // 10 мегабайт намного больше 8 килобайт
InitBuffer(Buffer,$2000); // инициализирую первые 8 килобайт буфера
WP := $2000; // с этой позиции начнётся запись

while поток не закончился do
begin
    while поток не закончился and (WP<$A00000) do
        begin
            // тут вся обработка и запись в буфер по индексу WP и инкремент WP на количество записанных байт
            // все обращения к последним данным через Buffer[WP-сколько_то]
        end;
    MoveToBegin (Buffer, $2000); // перемещаю последние 8 килобайт в начало буфера
    WP := $2000; // с этой позиции продолжится запись.
end;
PM MAIL   Вверх
cemick
Дата 12.5.2011, 09:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 416
Регистрация: 6.7.2006
Где: Санкт-Петербург

Репутация: нет
Всего: 6
Цитата(northener @  12.5.2011,  01:11 Найти цитируемый пост)
MOD - это не столько "деление" сколько ассемблерная инструкция. Так же как и INC.


Думайте пожалуйста, прежде чем такое говорить.

Цитата(northener @  12.5.2011,  01:11 Найти цитируемый пост)
А проверить?

А проверить не слабо:
Код

program Project1;


{$APPTYPE CONSOLE}

uses
  SysUtils, System, Windows;
  const arrayLength = 1000000;
        max = 1000000000;
  var
    A: array[0..arrayLength-1]  of integer;
    i: integer;
    n: integer;

    t1,t2: cardinal;
begin
    t1 := GetTickCount;
    for i := 0 to max  do
    begin
      A[i mod arrayLength] := i;
    end;
    t2 := GetTickCount - t1;
    Writeln(t2);


    n := 0;
    t1 := GetTickCount;
    for i := 0 to max  do
    begin
      A[n] := i;

      inc(n);
      if n = arrayLength then
        n := 0;
    end;
    t2 := GetTickCount - t1;
    Writeln(t2);
    Readln;


end.




Первый вариант в среднем 3600-4100
второй 1500-2000

Т.е. примерно как минимум в два раза быстрее.

Это сообщение отредактировал(а) cemick - 12.5.2011, 09:19
PM MAIL WWW   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Delphi: Для новичков"
SnowyMetalFan
bemsPoseidon
Rrader

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Литературу по Дельфи обсуждаем здесь
  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь
  • 90% ответов на свои вопросы можно найти в DRKB (Delphi Russian Knowledge Base) - крупнейшем в рунете сборнике материалов по Дельфи

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Snowy, MetalFan, bems, Poseidon, Rrader.
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Delphi: Для новичков | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1029 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.