Меню

Заметки по производительности и смежным вопросам

|

Сортированные внутренние таблицы обеспечивают большую производительность поиска по сравнению со стандартными внутренними таблицами, а именно за счет применения дихотомического алгоритма, который действует так.

2. Дихотомический поиск (bynary search) в стандартной таблице

Многократно говорилось, что сортированные внутренние таблицы обеспечивают большую производительность поиска по сравнению со стандартными внутренними таблицами, а именно за счет применения дихотомического алгоритма, который действует так. Берем среднюю запись. Либо попали, либо нет. Если попали, результат найден. Если не попали, то имеем либо перелет, либо недолет. Если, например перелет, берем нижнюю полутаблицу, если же недолет – верхнюю. Повторяем процедуру для выбранной полутаблицы. Таким образом, на каждом этапе отсекается половина оставшейся работы, и это, конечно, быстрее, чем сплошной просмотр. Это самое «быстрее» быстрее в логарифм от размера раз. Если таблица увеличится в 1000 раз то время поиска увеличится не в 1000 раз а приблизительно на 10 дихотомических шагов (210 = 1024 ~ 1000).

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

REPORT  ZQK002.

data
  : gt type standard table

Если хотите прочитать статью полностью и оставить свои комментарии присоединяйтесь к sapland

У вас уже есть учетная запись?

Войти