Wprowadzenie

Mam algorytm, który przyjmuje wskaźnik do tablicy char. Algorytm najpierw pobiera długość tablicy, a następnie odwraca tablicę.

Problem

Problem, który mam, polega na tym, że chcę użyć tego na tablicy wchar_t. I chcesz móc to zrobić bez konieczności kopiowania całej funkcji, zmiany nazwy i typu argumentu.

Oto wspomniana funkcja:

void reverseString(char *str){
  unsigned int l = getStringLength(str);
  int i = 0;
  int m = l >> 1;

  while(i < m){
    str[i] ^= str[l - 1];
    str[l - 1] ^= str[i];
    str[i] ^= str[l - 1];
    i++;
    l--;
  }
}

Od googlowania i czytania w SO nie będzie można użyć wskaźnika void (koncepcyjnie to samo przy użyciu union), ponieważ pozostawiłoby mnie to z takim rozwiązaniem, które jest dla mnie równie złe jak pisanie oddzielnych funkcji, ale z różnymi nazwami i typami argumentów:

void reverseString(void *array, short typeSize){
  unsigned int l = getArrayLength(array);
  int m = l >> 1;
  int i = 0;
  char *str = 0;
  wchar_t *wstr = 0;

  if(typeSize == 1){
    str = (char *) array;
    while(i < m){
      str[i] ^= str[l - 1];
      str[l - 1] ^= str[i];
      str[i] ^= str[l - 1];
      i++;
      l--;
    }
  }else if(typeSize == 4){
    wstr = (wchar_t *) array;
    while(i < m){
      wstr[i] ^= wstr[l - 1];
      wstr[l - 1] ^= wstr[i];
      wstr[i] ^= wstr[l - 1];
      i++;
      l--;
    }
  }
}

Uwaga: getStringLength to po prostu funkcja, która przechodzi przez wskaźnik, aż dojdzie do '\0' i zwróci sumę iteracji.

Odpowiedź

Szukam odpowiedzi, która powie mi, jak zrobić to w ładniejszy sposób, bez konieczności przepisywania wewnętrznych elementów algorytmu, lub odpowiedzi, że nie da się tego zrobić w inny sposób. Nie szukam odpowiedzi, która mówi mi, że powinienem używać tej i tej biblioteki, która robi to za mnie, ponieważ nie używam tego w kodzie produkcyjnym, to czysto edukacyjne, aby lepiej zrozumieć, jak działa zarządzanie pamięcią i inne koncepcje zarówno.

Edytuj: funkcja, którą pokazałem, to tylko przykład, szukam uniwersalnego rozwiązania problemów z algorytmami.

1
rzetterberg 17 czerwiec 2011, 18:43
Jakie są twoje przemyślenia na temat makr?
 – 
Oliver Charlesworth
17 czerwiec 2011, 18:46
3
Nie używaj l dla zmiennych jednoliterowych. Wszystkie zmienne jednoliterowe są złe, ale l jest &^%#*@ głupie i &*#%( demoniczne.
 – 
pmg
17 czerwiec 2011, 18:49
Myślę, że mówienie komuś, żeby coś zrobił, nie mówiąc mu, dlaczego powinien, jest &^%#*@ głupie i &*#%( demoniczne.
 – 
rzetterberg
17 czerwiec 2011, 19:24
Myślałem, że powód sugerowania unikania zmiennej jednoliterowej l był oczywisty... ale posłucham twojej rady i postaram się bardziej w przyszłości wyjaśnić powody moich sugestii. Dziękuję Ci.
 – 
pmg
17 czerwiec 2011, 20:01
Dziękuję, że nie odebrałeś tego w niewłaściwy sposób. Myślę, że wiedza oczywista będzie się różnić w zależności od osoby, dlatego uważam, że lepiej wyjaśnić, co masz na myśli. Posłuchaję również twojej rady, więc dziękuję za to! :)
 – 
rzetterberg
17 czerwiec 2011, 20:46

3 odpowiedzi

Najlepsza odpowiedź

Używanie „ogólnych” w C prawdopodobnie wytworzy kod, który jest zauważalnie wolniejszy i bardziej zawiły/trudny do odczytania/trudny w utrzymaniu niż oryginalny kod. Użyj preprocesora, jeśli musisz to zrobić.

Moim zaleceniem jest unikanie tej techniki, jeśli to w ogóle możliwe: naprawdę powinieneś używać tylko char lub wchar_t w swoim programie, a nie ich kombinacji! (char lub UChar lub prawie uniwersalnie preferowane, ponieważ możesz wybrać kodowanie, ale robię dygresję...)

#define gchar char
#define gstrlen strlen
#define func_name reverse
#include "reverse_impl.h"
#undef gchar
#undef gstrlen
#undef func_name

#define gchar wchar_t
#define gstrlen wstrlen
#define func_name wreverse
#include "reverse_impl.h"
#undef gchar
#undef gstrlen
#undef func_name

Następnie w reverse_impl.h:

void func_name(gchar *str)
{
    gchar *p = str, *q = str + gstrlen(str), t;
    if (p == q)
       return;
    q--;
    for (; p < q; p++, q--) {
        t = *p;
        *p = *q;
        *q = t;
    }
}

Ponadto NIE RÓB TEGO:

x ^= y; // bad!
y ^= x;
x ^= y;

Jest trudniejszy do odczytania i prawdopodobnie znacznie wolniejszy do wykonania.

Należy również pamiętać, że zarówno reverse, jak i wreverse zrobią śmieci, jeśli podasz im dane wejściowe Unicode: reverse spowoduje zniekształcenie danych wyjściowych, a wreverse może zmienić znaki diakrytyczne lub całkowicie schrzanić Hangul, w zależności od tego, jak są reprezentowane.

2
Dietrich Epp 17 czerwiec 2011, 22:54
Dziękuję za proste rozwiązanie. Doceniane są również punkty dotyczące innych rzeczy wokół odpowiedzi. Poczytam o makrach i preprocesorze. Jeszcze nic o tym nie czytałem.
 – 
rzetterberg
17 czerwiec 2011, 23:22
Pomyślałem również, że zamiana XOR będzie szybsza, ponieważ nie używa dodatkowej pamięci do przechowywania znaku. Ale teraz, kiedy o tym myślę, rzeczywista instrukcja XOR zajmuje więcej czasu niż instrukcja przenoszenia/kopiowania. Czy dobrze to zrozumiałem?
 – 
rzetterberg
17 czerwiec 2011, 23:29
Kompilator zna już wszystkie sztuczki, jeśli piszesz czysty kod. Jeśli używasz zmiennej tymczasowej, kompilator jest w stanie w wielu przypadkach zamienić zamianę w całkowity brak operacji poprzez analizę przepływu. W innych przypadkach twórcy kompilatorów zwykle znają najszybszy sposób zamiany zmiennej, a ty nie. Sprytne sztuczki, takie jak ta, często obniżają wydajność z innych powodów, ponieważ sabotują zdolność kompilatora do wykonywania analizy przepływu dla reszty funkcji.
 – 
Dietrich Epp
17 czerwiec 2011, 23:31
Dzięki za wyjaśnienie i wszystkie inne wskazówki! Kawałki zaczynają się układać :)
 – 
rzetterberg
17 czerwiec 2011, 23:39

Jest mało prawdopodobne, aby była wydajna, ale możesz łatwo odwrócić swoją wersję void reverseString(void *array, short typeSize) elementów za pomocą trywialnej arytmetyki wskaźnika i memcpys o odpowiednim rozmiarze.

Oczywiście to podejście nie ma zastosowania do każdego algorytmu, który ma być niezależny od typu. Z Twojego pytania nie wynika jasno, czy interesuje Cię tylko ten konkretny algorytm, czy algorytmy w ogóle.

[Na marginesie: Zauważ, że używanie zamiany XOR nie będzie bardziej efektywne niż robienie tego "naiwnie". Z pewnością jest mniej czytelny!]

2
Oliver Charlesworth 17 czerwiec 2011, 18:48
Dzięki za twoje przemyślenia na ten temat. Zredagowałem moje pytanie tak, że proszę o bardziej uniwersalne rozwiązanie niż konkretne rozwiązanie dla tego algorytmu. Skoro już to zostało powiedziane, czy istnieje uniwersalna najlepsza praktyka w tym zakresie? Omówię zamianę XOR na inne pytanie. Przeczytałem o tym tutaj, jeśli jesteś zainteresowany: graphics.stanford.edu/~seander/bithacks .html
 – 
rzetterberg
17 czerwiec 2011, 19:33

... uniwersalne rozwiązanie...

Rozwiązaniem jest napisanie czegoś takiego jak qsort(): wszystkie funkcje, które muszą znać rozmiar poszczególnych wartości, są przekazywane do twojej własnej funkcji ze wskaźnikami do void all over

#include <math.h>
#include <stdio.h>
#include <wchar.h>

void universalReverseArray(void *arr, size_t siz,
                           size_t (*arrlen)(void*),
                           void (*swap)(void*, void*))
{
  size_t elems = arrlen(arr);
  size_t i = 0;
  size_t m = elems >> 1;
  unsigned char *p = arr;

  while(i < m) {
    swap(p + i * siz, p + (elems - 1) * siz);
    i++;
    elems--;
  }
}

void cswap(void *a, void *b) {
  char *aa = a, *bb = b;
  char t = *aa;
  *aa = *bb;
  *bb = t;
}

void dswap(void *a, void *b) {
  double *aa = a, *bb = b;
  double t = *aa;
  *aa = *bb;
  *bb = t;
}

void wswap(void *a, void *b) {
  wchar_t *aa = a, *bb = b;
  wchar_t t = *aa;
  *aa = *bb;
  *bb = t;
}

size_t clen(void *arr) {
  char *aa = arr;
  size_t retval = 0;
  while (*aa) {
    retval += 1;
    aa += 1;
  }
  return retval;
}

size_t dlen(void *arr) {
  double *aa = arr;
  size_t retval = 0;
  while (fabs(*aa) >= 0.0001) {
    retval += 1;
    aa += 1;
  }
  return retval;
}

size_t wlen(void *arr) {
  wchar_t *aa = arr;
  size_t retval = 0;
  while (*aa) {
    retval += 1;
    aa += 1;
  }
  return retval;
}

int main(void) {
  double x[] = {1, 2, 3, 4, 5, 0};
  char y[] = "foobar";
  wchar_t z[4];
  z[0] = 'a'; z[1] = 'b'; z[2] = 'c'; z[3] = 0;

  for (int k=0; k<5; k++) {printf("%f ", x[k]);}
  printf("%s ", y);
  printf("%ls\n", z);

  universalReverseArray(x, sizeof *x, dlen, dswap);
  universalReverseArray(y, sizeof *y, clen, cswap);
  universalReverseArray(z, sizeof *z, wlen, wswap);

  for (int k=0; k<5; k++) {printf("%f ", x[k]);}
  printf("%s ", y);
  printf("%ls\n", z);

  return 0;
}

Możesz zobaczyć, jak działa na ideone: http://ideone.com/t1iOg

1
pmg 17 czerwiec 2011, 22:28
Dziękuję Ci! To ma sens i było czymś, o czym myślałem, co mogłoby rozwiązać mój problem. Jak wygląda to rozwiązanie pod względem wydajności w porównaniu z odpowiedzią Dietricha?
 – 
rzetterberg
17 czerwiec 2011, 23:30
Odpowiedź Dietricha prawdopodobnie generuje szybszy kod (aby mieć pewność, musisz zmierzyć). Ale tworzy kilka funkcji „odwrócenia”, a nie jedną funkcję uniwersalną :)
 – 
pmg
17 czerwiec 2011, 23:38
prawie to lubię! Ale czy nie jest to w zasadzie równoznaczne z istniejącym mechanizmem PO, z wyjątkiem tego, że różne przypadki specjalne funkcjonują teraz w oddzielnych funkcjach, a nie w dużym „jeśli-innym”? Ta sama ilość kodu musi zostać napisana i utrzymana w dowolny sposób (daj lub bierz).
 – 
Oliver Charlesworth
18 czerwiec 2011, 00:20
@Oli: jeśli przekażesz rozmiar elementu do funkcji swap, możesz napisać go do zamiany wartości dowolnego typu: universalSwap(size_t siz, void *a, void *b);. Funkcje len nie mogą być jednak 'uniwersalizowane'.
 – 
pmg
18 czerwiec 2011, 00:53