язык C в Linux: вопросы начального уровня

[Olej]

C99 тоже заслуживают отдельного рассмотрения:

Одно из нововведений:

Ещё одно нововведение C99 - массивы переменной длины (variable-length array, VLA).

Код: Выделить всё

void show2( char *str1, char *str2 ) {
   char *arr = " массив ", *len = " длины";
   char name[ strlen( str1 ) + strlen( arr ) +
              strlen( str2 ) + strlen( len ) + 1 ];
   strcpy( name, str1 );
   strcat( strcat( strcat( name, arr ), str2 ), len );
   printf( "%s: %d байт\n", name, sizeof( name ) );
}
   
void test02( void ) {
   show2( "показать", "переменной" );
};

Массивы переменной длины вообще любопытное место любого языка! А для C особенно :

1. Новички всегда первейшим делом норовят "увеличить" или "раздвинуть" массив - это такое всеобщее народное желание

2. С другой стороны, канон всякого языка со статической строгой типизацией (PASCAL, C, C++, Java, ...) вроде бы как постулирует, что массив - это структура с неизменными границами, ... а потом уже начинает добавлять всякие искусственные способы обойти эти ограничения (STL в C++, связные списковые структуры и др.)

3. Сам термин "массивы переменной длины" - он неоднозначный, и вносит путаницу ... по крайней мере на начальных этапах, "покрывая" собой 2 совершенно разных понятия:
- массивы, которые можно создавать с размером, заданным не константным выражением, вычисленным перед созданием (это, собственно, и есть VLA);
- массивы, размер которых можно изменять уже после их создания, по-ходу... (vector в STL, например), что правильно бы называть не массивами переменной длины, а ... динамическими массивами, массивами изменяемой длины и т.п.

Массивы VLA в стандарте C99 можно посмотреть здесь: Расширение массивов.
Там их пример-объяснение:

Код: Выделить всё

void f(int diml, int dim2)
{
  int matrix[diml][dim2]; /* двумерный массив переменной длины */
  /* ... */
}

Главная особенность VLA C99 в том, что они могут быть только локально определёнными.

[Olej]

Главная особенность VLA C99 в том, что они могут быть только локально определёнными.

В принципе, массивы VLA могут быть определены и использованы и до (без) стандарта C99 ... например так:

Код: Выделить всё

typedef struct vararr {
   int n, data[ 0 ];
} vararr_t;

void varfunc( vararr_t *a ) {
   int ni = a->n, j;
   printf( "[1:%d] элементы массива => ", ni );
   int *va = (int*)a;
   for( j = 1; j <= ni; j++ )
      printf( "%d%s", va[ j ], j != ni ? ", " : "\n" );
}

void test15( void ) {
   printf( "массивы переменной длины:\n" );
   int var[] = { 3, 5, 7, 10 }, i;
   for( i = 0; i < sizeof( var ) / sizeof( *var ); i++ ) {
      int len = var[ i ], j;
      vararr_t *arr = (vararr_t*)calloc( len + 1, sizeof( int ) );
      arr->n = len;
      for( j = 0; j < len; j++ ) arr->data[ j ] = j + 1;
      varfunc( arr );
      free( arr );
   }
}

- здесь функция varfunc() использует (для иллюстрации) индексирование массива [1...N] вместо [0...N-1] (но при желании, можно использовать индексирование и [0...N-1] как привычнее);
- такие вещи возможны тоже не с самого классического (рудиментарного) C, а с какого то его расширения (C89?), которое разрешает описание int data[ 0 ] ...
- и описание int data[ 0 ] для наших здесь целей - это радикально не то, что int *data, как понимаете;
- кстати, такое описание массива при дальнейших передачах между функциями - самоопределённое: размер массива задан в самой его структуре (так же точно могли бы быть заданы размерность многомерного массива + размеры по каждому измерению).

Вот как выглядит этот демонстрационный пример:

Код: Выделить всё

olej@notebook:~/2013_WORK/AntonG/examples.draft$ ./struct 4
04 ---------------------------------------
массивы переменной длины:
[1:3] элементы массива => 1, 2, 3
[1:5] элементы массива => 1, 2, 3, 4, 5
[1:7] элементы массива => 1, 2, 3, 4, 5, 6, 7
[1:10] элементы массива => 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
------------------------------------------

На подобные определения не распространяется ограничение VLA в C99 о том, что они могут быть только локально определёнными внутри прототипа или блока (но часто это и не такое уж сильное ограничение).

P.S. В архиве содержаться и все 5-7 предыдущих примеров (на расширения GCC, использование комплексных типов данных и др.), которые выше показывались раздельно.

[Olej]

В принципе, массивы VLA могут быть определены и использованы и до (без) стандарта C99 ... например так:

Код: Выделить всё

typedef struct vararr {
   int n, data[ 0 ];
} vararr_t;

Дальнейшее обсуждение выделено в отдельную тему: выделение памяти (язык C).
Потому что это а). важное, б). специфическое обсуждение.
Туда же перенесено несколько последних тем отсюда, затрагивающие:
- массивы переменной длины (VLA) GCC;
- использование массивов 0-й длины (data[ 0 ]) для создания объектов произвольной длины;
- выделение памяти под объекты в стеке;
- распределение памяти alloca() - плюсы и минусы;
- и вообще вопросы выделения памяти под объекты данных;

[Olej]

Совсем уж из вопросов начального уровня ... но только-что сам нарвался :

Код: Выделить всё

#define SIZE sizeof( int ) * 8
const int size = sizeof( int ) * 8;
//...
int x = 64;
printf( "%d\n", x / SIZE );
printf( "%d\n", x / size );

Какой будет результат? ... собственно, 2 результата подобных.
Почему так? объяснить ...
Если что-то не нравится, то как это что-то исправить ?

[Olej]

Совсем уж из вопросов начального уровня ...

Ещё пример ... - решето Эратосфена : способ нахождения всех простых чисел в диапазоне от 0 до N (ну, конечно же от 2 а не от 0 )
Описание этого общеизвестного алгоритма см. здесь: Решето Эратосфена.

Код: Выделить всё

void eratos1( short *arr, ulong size ) {
   ulong i, j;
   for( i = 2; i < size; i++ )                     // цикл по всему массиву от первого простого числа "2"
      if( 1 == arr[ i ] )
         for( j = i + i; j < size; j += i )        // вычеркивание всех чисел кратных i 
           arr[ j ] = 0;
}

И вызывающая тестовая программа:

Код: Выделить всё

#define eratos eratos1
//#define eratos eratos2
#define INLINE 10

int main( int argc, char **argv ) {
   long n;
   while( 1 ) {
      int i;
      printf( "граничное число: " );
      fflush( stdout );
      i = scanf( "%lu", &n );
      if( i <= 0 || n < 0 ) {
         printf( "\n" );
         break;
      }
      ulong k, j;
      short *a = calloc( n + 1, sizeof( short ) );
      a[ 0 ] = a[ 1 ] = 0;                   // вычёркиваем "0" и "1"
      for( k = 2; k < n; k++ ) a[ k ] = 1;   // остальные размечаем как простые
      eratos( a, n );
      for( k = 0, j = 0; k < n; k++ )
         j += ( a[ k ] != 0 ? 1 : 0 );
      printf( "%lu простых чисел:\n", j );
      for( k = 0, j = 0; k < n; k++ )
         if( 1 == a[ k ] ) {
            j++;
            printf( "%5lu%s", k, ( 0 == j % INLINE ? "\n" : "" ) );
         }
      if( j % INLINE != 0 ) printf( "\n" );
      free( a );
   }
   return 0;
}

Проверка:

Код: Выделить всё

olej@notebook:~/2013_WORK/AntonG/examples.draft$ ./erastof
граничное число: 100
25 простых чисел:
    2    3    5    7   11   13   17   19   23   29
   31   37   41   43   47   53   59   61   67   71
   73   79   83   89   97
граничное число: 

[Olej]

Ещё пример ... - решето Эратосфена : способ нахождения всех простых чисел в диапазоне от 0 до N (ну, конечно же от 2 а не от 0 )

Но предыдущее решение тривиальное, в лоб...
Интереснее то же, но заметно оптимизированное (интересно здесь именно за счёт чего оптимизация и почему это правильно работает):

Код: Выделить всё

void eratos2( short *arr, ulong size ) {           // оптимизированный вариант
   ulong i, j;
   for( i = 2; i * i <= size; i += i > 2 ? 2 : 1 ) // цикл по всему массиву от первого простого числа "2"
      if( 1 == arr[ i ] )
         for( j = i * i; j < size; j += i )        // вычеркивание всех чисел кратных i 
           arr[ j ] = 0;
}

[Olej]

Ещё пример ... - решето Эратосфена : способ нахождения всех простых чисел в диапазоне от 0 до N (ну, конечно же от 2 а не от 0 )

Но предыдущее решение тривиальное, в лоб...

И ещё один вариант: представление диапазона 0...N битовой последовательностью, в которой каждый последовательный бит описывает натуральное число: 1 - простое, 0 - составное:

Код: Выделить всё

#include <stdio.h>
#include <stdlib.h>

//#define TYPE unsigned long long
#define TYPE char

static const uint size = sizeof( TYPE ) * 8;

void set( TYPE arr[], ulong pos, int val ) {
   ulong el = pos / size,
         sh = 1 << ( pos % size );
   if( 0 == val ) 
      arr[ el + 1 ] &= ~sh;
   else
      arr[ el + 1 ] |= sh;
}

int get( TYPE arr[], ulong pos ) {
   ulong el = pos / size,
         sh = 1 << ( pos % size );
   return 0 == ( arr[ el + 1 ] & sh ) ? 0 : 1;
}

void eratos( TYPE *arr, ulong size ) {
   ulong i, j;
   for( i = 2; i * i <= size; i += i > 2 ? 2 : 1 ) // цикл от первого простого числа "2"
      if( 1 == get( arr, i ) ) 
         for( j = i * i; j < size; j += i )        // вычеркивание всех чисел кратных i 
            set( arr, j, 0 );
}

#define INLINE 10

int main( int argc, char **argv ) {
   long n;
   while( 1 ) {
      int i;
      printf( "граничное число: " );
      fflush( stdout );
      i = scanf( "%lu", &n );
      if( i <= 0 || n < 0 ) {
         printf( "\n" );
         break;
      }
      ulong k, j;
      k = n / size + 1;
      TYPE *a = calloc( k, size );
      set( a, 0, 0 );
      set( a, 1, 0 );                          // вычёркиваем "0" и "1"
      for( k = 2; k < n; k++ ) set( a, k, 1 ); // остальные размечаем как простые
      eratos( a, n );
      for( k = 0, j = 0; k < n; k++ )
         j += ( get( a, k ) != 0 ? 1 : 0 );
      printf( "%lu простых чисел:\n", j );
      for( k = 0, j = 0; k < n; k++ )
         if( 1 == get( a, k ) ) {
            j++;
            printf( "%5lu%s", k, ( 0 == j % INLINE ? "\n" : "" ) );
         }
      if( j % INLINE != 0 ) printf( "\n" );
      free( a );
   }
   return 0;
}

(архив дополнен всеми 3-мя вариантами)

[Olej]

Ещё пример ... - решето Эратосфена : способ нахождения всех простых чисел в диапазоне от 0 до N (ну, конечно же от 2 а не от 0 )

Но предыдущее решение тривиальное, в лоб...

И ещё один вариант: представление диапазона 0...N битовой последовательностью, в которой каждый последовательный бит описывает натуральное число: 1 - простое, 0 - составное:

Виноват
В предыдущее решение вкралась ошибочка... оно работает хорошо, если для представления битовой последовательности используется:

Код: Выделить всё

#define TYPE char

Но перестаёт работать, если для представления битовой последовательности используются 64 бит элементы:

Код: Выделить всё

#define TYPE unsigned long long

Ошибка настолько красивая , что её просто нужно показать, если разговор идёт об операциях C...
В функциях get() и set() в листинге выше вместо того что там написано:

Код: Выделить всё

