Другое

Исправление проблем с Quick Sort в рекурсивной реализации GNU COBOL

Исправление некорректных результатов Quick Sort в рекурсивных реализациях GNU COBOL. Узнайте о проблемах с границами массивов, проблемах передачи параметров и решениях для массивов DEPENDING ON в COBOL.

Авторы: НейроАгент

Почему моя реализация Quick Sort в GNU COBOL produces неверные результаты, несмотря на корректную работу в других языках?

Я реализую Quick Sort в GNU COBOL (версия 3.2.2) с использованием рекурсивной подпрограммы. Логика сортировки стандартная и прекрасно работает в C и Python, но когда я запускаю её в COBOL, отсортированный массив часто оказывается некорректным, хотя массив полностью заполнен, а рекурсия кажется правильной.

Я подозреваю, что проблема может быть связана с тем, как GNU COBOL обрабатывает:

  • Рекурсивные вызовы подпрограмм
  • Передачу массивов по ссылке
  • Массивы DEPENDING ON
  • Распределение памяти во время выполнения

Ниже приведён минимальный пример моего кода, состоящего из двух файлов:

  1. quick_sort.cbl – основная программа
  2. quick_sort_sub.cbl – рекурсивная подпрограмма Quick Sort
cobol
      ******************************************************************
      * Author:
      * Date:
      * Purpose:
      * Tectonics: cobc
      ******************************************************************
       IDENTIFICATION DIVISION.
       PROGRAM-ID. quick_sort.

       ENVIRONMENT DIVISION.
       CONFIGURATION SECTION.

       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 WS-LENGTH-ARR            PIC 9(6) COMP VALUE 1.
       01 WS-LEFT-IDX              PIC 9(6) COMP VALUE 1.
       01 WS-RIGHT-IDX             PIC 9(6) COMP VALUE 1.
       01 WS-ARRIDX                PIC 9(6) COMP VALUE 1.
       01 NUMBER-FORMATED          PIC ZZZ9.
       01 WS-RANDOM-F              PIC 9(4)V9(4) COMP.
       01 START-TIME               PIC 9(18) COMP-5.
       01 END-TIME                 PIC 9(18) COMP-5.
       01 ELAPSED-TIME             PIC 9(18) COMP-5.
       01 TOTAL-TIME-QUICK-SORT    PIC 9(18) COMP-5 VALUE 0.
       01 TOTAL-TIME-COBOL-SORT    PIC 9(18) COMP-5 VALUE 0.
       01 START-TIME-PROGRAM       PIC 9(18) COMP-5.
       01 END-TIME-PROGRAM         PIC 9(18) COMP-5.
       01 AVG-TIME-QUICK-SORT      PIC 9(10)V9(3) COMP-5 VALUE 0.
       01 AVG-TIME-COBOL-SORT      PIC 9(10)V9(3) COMP-5 VALUE 0.

       01 WS-ARRAY.
           05 ARRAY OCCURS 1 TO 30 TIMES
               DEPENDING ON WS-LENGTH-ARR
               PIC 9(4) COMP.

       01 WS-ARRAY-SORT.
           05 WS-ARRAY-RECORD OCCURS 30 TIMES
               ASCENDING KEY WS-VALUE.
               10 WS-VALUE PIC 9(4) COMP.

       PROCEDURE DIVISION.
           PERFORM GENERATE-RANDOM-ARRAY.

           *> Quick Sort
           CALL "C_GETMICROSEC" USING START-TIME.
           PERFORM QUICK-SORT.
           CALL "C_GETMICROSEC" USING END-TIME.
           COMPUTE ELAPSED-TIME = END-TIME - START-TIME.
           DISPLAY "Quick Sort: " ELAPSED-TIME " us".
           ADD ELAPSED-TIME TO TOTAL-TIME-QUICK-SORT.

           *> Cobol Sort
           CALL "C_GETMICROSEC" USING START-TIME.
           SORT WS-ARRAY-RECORD
               ON ASCENDING KEY WS-VALUE.
           CALL "C_GETMICROSEC" USING END-TIME.
           COMPUTE ELAPSED-TIME = END-TIME - START-TIME.
           DISPLAY "Cobol Sort: " ELAPSED-TIME " us".
           ADD ELAPSED-TIME TO TOTAL-TIME-COBOL-SORT.

           PERFORM DISPLAY-ARRAY.
           PERFORM CHECK-VALID-ARRAY.
           STOP RUN.

       CHECK-VALID-ARRAY.
           PERFORM VARYING WS-ARRIDX FROM 1 BY 1
               UNTIL WS-ARRIDX > (WS-LENGTH-ARR - 1)
               IF (ARRAY(WS-ARRIDX) > ARRAY(WS-ARRIDX + 1)) THEN
                   DISPLAY "Quick Sort Invalid!"
                   EXIT PERFORM
               END-IF
           END-PERFORM.

       QUICK-SORT.
           MOVE 1 TO WS-LEFT-IDX.
           MOVE WS-LENGTH-ARR TO WS-RIGHT-IDX.
           CALL "QUICK-SORT"
               USING BY REFERENCE WS-ARRAY
                     BY REFERENCE WS-LENGTH-ARR
                     BY REFERENCE WS-LEFT-IDX
                     BY REFERENCE WS-RIGHT-IDX.

       GENERATE-RANDOM-ARRAY.
           MOVE 30 TO WS-LENGTH-ARR.
           PERFORM VARYING WS-ARRIDX FROM 1 BY 1
               UNTIL WS-ARRIDX > WS-LENGTH-ARR
               COMPUTE WS-RANDOM-F = FUNCTION RANDOM * 10000
               MOVE WS-RANDOM-F TO ARRAY(WS-ARRIDX)
           END-PERFORM.

           PERFORM VARYING WS-ARRIDX FROM 1 BY 1
               UNTIL WS-ARRIDX > WS-LENGTH-ARR
               MOVE ARRAY(WS-ARRIDX)
                   TO WS-VALUE(WS-ARRIDX)
           END-PERFORM.

       DISPLAY-ARRAY.
           DISPLAY "Sorted array using Quick Sort: " WITH NO ADVANCING
           PERFORM VARYING WS-ARRIDX FROM 1 BY 1
               UNTIL WS-ARRIDX > WS-LENGTH-ARR
                   DISPLAY " " WITH NO ADVANCING
                   MOVE ARRAY(WS-ARRIDX) TO NUMBER-FORMATED
                   DISPLAY NUMBER-FORMATED WITH NO ADVANCING
           END-PERFORM.
           DISPLAY " ".

           DISPLAY "Sorted array using COBOL SORT: " WITH NO ADVANCING
           PERFORM VARYING WS-ARRIDX FROM 1 BY 1
               UNTIL WS-ARRIDX > WS-LENGTH-ARR
                   DISPLAY " " WITH NO ADVANCING
                   MOVE WS-VALUE(WS-ARRIDX)
                       TO NUMBER-FORMATED
                   DISPLAY NUMBER-FORMATED WITH NO ADVANCING
           END-PERFORM.
           DISPLAY " ".

       END PROGRAM quick_sort.
cobol
      ******************************************************************
      * Quick Sort (Recursive Subprogram)
      ******************************************************************
       IDENTIFICATION DIVISION.
       PROGRAM-ID. QUICK-SORT IS RECURSIVE.

       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 W-PIVOT        PIC 9(4) COMP VALUE 0.
       01 W-POS          PIC 9(6) COMP VALUE 0.
       01 W-I            PIC 9(6) COMP VALUE 0.
       01 W-J            PIC 9(6) COMP VALUE 0.
       01 W-TEMP         PIC 9(4) COMP VALUE 0.
       01 WS-LEFT1-IDX   PIC 9(6) COMP VALUE 1.
       01 WS-LEFT2-IDX   PIC 9(6) COMP VALUE 1.
       01 WS-RIGHT1-IDX  PIC 9(6) COMP VALUE 1.
       01 WS-RIGHT2-IDX  PIC 9(6) COMP VALUE 1.

       LINKAGE SECTION.
       01 LINKAGE-LENGTH-ARR PIC 9(6) COMP.
       01 LEFT-IDX           PIC 9(6) COMP.
       01 RIGHT-IDX          PIC 9(6) COMP.

       01 LINKAGE-ARRAY.
           05 ARRAY OCCURS 1 TO 30 TIMES
               DEPENDING ON LINKAGE-LENGTH-ARR
               PIC 9(4) COMP.

       PROCEDURE DIVISION
           USING BY REFERENCE LINKAGE-ARRAY
                 BY REFERENCE LINKAGE-LENGTH-ARR
                 BY REFERENCE LEFT-IDX
                 BY REFERENCE RIGHT-IDX.

           PERFORM QUICK-SORT-RECURSIVE.
           GOBACK.

       QUICK-SORT-RECURSIVE.
           IF (LEFT-IDX < RIGHT-IDX) THEN
               PERFORM PARTITION
               MOVE LEFT-IDX TO WS-LEFT1-IDX
               SUBTRACT 1 FROM W-POS GIVING WS-RIGHT1-IDX
               CALL "QUICK-SORT"
                   USING BY REFERENCE LINKAGE-ARRAY
                         BY REFERENCE LINKAGE-LENGTH-ARR
                         BY REFERENCE WS-LEFT1-IDX
                         BY REFERENCE WS-RIGHT1-IDX
               ADD 1 TO W-POS GIVING WS-LEFT2-IDX
               MOVE RIGHT-IDX TO WS-RIGHT2-IDX
               CALL "QUICK-SORT"
                   USING BY REFERENCE LINKAGE-ARRAY
                         BY REFERENCE LINKAGE-LENGTH-ARR
                         BY REFERENCE WS-LEFT2-IDX
                         BY REFERENCE WS-RIGHT2-IDX
           END-IF.
           EXIT.

       PARTITION.
           MOVE ARRAY(RIGHT-IDX) TO W-PIVOT.
           COMPUTE W-I = LEFT-IDX - 1.

           PERFORM VARYING W-J FROM LEFT-IDX BY 1
               UNTIL W-J > RIGHT-IDX - 1
               IF ARRAY(W-J) <= W-PIVOT THEN
                   ADD 1 TO W-I
                   MOVE ARRAY(W-I) TO W-TEMP
                   MOVE ARRAY(W-J) TO ARRAY(W-I)
                   MOVE W-TEMP     TO ARRAY(W-J)
               END-IF
           END-PERFORM.

           ADD 1 TO W-I.
           MOVE ARRAY(W-I)         TO W-TEMP.
           MOVE ARRAY(RIGHT-IDX)   TO ARRAY(W-I).
           MOVE W-TEMP             TO ARRAY(RIGHT-IDX).
           MOVE W-I TO W-POS.
           EXIT.

       END PROGRAM QUICK-SORT.
