Языки программирования Опции

[Etoprostoya]

Ограничение в 4 миллиарда - естественное ограничение для 32 бит, так что могу и воспользоваться, если будет нужно и если программа достаточно быстра.
А для бОльших чисел нужно использовать 64-битную арифметику или длинные числа.
Критикую так потому, что алгоритм мне кажется странным, а комментариев нет.

[tolich]

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

А такая беда только в гамаке или в любом языке?

В других языках есть целые переменные. А насчет быстродействия, скажем, для Си:

Код

int t=x; x=y; y=t;

скорее всего, превратится в

Код

mov EAX,x // а x,y и t что-то навроде [EBP+число]
mov t,EAX
mov EAX,y
mov x,EAX
mov EAX,t
mov y,EAX

А

Код

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

в

Код

mov EAX,x
xor y,EAX
mov EAX,y
xor x,EAX
mov EAX,x
xor y,EAX

Учитывая, что на современных процессорах и mov, и xor выполняются за 1 такт, разницы никакой, только аж 4 байта памяти экономится.

[Etoprostoya]

К предыдущему посту.
Код программы

(Раскрыть)

Код

#include <stdio.h>
#include <time.h>

void memswap1(int *arr1, int *arr2, int size)
{
    for(int i = 0; i < size; i++)
    {//t=x; x=y; y=t;
        int tmp = arr1[i];
        arr1[i] = arr2[i];
        arr2[i] = tmp;
    }
}
void memswap2(int *arr1, int *arr2, int size)
{
    for(int i = 0; i < size; i++)
    {// x^=y; y^=x; x^=y;
        int x = arr1[i], y = arr2[i];
        x ^= y; y ^= x; x ^= y;
        arr1[i] = x; arr2[i] = y;
    }
}
#define SZ 100000
void main()
{
    int arr1[SZ], arr2[SZ];
    clock_t t = clock();
    for(int i = 0; i < 1001; i++) memswap1(arr1, arr2, SZ);
    printf("Time to swap with temporary var is %d\n", clock() - t);
    t = clock();
    for(int i = 0; i < 1001; i++) memswap2(arr1, arr2, SZ);
    printf("Time to swap with XOR is %d\n", clock() - t);
    return;
}

Компиляция

Код

cl /O2 /FAcs memswap.cpp

Код функций в асме

(Раскрыть)

Код

_TEXT    SEGMENT
_arr1$ = 8                    ; size = 4
_arr2$ = 12                    ; size = 4
_size$ = 16                    ; size = 4
?memswap1@@YAXPAH0H@Z PROC            ; memswap1, COMDAT

; 5    : {

  00000    56         push     esi

; 6    :     for(int i = 0; i < size; i++)

  00001    8b 74 24 10     mov     esi, DWORD PTR _size$[esp]
  00005    85 f6         test     esi, esi
  00007    7e 1e         jle     SHORT $LN1@memswap1
  00009    8b 44 24 0c     mov     eax, DWORD PTR _arr2$[esp]
  0000d    8b 4c 24 08     mov     ecx, DWORD PTR _arr1$[esp]
  00011    2b c8         sub     ecx, eax
  00013    57         push     edi
$LL3@memswap1:

; 7    :     {
; 8    :         int tmp = arr1[i];
; 9    :         arr1[i] = arr2[i];

  00014    8b 38         mov     edi, DWORD PTR [eax]
  00016    8b 14 01     mov     edx, DWORD PTR [ecx+eax]
  00019    89 3c 01     mov     DWORD PTR [ecx+eax], edi

; 10   :         arr2[i] = tmp;

  0001c    89 10         mov     DWORD PTR [eax], edx
  0001e    83 c0 04     add     eax, 4
  00021    83 ee 01     sub     esi, 1
  00024    75 ee         jne     SHORT $LL3@memswap1
  00026    5f         pop     edi
$LN1@memswap1:
  00027    5e         pop     esi

; 11   :     }
; 12   : }

  00028    c3         ret     0
?memswap1@@YAXPAH0H@Z ENDP            ; memswap1
_TEXT    ENDS

Код

_TEXT    SEGMENT
_arr1$ = 8                    ; size = 4
_arr2$ = 12                    ; size = 4
_size$ = 16                    ; size = 4
?memswap2@@YAXPAH0H@Z PROC            ; memswap2, COMDAT

; 14   : {

  00000    57         push     edi

; 15   :     for(int i = 0; i < size; i++)

  00001    8b 7c 24 10     mov     edi, DWORD PTR _size$[esp]
  00005    85 ff         test     edi, edi
  00007    7e 28         jle     SHORT $LN1@memswap2
  00009    8b 44 24 0c     mov     eax, DWORD PTR _arr2$[esp]
  0000d    53         push     ebx
  0000e    56         push     esi
  0000f    8b 74 24 10     mov     esi, DWORD PTR _arr1$[esp+8]
  00013    2b f0         sub     esi, eax
$LL3@memswap2:

; 16   :     {// x^=y; y^=x; x^=y;
; 17   :         int x = arr1[i], y = arr2[i];

  00015    8b 08         mov     ecx, DWORD PTR [eax]

; 18   :         x ^= y; y ^= x; x ^= y;

  00017    8b 14 06     mov     edx, DWORD PTR [esi+eax]
  0001a    33 d1         xor     edx, ecx
  0001c    33 ca         xor     ecx, edx
  0001e    8b d9         mov     ebx, ecx
  00020    33 da         xor     ebx, edx

; 19   :         arr1[i] = x; arr2[i] = y;

  00022    89 1c 06     mov     DWORD PTR [esi+eax], ebx
  00025    89 08         mov     DWORD PTR [eax], ecx
  00027    83 c0 04     add     eax, 4
  0002a    83 ef 01     sub     edi, 1
  0002d    75 e6         jne     SHORT $LL3@memswap2
  0002f    5e         pop     esi
  00030    5b         pop     ebx
$LN1@memswap2:
  00031    5f         pop     edi

; 20   :     }
; 21   : }

  00032    c3         ret     0
?memswap2@@YAXPAH0H@Z ENDP            ; memswap2
_TEXT    ENDS

Результат

Код

E:\Projects\2>memswap.exe
Time to swap with temporary var is 1328
Time to swap with XOR is 1328

P.S. Сейчас попробую на интеловском оптимизирующем компиляторе попробовать.

Код

E:\Projects\2>memswap.exe
Time to swap with temporary var is 156
Time to swap with XOR is 234

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

[tolich]

Оптимизация, конечно, наше всё, но как научить компилятор использовать XCHG?

Код

mov eax,x
xchg eax,y
mov x,eax

lol?

Или интеловский компилятор его использует? 0_0

[Etoprostoya]

Нет, интеловский компилятор это не использует и вообще рекомендуют

minimize the use of xchg instructions on memory locations

А там, где интеловский компилятор в несколько раз обогнал по быстродействию программ, он просто переиначил двойной цикл
for(;i<1000;i++) for(;j<100000;j++)
в
for(;j<100000;j++) for(;i<1000;i++)
что, естественно, быстрее, так как подгружать маленькие блоки памяти можно быстрее. То есть, компилятор оптимизировал работу с памятью и всё, а майкрософтский не додумался до этого.

[gamecreator]

Ну да, всего лишь 4 миллиарда прогона цикла

в нормальных компиляторах

Код

for(uint i=0; i; ++i)

это 0 прогонов цикла

[tolich]

Да и в ненормальных тоже.

Этопростоон явно имел в виду:

Код

for(uint i=0; ; ++i)

ибо для uint i выражение i<0xFFFFFFFE всегда было бы true, если uint 16-битный.

[gamecreator]

где мы, а где 16битные процессоры?

[tolich]

Хм, я еще и восьмибитные не забыл.

[Etoprostoya]

А я четырёхбитный придумывал

Серьёзно.

[hippocamus]

А чего его придумывать? 4-битный ZX-Spectrum 8080 Прямой предок IBM AT 8086

[Etoprostoya]

Во-первых, ZX-Spectrum - 8-битный.
А во-вторых, я придумывал узкоспециализированный процессор для торгового автомата.

[Guevara-chan]

http://www.red-lang.org/ - внезапно заинтриговало.
Свободный, компилируемый, с синтаксисом а-ля REBOL...

[feanor]

Кто-нибудь с генетическим программированием игрался? Не с алгоритмами, а именно с программированием - выращиванием программы из дерева операторов?

А я четырёхбитный придумывал

Серьёзно.

Курсовик какой-то?)

[Etoprostoya]

Курсовик, да.

[feanor]

У нас тоже был..только не с темой, а процессор вообще - пять команд (у меня, впрочем, было примерно 25-30 хD), двуоперандные, однооперандные, безоперандные.

[feanor]

Так, вопрос.

Слышал/видел/знает ли кто алгоритм разбиения на треугольники невыпуклого полигона с прорехами внутри?

[tolich]

Это называется "триангуляция".

[feanor]

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

[IvanSav]

Хмм... Как насчет такого?
http://algolist.manual.ru/maths/geom/polygon/decompose.php
Насколько я понял, алгоритм будет работать и с прорехами. Одно но - на выходе будут не треугольники а все те же полигоны, но уже без дыр. Так что полученые полигоны еще нужно будет разбить на треугольники.

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