«Никогда не поверю!»,
сказала женщина, увидев жирафа».
(поговорка)

Отрадно, что тема произвотиельности на хеш-таблицах заинтересовала абапствующую публику. Устроим еще разок тест ни очем и продолжим злоберманью брехню.

Однократное измерение малопредставительно, а потому протестируем обращение к хешированной внутренней таблице по тысяче раз для различных размеров внутеренней таблицы. Будем записывать результаты каждого измерения, дабы, отранжировав их, получить квантили. Известно, что первое обращение к внутренней таблице происходит дольше, чем остальные, а потому два первых обращения (к последней и первой записям) измерять не будем, и тем, надеюсь, отсеем (незаслуженно презираемые некоторыми абаперами) накладные расходы на всю таблицу, на что бы они там не шли, оставив расходы лишь на каждое отдельное обращение. Для каждого размера будем создавать внутреннюю таблицу заново, предварительно уничтожив предыдущее содержимое и освободив память (команда FREE). Размеры таблиц по-прежнему будем брать как последовательные целые степени двойки. Результаты для каждого размера отсоортируем, определим медиану и крайние квантили: кватрили, децили, сентили. (Поскольку измерений тысяча, максимальное и минимальное значения окажутся и крайними миллилями, но это, конечно непредставительно в силу их единственности). Как все конечно же помнят, между крайними кватрилями попадает половина значений, между крайними децилями 80%, между крайними сентилями 98%. Будем делать все это 1000 раз. Мне представляется важным, чтобы для каждого размера проводилось не по 1000 измерений к одной и той же таблице, но чтобы таблица перестраивалась перед каждым измерением (мы еще помним, что пару первых обращений делаем без измерения времени). Для любителей нормального распределения подсчитаем первый и второй моменты, среднеарифметическое и дисперсию, ну и среднеквадратическое отклонение от среднего. Текст программы приведен ниже.

Можете назвать Злоберманна трусливым койотом, но первые два обращения я не измеряю, а таблицу пересоздаю перед каждой последовательностью из этих трех обращений, то есть 1000 * 2^N раз. Поэтому программа работает несколько неспешно. Для 2^21 ~ 2 миллинов записей программа работала 3 тысячи секунд, для 2^25 ~ 33.5 миллионов – 72 тысячи секунд, то есть несколько менее суток.

Листинги приведены ниже. Видно, что и медиана, и среднеарифметическое значение времени чтения записи из хеш-таблицы таки зависят от размера. Видно, что отклонения в сторону больших времен имеют гораздо больший размах, чем отклонения в меньшую сторону, что, впрочем, не удивитильно, ибо при таком размахе противоположный результат означал бы, что ответ приходит раньше запроса. Возьму на себя смелость обратить внимание на те случаи, когда максимальное значение отличается от медианного в сотни(!) раз. Бытовой аналог этого таков: взять задание на день и вернуться с результатом через год. У заказчика или начальства могут возникнуть вопросы, и не только чисто академический «где черти носили» (что ты там делала, кроме вычисления хэш-функции), но и более практически значимый «на кого работаешь за мою зарплату» (время-то засчитывается на мою операцию READ TABLE).

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

Текст программ приведен ниже. Можно скопировать в свою систему и исполнить. А можно и модифицировать, например, проверить, какое влияние окажет запрет переноса данных (TRANSPORTING NO FIELDS). Заранее предостерегу желающих вычислять моменты высоких порядков и проводить очень большое число измерений: ABAP не работает с целыми числами, большими, чем 2 ^ 31 - 1, но можно использовать другие числовые типы.

И хорошо бы огласить результаты, если это представляется значимым.

Текст проги.

* 006.Perfomance on Hashed Table (1000 tests for each table size)
REPORT  ZQK006.
selection-screen comment /1(80) t_worn.
selection-screen begin of line.
selection-screen comment 1(24)  t_power.
parameters       p_power type i default 8.
selection-screen end of line.
data
: gp_rpt  type i value 1000           " test number
, begin     of gs                     " hashed table line
,   nnn   type n length 12
, end       of gs
, gt      like hashed table of gs with unique key nnn
, begin     of gs_stat                " statistics line
,   no    type int2
,   cnt   type int4
,   rls   type standard table of i    " realisation table
, end       of gs_stat
, gt_stat like standard table of gs_stat with key no
, gp_cnt  type int4                   " hashed table size
, gp_trg  like gs-nnn                 " line to be found
, a type i, b type i, t type i
, list_header type string
.
start-of-selection.
do gp_rpt times.                 " 1000 tests
  do p_power times.              " Each test
    gp_cnt = 2 ** sy-index.
    gp_trg = gp_cnt - 1.
    free gt.
    do gp_cnt times.
      add 1 to gs-nnn.
      insert gs into table gt.
    enddo.
    read table gt into gs with table key nnn = gp_trg.
    read table gt into gs with table key nnn = 1.
    get run time field a.
    read table gt into gs with table key nnn = gp_trg.
    get run time field b.
    t = b - a.                   " Result
    perform result_collection.
  enddo.                         " End of test
enddo.                           " End of 1000 tests
perform result_processing.
uline.

write                            " Legend
  : / 'Count    - Hashed table size = line count'
  , / 'Avg      - Average'
  , / 'Disp     - Dispersion'
  , / 'rMS      - Root mean square '