bondpuoq
@bondpuoq
Web-программист с недавних пор

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

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

Попалась тут задача, - сделать свой класс стека, с методами .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;
            }
        }
    }
}
  • Вопрос задан
  • 1036 просмотров
Пригласить эксперта
Ответы на вопрос 4
@none7
Это невозможно! В тесте метод inc выполняется 108 раз. В среднем считывая по 2 * 108 байт данных за 1 проход. Даже если этот массив будет считать видеокарта GT 970, она сможет переварить чуть больше 1000 вызовов inc в секунду в среднем. В условие секунды можно вписаться если только переписать тест и класс и свести все 555 + 555 + 555 + 555 + ... в один 555 * n.
Ответ написан
Ayahuaska
@Ayahuaska
Хочу знать всё.
А разве не реализация стека на основе односвязаного списка - не канонiчная и наиболее верная?
Ответ написан
@theg4sh
Я задам несколько вопросов и было бы очень хорошо, чтобы вы ответили на них сами:
- За каким идет заполнение массива при создании Stack? Нужно ли вообще инициализировать и деиницализировать элементы массива?
- Почему 100000001, а не 100000000 (см. внимательно на условие i<count)? И почему явно используется число, а не директива препроцессора?
- Вы уверены в том что в StackTest необходимо замерять каждый метод по отдельности?
- Может будет достаточно одного вызова метода Inc для замера?

B.R., t4g
Ответ написан
bondpuoq
@bondpuoq Автор вопроса
Web-программист с недавних пор
Кому интересно - это возможно, обсуждение вот тут ru.stackoverflow.com/questions/605258/%D0%9A%D0%B0...
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы