Форум программистов, компьютерный форум CyberForum.ru

Сумматор - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.80
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
09.09.2011, 20:56     Сумматор #1
Можете привести код оптимизированного сумматора?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.09.2011, 20:56     Сумматор
Посмотрите здесь:

C++ Builder Одноразрядный сумматор
C# Сумматор
C++ Класс сумматор..
Сумматор в Quartus II
4-х разрядный сумматор на И-НЕ
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
19.11.2011, 16:21     Сумматор #21
Цитата Сообщение от Bers Посмотреть сообщение
... то используют кэширование данных.
*если нужно многократно считать сумму различных интервалов в массиве
Вот так надо было мне сперва написать. Не подумал, что могут быть разночтения.) Ведь именно для этих целей данное дерево и используется.

Однако, для однократной суммы последовательное сложение по прежнему остаётся самым эффективным вариантом.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Bers
Заблокирован
19.11.2011, 16:22     Сумматор #22
Цитата Сообщение от Deviaphan Посмотреть сообщение
Однако, для однократной суммы последовательное сложение по прежнему остаётся самым эффективным вариантом.
Для однократного сложения само дерево становится невыгодным
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
19.11.2011, 16:23     Сумматор #23
Цитата Сообщение от Bers Посмотреть сообщение
Выигрыш тут ещё в том, что простые вещи проще понимать, и проще использовать.
Плюс много.

Добавлено через 24 секунды
Цитата Сообщение от Bers Посмотреть сообщение
Для однократного сложения само дерево становится невыгодным
Это я уже написал.)
Bers
Заблокирован
19.11.2011, 16:28     Сумматор #24
Английская королева однажды издала указ: гранты и премии тому изобретателю, кто сделает изобретение "полезное" и "практичное".

"Полезное" - значит востребованное.
"Практичное" - значит простое в изготовлении, и удобное в использовании. Для нашей Индустрии ещё и доброе в сопровождении.

Резюмируя, можно сказать, что данный алгоритм интересен для пытливого ума, но не полезен, и не практичен.
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
19.11.2011, 16:29  [ТС]     Сумматор #25
неправда, все тесты просмотреть не получится.
Deviaphan
19.11.2011, 16:31
  #26

Не по теме:

Цитата Сообщение от Bers Посмотреть сообщение
Английская королева однажды издала указ: гранты и премии тому изобретателю, кто сделает изобретение "полезное" и "практичное".
Британские учёные хотят премию?

Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
19.11.2011, 16:31  [ТС]     Сумматор #27
но и практичен, если нужно много раз считать сумму, например вычисление максимальной возрастающей последовательности - максимум вычисляется не один раз, а если все время линейно просматривать так ждать долго очень придется, а сли написать максимизатор, все сразу будет работать в несколько раз быстрее.
Bers
Заблокирован
19.11.2011, 16:33     Сумматор #28
Цитата Сообщение от Даня98 Посмотреть сообщение
но и практичен, если нужно много раз считать сумму, например вычисление максимальной возрастающей последовательности - вычисляется не один раз, а если все время линейно просматривать так ждать долго очень придется, а сли написать максимизатор, все сразу будет работать в несколько раз быстрее.
Там, где требуется максимальная скорость, данный алгоритм будит работать катастрофически медленно.

В таких случаях используют кэширование.
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
19.11.2011, 16:37  [ТС]     Сумматор #29
Цитата Сообщение от Bers Посмотреть сообщение
Там, где требуется максимальная скорость, данный алгоритм будит работать катастрофически медленно.
В таких случаях используют кэширование.
Да нет же! Постоение начальное масимум не так долго, как вы предполагаете!!! А вычисляя, за log n каждый раз экономии будет выше крыши. Не то что ваше суммирование медленное, где все за о(n) вычисляется. Лучше писать сумматор. А какое там кэширование, если вычисляется каждый раз новое?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
19.11.2011, 16:41     Сумматор #30
Цитата Сообщение от Bers Посмотреть сообщение
В таких случаях используют кэширование.
В данном случае, для кэширования может потребоваться даже больше памяти, чем для исходного массива данных. Причем в N раз больше массива размером N. Т.е. N*N значений может потребоваться кэшировать.
Bers
Заблокирован
19.11.2011, 16:42     Сумматор #31
Цитата Сообщение от Даня98 Посмотреть сообщение
Да нет же! Постоение начальное масимум не так долго, как вы предполагаете!!! А вычисляя, за log n каждый раз экономии будет выше крыши. Не то что ваше суммирование медленное, где все за о(n) вычисляется. Лучше писать сумматор. А какое там кэширование, если вычисляется каждый раз новое?
Никто не делает линейное суммирование там, где нужна скорость.
Если сумма постоянно меняется, значит постоянно меняются сами данные.
Если постоянно меняются сами данные, значит имеем потери на дорого построение дерева.

При кэшировании ничего вообще не вычисляются. Сумма изначально известна на любой момент времени.

При этом отсутствуют потери связанные с дорогим построением дерева.
Хранить данные можно как угодно. Например - в обычном массиве.

Добавлено через 1 минуту
Цитата Сообщение от Deviaphan Посмотреть сообщение
В данном случае, для кэширования может потребоваться даже больше памяти, чем для исходного массива данных. Причем в N раз больше массива размером N. Т.е. N*N значений может потребоваться кэшировать.
Зависит от конкретной задачи. Не нужно кэшировать 100% всех вариантов, если работать нужно только с 1% из всех возможных случаев, что и бывает в 100% задач


Цитата Сообщение от Bers Посмотреть сообщение
Если запилить под конкретную задачу - потери будут минимальны. Настолько минимальны, что ими можно будит пренебречь.
Любые унифицированные алгоритмы - дороги.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
19.11.2011, 16:43     Сумматор #32
Цитата Сообщение от Bers Посмотреть сообщение
При кэшировании ничего вообще не вычисляются. Сумма изначально известна на любой момент времени.
Ты не понял. Речь не о сумме всех элементов массива, а о сумме произвольного интервала значений. Т.е. кэшировать нужно каждый возможный интервал.
Bers
Заблокирован
19.11.2011, 16:44     Сумматор #33
Цитата Сообщение от Deviaphan Посмотреть сообщение
Ты не понял. Речь не о сумме всех элементов массива, а о сумме произвольного интервала значений. Т.е. кэшировать нужно каждый возможный интервал.
Это унифицированный алгоритм. Реально не требуется знать "сумму произвольного интервала", а если потребовалось - это хороший повод пересмотреть архитектуру на предмет её косяков.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.11.2011, 16:45     Сумматор
Еще ссылки по теме:

Сумматор
C++ Сумматор - виртуальная машина
4-х разрядный сумматор

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
19.11.2011, 16:45  [ТС]     Сумматор #34
Цитата Сообщение от Bers Посмотреть сообщение
При этом отсутствуют потери связанные с дорогим построением дерева.
Ты не понял, перечитай еще раз.
Yandex
Объявления
19.11.2011, 16:45     Сумматор
Ответ Создать тему
Опции темы

Текущее время: 20:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru