Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 27.12.2009, 22:08
Аватар для Ilya Porublyov
Новичок

Отправить личное сообщение для Ilya Porublyov Посмотреть профиль Найти все сообщения от Ilya Porublyov
 
Регистрация: 28.09.2006
Адрес: Cherkasy, sometimes Kiev
Сообщений: 18

Аналог vector-а в Python
Необходимо переписать одну алгоритмическую программку на Python (язык питон задан жёстко, независимо от моего желания). В_связи с этим хотелось бы понять, что там явлется наиболее точным аналогом плюсового vector-а.

Некоторые источники заявляют "пользуйся списками (list)", но действительно ли это лучшее решение? Какая у того питонового list-а ассимптотика?

Надо иметь структуру данных, маленько похожую на списки смежности графа (но не в точности их). Я вполне уверен, что наиболее адекватное решение в плюсах -- vector<set<int> >. Ещё иначе говоря, и по одному, и по другому параметру константное или логарифмическое время допустимы, линейное -- нет.

Это был один вопрос. Другой (который я накрайняк могу и обойти мелкими изменениями алгоритма) -- какая получится групповая (суммарная) ассимптотическая оценка, если многократно удалять по несколько элементов из НАЧАЛА списка с помощью del a[0:i]?
__________________
Ilya Porublyov

Последний раз редактировалось Ilya Porublyov, 27.12.2009 в 22:30. Причина: исправление опечатки
  #2  
Старый 28.12.2009, 00:10
гость

 
Сообщений: n/a

Сообщение от Ilya Porublyov Посмотреть сообщение
Некоторые источники заявляют "пользуйся списками (list)", но действительно ли это лучшее решение? Какая у того питонового list-а ассимптотика?
хорошая, не волнуйся, такая же как и у std::vector - http://wiki.python.org/moin/TimeComplexity

Цитата:
Надо иметь структуру данных, маленько похожую на списки смежности графа (но не в точности их). Я вполне уверен, что наиболее адекватное решение в плюсах -- vector<set<int> >.
А зачем вам еще и std::set внутри? Почему не vector<vector<int> >?

Цитата:
Это был один вопрос. Другой (который я накрайняк могу и обойти мелкими изменениями алгоритма) -- какая получится групповая (суммарная) ассимптотическая оценка, если многократно удалять по несколько элементов из НАЧАЛА списка с помощью del a[0:i]?
Каждое удаление стоит O(n), так как все элементы сдвигаются каждый раз. У std::vector точно так же. Удалять надо из конца, тогда все будет хорошо.
  #3  
Старый 28.12.2009, 02:10
Аватар для Ilya Porublyov
Новичок

Отправить личное сообщение для Ilya Porublyov Посмотреть профиль Найти все сообщения от Ilya Porublyov
 
Регистрация: 28.09.2006
Адрес: Cherkasy, sometimes Kiev
Сообщений: 18

Сообщение от гость Посмотреть сообщение
хорошая, не волнуйся, такая же как и у std::vector - http://wiki.python.org/moin/TimeComplexity


А зачем вам еще и std::set внутри? Почему не vector<vector<int> >?
За ссылку спасибо.

А vector<vector<int> > таки не подходит, потому что весьма частая операция -- искать, есть ли в таком-то (по номеру) контейнере такой-то (по значению) элемент. Надеюсь, Вы не станете пытаться убеждать меня, что тут целесообразно использовать vector<vector<int> >...
__________________
Ilya Porublyov
  #4  
Старый 28.12.2009, 05:22
гость

 
Сообщений: n/a

Хеш-таблица побыстрее std::set будет. В питоне хеш-таблица - это dict.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра