Доброго всем времени суток!
Попалась тут задача, - сделать свой класс стека, с методами .pop(), .push(digit), .inc(x, y)
С первыми двумя думаю понятно, а вот inc стоит объяснить, он берет первые x элементов в массиве и прибавляет к ним число y (соответственно в результате мы должны получить измененный стек).
Нужно, чтобы запуская этот этот метод на стеке из 100000001 внутри цикла в 100000001, это дело не зависало и отрабатывало максимально быстро (человек, который проверяет эту работу, говорит, что можно сделать так, чтобы нижеуказанный тест проходил в пределах нескольких секунд). Маньяки оптимизации, прийдите!!!
Тест:
[Test]
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. Самая быстрая получилась через массив обычный. Вот такая:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Remoting.Messaging;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
namespace NewStack
{
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 <your digit> to push digit in stack, pop - to see last stack element, inc <count, multiplier> to multiply first <count> elements on <multiplier>");
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;
}
}
}
}
Средний
Простой
