Книга: Linux программирование в примерах

6.2.1.1. Пример: сортировка сотрудников

6.2.1.1. Пример: сортировка сотрудников

Для более сложных структур требуются более сложные функции. Например, рассмотрите следующую (довольно тривиальную) struct employee:

struct employee {
char lastname[30];
char firstname[30];
long emp_id;
time_t start_date;
};

Мы могли бы написать функцию для сортировки сотрудников по фамилии, имени и идентификационному номеру:

int emp_name_id_compare(const void *e1p, const void *e2p) {
 const struct employee *e1, *e2;
 int last, first;
 e1 = (const struct employee*)e1p; /* Преобразовать указатели */
 e2 = (const struct employee*)e2p;
 if ((last = strcmp(e1->lastname, e2->lastname)) != 0)
  /* Сравнить фамилии */
  return last; /* Фамилии различаются */
 /* фамилии совпадают, сравнить имена */
 if ((first = strcmp(e1->firstname, e2->firstname)) != 0)
  /* Сравнить имена */
  return first; /* Имена различаются */
 /* имена совпадают, сравнить номера ID */
 if (e1->emp_id < e2->emp_id) /* Сравнить ID сотрудника */
  return -1;
 else if (e1->emp_id == e2->emp_id)
  return 0;
 else
  return 1;
}

Логика здесь проста: сначала сравниваются фамилии, затем имена, а затем номера ID, если два имени совпадают. Используя для строк strcmp(), мы автоматически получаем правильное отрицательное/нулевое/положительное значение для возвращения.

При сравнении ID сотрудников нельзя просто использовать вычитание: представьте, что long 64-разрядный, а int 32-разрядный, а два значения отличаются лишь в старших 32 битах (скажем, младшие 32 бита равны нулю). В таком случае вычитание автоматически привело бы к приведению типа к int с отбрасыванием старших 32 битов и возвращением неверного результата.

ЗАМЕЧАНИЕ. Возможно, мы остановились при сравнении имен, в этом случае все сотрудники с совпадающими фамилиями и именами оказались бы сгруппированы, но никак не отсортированы

Это важный момент qsort() не гарантирует стабильной сортировки. Стабильна сортировка, в которой, если два элемента равны на основе значения какого-либо ключа(-ей), они сохраняют свой первоначальный порядок друг относительно друга в конечном отсортированном массиве. Например, рассмотрите трех сотрудников с одинаковыми фамилиями и именами и с номерами 17, 42 и 81. Их порядок в первоначальном массиве. возможно, был 42, 81 и 17 (Что означает, что сотрудник 42 находится по индексу с меньшим значением, чем сотрудник 81, который, в свою очередь, находится по индексу с меньшим значением, чем сотрудник 17). После сортировки порядок может оказаться 81, 42 и 17. Если ото представляет проблему, процедура сравнения должна рассматривать все важные ключевые значения (Наша так и делает.)

Просто используя другую функцию, мы можем отсортировать сотрудников по старшинству:

int emp_seniority_compare(const void *e1p,
 const void *e2p) {
 const struct employee *e1, *e2;
 double diff;
 /* Привести указатели к нужному типу */
 e1 = (const struct employee*)e1p;
 e2 = (const struct employee*)e2p;
 /* Сравнить времена */
 diff = difftime(e1->start_date, e2->start_date);
 if (diff < 0)
  return -1;
 else if (diff > 0)
  return 1;
 else
  return 0;
}

Для максимальной переносимости мы использовали difftime(), которая возвращает разницу в секундах между двумя значениями time_t. Для данного конкретного случая приведение, такое, как

return (int)difftime(e1->start_date, e2->start_date);

должно сработать, поскольку значения time_t находятся в приемлемом диапазоне. Тем не менее, мы вместо этого использовали полный трехсторонний оператор if, просто из предосторожности.

Вот пример файла данных со списком пяти президентов США:

$ cat presdata.txt
/* Фамилия, имя, номер президента, инаугурация */
Bush George 43 980013600
Clinton William 42 727552800
Bush George 41 601322400
Reagan Ronald 40 348861600
Carter James 39 222631200

В ch06-sortemp.c приведена простая программа, которая считывает этот файл в массив struct employee, а затем сортирует его, используя две только что представленные функции сравнения.

1   /* ch06-sortemp.c --- Демонстрирует qsort() с двумя функциями сравнения. */
2

