Зона кода

А давайте немного попрограммируем...

Задача о временном ключе. Часть 2

C99Решение задач

Это вторая часть статьи, посвящённой решению задачи о временном ключе, краткая формулировка которой приведена ниже.

Последовательность {an}, члены которой являются натуральными числами, задана с помощью рекуррентной формулы an+1 = an + S(an), справедливой при n ≥ 1, где S(n) — это количество единиц в двоичной записи натурального числа n, называемое "контрольной суммой" данного числа (первый член последовательности считается известным). Заданы натуральные числа N и K. Требуется написать программу, вычисляющую aK+1, при условии, что a1 = N.

В первой части уже приведены 3 версии программы, решающие поставленную задачу. Однако производительность этих программ нас не устроила: самая "быстрая" из данных версий обрабатывала максимально возможные (в соответствии с условием задачи) значения N и K в течение примерно 15 секунд, в то время, как программа не должна работать дольше одной секунды. В данной, заключительной части, мы обсудим способы повышения производительности и приведём код соответствующих новых версий программы.

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

Четвёртая версия программы

В идеальной ситуации нужно узнавать контрольные суммы только тех "байтовых" чисел, образующих значение переменной n, которые изменились после последней итерации. Однако выяснение того, какие числа изменились, а какие нет, требует как сохранения "старых" значений этих чисел, так и выполнения операций сравнения. И то, и другое будет забирать процессорное время.

Пытаясь придумать какие-нибудь компромиссные способы оптимизации времени работы программы, я решил "разбить" переменную n, которая в предыдущих программах в каждый момент времени содержит текущий член последовательности, на 2 переменные, скажем, r и s.

Как мы уже установили ранее, для хранения любого члена последовательности (если мы не будем выходить за рамки ограничений, заложенных в условии задачи), всегда можно обойтись пятью байтами. Давайте часть текущего члена последовательности, хранящегося в трёх старших байтах, поместим в переменную r, а часть, содержащуюся в оставшихся двух младших байтах — в переменную s. Например, если значение n равно 0x123456789A, то после такого разбиения в r и s будут содержаться числа 0x123456 и 0x789A соответственно.

Для чего это нужно? Понятно, что содержимое младших байтов будет в ходе итераций меняться чаще, чем старших. Поэтому можно в ходе итераций заниматься модернизацией лишь содержимого двух младших байтов, т. е. переменной s, до тех пор, пока не возникнет переполнения, т. е. пока в третьем байте s не появится единица. Как только это случится, мы модернизируем содержимое старших трёх байтов (т. е. увеличим значение r на единицу), обнулим третий байт s и снова в ходе последующих итераций будем изменять лишь s, не затрагивая r, до тех пор, пока снова не возникнет переполнение.

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

Вот программа, в которой реализована данная идея:

 1.#include <stdio.h>
 2.
 3.#define IN                                     \
 4.            FILE *f = fopen("INPUT.TXT", "r"); \
 5.               fscanf(f, "%llu %u", &n, &k);   \
 6.            fclose(f);
 7.
 8.#define OUT {                                       \
 9.                n = r;                              \
