| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
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 |
|
| Вернуться к началу |
|
|
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 |
|
| Вернуться к началу |
|
|
Kefir
Зарегистрирован: 16.04.2005
Сообщения: 443
Откуда: Пермь
|
| Добавлено: Чт Окт 05 2006 06:20 Заголовок сообщения: |
|
|
| Yello писал(а): | | Однонаправленные линейные списки / двунаправленные - я сравнил только эти 2 варианта (в каждом есть свои + и -). Но может, кто УЖЕ делал, знает нечто получше (т.е., не намного медленнее на "примитивах" и быстрее (чем линейные списки) на "алгебраических операциях")? |
Эт очень мало. Вам нужно больше почитать о различных коллекциях. И не только то чему учат в ВУЗах...
_________________
Самоловских Виталий aka Kefir |
|
| Вернуться к началу |
|
|
Yello
Зарегистрирован: 09.03.2006
Сообщения: 107
|
| Добавлено: Пт Окт 06 2006 15:47 Заголовок сообщения: |
|
|
| Кстати, а не знаете, где про них почитать? (Понятно, что можно и самому придумать другие виды "списков", но придумаешь - а потом через время поймешь, что это не оптимально (и переделывай). Так что охота почитать что уже есть). |
|
| Вернуться к началу |
|
|
Kefir
Зарегистрирован: 16.04.2005
Сообщения: 443
Откуда: Пермь
|
| Добавлено: Ср Окт 11 2006 12:20 Заголовок сообщения: |
|
|
По идее, все в том же Кнуте должно сие быть... Но не гарантирую... Лично я джавовский хелп читал... И книжку Эккеля про Джава. Впринципе в описании STL должно быть описано какие списки в каких случаях применять...
_________________
Самоловских Виталий aka Kefir |
|
| Вернуться к началу |
|
|
|
FAQ 
Поиск 
Пользователи 
Группы
Регистрация
Профиль 
Войти и проверить личные сообщения 
Вход 
