8

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

Попалась тут задача, - сделать свой класс стека, с методами .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 <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;
        }
    }
}
3
  • А чем вас стандартный стек не устраивает? Он слишком медленный? Попробуйте нативную реализацию на чистом C, намного ли она быстрее?
    – VladD
    19 дек 2016 в 11:42
  • @VladD тут видимо задача из собеседования / ВУЗа / школы - требуется самому реализовать. Мне кажется с будет быстрее выполняться - там же код оптимизируется и транслируется сразу в машинный код, а не в байт код.Если я не ошибаюсь)
    – Trymount
    19 дек 2016 в 11:48
  • 3
    100000001 внутри цикла в 100000001 выполнялось быстро. А это можно только, если компилятор выбросит код. Допустим, что наш процессор выполняет 2*10 в 9 операций в секунду (то есть, такой себе фиктивный 2гигагерцовый). В этом случае нам нужно 100000001*100000001 / 2000000000 / 60 / 60 / 24 а это около 58 дней. Но я сильно сомневаюсь, что на обычном pc получиться сделать 2 миллирда операций, даже если это распаралелить.
    – KoVadim
    19 дек 2016 в 11:48

3 ответа 3

9

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

http://ideone.com/QTmDnz

public class StackClass
{
    private List<int> data = new List<int>(100000001);
    private List<int> add = new List<int>(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
1
  • Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
    – user177221
    6 янв 2017 в 12:49
3

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

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

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

3
  • Попробую реализовать что-то из предложенного вами, если получится, однозначно вам + в карму
    – Alex Sh
    19 дек 2016 в 12:04
  • @AlexSh декомпозицию точно не надо использовать... корень из 100 млн это 10тыс итого порядка 10^12 операций. Точно не успеет. Логарифмические структуры - тяжело но может быть успеет. Конечно тут мы точно знаем порядок действий, поэтому можно читерить (но думаю не оценят идею забить сразу генератор ответа).
    – pavel
    19 дек 2016 в 14:14
  • @AlexSh самая простая из этих структур данных - последняя. 20 дек 2016 в 7:09
2
  1. В методе Pop можно не обнулять значение массива и не использовать лишнюю переменную. Это избыточно. Как
  2. Единственная идея, которая приходит на ум - не производить сложения, а записывать интервалы, которые требуется изменить. И при попытке обращения к элементу, проходить все эти запросы и выдавать вычисленный элемент. Следует не забыть, что при извлечении элементов потребуется так же править интервалы - вы не должны в итоге прибавить число к элементу, которого не было на момент запроса

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.