int get( TYPE arr[], ulong pos ) {
   ulong el = pos / size,
         sh = 1 << ( pos % size );
   ...

Должно быть записано, например, так:

Код: Выделить всё

int get( TYPE arr[], ulong pos ) {
   ulong el = pos / size;
   TYPE  sh = (TYPE)1 << ( pos % size );
   ...

И самое главное здесь: (TYPE)1

[Olej]

Точность итерационных вычислений изменилась ... на 10 порядков!
P.S. Но с этим нужно ещё очень сильно разбираться!!!

Ну как? Вам ещё не кажутся такие тесты весёлыми?
Мне - кажутся.

В тех и ближайших к ним тестах в код вкрались ошибки ... всё делалось быстро, на ходу (вычисляется значение y, а выводится значение x , недостаточно корректное явное преобразование типов и т.д. ... удивляет что файлы десятки раз скачаны, но никто не высказал замечаний по элементарным опискам ... зачем тогда скачивать?).

Если это сделать корректно, то и результаты становятся явно более внятные и интересные...
Вот тот код, который касается точности вещественных вычислений:

Код: Выделить всё

const long double PI = 3.1415926535897932384626433832795028841971\
6939937510582097494459230781640628620899862803482534211706798214808651\
3282306647093844609550582231725359408128481117450284102701938521105559\
6446229489549303819644288109756659334461284756482337867831652712019091\
4564856692346034861045432664821339360726024914127372458700660631558817\
4881520920962829254091715364367892590360011330530548820466521384146951\
9415116094330572703657595919530921861173819326117931051185480744623799\
6274956735188575272489122793818301194912983367336244065664308602139494\
6395224737190702179860943702770539217176293176752384674818467669405132\
0005681271452635608277857713427577896091736371787214684409012249534301\
4654958537105079227968925892354201995611212902196086403441815981362977\
4771309960518707211349999998372978049951059731732816096318595024459455\
3469083026425223082533446850352619311881710100031378387528865875332083\
8142061717766914730359825349042875546873115956286388235378759375195778\
18577805321712268066130019278766111959092164201989L;

void test020( void ) {      // "неточность" вещественных данных
   printf( "точность представления вещественных типов:\n" );
   long double rl = (long double)PI;
   double rd = (double)PI;
   float rf = (float)rd;
   printf( "%12s[%2d байт] : %15.12Lf - %15.12f = %15.12Le\n",
           "float", sizeof( rf ), rl, rf, rl - (long double)rf );
   printf( "%12s[%2d байт] : %15.12Lf - %15.12f = %15.12Le\n",
           "double", sizeof( rd ), rl, rd, rl - (long double)rd );
   printf( "%12s[%2d байт] : %15.12Lf - %15.12Lf = %15.12Le\n",
           "long double", sizeof( rl ) , rl, rl, rl - rl );
}

Код: Выделить всё

#define DIV 10.

void test021( void ) {    // максимальная точность итерационных вычислений
   printf( "максимальная точность итерационных вычислений:\n" );
   int i;
   float x = 1.;
   double y = 1.;
   long double z = 1.;
   for( i = 0; ; i++ ) {
      if( (float)1. + x == (float)1. + x / (float)DIV ) break;
      x /= (float)DIV;
   }
   printf( "для float\t: %e (число итераций %d)\n", x, i );
   for( i = 0; ; i++ ) {
      if( ( (double)1. + y ) == ( (double)1. + y / (double)DIV ) ) break;
      y /= (double)DIV;
   }
   printf( "для double\t: %e (число итераций %d)\n", y, i );
   for( i = 0; ; i++ ) {
      if( ( (long double)1. + z ) == ( (long double)1. + z / (long double)DIV ) ) break;
      z /= (long double)DIV;
   }
   printf( "для long double\t: %Le (число итераций %d)\n", z, i );
}

И вот вам результат:

Код: Выделить всё

olej@notebook:~/2014_WORK/AntonG/examples.draft$ ./type 1 2
01 ---------------------------------------
точность представления вещественных типов:
       float[ 4 байт] :  3.141592653590 -  3.141592741013 = -8.742278000367e-08
      double[ 8 байт] :  3.141592653590 -  3.141592653590 = 1.225148454909e-16
 long double[12 байт] :  3.141592653590 -  3.141592653590 = 0.000000000000e+00
02 ---------------------------------------
максимальная точность итерационных вычислений:
для float	: 1.000000e-08 (число итераций 8)
для double	: 1.000000e-16 (число итераций 16)
для long double	: 1.000000e-20 (число итераций 20)
------------------------------------------

Здесь интересно то, например, что если вы задумаете в представлении float: вычислять значение спецфункции в виде ряда, решать итерационно нелинейное уравнение, искать экстремумы функции ... но закажите при этом относительную погрешность сходимости (прекращения итераций) как 1e-9, то ваш алгоритм вообще никогда не закончится , и вовсе не потому, что он неправильно записан (долго ошибку искать можно! ), а потому, что это просто недостижимая точность.

И то же самое, но не для GCC, а для Clang:

Код: Выделить всё

olej@notebook:~/2014_WORK/AntonG/examples.draft$ make typel
clang -xc -Wall -lm -O 1.c -o typel

olej@notebook:~/2014_WORK/AntonG/examples.draft$ ./typel 1 2
01 ---------------------------------------
точность представления вещественных типов:
       float[ 4 байт] :  3.141592653590 -  3.141592741013 = -8.742278000367e-08
      double[ 8 байт] :  3.141592653590 -  3.141592653590 = 1.225148454909e-16
 long double[12 байт] :  3.141592653590 -  3.141592653590 = 0.000000000000e+00
02 ---------------------------------------
максимальная точность итерационных вычислений:
для float	: 9.999999e-09 (число итераций 8)
для double	: 1.000000e-16 (число итераций 16)
для long double	: 1.000000e-20 (число итераций 20)
------------------------------------------

[Olej]

Итоги того, что обсуждалось здесь в теме на 7-ми страницах форумного обсуждения, оформлены внятным текстом и выложены здесь: язык C: неизвестное о известном.

(Примеры кода там - не эквивалентны примерам здесь. Но они во многом пересекаются ... переписаны, выправлены и выверены.)