Быстрый Swap,

← →
main © (2008-11-15 20:02) [0]

Нужна максимально быстрая процедура, которая меняет местами содержимое блоков памяти. Что-то вроде:

procedure QuickSwap( Source,Dest :pointer; count :integer );
begin
???
end;

Почему такой процедуры нет среди стандартных? О_о

← →
tesseract © (2008-11-15 20:17) [1]

move. Стандартнее не бывает. Читайте документацию.

← →
main © (2008-11-15 20:27) [2]

> tesseract © (15.11.08 20:17) [1]
> move. Стандартнее не бывает. Читайте документацию.

move - копирует, а мне нужно именно менять местами.

Я немного не правильно написал:

procedure QuickSwap( PData1,PData2 :pointer; count :integer );
begin
???
end;

← →
main © (2008-11-15 20:32) [3]

Погуглил, ничего стоящего не нашел.
В принципе я и сам могу что-нибудь намутить, только вот стоит ли изобретать велосипед,
это ведь стандартная рутина, наверняка уже есть готовые решения.
С удовольствием бы скопипастил! :)
Интересно, почему такой процедуры нет среди стандартных? О_о

← →
tesseract © (2008-11-15 21:18) [4]

> move - копирует, а мне нужно именно менять местами.

2 move. Случай сильно прикручен.

← →
Anatoly Podgoretsky © (2008-11-15 21:58) [5]

> main (15.11.2008 20:27:02) [2]

Обмен сводится к трем move.
Видимо данная функция мало кому нужна, поэтому и не включили.
Правда иногда Борланд шел навстречу подобным заявкам, например когда делал IncDay

← →
main © (2008-11-15 22:37) [6]

> Anatoly Podgoretsky © (15.11.08 21:58) [5]
> > main (15.11.2008 20:27:02) [2]Обмен сводится к трем
> move.Видимо данная функция мало кому нужна, поэтому и не
> включили.Правда иногда Борланд шел навстречу подобным заявкам,
> например когда делал IncDay

А если размер данных большой, и их размер заранее не известен,
надо ведь еще под временный буфер память выделить.
Это как-нибудь можно на стеке динамически выделять?

А может небольшими порциями менять быстрее?

П.С.
Я вобщем-то для своего частного случая объявил в начале процедуры:
var temp :array[0..1023] of byte;
Т.к. у меня известно что count <= 1024

Но хотелось бы универсальное решение ... :)

← →
main © (2008-11-15 22:43) [7]

Подчеркну, мне нужна не какая-нибудь, а именно быстрая, желательно самая быстрая. :)
А просто какую-нибудь я и сам сейчас за минуту напишу, и даже много разных.

← →
Anatoly Podgoretsky © (2008-11-15 23:04) [8]

> main (15.11.2008 22:37:06) [6]

Зачем на стеке, стек маленький, зато куча большая.
Менять можно небольшими порциями, но скороть будет значительно меньше.
Это тебе домашнее задание протестировать это.
Для случая 1024 без разницы где объявлять, это не размер.
Кроме того при таком размере беспокоиться о скорости, это экономия на спичках.

← →
Johnmen © (2008-11-15 23:21) [9]

> main © (15.11.08 20:02)

Это эквивалентно поменянию значениями указателей
:)))

← →
palva © (2008-11-15 23:28) [10]

При обмене не надо писать в промежуточную память. Нужно вести обмен в цикле по четыре байта, используя регистры. Ну то есть память по первому пойнтеру пишем в EAX, по второму пойнтеру - в EDX, потом возвращаем данные в память, но поменяв местами. Затем увеличиваем пойнтеры на 4. Последнюю порцию, которая может не равняться четырем, обмениваем побайтно. Естественно, что писать на ассемблере. Может быть, можно добиться хорошего кода и на делфи, но этого не так легко добиться - больше времени убьете.

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

← →
main © (2008-11-16 00:03) [11]

Интересно почему переместили в "начинающим"?
Разве это так уж элементарно?

...
> Кроме того при таком размере беспокоиться о скорости, это
> экономия на спичках.

А если нужно очень много раз применить,
например такая стандартная задача:
Есть ОЧЕНЬ большой массив record"ов.
Вот нужно дапустим его определенным образом отсортировать.
И размер одного record"а допустим НЕ маленький.
И все это в динамической игре и в реальном времени, да чтоб не тормозило и было как минимум 30 кадров в секунду, и это только малая часть всех расчетов ...

И вобщем-то 3 вызова move не желательно, т.е. надо бы без move.

Там где это можно я тусую указатели.
Но иногда возникает необходимость тусовать именно данные.
...

Ну нет, так нет, значит самому придется писать. :(

← →
Германн © (2008-11-16 00:03) [12]

> Johnmen © (15.11.08 23:21) [9]
>
>

Опередил :)

← →
main © (2008-11-16 00:10) [13]

> palva © (15.11.08 23:28) [10]

Я уже пробывал такой вариант,
и пробывал вариант с регистрами сопроцессора ( по 8 байт ).
Разницы вроде нет.
А с move вроде даже чуть быстрее ( но тест был так - приблизительный ).

← →
Германн © (2008-11-16 00:12) [14]

> Есть ОЧЕНЬ большой массив record"ов.
> Вот нужно дапустим его определенным образом отсортировать.
>
> И размер одного record"а допустим НЕ маленький.

Вот и мы с Johnmen © о том же.

← →
DVM © (2008-11-16 00:17) [15]

> И все это в динамической игре и в реальном времени, да чтоб
> не тормозило и было как минимум 30 кадров в секунду, и это
> только малая часть всех расчетов ...
>
> И вобщем-то 3 вызова move не желательно, т.е. надо бы без
> move.
>

многие люди недооценивают производительность современных компьютеров и скорость работы MOVE.

← →
Johnmen © (2008-11-16 00:22) [16]

> Германн © (16.11.08 00:12) [14]

Есть люди, которые хотят заблуждаться. И кто мешает им в этом - тот козел...:)
Как мы с тобой...:)

← →
DVM © (2008-11-16 00:22) [17]

Да, еще, не надо гонять туда-сюда сами данные, чтобы их отсортировать, гоняйте индексы.

← →
main © (2008-11-16 00:30) [18]

> Johnmen © (15.11.08 23:21) [9]
>
> > main © (15.11.08 20:02)
>
> Это эквивалентно поменянию значениями указателей
> :)))

Если бы там было было ( var PData1,PData2 :pointer; count :integer ),
то еще можно было бы подумать что "эквивалентно поменянию значениями указателей" ...

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

← →
Anatoly Podgoretsky © (2008-11-16 00:35) [19]

Совет от Кнута: вместо данных сортируй указатели.

← →
main © (2008-11-16 00:36) [20]

> DVM © (16.11.08 00:22) [17]
> Да, еще, не надо гонять туда-сюда сами данные, чтобы их
> отсортировать, гоняйте индексы.

Я уж написал, что где можно тусую только указатели.
И да, где можно, тусую индексы.
Но иногда вот требуется именно данные обменять ( очень много и разных данных ). Функция должна быть максимум критична ко времени.

← →
main © (2008-11-16 00:42) [21]

> Johnmen © (15.11.08 23:21) [9]
>
> > main © (15.11.08 20:02)
>
> Это эквивалентно поменянию значениями указателей
> :)))

> Johnmen © (16.11.08 00:22) [16]
>
> > Германн © (16.11.08 00:12) [14]
>
> Есть люди, которые хотят заблуждаться. И кто мешает им в
> этом - тот козел...:)
> Как мы с тобой...:)

Козел тут скорее всего я. :) А вот заблуждаетись скорее всего "наоборот".
Интересно, как это вы обменяете значения указателей если функция объявлена как в 0 посте.

← →
Германн © (2008-11-16 00:42) [22]

> Johnmen © (16.11.08 00:22) [16]
>
>
> > Германн © (16.11.08 00:12) [14]
>
> Есть люди, которые хотят заблуждаться. И кто мешает им в
> этом - тот козел...:)
> Как мы с тобой...:)
>

Теперь мы не одиноки!

> Anatoly Podgoretsky © (16.11.08 00:35) [19]
>
> Совет от Кнута: вместо данных сортируй указатели.
>

Не завидую тому кто посмеет назвать АП козлом! :)
Кнут, конечно, сам не сможет вмешаться, но тут найдётся много тех, кто не потерпит такого!

← →
Johnmen © (2008-11-16 00:43) [23]

> main © (16.11.08 00:36) [20]
> Но иногда вот требуется именно данные обменять

Поверь старому козлу, это самообман...

← →
Германн © (2008-11-16 00:47) [24]

> Интересно, как это вы обменяете значения указателей если
> функция объявлена как в 0 посте.
>

А эту функцию ты сам придумал? Или взял откуда?

← →
main © (2008-11-16 00:56) [25]

> Поверь старому козлу, это самообман...

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

Я их и не меняю эти данные....
... но ... редко но бывает что нужно именно данные обменять ( ну бывает такое ).

:)))

← →
Германн © (2008-11-16 01:03) [26]

> ... но ... редко но бывает что нужно именно данные обменять
> ( ну бывает такое ).

Тогда проясни "твою конкретную задачу". Словосочетания типа "редко но бывает что нужно" не способствуют получению наилучшего ответа-решения.

