Два слова: двоичный поиск aka BINARY SEARCH

При разработке отчётных форм часто возникают задачи по их оптимизации. C’est la vie, возникают они уже на стадии продуктивной эксплуатации, потому что в тестовой среде нечасто заботит обработка больших объёмов данных.

Для примера, все разработчики ABAP должны знать о проблемах вложенных LOOP.

Сегодня речь несколько другом примере:

loop at lt_anlp.
  read table gt_report assigning <gs_report>
    with key bukrs = lt_anlp-bukrs 
             anln1 = lt_anlp-anln1 
             anln2 = lt_anlp-anln2.
  check sy-subrc = 0.
  …
  <gs_report>-fig_h_knafa = … lt_anlp-knafa …
endloop.

Так что же с ним не то?

Если записей в обеих таблицах много, то накладные расходы на операцию READ TABLE становятся очень высокими, так как в случае использования стандартных таблиц будет применяться линейный поиск. При этом можно предположить, что с ростом таблицы время выполнения будет расти нелинейно.

Тут всех спасёт включение двоичного поиска вместо линейного. Добавляем слова:

read table gt_report_det assigning <gs_report_det>
  with key bukrs = lt_anlp-bukrs 
           anln1 = lt_anlp-anln1 
           anln2 = lt_anlp-anln2
  binary search.

 

Кто не знает что это такое в принципе – мигом бегут учить матчасть.

В моём условном примере на 300к + 50к записей я получил практически сразу сорокократный (SIC!) общий прирост производительности: 23 секунды против 910 секунд. В отчёте есть ещё много разных вычислений, поэтому можно предположить что скорость работы именно этого блока могла вырасти и более чем в сорок раз.

Невероятно? Но знающие матчасть легко посчитают, что используя двоичный поиск найти последний элемент в таблице с 50к записей можно за 16 итераций, тогда как линейный поиск найдёт последний элемент за …(барабанная дробь)… 50 000 итераций.

 

PS. Да, в пренебрегаю расходами на вычисление и сравнение.

PPS. Да, таблицу надо предварительно отсортировать по ключу поиска.

PPPS. Да, есть не только стандартные таблицы.

Опубликовано 09.08.2014 в 10:42 · Автор ivan · Ссылка
Рубрики: ABAP

Написать комментарий