6.9. Работа с массивом без инициализации

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

Примечание

На самом деле, как известно, все глобальные переменные и FP, и Delphi инициализируют, заполняя нулями (т.е. и FP, и Delphi в начало программы автоматически вставляют код, который заполнит нулями всю используемую глобальными переменными память). Но настоятельно не рекомендую на это полагаться: во-первых, это относится только к глобальным переменным; локальные переменные внутри функций не инициализируются, и, привыкнув, что глобальные переменные зануляются, вы можете случайно рассчитать на то же и с локальными; во-вторых, на других языках ничего подобного может и не быть, и потому привычка полагаться на зануление переменных может вам сильно помешать при работе с другими языками программирования; в-третьих, вполне может оказаться, что какой-нибудь другой компилятор паскаля не инициализирует переменные и т.п.

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

Но может такое случиться, что у вас есть массив, в котором вы используете лишь часть элементов, а часть вам на самом деле не будет нужна, причём, возможно, вы заранее даже не знаете, что это будут за элементы. Например, задача: вам даны \(N\) целых чисел, каждое от \(1\) до \(M\), надо определить, есть ли среди них число, которое встречается как минимум 4 раза. Решить эту задачу можно легко: заведём массив \(a\) длины \(M\), в элементе \(a[i]\) будем помечать, сколько раз нам встретилось уже число \(i\). Просто пробежимся по числам и для каждого числа \(i\) увеличим \(a[i]\) на единицу и проверим, не четвертей ли раз встречается это число:

for i:=1 to n do begin
    read(x);
    inc(a[x]);
    if a[x]>=4 then writeln(x);
end;

Вроде все просто, только давайте оценим время работы этого алгоритма. На первый взгляд это просто: \(O(N)\), тут ведь простой цикл…Но! Не забудем про то, что массив \(a\) надо изначально проинициализировать, на что, очевидно, потребуется время \(O(M)\). Поэтому общее время работы алгоритма будет \(O(N+M)\), что в определённых ситуациях нам может не очень понравиться (если \(M\gg N\), т.е. много больше, то времени на инициализацию может не хватить). Но всё это из-за того, что массив пришлось инициализировать, все остальное у нас работает за \(O(N)\), поэтому имеет смысл думать, нельзя ли как-нибудь обойтись без инициализации за \(O(M)\)

Примечание

Тот момент, что все остальное работает за \(O(N)\), очевидно, очень важен: если не так, то все равно бессмысленно оптимизировать инициализацию. Именно поэтому, в частности, я не стал в качестве примера приводить сортировку подсчётом — я понял, что не знаю, как её реализовать так, чтобы все, кроме инициализации, работало за \(O(N)\). Обратите внимание, как в приведённом выше коде я ушёл от необходимости после чтения входного файла дополнительно пробегаться по массиву \(a\), чтобы искать элементы, которые \(\geq 4\).

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

Однократная инициализация. Пусть на самом деле все не так плохо. Пусть на самом деле один раз за время работы программы мы можем проинициализировать массив, но задачу наша программа должна решать не один, а несколько (пусть \(K\)) раз (т.е. во входном файле мультитест — несколько тестов, каждый из которых надо решить и вывести ответ в выходной файл). Тупой вариант — каждый раз заново инициализировать массив:

for j:=1 to k do begin
    read(n);{Будем считать, что формат входных данных именно такой}
    fillchar(a,sizeof(a),0);
    for i:=1 to n do begin
        read(x);
        inc(a[x]);
        if a[x]>=4 then writeln(x);
    end;
end;

Но предположим, что его мы себе позволить не можем (например, \(N\leq 100\), \(M\leq 10\,000\), \(K\leq 100\,000\) — ясно, что \(100\,000\) раз пробежаться по 100 чисел мы вполне можем, а вот \(100\,000\) раз инициализировать \(10\,000\)-й массив заново — не очень, хотя один раз его проинициализировать — не проблема). Тогда есть следующее простое решение: заведём второй массив, \(b\), в элементе \(b[i]\) которого будем хранить, на каком по счету «тесте», т.е. на каком наборе из \(N\) чисел, мы последний раз использовали элемент \(a[i]\). Т.е. в \(b[i]\) будем хранить последнее значение \(j\), когда мы использовали \(a[i]\). Если мы ещё ни разу не использовали элемент \(a[i]\), то в \(b[i]\) будет лежать 0; если, например, последний раз \(a[i]\) мы использовали на 10-й итерации внешнего цикла (при \(j=10\)), то \(b[i]\) будет равно 10. Тогда мы сможем инициализировать не весь массив \(a\) на каждой итерации, а только те элементы, которые понадобятся. По элементу массива \(b\) мы запросто отличим, использовался ли элемент массива \(a\) на текущей итерации. Если нет, то проинициализируем его, а потом делаем то же, что делали бы и раньше:

