Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 12.10.2013, 20:58   #31
eval
Подтвердите свой е-майл
 
Регистрация: 29.08.2012
Сообщений: 4,011
По умолчанию

Цитата:
если и ограничен, то особенностями среды выполнения
это максимум, грубо говоря, но никто не мешает его ограничивать так как этого требует логика.
Цитата:
про О(1)
поясните мне серому что такое о(1)

Цитата:
но когда я беру класс стека, я от него кое что ожидаю (я описал что я от него хочу). И именно этого от него ожидают те, кто знает что такое стек.
ну так а кто говорит что он не будет этого вам предоставлять? только кто мешает добавить еще чего? я же вам цитату привел про тот-же лисп, все списки дают такую возможность и не только и не у кого не вызывает никаких затруднений, чего ожидают то и получают в полном соответствии..

Цитата:
размер стека всегда ограничен и этот, предельный, размер может передаваться в конструктор.
и правильно, где тут противоречие? если логика этого требует то нет проблем.
И это размер стека и размер массива это разные вещи, осюсяете?
Цитата:
что же такое "сайз"?
size, типа ограничение на возможное макс. кол-во данных в стеке.
eval вне форума Ответить с цитированием
Старый 12.10.2013, 21:06   #32
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 17,351
По умолчанию

Цитата:
size, типа ограничение на возможное макс. кол-во данных в стеке.
По-русски сказать размер нельзя? И если нет, то почему?
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Старый 12.10.2013, 21:07   #33
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,577
По умолчанию

Цитата:
поясните мне серому что такое о(1)
не о(1), а О(1) - это разные понятия xD
Открой любую книжку по алгоритмам, ты обязательно встретишь там где-то в начале эти обозначения. О(1) означает, что время выполнения операции не зависит от размера твоего стека, в данном случае

Цитата:
это максимум, грубо говоря, но никто не мешает его ограничивать так как этого требует логика.
если логика требует ограничить размер стека сверху - не используй стек - используй массив - это гораздо оптимальнее. Стек, очередь, дек, ... имееет смысл применять только если объем данных заранее не известен. И не надо тут воду мутить.
Цитата:
и правильно, где тут противоречие? если логика этого требует то нет проблем.
И это размер стека и размер массива это разные вещи, осюсяете?
Если ты не заметил, still_alive, предлагает стек реализовывать на массивах (и ты тоже предлагал именно это), дак чем тогда размер стека будет отличаться от размера массива?
Я то вообще уже устал писать, что размера стека нет и быть не может, если это не текущий размер стека.
Цитата:
По-русски сказать размер нельзя? И если нет, то почему?
можно, я так и делаю )
rrrFer вне форума Ответить с цитированием
Старый 12.10.2013, 21:19   #34
still_alive
Great Code Monkey
Форумчанин
 
Аватар для still_alive
 
Регистрация: 09.08.2007
Сообщений: 533
По умолчанию

Цитата:
что это она самая быстрая?
Ну вот так сложилось, что обычно меньше операций требуется для вставки и удаления.

Цитата:
к твоему массиву доступ/удаление - О(1), а вставка - О(1), НО ИНОГДА О(N) - это вообще не стек, т.е., оно не стабильно себя ведет и ненужно.
Мы живем не в идеальном мире. Если память будет перераспределяться раз в очень долгое время, то почему бы мне не увеличить скорость вставки и удаления в 99% случаев?

Цитата:
Я уже не говорю, что под твоими массивами памяти может быть выделено больше чем надо (но чем больше - тем реже ты получишь О(N) при вставке).
Между памятью и быстродействием почти всегда выбирают второе.

Цитата:
И еще раз, какой из этого профит? - я красным уже выделял. Массивы могут дать хорошее время произвольного доступа, но оно от стека не требуется. Что-то еще?
Не надо каждый раз выделять/освобождать память узла.