10.                n = (n << 16) + s;                  \
11.                f = fopen("OUTPUT.TXT", "w");       \
12.                fprintf(f, "%llu", n);              \
13.                fclose(f);                          \
14.                return 0;                           \
15.            }
16.
17.const int ar[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
18.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
19.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
20.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
21.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
22.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
23.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
24.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
25.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
26.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
27.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
28.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
29.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
30.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
31.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
32.                  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
33.
34.int main()
35.{
36.    unsigned long long n;
37.    unsigned int k;
38.    IN;
39.    unsigned int r = n >> 16, s = n - (r << 16);
40.    unsigned char *p1 = (unsigned char *) &r, *p2 = p1 + 1, *p3 = p1 + 2;
41.    unsigned char *p4 = (unsigned char *) &s, *p5 = p4 + 1, *p6 = p4 + 2;
42.    int t = ar[*p1] + ar[*p2] + ar[*p3];
43.    for (int i = 0; i < k; i++)
44.    {
45.        s += t + ar[*p4] + ar[*p5];
46.        if (*p6)
47.        {
48.            r++;
49.            t = ar[*p1] + ar[*p2] + ar[*p3];
50.            *p6 = 0;
51.        }
52.    }
53.    OUT;
54.}

Содержимое n перераспределяется по переменным r и s в строке 39. Адреса младших трёх байтов переменной r сохраняем в указателях p1, p2, p3 (стр. 40), а адреса младших трёх байтов переменной s — в указателях p4, p5, p6 (стр. 41). В переменной t сохраняем контрольную сумму значения, хранящегося в r (стр. 42). Она понадобится нам при вычислениях контрольных сумм членов последовательностей в ходе итераций. Отмечу, что теперь текущий член последовательности будет содержаться не в n, а в паре r, s.

Сами итерации реализованы в цикле for (см. стр. 43). На каждой итерации увеличиваем значение s на контрольную сумму текущего члена последовательности (стр. 45), и проверяем, не возникло ли переполнение, т. е., остаётся ли третий байт s нулевым. Если переполнение возникло, т. е. третий байт стал отличен от нуля (стр. 46), то увеличиваем на единицу значение переменной r (стр. 48), обновляем его контрольную сумму (стр. 49) и обнуляем третий байт переменной s (стр. 50).

После завершения цикла выводим в выходной файл результат и завершаем работу программы (стр. 53). Обратите внимание на то, что мы записываем в выходной файл значение переменной n, предварительно сформировав его из значений переменных r и s (см. определение макроса OUT в строках 8-15).

На тех же входных данных, что и в предыдущем случае, программа работает примерно 10 секунд. Таким образом, мы получили выигрыш в 5 секунд по сравнению с третьей версией программы. Но 10 секунд — это на порядок больше, чем требуется. Так что время работы программы нас по-прежнему не устраивает.

Пятая (последняя) версия программы

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

Давайте обратимся к коду предыдущей версии программы. Предположим, что была выполнена 50-я строка кода, т. е. был обнулён третий байт переменной s. Назовём содержимое этой переменной, оказавшееся в ней после данного обнуления, "начальным значением s". Пусть теперь было выполнено такое наименьшее количество итераций цикла for, которое снова привело нас к строке 50. Теперь содержимое переменной s, оказавшееся в ней после обнуления третьего байта, назовём "конечным значением s".

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

Зададимся вопросом: от чего зависит конечное значение s? Во-первых, от начального значения s, а, во-вторых, от того значения переменной t, которое было обновлено непосредственно перед первым из двух рассматриваемых нами обнулений третьего байта переменной s (см. стр. 49). Это значение t было неизменным в ходе всех обновлений значений переменной s (см. стр. 45), "попавших" в промежуток между двумя обнулениями третьего байта s. Больше начальное значение s не зависит ни от чего!

В каких пределах могут меняться начальное значение s и значение t? Для ответа на этот вопрос заметим, что результат работы предыдущей версии программы, соответствующий максимально возможным начальным данным N = K = 2×109, т. е. число 36359345582, удовлетворяет неравенству

235 − 1 < 36359345582 < 236 − 1,

причём отношение (236 − 1) / 36359345582 превышает 1,89. Понятно, что, даже при максимальных значениях N и K число 36359345582 не "обязано" быть максимально возможным результатом (нельзя исключать того, что, оставив K неизменным и немного уменьшив N, мы получим результат, превышающий данное число), однако крайне маловероятно, что максимально возможный результат превысит это число более чем в 1,89 раза.

Так что будем считать, что любой результат окажется меньшим числа 236 − 1. Это означает, что в ходе наших итераций мы никогда не столкнёмся с членом последовательности, контрольная сумма которого превысит 35. Так что начальные значения s всегда будут попадать в диапазон от 0 до 34 (в дальнейшем, все такие значения переменной s будем называть начальными). Что касается t, то максимально возможное значение контрольной суммы числа, содержащегося в переменной r, равно 35 − 16 = 19, поэтому значения t всегда будут лежать в диапазоне от 0 до 19.

Таким образом, всего существует 35 × 20 = 700 возможных сочетаний начальных значений s и значений t. Некоторые из этих сочетаний могут попадаться в ходе наших итераций неоднократно. Если при первом появлении такой пары запомнить (кэшировать) соответствующее ей конечное значение s, то при последующих её появлениях можно сразу же перейти к конечному значению s и инкременту переменной r (см. строку 48 предыдущей программы), избежав достаточно большого количества итераций, необходимых для непосредственного вычисления конечного значения s.

Отметим, что, когда мы таким образом "экономим" итерации, используя сохранённое ранее конечное значение s, то мы должны скорректировать число оставшихся итераций, уменьшив его на число сэкономленных. Так что число итераций, требующихся для перехода от начального значения s к конечному путём непосредственных вычислений, также необходимо запоминать.

Такой подход может существенно сократить время выполнения программы.

Результаты кэширования будем хранить в двухмерных массивах cache1 и cache2. Каждый из них будет иметь размер 35x20.

Элемент первого массива будет содержать конечное значение s, соответствующее начальному значению s, совпадающему с первым индексом, и значению переменной t, совпадающему со вторым, при условии, разумеется, что это конечное значение уже вычислено. В противном случае данный элемент массива будет нулевым. Хранимое значение не будет превышать 34, поэтому в качестве базового типа массива нас вполне устроит unsigned char.

Элемент второго массива будет содержать количество итераций, которое требуется для вычисления конечного значения s, соответствующего начальному значению s, совпадающему с первым индексом, и значению переменной t, совпадающему со вторым, при условии, разумеется, что итерации уже выполнены, а конечное значение уже вычислено. Такое количество итераций, даже если мы будем двигаться от начального значения к конечному с шагом 1, никогда не превзойдёт 216 − 1, поэтому в качестве базового типа массива мы возьмём unsigned short.

Давайте теперь рассмотрим код пятой версии программы.

 1.#include <stdio.h>
 2.#include <string.h>
 3.
 4.#define IN                                     \
 5.            FILE *f = fopen("INPUT.TXT", "r"); \
 6.               fscanf(f, "%llu %u", &n, &k);   \
 7.            fclose(f);
 8.
 9.#define OUT {                                       \
10.                n = r;                              \
11.                n = (n << 16) + s;                  \
12.                f = fopen("OUTPUT.TXT", "w");       \
13.                fprintf(f, "%llu", n);              \
14.                fclose(f);                          \
15.                return 0;                           \
16.            }
17.
18.const int ar[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
19.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
20.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
21.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
22.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
23.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
24.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
25.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
26.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
27.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
28.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
29.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
30.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
31.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
32.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
33.                  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
34.
35.int main()
36.{
37.    unsigned char cache1[35][20];
38.    unsigned short cache2[35][20];
39.    memset(&cache1, '\0', 700);
40.    unsigned long long n;
41.    unsigned int k;
42.    IN;
43.    unsigned int r = n >> 16, s = n - (r << 16);
44.    unsigned char *p1 = (unsigned char *) &r, *p2 = p1 + 1, *p3 = p1 + 2;
45.    unsigned char *p4 = (unsigned char *) &s, *p5 = p4 + 1, *p6 = p4 + 2;
46.    int t = ar[*p1] + ar[*p2] + ar[*p3];
47.    if (s >= 35)
48.    {
49.        do
50.        {
51.            s += t + ar[*p4] + ar[*p5];
52.            if (!--k)
53.                OUT;
54.        }
55.        while (!*p6);
56.        r++;
57.        t = ar[*p1] + ar[*p2] + ar[*p3];
58.        *p6 = 0;
59.    }
60.    while (k)
61.    {
62.        if (cache1[s][t])
63.        {
64.            if (cache2[s][t] <= k)
65.            {
66.                k -= cache2[s][t];
67.                s = cache1[s][t];
68.                r++;
69.                t = ar[*p1] + ar[*p2] + ar[*p3];
70.                continue;
71.            }
72.            do
73.                s += t + ar[*p4] + ar[*p5];
74.            while (--k);
75.            OUT;
76.        }
77.        int j = k, s_old = s;
78.        do
79.        {
80.            s += t + ar[*p4] + ar[*p5];
81.            if (!--k)
82.                OUT;
83.        }
84.        while (!*p6);
85.        *p6 = 0;
86.        cache1[s_old][t] = s;
87.        cache2[s_old][t] = j - k;
88.        r++;
89.        t = ar[*p1] + ar[*p2] + ar[*p3];
90.    }
91.    OUT;
92.}

Остановимся на основных особенностях этой программы.

На этот раз мы уже будем, для удобства, "крутить" счётчик итераций, роль которого теперь будет играть переменная k, в "обратном направлении". Другими словами, мы сначала присвоим k значение, равное K (см. стр. 6), а затем будем уменьшать значение этой переменной до тех пор, пока оно не обнулится, что будет являться сигналом к окончанию итераций.

Обратите внимание на то, что после объявления массивов cache1 и cache2 (стр. 37 и 38) мы обнуляем значения всех элементов первого из этих массивов (стр. 39); напомню, что нулевое значение элемента массива cache1 сигнализирует о том, что соответствующее индексам конечное значение переменной s ещё не было кэшировано.

В строках 44 и 45 записываем в шести указателях адреса трёх младших байтов каждой из переменных r и s. Не забываем внести в t контрольную сумму значения переменной r (стр. 46).

Если перед началом всех итераций значение s превышает 34, то его нельзя рассматривать как начальное значение. И то конечное значение s, которое получится в результате первых итераций, кэшировать не получится именно потому, что соответствующее ему начальное значение s неизвестно. По этой причине мы в этом случае "отбрасываем" все мысли о кэшировании и просто выполняем итерации до тех пор, пока в s не возникнет переполнение или пока значение счётчика k не обнулится; в последнем случае результат работы выводим в файл и завершаем работу программы (см. стр. 47-59).

Таким образом, перед началом выполнения цикла while (см. стр. 60), значение s заведомо не будет превышать 34-х.

Каждая итерация цикла while будет проходить по одному из трёх сценариев.

Если информация, соответствующая текущим значениям переменных s и t уже кэширована (стр. 62) и, при этом, количество соответствующих этим значениям итераций не превышает числа оставшихся итераций, хранящихся в счётчике k (стр. 64), то мы используем результаты кэширования. А именно, заменяем начальное значение s конечным, уменьшаем значение k на количество "сэкономленных" итераций, выполняем инкремент r и обновляем значение t, после чего переходим к следующей итерации цикла while (см. стр. 66-70).

Если же информация, соответствующая текущим значениям переменных s и t уже кэширована но, при этом, количество соответствующих этим значениям итераций меньше числа оставшихся итераций, хранящихся в счётчике k, то результатами кэширования воспользоваться не удастся. Поэтому мы просто выполняем оставшиеся итерации, после чего выводим результат в файл и завершаем работу программы (см. стр. 72-75).

Наконец, если информация, соответствующая текущим значениям переменных s и t, отсутствует в кэше, то сохраняем количество оставшихся итераций и начальное значение s в переменных j и s_old соответственно (стр. 77). Далее пытаемся в рамках цикла do while (стр. 78-84) выполнить итерации, приводящие к нахождению конечного значения s.

В случае неудачи, т. е. при обнулении счётчика k до нарушения условия продолжения цикла, выводим результат в файл и завершаем работу программы (см. стр. 81-82). А в случае удачи обнуляем третий байт переменной s (стр. 85), сохраняем конечное значение s и количество итераций, потребовавшихся для его достижения, в кэше (стр. 86, 87), выполняем инкремент r (стр. 88) и обновляем значение t (стр. 89), после чего переходим к следующей итерации цикла while.

После окончания цикла выводим результат в файл и завершаем работу программы (стр. 91). Отметим, что цикл завершится успешно и управление будет передано строке 91 лишь в случае, если после использования результатов кэширования счётчик итераций окажется равным 0. Во всех остальных ситуациях цикл прерывается инструкцией return, "запрятанной" в макрос OUT (см. стр. 75 и 82).

На входных данных N = K = 2×109 программа выполняется почти мгновенно и выводит в выходной файл верный результат. Операционная система показывает, что время выполнения составляет 0,18с. Что ж, это нас вполне устраивает. Теперь уже можно заявить, что задача полностью решена!

Заключение

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

Конечно же, даже последнюю версию программы можно, при желании, улучшить. Заметим, например, что результаты кэширования, соответствующие нулевому значению t, никогда задействованы не будут. И крайне маловероятно то, что когда-нибудь начальное значение s будет равно 34, а значит, и то, что будут заполнены элементы массивов, с максимальными первыми индексами.

И вообще, массивы cache1 и cache2 после всех кэширований будут весьма разряженными. Эксперимент показал, что даже при максимально возможных значениях входных данных перед окончанием работы программы лишь 135 значений элементов массива cache1 оказываются отличными от 0, что означает заполненность каждого из массивов примерно на 19,2%.

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

Исходный код всех программ, рассмотренных в обеих частях статьи, можно скачать по приведённой ниже ссылке.

Скачать исходный код