Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Архив форумов ЦИТФорума
Море(!) вопросов - Море(!) ответов
 
 FAQFAQ   ПоискПоиск   ПользователиПользователи   ГруппыГруппы   РегистрацияРегистрация 
 ПрофильПрофиль   Войти и проверить личные сообщенияВойти и проверить личные сообщения   ВходВход 
Как правильно задавать вопросы

Какие списки взять?

 
Перейти:  
Этот форум закрыт, вы не можете писать новые сообщения и редактировать старые.   Эта тема закрыта, вы не можете писать ответы и редактировать сообщения.    Список форумов Архив форумов ЦИТФорума -> Программирование
Предыдущая тема :: Следующая тема  
Автор Сообщение
Yello



Зарегистрирован: 09.03.2006
Сообщения: 107

СообщениеДобавлено: Вт Окт 03 2006 11:13    Заголовок сообщения: Какие списки взять? Ответить с цитатой

хочу задать вопрос тому, кто уже делал ОПТИМИЗИРОВАННЫЙ ПО СКОРОСТИ класс «УПОРЯДОЧЕННЫЙ полином от НЕСКОЛЬКИХ переменных» - на каких списках делать для получения максимальной скорости? (хэшировать «старшинство» мономов нельзя, можно только сравнивать; тот кто пользует класс, разные «арифметические» операции вызывает с одинаковой частотой, а присваивание – раза в 2-3 чаще; в каждом полиноме количество мономов - МНОГО). Может это всё давно известно? (Например, как сделано в системах комп. алгебры тип мэпл и т.п.?)
А то вот сделал на линейных однонаправленных списках, а теперь склоняюсь к тому, что это есть не лучший по скорости вариант…
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Kefir



Зарегистрирован: 16.04.2005
Сообщения: 443
Откуда: Пермь

СообщениеДобавлено: Вт Окт 03 2006 12:32    Заголовок сообщения: Ответить с цитатой

А Вы не думаете, что я не знаю на каком ЯП Вы пишите?
Какие библиотеки Вам доступны? и прочеее...

Почему нельзя получить хэш-функцию объекта мне совершенно непонятно...

Далее. Многое зависит от того как Вы создаете эти классы. Например, я бы (программирую на Java) делал их неизменяемыми объектами. Присваивание в этом случае указателя на объект практически не требовало бы времени.

При работе с коллекциями следует учесть следующие характеристики:
1. Добавление элемента в начало/конец списка
2. Добавление элемента в произвольное место списка
3. Доступ к произвольному элементу списка
4. Последовательный доступ к элементам списка

Что из этих характеристик для Вас важнее?
_________________
Самоловских Виталий aka Kefir
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Yello



Зарегистрирован: 09.03.2006
Сообщения: 107

СообщениеДобавлено: Вт Окт 03 2006 13:48    Заголовок сообщения: Ответить с цитатой

Цитата:
А Вы не думаете, что я не знаю на каком ЯП Вы пишите?
Какие библиотеки Вам доступны? и прочеее...

Вообще-то библиотечными классами "контейнер" я всё равно не пользуюсь, так что вроде без разницы, но вообще С++.
Цитата:
1. Добавление элемента в начало/конец списка
2. Добавление элемента в произвольное место списка
3. Доступ к произвольному элементу списка
4. Последовательный доступ к элементам списка

Да вообще-то почти одинаково часто используются все 4.
Вы же представляете, что такое полином - это многочлен, список контейнеров, в каждом - моном. Список - упорядочен по "правилу сравнения" двух мономов между собой (из этого правила можно построить числовую хэш-функцию, но ее значения будут ОГРОМНЫЕ числа). Операции - стандартные (например, умножить полином на моном, сложить два полинома).
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Yello



Зарегистрирован: 09.03.2006
Сообщения: 107

СообщениеДобавлено: Вт Окт 03 2006 18:10    Заголовок сообщения: Ответить с цитатой

Однонаправленные линейные списки / двунаправленные - я сравнил только эти 2 варианта (в каждом есть свои + и -). Но может, кто УЖЕ делал, знает нечто получше (т.е., не намного медленнее на "примитивах" и быстрее (чем линейные списки) на "алгебраических операциях")?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Kefir



Зарегистрирован: 16.04.2005
Сообщения: 443
Откуда: Пермь

СообщениеДобавлено: Чт Окт 05 2006 06:16    Заголовок сообщения: Ответить с цитатой

Yello писал(а):

Вообще-то библиотечными классами "контейнер" я всё равно не пользуюсь, так что вроде без разницы, но вообще С++.

Это зря... Стнадартные библиотеки давно написаны, протестированы и оптимизированы.
Цитата:

Да вообще-то почти одинаково часто используются все 4.
Вы же представляете, что такое полином - это многочлен, список контейнеров, в каждом - моном. Список - упорядочен по "правилу сравнения" двух мономов между собой (из этого правила можно построить числовую хэш-функцию, но ее значения будут ОГРОМНЫЕ числа). Операции - стандартные (например, умножить полином на моном, сложить два полинома).

А вот мне кажется что операции последовательного доступа встречаются гораздо чаще... А хэш-функция необязана быть болльшой и разной для каждого объекта. Для упорядоченных множеств можно использовать деревья - очень хороший вариант, для вставки особенно.
_________________
Самоловских Виталий aka Kefir
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Kefir



Зарегистрирован: 16.04.2005
Сообщения: 443
Откуда: Пермь

СообщениеДобавлено: Чт Окт 05 2006 06:20    Заголовок сообщения: Ответить с цитатой

Yello писал(а):
Однонаправленные линейные списки / двунаправленные - я сравнил только эти 2 варианта (в каждом есть свои + и -). Но может, кто УЖЕ делал, знает нечто получше (т.е., не намного медленнее на "примитивах" и быстрее (чем линейные списки) на "алгебраических операциях")?

Эт очень мало. Вам нужно больше почитать о различных коллекциях. И не только то чему учат в ВУЗах...
_________________
Самоловских Виталий aka Kefir
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Yello



Зарегистрирован: 09.03.2006
Сообщения: 107

СообщениеДобавлено: Пт Окт 06 2006 15:47    Заголовок сообщения: Ответить с цитатой

Кстати, а не знаете, где про них почитать? (Понятно, что можно и самому придумать другие виды "списков", но придумаешь - а потом через время поймешь, что это не оптимально (и переделывай). Так что охота почитать что уже есть).
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Kefir



Зарегистрирован: 16.04.2005
Сообщения: 443
Откуда: Пермь

СообщениеДобавлено: Ср Окт 11 2006 12:20    Заголовок сообщения: Ответить с цитатой

По идее, все в том же Кнуте должно сие быть... Но не гарантирую... Лично я джавовский хелп читал... И книжку Эккеля про Джава. Впринципе в описании STL должно быть описано какие списки в каких случаях применять...
_________________
Самоловских Виталий aka Kefir
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Показать сообщения:   
Этот форум закрыт, вы не можете писать новые сообщения и редактировать старые.   Эта тема закрыта, вы не можете писать ответы и редактировать сообщения.    Список форумов Архив форумов ЦИТФорума -> Программирование Часовой пояс: GMT + 3
Страница 1 из 1

 
Перейти:  
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах


Powered by phpBB © 2001, 2002 phpBB Group
Русская поддержка phpBB

 

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 6608306, ICQ 232284597
Пресс-релизы — pr@citforum.ru
Послать комментарий
Информация для авторов
This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2006 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...