Re[13]: Зачем просят перевернуть строку на интервью?
От: CreatorCray  
Дата: 11.10.18 08:18
Оценка:
Здравствуйте, 0xCAFEDEAD, Вы писали:

CAF>А какое решение быстрее (я слабо знаком с оптимизациями компиляторов, поэтому любые комменты от опытных тов приветствуются)

Как правило компилятор всё равно преобразует кашу с индексами в адресную арифметику.

Ради интереса скормил код онлайн компилеру https://godbolt.org/ x86-64 gcc (trunk) -O3
1.Nuzhny
Автор: Nuzhny
Дата: 10.10.18
, малость адаптирован чтоб таки скомпилить

#include <algorithm>

void revert(char* first, char* last)
{
    while ((first != last) && (first != --last)) {
        std::iter_swap (first++, last);
    }
}


2.RussianFellow
Автор: RussianFellow
Дата: 10.10.18
, для честности вынес strlen наружу как параметр

#include <stddef.h>

void revert(char* s, size_t n)
{
    for (auto i=0; i<n/2; i++)
    {
        auto c = s[i];
        s[i] = s[n-1-i];
        s[n-1-i] = c;
    }
}


Итого:

1.
revert(char*, char*):
        cmp     rdi, rsi
        jne     .L3
        jmp     .L1
.L6:
        add     rdi, 1
        movzx   edx, BYTE PTR [rsi]
        movzx   eax, BYTE PTR [rdi-1]
        mov     BYTE PTR [rdi-1], dl
        mov     BYTE PTR [rsi], al
        cmp     rsi, rdi
        je      .L1
.L3:
        sub     rsi, 1
        cmp     rsi, rdi
        jne     .L6
.L1:
        ret


2.
revert(char*, unsigned long):
        mov     rdx, rsi
        shr     rdx
        je      .L1
        lea     rax, [rdi-1+rsi]
        lea     rsi, [rdi+rdx]
.L4:
        movzx   ecx, BYTE PTR [rax]
        movzx   edx, BYTE PTR [rdi]
        add     rdi, 1
        sub     rax, 1
        mov     BYTE PTR [rdi-1], cl
        mov     BYTE PTR [rax+1], dl
        cmp     rdi, rsi
        jne     .L4
.L1:
        ret


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

Clang (trunk) -O3
revert(char*, unsigned long):                           # @revert(char*, unsigned long)
        mov     rcx, rsi
        shr     rcx
        je      .LBB0_6
        mov     r8d, ecx
        and     r8d, 1
        cmp     rcx, 1
        jne     .LBB0_7
        xor     ecx, ecx
        test    r8, r8
        jne     .LBB0_5
        jmp     .LBB0_6
.LBB0_7:
        lea     rdx, [rdi + 1]
        lea     r11, [rdi + rsi]
        add     r11, -1
        mov     r9, r8
        sub     r9, rcx
        xor     ecx, ecx
.LBB0_8:                                # =>This Inner Loop Header: Depth=1
        movzx   r10d, byte ptr [rdx - 1]
        movzx   eax, byte ptr [r11 + rcx]
        mov     byte ptr [rdx - 1], al
        mov     byte ptr [r11 + rcx], r10b
        movzx   r10d, byte ptr [rdx]
        movzx   eax, byte ptr [r11 + rcx - 1]
        mov     byte ptr [rdx], al
        mov     byte ptr [r11 + rcx - 1], r10b
        add     rdx, 2
        add     rcx, -2
        cmp     r9, rcx
        jne     .LBB0_8
        neg     rcx
        test    r8, r8
        je      .LBB0_6
.LBB0_5:
        mov     r8b, byte ptr [rdi + rcx]
        mov     rdx, rcx
        not     rdx
        add     rdx, rsi
        mov     al, byte ptr [rdi + rdx]
        mov     byte ptr [rdi + rcx], al
        mov     byte ptr [rdi + rdx], r8b
.LBB0_6:
        ret


CAF>Ну и конечно на десерт, можно ли еще быстрее?

Тут скорее не про быстрее стоит вести речь а про вменяемее.

CC>>Из моего опыта — любители индексов в массе пишут спагетти код.

CAF>Это мнение субъективное Спорить с таким утверждением бессмысленно.
Ну так там так и написано "Лично я увидев в этой задаче индексы..."
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.