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. Единственная идея, которая приходит на ум - не производить сложения, а записывать интервалы, которые требуется изменить. И при попытке обращения к элементу, проходить все эти запросы и выдавать вычисленный элемент. Следует не забыть, что при извлечении элементов потребуется так же править интервалы - вы не должны в итоге прибавить число к элементу, которого не было на момент запроса

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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