Делфи. Вопросы возникающие в ходе обучения

[PAV]

Если именно эта обработка занимает хоть сколько-нибудь ощутимое время, которое можно измерить, то можно попробовать избавиться от оператора if и посмотреть, повлияет ли это на скорость.

Сколько ядер на процессоре? Сколько собственно времени занимает обработка?

Конечно же, если эти строки обрабатываются параллельно, то процедуру можно распараллелить на несколько потоков, но это отдельная техника программирования.

Добавлено спустя 2 минуты 52 секунды:

Каждый байт обрабатывается отдельно - получается 200 тысяч элементов. Возможно, есть за что бороться.

[Student2007]

2 ядра. По времени уходит секунд 10, проц и так загружен не слабо.. Но 10 секунд вместе с другими вычислениями...
***
многопоточность пока не осилил

[PAV]

И Вы абсолютно уверены, что 10 секунд происходит именно та процедура, которую Вы здесь описывали?

Если да, тогда точно следует попробовать ускорить. Почитайте Уоррена, там буквально в первой главе что-то очень похожее есть. Пишите, обсудим. Мне самому очень интересно, дадут ли методы ускорение. Правда, Дельфи я не владею. Там есть весь набор побитовых логических операций?

[ewert]

В данном случае Дельфи -- это Паскаль, там есть всё. А вот за счёт чего возможно ускорение, притом "существенное" -- категорически непонятно. По сравнению с просто арифметической операцией условный оператор дополнительно привносит в среднем всего-навсего полторы операции перехода. Если упомянутое трюкачество требует хотя бы трёх операций (а меньше вряд ли), то оно даст безусловный проигрыш.

[PAV]

Это связано с архитектурой процессора. Последовательность арифметических действий без условных переходов автоматически парралелится и выполняется быстро. Условные переходы мешают процессору проводить этот процесс. Это точно. Я не являюсь специалистом по ускорению, но со мной работают люди, занимающиеся этим профессионально. Устранение операторов if во внутренних циклах, даже если это привносит несколько дополнительных арифметических операций - это один из характерный их приемов.

Добавлено спустя 12 минут 19 секунд:

Вот нашел ссылку:

Техника оптимизации программ (фрагмент книги)

Цитата:

...свести к минимуму ветвления...

[Student2007]

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

for i:=1 to k do 
    if a[i]=b[i] 
        then c[i]:=a[i] 
        else c[i]:=0;

я смогу сказать завтра.. Сейчас тогда буду книгу читать.
ewert
если можно будет снизить загруженность процессора, даже если результат будет с большей задержкой, меня это вполне устраивает.

Добавлено спустя 3 минуты 8 секунд:

PAV
и еще свести к минимуму циклы:)

Добавлено спустя 3 минуты 47 секунд:

Джон Бентли - Жемчужины программирования. Всю книгк не осилил еще, но тоже много внимания уделяется оптимизации

Добавлено спустя 2 минуты 47 секунд:

просмотрел ссылку.. интересный материал

Добавлено спустя 17 минут 18 секунд:

дополню... Меня больше чем устроит, если не надо заполнять массив c, а результат вычислений запишется или в массив а или б. Тоесть данные в этих массивах актуальны только до обработки.

[PAV]

Попробуйте для начала сделать так.

Заведите заранее массив из 256 элементов (обозначим его x), в нулевой элемент запишите число 255 (0xFF), а во все остальные элементы - нули.

Тогда операция без ветвления будет выглядеть так (результат сохраняем в массив a):

a[i]:=a[i] and x[a[i] xor b[i]]

Тут же для ускорения советую завести два указателя, которые будут указывать на текущие элементы массивов a и b, и на каждой итерации цикла сдвигать их на одну позицию. И внутри вместо a[i] и b[i] обращаться к элементам, на которые указывают эти указатели.

Но вообще-то, конечно же, надо проверить, какая часть всей программы самая долгая. Возможно, ускорять надо не этот кусок, а совсем другой.

[Student2007]

PAV
спасибо за помощь, отпишусь по теме чуть позже, надо кое-какие другие задачи решить (а то несоответствие типов у меня )..
в частности стоит задача о сравнении массива байтов с другим массивом, без того, что бы делать цикл.. =).. Первый серьезный проект, а проблем ужс.... У меня этих циклов в программе слишком много получается..

[ewert]

Student2007 в сообщении #205640 писал(а):