fillchar(b,sizeof(b),0);
for j:=1 to k do begin
    read(n);
    for i:=1 to n do begin
        read(x);
        if b[x]<>j then begin
           a[x]:=0; {Инициализируем этот элемент}
           b[x]:=j; {Помечаем, что его уже использовали на этой итерации}
        end;
        inc(a[x]);
        if a[x]>=4 then writeln(x);
    end;
end;

Я надеюсь, что понятно, как работает этот код. Он отличается от того, что приведён выше, только наличием внутреннего if’а, и отсутствием инициализации массива \(a\). Эта инициализация теперь присутствует на самом деле внутри if’a: мы инициализируем только те элементы, которые нам будут нужны. Массив же \(b\) инициализируется лишь один раз во всей программе.

Примечание

Казалось бы, можно было бы сразу в if писать \(a[x]:=1\): зачем его занулять, если потом сразу надо будет увеличить на единицу? (А inc тогда вынести в else). Можно и так сделать. Но имхо понятнее так, как приведено выше: там внутри if’а чистая инициализация, а вне if’а — то, что мы делали с этим элементом раньше. Пусть, например, нам надо сделать с \(a[x]\) что-нибудь более хитрое, чем inc’нуть (например, \(a[x]:=a[x]\cdot a[x]+x\cdot a[x]+x\cdot x\). Зачем? А черт его знает, по условию так надо, например), или пусть кроме изменения массива \(a\) надо что-то ещё делать. Можно, конечно, мудрить, и отдельно соображать, что надо делать внутри if’а, а что вне, а можно в if просто проинициализировать элемент — поставить \(a[x]:=0\), в соответствии с тем, что раньше у нас стояло fillchar(a,sizeof(a),0), — а вне if’а сделать все, что надо.

Этот код теперь работает за \(O(M+KN)\), а тупой код — за \(O((M+N)K)\). Явно лучше.

А без полной инициализации вообще? Но пусть все настолько плохо, что зависимость времени работы от \(M\) надо убрать вообще. Вернёмся к первому варианту задачи, т.е. без всякого \(K\), и попробуем обойтись без инициализации всего массива \(a\). На первый взгляд задача кажется невыполнимой и даже абсурдной: как же мы сможем так сделать? Ну пусть даже мы заведём второй массив, в котором будем помечать, используется ли данный элемент…Этот второй массив ведь тоже придётся инициализировать!.. Что бы мы ни делали, все равно ведь в конечном счёте придётся что-то инициализировать!..

Но решение, как ни странно, есть. Заведём второй массив \(b\). Если мы стали использовать некоторый элемент \(a[i]\), то присвоим ему ещё «индивидуальный номер» — каким по счёту мы стали его использовать — и этот номер будем хранить в \(b[i]\). А именно, если, например, в нашей задаче мы первым считали число 10, то мы тут же будем использовать элемент \(a[10]\) — присвоим ему номер 1: \(b[10]:=1\). Считали потом число 137 — запишем \(b[137]:=2\). Считали опять 10 — элемент \(a[10]\) мы уже используем (хотя пока и не понятно, как мы в программе поймём, что мы его уже используем, но что-нибудь придумаем), поэтому с \(b\) ничего не делаем. Считали потом 1061 — пишем \(b[1061]:=3\) и т.д. Т.е. у нас будет счётчик \(nall\), сколько всего различных чисел на данный момент встретилось, и при считывании очередного числа \(x\), если оно действительно новое, увеличим \(nall\) на единицу и запишем \(b[x]:=nall\).

Теперь, казалось бы, можно определить, встречалось ли число \(x\) раньше. Просто сравним \(b[x]\) с \(nall\): если \(b[x]>nall\), то явно не встречалось, иначе встречалось…Нет! Если \(b[x]>nall\), то число \(x\) точно раньше не встречалось (если бы оно встречалось, то мы бы уже устанавливали \(b[x]\) и было бы \(b[x]\leq nall\)). Но если \(b[x]\leq nall\), то это ещё ничего не значит…Может быть, на самом деле число \(x\) уже встречалось, и оно было \(b[x]\)-ым по счету среди «новых», а может быть, оно не встречалось, просто так получилось, что элемент \(b[x]\) имеет такое значение (мы ведь, конечно, не инициализируем массив \(b\) заранее — у нас нет на это времени!) Так что вроде такая конструкция ничем не лучше, чем то, что было раньше…но сделаем вот ещё что: заведём третий массив \(c\), и в \(c[i]\) будем хранить то число \(x\), которое было \(i\)-м по счету новым! Т.е. в примере выше после считывания чисел 10, 137, 10, 1061 будет \(nall=3\), \(b[10]=1\), \(b[137]=2\), \(b[1061]=3\), и при этом \(c[1]=10\), \(c[2]=137\), \(c[3]=1061\); остальные элементы \(b\) и \(c\) ещё не будут инициализированы.

Пусть следующим мы считываем число 40. Нам надо определить, появлялось ли оно раньше. Посмотрим на \(b[40]\). Если \(b[40]>nall=3\), то очевидно, что числа 40 раньше не было. А что делать, если, например, \(b[40]<nall\), например, \(b[40]=2\)? А очень просто! Посмотрим на \(c[b[40]]=c[2]\). И мы увидим, что \(c[2]=137\), т.е. что вторым числом было 137, а вовсе не 40! Значит, число 40 нам ещё не встречалось. Обратите внимание, что \(c[2]\) не может быть каким попало: \(2\leq nall\), т.е. мы уже устанавливали \(c[2]\) в то значение, которое нам надо. В частности, никак не может такого случится, что \(c[2]=40\): оно обязательно будет равно 137 (если мы действительно только что считали числа 10, 137, 10, 1061 и все).

Т.е. теперь обнаруживается очень простой способ проверить, встречалось ли нам число \(x\) раньше: оно встречалось, если

if (b[x]>0)and(b[x]<=nall)and(c[b[x]]=x)

(Сравнение с нулём добавлено ясно зачем; выше я его не упоминал просто для ясности).

Докажем, что это так. Действительно, если \(x\) действительно встречалось раньше, то, во-первых, \(b[x]\) есть его «порядковый номер» и потому точно \(b[x]\leq nall\) (т.к. \(nall\) — общее количество различных встречавшихся чисел), а во-вторых, \(c[b[x]]\) хранит, какое число имеет порядковый номер \(b[x]\), а раз это как раз номер числа \(x\), то \(c[b[x]]=x\) (ещё раз: \(c[b[x]]\) есть ”число, «порядковый номер» которого есть «порядковый номер» числа \(x\)”, т.е. само \(x\)).

А пусть теперь число \(x\) не встречалось раньше. Тогда \(b[x]\) может быть каким попало. Если \(b[x]>nall\) или \(b[x]\leq 0\), то вопросов нет, все ясно и наш if сработает верно. Если же так случилось, что \(0<b[x]\leq nall\)?.. А тогда \(c[b[x]]\) не может хранить какое попало число — мы в него раньше специально записали то число, которое имеет номер \(b[x]\), а это точно не \(x\), т.к. по предположению \(x\) ещё не встречался (\(c[b[x]]\) — это то число, которое на самом деле имеет номер \(b[x]\), а \(b[x]\) здесь не есть номер числа \(x\), а просто случайное число, которое там валялось ещё до запуска нашей программы: в \(b[x]\) мы ещё ничего не записывали, а у числа \(x\) пока ещё нет никакого номера). Поэтому \(c[b[x]]\neq x\) и потому опять-таки наш if сработает верно.

