Привет!!!
Есть два указателя, которые являются элементами массива.
Как быстро поменять их местами(без использования третьего элемента)?

Здравствуйте, Faust, Вы писали:


F>Привет!!!
F>Есть два указателя, которые являются элементами массива.
F>Как быстро поменять их местами(без использования третьего элемента)?

T a, b;

a+=b;
b=a-b;
a-=b;

но только почему это быстро?

Здравствуйте, Faust, Вы писали:

F>Есть два указателя, которые являются элементами массива.
F>Как быстро поменять их местами(без использования третьего элемента)?

A и B

A = A + B
B = A - B
A = A - B;

или

A = A ^ B
B = A ^ B
A = A ^ B

Здравствуйте, UgN, Вы писали:

UgN>Здравствуйте, Faust, Вы писали:

F>>Есть два указателя, которые являются элементами массива.
F>>Как быстро поменять их местами(без использования третьего элемента)?

UgN>

UgN>A и B

UgN>A = A + B
UgN>B = A - B
UgN>A = A - B;

UgN>или

UgN>A = A ^ B
UgN>B = A ^ B
UgN>A = A ^ B 

UgN>

а есть еще какие-нибудь варианты?
эти я уже опробовал.

Здравствуйте, Faust, Вы писали:

F>а есть еще какие-нибудь варианты?
F>эти я уже опробовал.


ну можно построить на основе любой бинарной операции у которой существует обратная операция

Здравствуйте, Faust, Вы писали:


F>Привет!!!
F>Есть два указателя, которые являются элементами массива.
F>Как быстро поменять их местами(без использования третьего элемента)?

x^=y; y^=x; x^=y;

Здравствуйте, Faust, Вы писали:

Стек

Здравствуйте, Креатив Рекъйооред, Вы писали:

КР>Стек

По условию нельзя.

Здравствуйте, Faust, Вы писали:

F>а есть еще какие-нибудь варианты?
F>эти я уже опробовал.


В принципе, обмен с третьей ячейкой быстрее.


Обмен с XOR:

Память -> Регистр
Память -> Регистр
XOR
XOR
XOR
Регистр -> Память
Регистр -> Память

Обмен с третьей ячейкой (регистр)

Память -> Регистр
Память -> Регистр
Регистр -> Память
Регистр -> Память

A>
A>ну можно построить на основе любой бинарной операции у которой существует обратная операция

например так:

a=a-b;
b=b+a;
a=b-a;

или в 2 оператора:

b+=a-=b;
a=b-a;

Здравствуйте, UgN, Вы писали:

UgN>Обмен с третьей ячейкой (регистр)

UgN>Память -> Регистр
UgN>Память -> Регистр
UgN>Регистр -> Память
UgN>Регистр -> Память

а так хуже будет?

mov ax, [a]
mov [a], [b]
mov [b], ax

А вообще, если так нужна скорость, то стоит попробовать MMX применить...

Здравствуйте, Atilla, Вы писали:

UgN>>Обмен с третьей ячейкой (регистр)

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

Вариант A.

UgN>>Память -> Регистр
UgN>>Память -> Регистр
UgN>>Регистр -> Память
UgN>>Регистр -> Память

A>а так хуже будет?

А у тебя только третья.

Вариант B.

A>

A>mov ax, [a]
A>mov [a], [b]
A>mov [b], ax
A>

Даже лучше.

Но, наверное, зависит от системы, от того, как она с памятью работает
Может оказаться, что вариант А сработает быстрее (за 2 такта), ибо читаться и писаться будут сразу два числа.
Если память двухпортовая, то можно делать чтение и запись одновременно (разных ячеек) — тоже повод поизвращаться.


A>А вообще, если так нужна скорость, то стоит попробовать MMX применить...
А там с памятью по особому работают?

Здравствуйте, UgN, Вы писали:

A>>А вообще, если так нужна скорость, то стоит попробовать MMX применить...
UgN>А там с памятью по особому работают?

точнее не MMX, а SIMD. Там можно и кэшем управлять (например, когда пишем в b, можно указать, чтоб проц это число выкинул из кэша, т.к. оно нам больше не понадобится), а в MMX можно обменивать сразу несколько пар одной операцией. В общем, в некоторых задачах может помочь.

Спасибо всем кто участвовал.

Здравствуйте, UgN, Вы писали:

UgN> Здравствуйте, Atilla, Вы писали:

UgN>>>Обмен с третьей ячейкой (регистр)

UgN>Никто и не заметил, а тут и четвертая ячейка есть...

UgN>Вариант A.

UgN>>>Память -> Регистр
UgN>>>Память -> Регистр
UgN>>>Регистр -> Память
UgN>>>Регистр -> Память

A>>а так хуже будет?

UgN>А у тебя только третья.

UgN>Вариант B.

A>>

A>>mov ax, [a]
A>>mov [a], [b]
A>>mov [b], ax
A>>

UgN>Даже лучше.

UgN>Но, наверное, зависит от системы, от того, как она с памятью работает
UgN>Может оказаться, что вариант А сработает быстрее (за 2 такта), ибо читаться и писаться будут сразу два числа.
UgN>Если память двухпортовая, то можно делать чтение и запись одновременно (разных ячеек) — тоже повод поизвращаться.

UgN>
A>>А вообще, если так нужна скорость, то стоит попробовать MMX применить...
UgN>А там с памятью по особому работают?

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

Здравствуйте, cpp, Вы писали:

cpp>SSE инструкция prefetch — запись мимо кэша , если много сразу обменов, например в массиве, то должно помочь.

только не надо дезынформации! prefetch — это предварительная выборка из памяти в кэш, а запись мимо кэша — это sfence

ой, нет, sfence — это не то.
Мимо кэша пишут movntq и movntps... вроде бы

Здравствуйте, Atilla, Вы писали:

A>Здравствуйте, cpp, Вы писали:

cpp>>SSE инструкция prefetch — запись мимо кэша , если много сразу обменов, например в массиве, то должно помочь.

A>только не надо дезынформации! prefetch — это предварительная выборка из памяти в кэш, а запись мимо кэша — это sfence

Говорю prfetch + movntq. "Команда sfence гарантирует, что все операции записи в память, расположенные в тексте программы до нее, будут выполнены раньше, чем процессор начнет выполнять операции, помещенные в текст прораммы позднее". Конец цитаты. В общем насильная запись кэша.

Здравствуйте, Atilla, Вы писали:

mov [a], [b]

Что это? Я такого не помню.

Здравствуйте, WolfHound, Вы писали:

WH>

WH>mov [a], [b]
WH>

WH>Что это? Я такого не помню.

Это mov из ячейки a в ячейку b.

Т.е. a = b, где a и b — ячейки в памяти (переменные);

[ a ] и [ b ] -- соответственно адрес ячейки a и ячейки b



PS: странные глюки из-за совпадения с тегом раскраски [b]