3   #include <stdio.h>
4   #include <stdlib.h>
5   #include <time.h>
6
7   struct employee {
8    char lastname[30];
9    char firstname[30];
10   long emp_id;
11   time_t start_date;
12  };
13
14  /* emp_name_id_compare --- сравнение по имени, затем no ID */
15
16  int emp_name_id_compare(const void *e1p, const void *e2p)
17  {
     /* ...как показано ранее, опущено для экономии места... */
39  }
40
41  /* emp_seniority_compare --- сравнение по старшинству */
42
43  int emp_seniority_compare(const void *e1p, const void *e2p)
44  {
     /* ...как показано ранее, опущено для экономии места... */
58  }
59
60  /* main --- демонстрация сортировки */
61
62  int main(void)
63  {
64   #define NPRES 10
65   struct employee presidents[NPRES];
66   int i, npres;
67   char buf[BUFSIZ];
68
69   /* Очень простой код для чтения данных: */
70   for (npres = 0; npres < NPRES && fgets(buf, BUFSIZ, stdin) != NULL;
71    npres++) {
72    sscanf(buf, "%s %s %ld %ldn",
73     presidents[npres].lastname,
74     presidents[npres].firstname,
75     &presidents[npres].emp_id,
76     &presidents[npres].start_date);
77   }
78
79   /* npres теперь содержит число прочитанных строк. */
80
81   /* Сначала сортировка по имени */
82   qsort(presidents, npres, sizeof(struct employee), emp_name_id_compare);
83
84   /* Вывести результат */
85   printf("Sorted by name:n");
86   for (i = 0; i < npres; i++)
87    printf("t%s %st%dt%s",
88     presidents[i].lastname,
89     presidents[i].firstname,
90     presidents[i].emp_id,
91     ctime(&presidents[i].start_date));
92
93   /* Теперь сортировка по старшинству */
94   qsort(presidents, npres, sizeof(struct employee), emp_seniority_compare);
95
96   /* И снова вывести */
97   printf("Sorted by seniority:n");
98   for (i = 0; i < npres; i++)
99    printf("t%s %st%dt%s",
100    presidents[i].lastname,
101    presidents!i].firstname,
102    presidents[i].emp_id,
103    ctime(&presidents[i].start_date));
104 }

Строки 70–77 считывают данные. Обратите внимание, что любое использование scanf() требует от входных данных «хорошего поведения». Если, например, какое-нибудь имя содержит более 29 символов, возникает проблема. В данном случае, мы вне опасности, но в коде изделия нужно быть гораздо более осмотрительным.

Строка 82 сортирует данные по имени и по ID сотрудника, а затем строки 84–91 выводят отсортированные данные. Сходным образом строка 94 пересортировывает данные, на этот раз по старшинству, а строки 97–103 выводят результаты. После компилирования и запуска программа выдает следующие результаты:

$ ch06-sortemp < presdata.txt
Sorted by name:
  Bush George 41 Fri Jan 20 13:00:00 1989
  Bush George 43 Sat Jan 20 13:00:00 2001
  Carter James 39 Thu Jan 20 13:00:00 1977
  Clinton William 42 Wed Jan 20 13:00:00 1993
  Reagan Ronald 40 Tue Jan 20 13:00:00 1981
Sorted by seniority:
  Carter James 39 Thu Jan 20 13:00:00 1977
  Reagan Ronald 40 Tue Jan 20 13:00:00 1981
  Bush George 41 Fri Jan 20 13:00:00 1989
  Clinton William 42 Wed Jan 20 13:00:00 1993
  Bush George 43 Sat Jan 20 13:00:00 2001

(Мы использовали 1 час пополудни как приблизительное время, когда все президенты начали работать.)[66]

Стоит заметить одну вещь: qsort() переставляет данные в массиве. Если каждый элемент массива представляет собой большую структуру, при сортировке массива большое количество данных будут копироваться туда-сюда. Вместо этого может оказаться выгодным создать отдельный массив указателей, каждый из которых указывает на один элемент массива. Затем использовать qsort() для сортировки массива указателей, получая доступ к несортированным данным через сортированные указатели.

Платой за это является дополнительная память для размещения указателей и модификация функций сравнения для дополнительного перенаправления указателей при сравнении структур. Полученной выгодой может стать значительное ускорение работы, поскольку на каждом шаге перемещается лишь четырех- или восьмибайтный указатель вместо большой структуры. (Наша struct employee имеет размер по крайней мере 68 байтов. При обмене четырехбайтных указателей перемещается в 17 раз меньше данных, чем при обмене структур.) Для тысяч размещенных в памяти структур разница мажет быть существенной.

ЗАМЕЧАНИЕ. Если вы являетесь программистом С++, знайте! qsort() может быть опасной для использования с массивами объектов! qsort() осуществляет простые перемещения памяти, копируя байты. Она совершенно ничего не знает о конструкциях С++, таких, как конструкторы копирования или функции operator=(). Вместо этого используйте одну из функций сортировки STL[67] или используйте методику отдельного массива указателей.

Оглавление книги


Генерация: 1.307. Запросов К БД/Cache: 3 / 0
поделиться
Вверх Вниз