Цитата:
Если ты не заметил, still_alive, предлагает стек реализовывать на массивах
Я не предлагаю, я утверждаю, что такая возможность есть и может использоваться. В любом решении есть свои плюсы и минусы. Тот же STL позволяет сделать stack на векторе, списке или деке (он по умолчанию).
still_alive вне форума Ответить с цитированием
Старый 12.10.2013, 21:20   #35
eval
Подтвердите свой е-майл
 
Регистрация: 29.08.2012
Сообщений: 4,011
По умолчанию

Цитата:
По-русски сказать размер нельзя? И если нет, то почему?
переключать клаву иногда лениво а что, напрягает сильно?



Цитата:
если логика требует ограничить размер стека сверху - не используй стек - используй массив - это гораздо оптимальнее.
с какого перепуга? мне нужен именно стек, тобишь те самые поп и пуш, и все втикающее и вытекающее.

Цитата:
Стек, очередь, дек, ... имееет смысл применять только если объем данных заранее не известен. И не надо тут воду мутить.
не надо за всех говорить, ку? вот преподаватель тоже не того-же мнения.

Цитата:
и ты тоже предлагал именно это
игде? вы определенно, любитель за других додумать, чревато это
eval вне форума Ответить с цитированием
Старый 12.10.2013, 21:28   #36
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,577
По умолчанию

still_alive, более чем убедил, вот этим: "Не надо каждый раз выделять/освобождать память узла."
хотя...
Цитата:
Мы живем не в идеальном мире. Если память будет перераспределяться раз в очень долгое время, то почему бы мне не увеличить скорость вставки и удаления в 99% случаев?
может быть потому, что в 1% случаев память будет распределяться 99% времени? ))
Наверное поэтому, чтобы ваша программа в 1% случаев не вставала всерьез и надолго, по умолчанию в STL стек таки использует deque? )

eval
Цитата:
не надо за всех говорить, ку? вот преподаватель тоже не того-же мнения.
обоснуй. Ссылка на неизвестного преподавателя не канает, ку?
Т.е. я жду любой пример, когда использование стека будет лучше чем использование массива при условии, что количество элементов заранее известно.
Я могу придумать пример, но он из древности (и уже лет 20 не актуален).

И еще, я ж с 25 поста жду код, который решает все проблемы при помощи эксепшна или какой-то там проверки.

Цитата:
игде? вы определенно, любитель за других додумать, чревато это
ничего не остается, вы пишите какой-то неаргументированный набор слов..
"я же вам цитату привел про тот-же лисп"
еще бы указали откуда взята цитата, я так полагаю, надо контекст учитывать, а вы что-то вырвали откуда-то. То на непонятную цитату, то на неизвестного нам препода ссылаетесь.

Кстати, я внимательно прочитал цитату:
Цитата:
В некоторых языках(например, Lisp, Python[3]) стеком можно назвать любой список, так как для них доступны операции pop и push.
Бред какой-то. Причем тут "некоторые языки" и "лисп" в частности? - по определению "стек - это список". (по определению с вашей любимой вики, но still_alive таки пояснил нам, что так не всегда). А как там список устроен в лиспе ИМХО вообще нельзя быть уверенным, может быть он там на массивах? (а вдруг?) - а может быть, "иногда на массивах", мы же не знаем какое решение примет оптимизатор лиспопрограмм (а мы всегда на него надеемся).

Последний раз редактировалось rrrFer; 12.10.2013 в 21:58.
rrrFer вне форума Ответить с цитированием
Старый 12.10.2013, 22:23   #37
still_alive
Great Code Monkey
Форумчанин
 
Аватар для still_alive
 
Регистрация: 09.08.2007
Сообщений: 533
По умолчанию

Цитата:
Сообщение от rrrFer Посмотреть сообщение
still_alive, более чем убедил, вот этим: "Не надо каждый раз выделять/освобождать память узла."
хотя...
может быть потому, что в 1% случаев память будет распределяться 99% времени? ))
Наверное поэтому, чтобы ваша программа в 1% случаев не вставала всерьез и надолго, по умолчанию в STL стек таки использует deque? )
Ну это долго, да. Да, чтобы сократить время, используется дек. Но что такое по сути дек? Это набор векторов. Чтобы при перераспределении памяти нужно было копировать не все элементы, а только часть.

