Как ускорить работу стека построенного на массиве размером 100М элементов?

#c_sharp #алгоритм #оптимизация #коллекции #быстродействие

Доброго всем времени суток!

Попалась тут задача, - сделать свой класс стека, с методами .pop(), .push(digit),
.inc(x, y)
С первыми двумя думаю понятно, а вот inc стоит объяснить, он берет первые x элементов
в массиве и прибавляет к ним число y (соответственно в результате мы должны получить
измененный стек). 

Нужно, чтобы запуская этот этот метод на стеке из 100000001 внутри цикла в 100000001,
это дело не зависало и отрабатывало максимально быстро (человек, который проверяет
эту работу, говорит, что можно сделать так, чтобы нижеуказанный тест проходил в пределах
нескольких секунд). Маньяки оптимизации, прийдите!!!

public void StackTest()
{
 var watch = new Stopwatch();
 var stack = new StackClass();

 var count = 100000001;

 watch.Start();
 for (int i = 0; i < count; i++)
 {
     stack.Push(i);
 }
 Console.WriteLine(watch.Elapsed);
 watch.Restart();

 for (int i = 0; i < count; i++)
 {
     stack.Inc(i, 2);
 }
 Console.WriteLine(watch.Elapsed);
 watch.Restart();

 for (int i = 0; i < count; i++)
 {
     stack.Pop();
 }
 Console.WriteLine(watch.Elapsed);
}


Я попробовал несколько реализаций, через List, Collection, Array. Самая быстрая получилась
через массив обычный. Вот такая:

class Stack
{
    private int[] arr = new int[100000001];
    private int _count;
    private int _currentIndex;
    public Stack()
    {
        _count = 0;
        _currentIndex = -1;
    }

    public void Push(int digit)
    {
        if (IsFull)
        {
            throw new Exception("Array is full");
        }
        _currentIndex++;
        arr[_currentIndex] = digit;
        _count++;
    }

    public int Pop()
    {
        int tmp = 0;
        if (IsEmpty)
        {
            throw new Exception("No elements in array");
        }
        tmp = arr[_currentIndex];
        arr[_currentIndex] = default(int);
        _count--;
        _currentIndex--;
        return tmp;
    }

    public void Inc(int count, int multiplier)
    {
        if (count > _count)
        {
            throw new Exception("Not enought element in array");
        }
        for (int i = 0; i < count; i++)
        {
            arr[i] += multiplier;
        }
        Console.WriteLine("Ready");
    }

    private bool IsEmpty {
      get{ return _count == 0; }
    }        
    private bool IsFull {
      get { return _currentIndex == arr.Length; }
    }
}
class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("Type exit and press enter to quit, type push 
to push digit in stack, pop - to see last stack element, inc  to
multiply first  elements on ");
        Stack stack = new Stack();
        while (true)
        {
            string[] input;
            string command = "";
            input = Console.ReadLine().Split(new char[] { ' ' });
            command = input[0];
            try
            {
                switch (command)
                {
                    case "push": { stack.Push(Convert.ToInt32(input[1])); break; }
                    case "pop": { Console.WriteLine(stack.Pop().ToString()); break; }
                    case "inc": { stack.Inc(Convert.ToInt32(input[1]), Convert.ToInt32(input[2]));
break; }
                }
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }
            if (command == "exit") break;
        }
    }
}

    

Ответы

Ответ 1

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

http://ideone.com/b3T3ci

public class StackClass
{
    private int[] data = new int[100000001];
    private int[] add = new int[100000001];
    private int inc = 0;
    private int i = -1;

    public void Push(int x)
    {
        if (i >= 0) add[i] += inc;
        inc = 0;
        data[++i] = x;
    }

    public int Pop()
    {
        inc += add[i];
        add[i] = 0;
        return data[i--] + inc;
    }

    public void Inc(int r, int delta)
    {
        if (r <= i)
            add[r] += delta;
        else
            inc += delta;
    }
}



  Успешно   #stdin #stdout 1.38s 29672KB


00:00:00.5797480
00:00:00.3059362
00:00:00.4621549


Думаю, можно даже нормально List применить:

http://ideone.com/QTmDnz

public class StackClass
{
    private List data = new List(100000001);
    private List add = new List(100000001);
    private int inc = 0;

    public void Push(int x)
    {
        data.Add(x);
        if (add.Count > 0) add[add.Count-1] += inc;
        add.Add(0);
        inc = 0;
    }

    public int Pop()
    {
        int i = data.Count - 1;
        int res = data[i] + (inc += add[i]);

        add.RemoveAt(i);
        data.RemoveAt(i);

        return res;
    }

    public void Inc(int r, int delta)
    {
        if (r < add.Count)
            add[r] += delta;
        else
            inc += delta;
    }
}


Секунд в 6 должна уложиться, но ideone хочет 5:


  Превышено ограничение на время    #stdin #stdout 5s 29800KB


00:00:02.2248518
00:00:01.1903442
00:00:02.0052423


Более ранняя версия с багами:
http://ideone.com/16JZ5V


  Успешно   time: 4.67 memory: 29808 signal:0


00:00:01.3654668
00:00:01.1821722
00:00:02.0888570


Ответ 2

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


sqrt-декомпозиция, сложность O(sqrt(n))
дерево отрезков, O(ln(n))
Дерево Фенвика, O(ln(n))


Как реализовать их, можно прочитать, например, здесь http://e-maxx.ru/algo/sqrt_decomposition


Ответ 3

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