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

Доброго всем времени суток!
Попалась тут задача, - сделать свой класс стека, с методами .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; } } }

Ответ

Думаю, правильное решение примерно такое: для каждой позиции в имеющемся массиве храним значение инкремента, действующее на неё и левее (но не правее). В 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