Witam ponownie i dwa rozwiązania prostego zadania z C++

0

Witam szanownych kolegów z 4p - po prawie 7 latach od rozpoczęcia mojej działalności na 4p i ponad 3 latach od napisania ostatniego z ponad 3000 postów. Ciekawe, czy mnie ktoś tu jeszcze pamięta :-).

A już zwłaszcza tu, w C/C++ - bo wtedy pisałem w Delphi.

Tak czy owak, napisałem sobie w Delphi parę fajnych rzeczy, m.in. dzięki temu, czego nauczyłem się na 4p. Potem pisałem w nieco bardziej egzotycznych rzeczach, jak Matlab, czy języki skryptowe programów CED Spike2 i NBS Presentation.

A teraz na starość naszła mnie myśl, że głupio tak mało wiedzieć o C++. Więc sobie ściągnąłem frikowe Visual C++, ściągnąłem jakiegoś ebooka, wykopałem napisany bagatela 15 lat temu przez przyjaciela prawie 700-stronicowy podręcznik do Borland C++ i sobie przerabiam podstawy.

Będę tu wpadał z pytaniami :-)

Na dziś jedno proste. W ramach podstaw ebook zadał mi prościutkie zadanie: napisz odpowiednik funkcji strlen().

Napisałem, po czym sprawdziłem w odpowiedziach - była inna wersja. Obie najwyraźniej poprawne, ale ciekaw jestem opinii znawców: czy któraś jest zdecydowanie wydajniejsza, lub bardziej elegancka, czy też są to dwa całkowicie równoważne rozwiązania.

Kod z odpowiedzi:

int mystrlen2(char *str)
{
	int i;

	for(i=0; str[i]; i++);

	return i;
}

Mój kod:

int mystrlen(char* str)
{
	char* index=str;

	while (*index)
		index++;

	return index-str;
}

pozdr, pq

0

Kod odpowiedzi zrozumie każdy w ułamku sekundy.

Natomiast nad twoim kodem trzeba chwilę posiedzieć by go zrozumieć.Taką widzę różnice. Po co kombinować.

KISS - Keep It Simple Stupid.</url>

0

W sumie to żadne nie jest 100% poprawne - strlen nie zmienia w żaden sposób stringa, więc powinno przyjmować const char*. Poza tym, kody są w sumie równoważne...

@up: dyskusyjne jak cholera.

0

skoro nie korzystasz z const char* to nie potrzebujesz dodatkowego indeksu, bo przeciez nie zmieniasz zawartosci bufora tylko wskaznik do niego.

trzecia, mieszana wersja i chyba najwolniejsza poprzez podwojna inkrementacje

int mystrlen(char* str)
{
  int i=0
  while (*str){
    str++
    i++;
  }
  return i;
}

pq, znasz metode na pewno, odpalic jedna i druga funkcje milionpincet raz i zobaczyc, w przypadku indeksu tablicy bedzie troche wiecej kodu.

// dawno faktycznie cie nie bylo, chcesz posprzatac w dziale delphi ?

0

@pq:
Wersja wskaźnikowa może być tu nieco szybsza. W wersji tablicowej w każdej iteracji masz odniesienie str[i], co jest równoważne z *(str + i), a więc jest tam ukryta jedna operacja dodawania. W wersji wskaźnikowej tego dodawania nie ma, jest po prostu *str. To jest raczej standardowy przykład na to, jak korzystanie ze wskaźników może zwiększyć wydajność.

Może, bo sporo zależy tu od kompilatora. Teoretycznie mógłby on sam zoptymalizować wersję tablicową tak, by kod był bardzo podobny do tego z wersji wskaźnikowej. No i sporo zależy od użycia funkcji strlen. Przedwczesna optymalizacja to źródło wszelkiego zła i nie wolno pisać nieczytelnego kodu tylko dlatego, że jest szybszy -- nie sprawdzając, czy różnica w prędkości jest istotna. Moim zdaniem wersja wskaźnikowa jest tutaj nieco mniej czytelna, tzn. mniej oczywiste jest to, czy zawiera błąd off-by-one, czy nie (chodzi o inkrementację w ciele pętli + odejmowanie na końcu). Sama pętla jest jednak zrozumiała i ludzie korzystający ze wskaźników natychmiast zrozumieją ten kod, tyle że trzeba chwilę pomyśleć, czy odejmowanie i przesuwanie wskaźnika jest poprawne. Także czytelność aż tak tutaj nie cierpi. Ale wersja tablicowa to no-brainer.

edit:
@flabra:
Wcale nie jestem pewien, czy ta wersja mieszana jest najwolniejsza. Powinna być wolniejsza od typowo wskaźnikowej, ale od tablicowej wcale nie musi być. Tzn. nie sądzę, by była. Choć zależy to od tego, co z tym zrobi kompilator.

0

Dzięki za odzew!

LaM napisał(a)

Natomiast nad twoim kodem trzeba chwilę posiedzieć by go zrozumieć.Taką widzę różnice. Po co kombinować.

No to chyba zależy od przyzwyczajeń. Nawiasem mówiąc, ja nie kombinowałem, przeczytałem problem, wymyśliłem rozwiązanie jakie przyszło mi do głowy.

flabra napisał(a)

pq, znasz metode na pewno, odpalic jedna i druga funkcje milionpincet raz i zobaczyc, w przypadku indeksu tablicy bedzie troche wiecej kodu.

Znam, tylko w zasadzie na razie ćwiczę czyste C++, nie zacząłem grzebać Windows API. Ale na życzenie publiczności użyłem QueryPerformanceCounter(), wyniki poniżej.

flabra napisał(a)

// dawno faktycznie cie nie bylo, chcesz posprzatac w dziale delphi ?

Yyyy... nie chcę :-)

bswierczynski napisał(a)

Wersja wskaźnikowa może być tu nieco szybsza.

Jest! Ciut.

Milion wykonań kodu

for (i=0;i<1000000;i++)
{f=mystrlen2(str);}

i pomiar QueryPerformanceCounter() dla różnych stringów dał takie czasy (w sekundach, pierwsze kod wskaźnikowy, drugie tablicowy)

C:\Users\Pawel\Desktop\dupa\Debug>dupa
x
0.032186
0.0329452

C:\Users\Pawel\Desktop\dupa\Debug>dupa
dupa
0.0442594
0.0462709

C:\Users\Pawel\Desktop\dupa\Debug>dupa
trelemorele
0.0803793
0.0861045


C:\Users\Pawel\Desktop\dupa\Debug>dupa
qqqqqqqqqqqqqqqqqqqhhhhhhhhhhhhhhhhhhhhhhhhhhjjjjjjjjjjjjjjjjjj
0.292733
0.322673

1 użytkowników online, w tym zalogowanych: 0, gości: 1