в частности стоит задача о сравнении массива байтов с другим массивом, без того, что бы делать цикл.. =)

Не стоит, а висит. Без цикла тут никак. Ну разве что массив представляет собой строку (для сравнения строк в процессоре есть специальные команды, которые реализуются, конечно, циклами, но -- зашитыми внутрь самой команды).

[Student2007]

ewert
массив сформирован как динамический, элементами которого являются массивы байтов:

type
  ProbBuf=array[1..200] of Byte;
var
  MainBufer:array of ProbBuf;

Добавлено спустя 2 минуты 59 секунд:

сортирую его следующей конструкцией:

  buf:='';
  for j:=200 downto 1 do begin
    flag:=TRUE;
  while FLAG do begin
    flag:=FALSE;
    for i:=0 to FilesCount-2 do begin
      if MainBufer[i,j]>MainBufer[i+1,j] then begin
        SortMbuf:=MainBufer[i];
        MainBufer[i]:=MainBufer[i+1];
        MainBufer[i+1]:=SortMbuf;
        Flag:=TRUE;
      end;
    end;
  end;
  end;

тоесть начиная от последнего байта к первому, пузырьковым методом.

Добавлено спустя 1 минуту 25 секунд:

по поводу лишних begin - end, знаю, что можно сократить при одном операторе в цикле - дурацкая привычка писать всё полностью..

[ewert]

Дело в том, что я не знаю Дельфи. И не знаю, в частности, есть ли там длинные строки (длиннее 255 байт); смутно припоминаю, что есть. Но что совершенно точно -- что в Паскале есть операции сравнения строк (коротких, до 255 байт). И уж во всяком случае операция сравнения "=" наверняка транслируется в ту самую команду. Так что внутренний тип лучше определить как строковый.

Добавлено спустя 3 минуты 46 секунд:

Student2007 в сообщении #205678 писал(а):

, пузырьковым методом.

А почему пузырьковым-то (раз уж важна эффективность)? Он ведь требует порядка $n^2$ операций. В то время как есть метод со скоростью порядка $n\,\log n$. Я его, естественно, не помню (и не помню даже названия), но он вполне стандартен и общепринят.

[Student2007]

ewert
тема в том, что я массив заполняю байтами с бинарных файлов, поэтому работать приходится не как с текстом..
В делфи есть строки больше 255 байт, но они рассматриваются уже как динамический массив...

вообще я знаю только 3 метода сортировки:
прямого перебора,
пузырьковый,
вставкой.
***
есть еще какой-то рекурсивный метод, но я в рекурсиях быстро путаюсь, и что происходит внутри рекурсии для меня не очевидно.

[ewert]

Student2007 в сообщении #205688 писал(а):

тема в том, что я массив заполняю байтами с бинарных файлов, поэтому работать приходится не как с текстом..

Да, тут есть некоторая проблема, но она лишь в том, что начальный байт строки -- это счётчик длины. Просто устанавливайте его в своих файлах принудительно в 200, потери памяти будут ничтожными.

Student2007 в сообщении #205688 писал(а):

Более быстрый метод случайно называется не сортировка вставкой?

Совершенно не помню. Но идея там состоит в том, что массив рекурсивно делится пополам (почти пополам, естественно) и каждая половинка сортируется отдельно, а потом всё склеивается. Где-то так.

[Student2007]

ewert
подкорректировал предыдущий пост (не увидел вовремя ваш ответ..)... вставка тоже n квадрат...
Ваш более быстрый метод действительно рекурсивный, сейчас открыл книгу Жемчужины программирования, там этот способо подробно описан..

Добавлено спустя 2 минуты 31 секунду:

ewert писал(а):

Да, тут есть некоторая проблема, но она лишь в том, что начальный байт строки -- это счётчик длины. Просто устанавливайте его в своих файлах принудительно в 200, потери памяти будут ничтожными.

исходный файлы не хотелось бы подвергать изменениям

[ewert]

Student2007 в сообщении #205693 писал(а):

исходный файлы не хотелось бы подвергать изменениям

Ну тогда просто при вводе-выводе буферизуйте файлы. И переносите записи в/из буфера командой Move, а байт счётчика вводите/игнорируйте принудительно. Это недорого обойдётся, и сама эта команда тоже транслируется в одну машинную (т.е. потерь по сравнению с прямым потоковым чтением должно быть немного).