Как обнулить массив за O(1)?

#алгоритм #любой_язык

Есть массив с N элементами. Нужно обнулить все элементы в массиве. 
Естественно можно сделать цикл и обойти массив - но время затраченное на эту операцию
займет O(n).
    

Ответы

Ответ 1

Есть один читерский метод обнуления. Он ширико используется на олимпиадах. Примерный
код (псевдостиль, чисто ради принципа). Для примера массив не может быть расширен (это
не так важно).

class MyArray{
     private Array value;
     private Array mask;
     private int current;

     public MyArray(int size){
         value = new Array(size);
         mask  = new Array(size);  //we hope new array fill 0. If not - fill
         current = 0;
     }  

     public  T get(int pos){
          //ToDO validate pos
          if (mask[pos] != current) 
             return null;  //or any default value for clean. 
                           //So you can "clean" different value
          return value[pos];
     }

     public void set(int pos, T val){
         //ToDO validate pos
         mask[pos] = current;
         value[pos] = val;
     }

     public void cleanAll(){
          current++;
     }

}


Думаю идея в дальнейшем объяснении не нуждается.

Нетрудно заметить, что время доступа по прежнему O(1). При этом "обнуление" - 1 операция.


Ответ 2

Время всегда будет O(n). Но вы можете обнулять массив используя несколько потоков.
В Java 8 есть метод

Arrays.parallelSetAll()


Ответ 3

Обнулить за время O(1) можно разряженный массив, который обычно реализуют либо через
хеш-таблицу, либо через сбалансированное дерево.

Подробности

Для начала попробуем абстрагироваться от реализации массива, и поговорим об его интерфейсе.
В массиве хранятся однотипные элементы, доступные по целочисленным индексам. Мы можем
узнать длину массива length, а индексы могут принимать значения от 0 до length - 1.

Обычно реализация массива проста: мы выделяем память подряд, достаточную, чтобы хранить
length элементов заданного типа. Если double требует 8 байт, то массив из 1000 чисел
двойной точности потребует 8000 байт подряд, а i-ый элемент будет находиться по смещению
8 * i байт от начала.

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

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

103 => 145000.3
457 => 267000.5
732 => 197500.2


Здесь 103, 457 и 732 — индексы значимых элементов массива, все остальные элементы
равны 0.0. Если это массив из 1000 элементов, экономия памяти налицо.

Интерфейс массива должен быть реализован следующим образом: длина массива length
задана изначально, а список пар индекс => значение пуст. Операция чтения по заданному
индексу должна проверять, есть ли этот индекс в списке. Если индекс есть, операция
возвращает связанное значение, а если его нет, то нулевое.

Операция записи смотрит на значение. Если это значение нулевое, пара с заданным индексом
должна быть удалена из списка, а если ненулевое — добавлена.

Остаётся решить вопрос эффективности поиска пары с заданным индексом. Если хранить
пары в произвольном порядке, то скорость работы с таким массивом будет удручающе низкой —
O(M) для чтения/записи элемента вместо O(1). Здесь M — количество значимых элементов
в массиве.

Пары можно организовать в двоичное дерево, тогда скорость возрастёт до O(log N).
Можно также воспользоваться хеш-таблицей, тогда скорость приблизится к обычному массиву
O(1).

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

Конкретно: мы хотим хранить миллиард чисел двойной точности, что заняло бы 8 гигабайт
оперативной памяти. Значимых чисел в этом массиве всего 5% или пятьдесят миллионов.
Чтобы эффективно работать с таким количеством пар, нам нужно место для хранения ста
миллионов пар. Каждая пара состоит из целого индекса (4 байта) и значения двойной точности
(8 байт). Итого размер хеш-таблицы составит 1,2 гигабайта, что почти в 7 раз меньше
8-ми гигабайтов. При этом чтение и запись элемента с произвольным индексом i составит
O(1), как в классическом массиве.

Возвращаемся к главному вопросу: как очистить такой массив за время O(1)? Для этого
нам нужно очистить внутреннюю хеш-таблицу. Это непрерывный массив, место на который
мы выделили в куче. Чтобы его очистить, достаточно вернуть эту память в кучу, что можно
считать операцией с фиксированным временем.

Тут я сделаю отступление. В общем случае время может быть не фиксированным, но это
тема для глубокого обсуждения. В современных средах, где работает сборка мусора, мы
можем говорить о времени освобождения в пределах O(1).


Ответ 4

Хранить битовую маску ненулевых элементов. Для нее хранить еще одну маску и так далее.
Вот только доступ (проверка на не 0) станет в O(log?(N)).