Upd
Так сказать, дек - это компромиссное решение.
По сравнению с вектором - куда быстрее перераспределение, чуть медленнее вставка/удаление (за счет переходов между блоками и немногих дополнительных выделений памяти).
По сравнению со списком - больше памяти (если размером указателей в списке можно пренебречь), быстрее вставка/удаление, но часть памяти иногда перераспределяется.

Последний раз редактировалось still_alive; 12.10.2013 в 22:31.
still_alive вне форума Ответить с цитированием
Старый 13.10.2013, 10:36   #38
simples
Форумчанин
 
Регистрация: 03.10.2013
Сообщений: 142
По умолчанию

Цитата:
Сообщение от rrrFer Посмотреть сообщение
ты пнимаешь, что стек - это не массив. Какой смысл в него сайз передавать?
Передаю секретные данные. После прочтения - сжечь.
Код:
    public class Stack : ICollection, IEnumerable, ICloneable
    {
        private object[] _array;
        private const int _defaultCapacity = 10;

        public Stack()
        {
            this._array = new object[10];
            this._size = 0;
        }
        
        public Stack(int initialCapacity)
        {
            if (initialCapacity < 10)
            {
                initialCapacity = 10;
            }
            this._array = new object[initialCapacity];
            this._size = 0;
        }
это все выдержки из МС реализации стэка в НЕТ.



Цитата:
Сообщение от rrrFer Посмотреть сообщение
довай кодом, я не представляю как ты в массив будешь за О(1) элементы добавлять.
Гм... а с каких пор добавление нового элемента в массив - НЕ О(1) операция?
На примере того же кода от МС если не трудно объясните.

Последний раз редактировалось simples; 13.10.2013 в 10:49.
simples вне форума Ответить с цитированием
Старый 13.10.2013, 10:52   #39
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 17,351
По умолчанию

Цитата:
переключать клаву иногда лениво а что, напрягает сильно?
Конечно, чтобы писать по-русски и далее писать слово "размер" нужно переключить регистр. Не просто напрягает - режет слух. Я понимаю когда имеется специфический термин, который сложно выразить на русском одним-двумя словами. Но размер-то чем не угодил?
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Старый 13.10.2013, 14:36   #40
still_alive
Great Code Monkey
Форумчанин
 
Аватар для still_alive
 
Регистрация: 09.08.2007
Сообщений: 533
По умолчанию

simples

Прочитал. Увы, сжечь майкрософт не могу. Хотя давно пора.
Во-первых, причем тут Net? Мне на него физически больно смотреть. Я тогда сейчас хаскелл запилю в тред.

Во-вторых, тут передается емкость, по умолчанию равная 10 (а почему 10, а не 9? или 8? или 666?) Емкость - это ни разу не максимальный размер стека и тем более не размер стека. Емкость - это сколько элементов может находиться в стеке при текущем объеме выделенной памяти.

В-третьих, добавление элемента в стек, когда массив уже заполнен, требует выделения нового куска памяти и копирования туда всех элементов - длительность этой операции зависит от кол-ва элементов в стеке.
still_alive вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Cоздать класс жидкость. определить конструкторы деструкторы и функцию печати. создать публик производный класс. (С++) Динар Габбасов Помощь студентам 0 28.05.2012 18:44
Определить пользовательский класс... BoCbMou C# (си шарп) 0 18.04.2012 12:59
задача - определить Класс Andrew_s Visual C++ 2 13.12.2011 22:58
Определить, создан ли класс. Alex Cones Общие вопросы Delphi 4 14.01.2010 18:12
создать динамический Стек через класс шаблон Petruha-nsk Общие вопросы C/C++ 1 08.11.2009 12:41