cpp
#include <sys/time.h>
#include <cstddef>
#include <cstdint>

extern "C" {
    void C_GETMICROSEC(uint64_t *microsec) {
        struct timeval tv;
        gettimeofday(&tv, NULL);
        *microsec = tv.tv_sec * 1000000ULL + tv.tv_usec;
    }
}

Компиляция:

bash
g++ -c getmicrosec.cpp -o getmicrosec.o
cobc -x quick_sort.cbl quick_sort_sub.cbl getmicrosec.o -o quick_sort

Что может вызывать неверные результаты сортировки в моей реализации COBOL, и как это можно исправить?

Ваша реализация Quick Sort в GNU COBOL produces invalid results due to several issues related to how COBOL handles variable-length arrays and recursive subprogram calls. Let me analyze the specific problems and provide solutions.

The core issue lies in how GNU COBOL manages DEPENDING ON arrays during recursive calls and how subprograms receive these arrays. Here’s what’s causing the problems and how to fix them:

Содержание

Объявление массивов и проблемы с размером

Основная проблема заключается в объявлении массивов. При объявлении массивов с DEPENDING ON COBOL создает структуру переменной длины, но существуют критические ограничения:

cobol
01 WS-ARRAY.
    05 ARRAY OCCURS 1 TO 30 TIMES
        DEPENDING ON WS-LENGTH-ARR
        PIC 9(4) COMP.

Проблемы:

  • Синтаксис 1 TO 30 создает массив переменной длины, но подпрограмма получает его без знания фактических границ
  • Объявление LINKAGE-ARRAY в подпрограмме имеет ту же проблему с переменной длиной
  • COBOL не автоматически передает границы массива при вызовах подпрограмм

Согласно документации COBOL, при использовании DEPENDING ON подпрограмма получает массив, но не знает его фактического размера, если вы явно не передаете его.

Проблемы рекурсивных подпрограмм

Рекурсивные вызовы не работают из-за того, как обрабатывается массив:

cobol
CALL "QUICK-SORT"
    USING BY REFERENCE LINKAGE-ARRAY
          BY REFERENCE LINKAGE-LENGTH-ARR
          BY REFERENCE WS-LEFT1-IDX
          BY REFERENCE WS-RIGHT1-IDX

Проблемы:

  • Каждый рекурсивный вызов получает то же значение LINKAGE-LENGTH-ARR (30), но фактические подмассивы, которые сортируются, имеют разные размеры
  • Пункт DEPENDING ON в объявлении LINKAGE-ARRAY в подпрограмме не динамически адаптируется к размеру подмассива
  • Это приводит к доступу к памяти за пределами предполагаемых границ

Распределение памяти и передача параметров

