Индекс последнего ключа

Yanvladimirovich

Предположим, есть сортированная таблица TABTAB с полями A и B. Таблица содержит, пускай, сто тысяч записей, а в поле A всего несколько уникальных значений, например "1", "7" и "15". Количество записей с этими ключами примерно одинаковое. Вот такой код

Code:

READ TABLE tabtab ASSIGNING <fs_rec> WITH KEY A='7'

установит sy-tabix на первую запись с ключом. Вопрос такой, какой наиболее быстрый способ найти последнюю запись, удовлетворяющую условию?

Если сделать LOOP AT со стартового индекса, то он переберет все записи, это хуже чем log2(n) при бинарном поиске. То есть, имеем в первом случае 17 обращений, во втором - придётся сделать несколько тысяч.

Можно написать ручками, но уж очень не хочется.

Удав

Если есть сортировка по другим полям, то можно при сортировке таблицы указать обратный порядок для поля, следующего в ключе за полем A.
Если сортировки по другим полям нет - искать последнюю запись бессмысленно

ArmAnn

Я вижу тут два варианта:
1. Реализовать свой бинарный поиск, но искать не первую попавшуюся строку, удовлетворяющую условию, а перебирать все подходящие

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

Code:

" Заполняем таблицу так, чтоб строка-маркер оказалась последняя для каждого уникального значения ключа A
wa_tabtab-A = '1'. wa_tabtab-B = '12353'. insert wa_tabtab to table tabtab.
wa_tabtab-A = '1'. wa_tabtab-B = '3578'. insert wa_tabtab to table wa_tabtab.
wa_tabtab-A = '1'. wa_tabtab-B = 'ZZZZZZ'. insert wa_tabtab to table wa_tabtab. 
wa_tabtab-A = '7'. wa_tabtab-B = '3as5'. insert wa_tabtab to table wa_tabtab.
wa_tabtab-A = '7'. wa_tabtab-B = 'hhffg44'. insert wa_tabtab to table wa_tabtab.
wa_tabtab-A = '7'. wa_tabtab-B = '1'. insert wa_tabtab to table wa_tabtab.
wa_tabtab-A = '7'. wa_tabtab-B = 'ZZZZZZ'. insert wa_tabtab to table wa_tabtab. 
wa_tabtab-A = '15'. wa_tabtab-B = 'yhf65'. insert wa_tabtab to table wa_tabtab.
wa_tabtab-A = '15'. wa_tabtab-B = 'ZZZZZZ'. insert wa_tabtab to table wa_tabtab. 


READ TABLE tabtab ASSIGNING <fs_rec> WITH KEY A='7' B = 'ZZZZZZ' binary search.
last_pos = sy-tabix - 1.

Естесственно такие строки при обработке надо не забывать учитывать.
Если нет возможности для создания маркерных строк при текущем наборе полей - то можно добавить поле для маркера, между A и B, если конечно это допустимо по условиям задачи.
Вот, примерно так

demst

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

Code:

READ TABLE tabtab ASSIGNING <fs_rec> WITH KEY A='15' 
last_pos = sy-tabix - 1.

ArmAnn

demst написал(а):

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

Code:

READ TABLE tabtab ASSIGNING <fs_rec> WITH KEY A='15' 
last_pos = sy-tabix - 1.

Если это будет двоичный поиск - то ваш пример не сработает. Если поиск обычный - то будет перебор всех записей до первой с ключом A = 15, а топикстартер хочет быстрого поиска

demst

ArmAnn написал:

Если это будет двоичный поиск - то ваш пример не сработает.

почему не сработает? не понимаю

ArmAnn

demst написал(а):

ArmAnn написал:

Если это будет двоичный поиск - то ваш пример не сработает.

почему не сработает? не понимаю

Read table ищет первую попавшуюся запись, удовлетворяющую заданному условию. В случае обычного (линейного) поиска эта первая попавшаяся и будет первой по списку, а в случае двоичного поиска - найденная запись не обязательно будет первой по списку
Тут есть достаточно подробное описание алгоритма двоичного поиска

Удав

ArmAnn, это теория

А на практике запусти тестовую программу

Code:

REPORT  z_read_binary_search                    .

PARAMETERS: p_cnt TYPE bkpf-gjahr DEFAULT 100,
            p_sub TYPE bkpf-belnr DEFAULT 200.

DATA: BEGIN OF gs_data,
        a TYPE bkpf-gjahr,
        b TYPE bkpf-belnr,
      END OF gs_data,
      gt_data LIKE STANDARD TABLE OF gs_data.

START-OF-SELECTION.

  DO p_cnt TIMES.
    CLEAR gs_data.
    gs_data-a = 2000 + sy-index.
    DO p_sub TIMES.
      gs_data-b = sy-index.
      APPEND gs_data TO gt_data.
    ENDDO.
  ENDDO.

  SORT gt_data BY a b DESCENDING.

  DO p_cnt TIMES.
    gs_data-a = 2000 + ( p_cnt - sy-index + 1 ).
    READ TABLE gt_data INTO gs_data WITH KEY a = gs_data-a
      BINARY SEARCH.

    IF sy-subrc = 0.
      WRITE: / gs_data-a, gs_data-b.
    ENDIF.
  ENDDO.

ArmAnn

Удав написал(а):

ArmAnn, это теория

А на практике запусти тестовую программу

Блин, действительно

Я был не прав, вариант demst'a вполне себе рабочий

Jelena

demst написал(а):

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

Code:

READ TABLE tabtab ASSIGNING <fs_rec> WITH KEY A='15' 
last_pos = sy-tabix - 1.

Тогда нужно еще ставить дополнительную обработку на случай, когда ключ, который мы ищем, последний. Т.е., продолжая пример 1-7-15, такой код найдет последнюю запись с ключом 7. А как вы будете искать запись с ключом 15?

IMHO Удав уже правильно подсказал - надо просто делать сортировку DESCENDING по второму полю. Хотя может я не совсем правильно понимаю условия задачи.

Правила форума

Индекс последнего ключа

Кто сейчас на конференции