То же самое можно изложить по-другому: как мы уже видели, если \(x\) действительно встречалось раньше, то if выполнится. Иначе (если \(x\) ещё не встречался) if не выполнится, как бы ни старались против этого те элементы массивов \(b\) и \(c\), которые ещё пока не инициализированы (т.е. в которые мы пока ещё ничего не писали). Действительно, элемент \(b[x]\) ещё пока не инициализирован, поэтому он может попытаться обмануть нас (чтобы мы поверили, что \(x\) встречался раньше, что \(x\) — это элемент с номером \(b[x]\)). Если этот номер окажется \(>nall\) или \(\leq 0\), то мы его тут же раскусим: чисел с таким номером мы точно ещё не встречали. Но \(b[x]\) может оказаться хитрее и оказаться \(\leq nall\) и \(>0\). Но не тут-то было: мы обратимся к элементу \(c[b[x]]\). А он уже инициализирован, т.е. в него мы уже что-то записывали (и не что-то, а вполне понятно, что), поэтому он не сможет увиливать и честно ответит: ничего подобного, число с этим номером — вовсе не \(x\), а другое. И мы тут же распознаем, что \(x\) — самозванец.

Объединяя все вышесказанное, получим программу решения нашей задачи, работающую за \(O(N)\):

nall:=0;
for i:=1 to n do begin
    read(x);
    if not( (b[x]>0)and(b[x]<=nall)and(c[b[x]]=x) ) then begin
       inc(nall);
       b[x]:=nall;
       c[b[x]]:=x; {*}
       a[x]:=0; {**}
    end;
    inc(a[x]);
    if a[x]>=4 then writeln(x);
end;

Аналогично коду, приведённому в первом способе, тут опять появляется внутренний if, который проверяет, верно ли, что считанное число — новое (обратите внимание, что появился not), и, если да, то инициализирует элемент \(a[x]\) (строкой **), и кроме того, корректирует все «служебные» переменные (в данном случае \(nall\), \(b\) и \(c\)). Обратите внимание, что теперь инициализация никаких массивов заранее не нужна. Даже несмотря на её отсутствие, мы точно никогда не обратимся ни к какому элементу, в который бы раньше ничего не записывали (кроме как в условии if’а, где все возможные подлости предусмотрены). При желании можете это проверить ещё раз.

Ещё обратите внимание на строку (*). Можно было бы написать и \(c[nall]:=x\), и было бы то же самое, но такая запись лишний раз подчёркивает, что всегда будет \(c[b[x]]=x\), если \(x\) уже встречался.

Итак, в результате получили способ решать задачу за время \(O(N)\).

Наконец, финальные замечания. На самом деле я очень плохо представляю себе задачу, в которой пришлось бы это использовать. Действительно, проинициализировать (особенно fillchar’ом) даже сотни мегабайт памяти можно очень быстро. Если это надо делать один раз за время выполнения программы, то вроде потери такого времени и не страшны (а если несколько раз, то вам поможет первый способ). Кроме того, применяя этот способ, надо быть полностью уверенным, что нигде больше не будет затрат, линейных по размеру требуемой памяти. Например (внимание!), не удивлюсь, что, просто на выделение программе нескольких сотен мегабайт памяти, Windows с её хитрыми способами работы с памятью потратит некоторое время, сравнимое с временем инициализации этой памяти — и тогда отказ от инициализации вам не сильно поможет. Кроме того, конечно же, надо быть уверенным, что Delphi вам сама не будет инициализировать эту память (если \(a\), \(b\) и \(c\) будут глобальными переменными, то, ясно, что все эти ухищрения останутся бессмысленными: время на инициализацию все равно потратится). Тем не менее идея имхо красивая, вдруг вы найдёте этой идее ещё применения? Идея вообще сама по себе кажется многообещающей.

И наконец, это, имхо, очень яркий пример того, что можно решить даже такую задачу, которая на первый взгляд является неразрешимой. Мы сумели избавиться от инициализации массива за \(O(M)\), хотя на первый взгляд задача казалась такой невыполнимой и даже абсурдной. Но вот именно, что казалась: строгого доказательства у нас не было, только какие-то туманные намёки. Что ж, они оказались тут не верны. Более того, даже будь у нас доказательство, вполне могло бы быть, что в нем мы явно или неявно использовали бы те или иные предположения о структуре решения, которым наше решение не соответствовало бы. В общем, не надо считать, что задача неразрешимая, если вы не можете её решить. Считайте так, только если смогли строго доказать.