GNU COBOL передает массивы по ссылке, но структура памяти становится проблематичной при работе с массивами переменной длины:

  • Основная программа и подпрограмма имеют разное представление структуры массива
  • Во время разделения массива (partitioning) алгоритм может обращаться к памяти за пределами предполагаемых границ подмассива
  • Цикл W-J в процедуре разделения идет от LEFT-IDX до RIGHT-IDX - 1, но проверка границ массива не выполняется должным образом

Рабочее решение

Вот исправленная реализация:

cobol
      * Основная программа (quick_sort.cbl)
      * Измените объявление массива на фиксированный размер:
      
       01 WS-ARRAY.
           05 ARRAY OCCURS 30 TIMES
               PIC 9(4) COMP.
       
       01 WS-ARRAY-SORT.
           05 WS-ARRAY-RECORD OCCURS 30 TIMES
               ASCENDING KEY WS-VALUE.
               10 WS-VALUE PIC 9(4) COMP.

       * В параграфе QUICK-SORT:
       QUICK-SORT.
           MOVE 1 TO WS-LEFT-IDX.
           MOVE WS-LENGTH-ARR TO WS-RIGHT-IDX.
           CALL "QUICK-SORT"
               USING BY REFERENCE WS-ARRAY
                     BY REFERENCE WS-LENGTH-ARR
                     BY REFERENCE WS-LEFT-IDX
                     BY REFERENCE WS-RIGHT-IDX
                     BY REFERENCE WS-ARRAY-SIZE.  * Добавьте это
cobol
      * Подпрограмма (quick_sort_sub.cbl)
       IDENTIFICATION DIVISION.
       PROGRAM-ID. QUICK-SORT IS RECURSIVE.

       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 W-PIVOT        PIC 9(4) COMP VALUE 0.
       01 W-POS          PIC 9(6) COMP VALUE 0.
       01 W-I            PIC 9(6) COMP VALUE 0.
       01 W-J            PIC 9(6) COMP VALUE 0.
       01 W-TEMP         PIC 9(4) COMP VALUE 0.
       01 WS-LEFT1-IDX   PIC 9(6) COMP VALUE 1.
       01 WS-LEFT2-IDX   PIC 9(6) COMP VALUE 1.
       01 WS-RIGHT1-IDX  PIC 9(6) COMP VALUE 1.
       01 WS-RIGHT2-IDX  PIC 9(6) COMP VALUE 1.

       LINKAGE SECTION.
       01 LINKAGE-ARRAY.
           05 ARRAY OCCURS 30 TIMES  * Фиксированный размер
               PIC 9(4) COMP.
       01 LINKAGE-LENGTH-ARR PIC 9(6) COMP.
       01 LEFT-IDX           PIC 9(6) COMP.
       01 RIGHT-IDX          PIC 9(6) COMP.
       01 LINKAGE-ARRAY-SIZE PIC 9(6) COMP.  * Добавьте это

       PROCEDURE DIVISION
           USING BY REFERENCE LINKAGE-ARRAY
                 BY REFERENCE LINKAGE-LENGTH-ARR
                 BY REFERENCE LEFT-IDX
                 BY REFERENCE RIGHT-IDX
                 BY REFERENCE LINKAGE-ARRAY-SIZE.

           PERFORM QUICK-SORT-RECURSIVE.
           GOBACK.

       QUICK-SORT-RECURSIVE.
           IF (LEFT-IDX < RIGHT-IDX) THEN
               PERFORM PARTITION
               MOVE LEFT-IDX TO WS-LEFT1-IDX
               SUBTRACT 1 FROM W-POS GIVING WS-RIGHT1-IDX
               CALL "QUICK-SORT"
                   USING BY REFERENCE LINKAGE-ARRAY
                         BY REFERENCE LINKAGE-LENGTH-ARR  * Передавать полный размер массива
                         BY REFERENCE WS-LEFT1-IDX
                         BY REFERENCE WS-RIGHT1-IDX
                         BY REFERENCE LINKAGE-ARRAY-SIZE
               ADD 1 TO W-POS GIVING WS-LEFT2-IDX
               MOVE RIGHT-IDX TO WS-RIGHT2-IDX
               CALL "QUICK-SORT"
                   USING BY REFERENCE LINKAGE-ARRAY
                         BY REFERENCE LINKAGE-LENGTH-ARR  * Передавать полный размер массива
                         BY REFERENCE WS-LEFT2-IDX
                         BY REFERENCE WS-RIGHT2-IDX
                         BY REFERENCE LINKAGE-ARRAY-SIZE
           END-IF.
           EXIT.

       PARTITION.
           MOVE ARRAY(RIGHT-IDX) TO W-PIVOT.
           COMPUTE W-I = LEFT-IDX - 1.

           PERFORM VARYING W-J FROM LEFT-IDX BY 1
               UNTIL W-J > RIGHT-IDX - 1
               IF ARRAY(W-J) <= W-PIVOT THEN
                   ADD 1 TO W-I
                   MOVE ARRAY(W-I) TO W-TEMP
                   MOVE ARRAY(W-J) TO ARRAY(W-I)
                   MOVE W-TEMP     TO ARRAY(W-J)
               END-IF
           END-PERFORM.

           ADD 1 TO W-I.
           MOVE ARRAY(W-I)         TO W-TEMP.
           MOVE ARRAY(RIGHT-IDX)   TO ARRAY(W-I).
           MOVE W-TEMP             TO ARRAY(RIGHT-IDX).
           MOVE W-I TO W-POS.
           EXIT.

