Реклама:

4. Ключ = В = С, но не равен А

5. Ключ = А, но не равен ни В, ни С

6. Ключ = В, но не равен ни А, ни С

7. Ключ = С, но не равен ни А, ни В

8. Ключ не равен ни А, ни В, ни С

Поэтому основной выбор в структуре программы включал бы восемь возможных выбираемых частей вместо четырех.

Общее правило состоит в том, что полная структура программы будет включать основной выбор из 2П частей, где п - число сопоставляемых входных файлов. Поэтому число выбираемых частей для различных количеств подлежащих сопоставлению входных файлов может быть выражено следу щей таблицей:

Число входных файлов 2 3 4 5 6

Число частей в выборе 4 8 16 32 64

и так далее...

Ясно, что имеет смысл сократить число упорядочиваемых одновременно файлов до количества, поддающегося обработке.

Впрочем, в большинстве практических программ просто не требуется обрабатывать отдельно многие возможные выборы. Если обработка каждого возможного значения ключа несущественна, то в упомянутом выше случае трех входных файлов совсем никакого интереса не будет представлять «нулевая ситуация», т.е. ситуация 8 сопоставимости/несопоставимости. Кроме того, для многих целей обработки в основном идентичны ситуации 5, 6 и 7, поскольку все они представляют случай полного отсутствия сопоставимости между файлами. Поэтому в любом конкретном варианте возникнет возможность существенно сократить размер требуемой программы. Тем не менее полезно уметь начать со стандартной структуры, просто задавшись вопросом: «Сколько файлов мы хотим упорядочить совместно?».

Упорядочение при многих записях на ключ

Предположим теперь, что ситуация слегка усложнилась. У нас по-прежнему есть файл А, состоящий из последовательно отсортированных основных записей с числовым ключом. Но записи в файле В поступают группами. Допускается наличие в файле В нескольких записей с одинаковым значением ключа. Как и раньше, файл В сортируется в порядке возрастания значений ключа, но теперь для каждой основной записи в файле А может найтись более чем одна соответствующая запись транзакции в файле В. Такая ситуация могла бы возникнуть, когда все обновленные в течение месяца транзакции накапливаются и сортируются, а затем используются как входные данные, сопоставляемые с основным файлом.

Теперь структуры данных таковы, как показано на рис. 6.9.

Кинг Д. Создание эффективного программного обеспечения

Рис. 6.9. Структуры данных для многих записей на ключ.

Заметим, что в структуре файла В сопоставляемыми или несопоставляемыми являются группы В-записей. Для этой ситуации получается структура программы, представленная на рис. 6.10.

Кинг Д. Создание эффективного программного обеспечения

Рис. 6.10. Структура программы для упорядочения при многих записях на ключ.

Структурное изложение для этой версии программы упорядочения имеет вид

УПОРЯДОЧЕНИЕ поел

Открыть файлы, Читать А, Читать В Установить Ключ = Min (А, В)

ТЕЛО УПОРЯДОЧЕНИЯ повт пока не Конец-файла в файле

А и файле В

ОБРАБОТКА ГРУППЫ поел

Установить ВЛАКОП значение О ОБРАБОТКА ТЕЛА ГРУППЫ выб услов ключ = А = В ОБРАБОТКА СОПОСТАВЛЯЕМЫХ А + В поел


⇐ Предыдущая страница| |Следующая страница ⇒