← →
main © (2008-11-16 01:16) [27]

> Тогда проясни "твою конкретную задачу". Словосочетания типа
> "редко но бывает что нужно" не способствуют получению наилучшего
> ответа-решения.

Ну вот допустим реальный и понятный пример, загрузил картинку ( 2024х2024 ), нужно ее перевернуть - верх/низ. Построчно меняю данные, размер строки 2024 * 4 байта, и так 1024 обмена.

← →
Германн © (2008-11-16 01:25) [28]

> main © (16.11.08 01:16) [27]
>
>
> > Тогда проясни "твою конкретную задачу". Словосочетания
> типа
> > "редко но бывает что нужно" не способствуют получению
> наилучшего
> > ответа-решения.
>
>
> Ну вот допустим реальный и понятный пример, загрузил картинку
> ( 2024х2024 ), нужно ее перевернуть - верх/низ. Построчно
> меняю данные, размер строки 2024 * 4 байта, и так 1024 обмена.
>

И как это совместить с "Есть ОЧЕНЬ большой массив record"ов.
Вот нужно дапустим его определенным образом отсортировать."?

Опять партизаны, блин!

> main © (16.11.08 01:16) [27]

Этот пример не есть пример обмена, то бишь свопирования, памяти. Это, можно сказать, классический пример свопирования указателей...:)
Причем, я подозреваю, что белкин таки двигает области! Но на то он и белкин, чтобы вести себя разнузданно...:)

Я вот думаю, а мне это нужно - оправдываться тут.
Спасибо конечно что отвечаете, но простите, я вовсе и не просил советов, нужна мне эта функция или нет.
А просил я совет как сделать ее быстрее.

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

> Германн © (16.11.08 01:03) [26]
>
> > ... но ... редко но бывает что нужно именно данные обменять
>
> > ( ну бывает такое ).
>
> Тогда проясни "твою конкретную задачу". Словосочетания типа
> "редко но бывает что нужно" не способствуют получению наилучшего
> ответа-решения.

Не понимаю я. Вроде ясно написал, отсортировать по определенным приоритетам массив рекордов. Что, это разве не "конкретная задача"?

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

Всё-таки давай конкретное условие задачи с типом записей и их примерным количеством, тогда посмотрим, как можно оптимизировать

> Не понимаю я. Вроде ясно написал, отсортировать по определенным приоритетам массив рекордов.
> Что, это разве не "конкретная задача"?
это вообще не задача, это путь решения, твой путь, возможно неверный (почему никто и не хочет его "разрабатывать").
задача это то что делается, а не каким образом, и возможно, именно для задачи, не только сортировка но и вообще массив рекордов не понадобится... при другом алгоритме решения.

← →
Хитрий Лис (2008-11-16 13:23) [35]

Давненько в одной ветке столько голубых значков небыло :) зацепило таки...

> это вообще не задача,

Ну почему не задача? Как раз задача - оптимизировать процесс.

> main © (16.11.08 05:32) [32]

Обрати внимание - как сказал MBo в [33] для оптимизации нужны точные условия. В общем случае задача не решается.

> Как раз задача - оптимизировать процесс.
видимо я по другому понимаю что такое задача.

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

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

и да, конечно, можно и "оптимизировать процесс" рассматривать как задачу, но только для решения основной ("перейти улицу"/"сходить за хлебом"/"хлеб на столе") она довольно бессмысленна, вот будешь ты тут рассчитывать время выхода, скорость движения, чтобы попасть не в час пик, т.е. удобное время для "перебега" и т.д. т.е. сокращать время которое для него потребуется, а ведь можно пойти вообще другим путём, и например заказать хлеб по интернету... сократив своё время похода до 0, и сделав вообще ненужными все подзадачи.

procedure QuickSwap(PData1,PData2 :pointer; count :integer );
begin
???
end;

а так не пойдет? :)

procedure QuickSwap(var PData1, PData2 :pointer);
var
temp: pointer;
begin
temp := PData1;
PData1 := PData2;
PData2 := temp;
end;

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

← →
Sapersky (2008-11-16 17:16) [39]

Посмотрите, какие оптимизации используются в FastCode Move Challenge:
http://fastcode.sourceforge.net/challenge_content/Move.html
Задача-то в общем сходная.
Если у вас BDS2006 или более новая версия, оптимизированный вариант Move с FastCode должен быть уже встроен в system.pas.

Хотя, конечно, если производительность упирается в move или swap - в консерватории что-то не так...

> хранить указатели на данные, их же и сортировать.

См Связанный двунаправленный список . ИМХО его ты и пытаешься реализовать.

Быстрый Swap, Найти похожие ветки