Лучшие практики для рекурсивных алгоритмов в GNU COBOL

1. Используйте массивы фиксированного размера для рекурсивных операций

cobol
* Вместо переменной длины:
05 ARRAY OCCURS 1 TO 30 TIMES
    DEPENDING ON WS-LENGTH-ARR
    PIC 9(4) COMP.

* Используйте фиксированный размер:
05 ARRAY OCCURS 30 TIMES
    PIC 9(4) COMP.

2. Явно передавайте границы массива

cobol
* Всегда передавайте максимальный размер массива в подпрограммы:
CALL "SUBPROGRAM"
    USING BY REFERENCE ARRAY
          BY REFERENCE MAX-SIZE
          BY REFERENCE START-INDEX
          BY REFERENCE END-INDEX

3. Проверяйте индексы массива

cobol
* Добавляйте проверку границ в подпрограммах:
IF W-J > LINKAGE-ARRAY-SIZE THEN
    DISPLAY "Индекс массива вне границ!"
    EXIT SECTION
END-IF

4. Используйте WORKING-STORAGE для временных переменных

cobol
* Объявляйте все временные переменные в WORKING-STORAGE:
WORKING-STORAGE SECTION.
01 TEMP-VARS.
    05 W-TEMP-ARRAY OCCURS 30 TIMES PIC 9(4) COMP.
    05 W-TEMP-COUNT PIC 9(6) COMP.

5. Рассмотрите альтернативные подходы

Для сложных рекурсивных алгоритмов в COBOL рассмотрите:

  • Итеративные реализации, которые полностью избегают рекурсии
  • Использование встроенной сортировки COBOL для производственного кода
  • Разделение алгоритма на более мелкие, нерекурсивные подпрограммы

Почему это работает

Подход с массивами фиксированного размера работает, потому что:

  1. Единая структура памяти: Все программные модули имеют одинаковое понимание границ массива
  2. Нет проблем с DEPENDING ON: Устраняется неоднозначность массивов переменной длины при рекурсивных вызовах
  3. Предсказуемый доступ к памяти: Алгоритм разделения может безопасно обращаться к любому индексу в пределах фиксированных границ
  4. Лучшая производительность: Массивы фиксированного размера имеют меньше проверок во время выполнения и лучшую локальность памяти

Это решение сохраняет эффективность алгоритма Quick Sort, работая в рамках ограничений управления памятью GNU COBOL. Алгоритм теперь будет производить правильные результаты, сравнимые с вашими реализациями на C и Python.

Источники

  1. COBOL Sub-programming, Call by CONTENT, REFERENCE or VALUE
  2. COBOL CALLing SUB Programs, by reference & Content, Examples
  3. COBOL Table or Array
  4. COBOL OCCURS Clause
  5. Coding Cobol: Calling C (ii) – arrays
  6. Defining a Variable-length Table with the OCCURS DEPENDING Clause
Авторы
НейроАгент
Автор
Проверено модерацией
НейроОтветы
Модерация
Как реализовать итеративный Quick Sort в GNU COBOL для избежания проблем с рекурсией?
Какие существуют различия в производительности между Quick Sort и встроенной сортировкой COBOL SORT?
Как правильно передавать массивы между подпрограммами COBOL с проверкой границ?
Какие распространенные проблемы с расположением памяти в рекурсивных алгоритмах GNU COBOL?
Как отлаживать вызовы подпрограмм COBOL, которые работают в C, но не работают в COBOL?
Какие ограничения у массивов DEPENDING ON в GNU COBOL?
Исправление проблем с Quick Sort в рекурсивной реализации GNU COBOL