Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Я вот летом для себя исследовал сложение в системе Фибоначчи. Интересно так вышло. Отпишу если не забуду. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.10.2014, 16:56 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Здравствуйте. Anatoly MoskovskySashaMercury, Алгоритм использующий malloc не может быть оптимальным :) Начните с того что отделите выделение памяти от собственно вычислений. Всегда можно сделать функцию поверх них, которая их совместит. Лучше было бы передать в функцию адрес по которому будет записан результат ? Т.о. функция должна нести функционал только касаемо алгоритма, и не должна решать вопросы касаемо аллоцирования ? Прототип такой функции будет выглядеть следующим образом. Код: plaintext 1. Вывод выделенный красным нужно использовать и в дальнейшем при проектировании функций и разработке алгоритмов в целом ? То есть существует негласное правило о том, что нужно отделять алгоритм, от работы с памятью ? Я раньше всегда задумывался об этом, но почему-то выбирал тот вариант, по которому вы сделали замечание. Хотя мне ваше замечание нравится, оно вполне обоснованно, и я буду рад его использовать, если вы подтвердите то, что я написал выше. Anatoly Moskovskymemmove в вашем алгоритме не нужна, т.к. нет пересекающихся областей памяти, memcpy - быстрее в теории. разве в данном случае нет пересекающихся областей ? Код: plaintext 1. 2. 3. 4. Почему memcpy быстрее в теории ? Это не макрозамена, как например getchar()? Anatoly MoskovskyНу и если речь зашла про оптимальность, то хранить и обрабатывать числа в виде десятичных цифр - это далеко не оптимально. Храните в виде 32- или 64-битных двоичных цифр размером в машинное слово. В этом случае ускорятся вычисления, но затормозится отображение (что практически никогда не является критичным) то есть сейчас я использую 1 байт на 1 знак, а если буду хранить числа в массиве int, и получить результирующее число как результат контактенции этих чисел, то я буду тратить хм..4 Байта,2^32<10^10, значит 9 знаков на 4 Байта, т.о. выигрываю где-то в два раза,1 знак-4/9 байта. Я вас правильно понял ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 03:39 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
maytonЯ вот летом для себя исследовал сложение в системе Фибоначчи. Интересно так вышло. Отпишу если не забуду. отпишите, будем ждать :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 03:40 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Допустим я разделяю алгоритм и работу с памятью. Тогда я не буду знать сколько нужно памяти выделять на сумму. Значит мне нужно, для реализации всего, реализовать две функции и одну статическую внешнюю переменную, в которую функция будет передавать длину результата, и только потом будет запускаться вторая функция, и выделять память для результат. И мне мало того что она статическая внешняя. Хочется сделать чтобы она была видна только двум этим функциям, и никакие другие функции не могли бы её изменить. Но я не встретил такого класса памяти к K&R и в стандарте ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 04:41 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Сегодня разминался, нужно было считать данные из файла. Первая строка количество строк квадратной матрицы, затем все элементы матрицы по строкам. Вот так организовал чтение данных Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. Разделил чтение данных, и выделение памяти ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 09:20 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
SashaMercury, сходу закину тебе поток тегов для размышления. В математической физике при решении дифуров часто нужны офигенские матрицы заполненные в основном нулями. И лишь на диагонали лежат значимые коэффициенты. И еще где-то децл ненулевых элементов. Причём еще и зеркальны относительно диагонали. Вобщем тут на англичанской мове основные тезисы: http://en.wikipedia.org/wiki/Sparse_matrix Подумай над этим. P.S. Ну как закинул? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 12:14 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
SashaMercury Код: plaintext 1. 2. 3. 4. Тут я-бы по другому переписал Код: plaintext 1. 2. 3. Ну и цикл естественно в обратную сторону развернуть. Кстати это может быть объяснением по поводу отсутствия в API memcpy копирующей на символ назад. Возможно по соображениям неэффективной хардварной реализации. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 12:24 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
SashaMercury//установка стартового значения //пишем в конец результирующей строки минимальное число Скопировав в результат длиннейшее число ты сэкономишь время как на копировании, так и на сложении. SashaMercury//сдвиг return res; Вернув res+1 ты сэкономишь время на сдвиге. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 14:02 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Если создать класс - "цепочка операций" (OperationChain) то можно некоторые действия сокращать. К примеру в следующем примере арифметика сокращается законами алгебры. Код: plaintext 1. Ну или если Саша допилит умножение то учитывать умножение не ноль в конце цепочки. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 14:29 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
SashaMercuryДопустим я разделяю алгоритм и работу с памятью. Тогда я не буду знать сколько нужно памяти выделять на сумму. Значит мне нужно, для реализации всего, реализовать две функции и одну статическую внешнюю переменную, в которую функция будет передавать длину результата, и только потом будет запускаться вторая функция, и выделять память для результат. И мне мало того что она статическая внешняя. Хочется сделать чтобы она была видна только двум этим функциям, и никакие другие функции не могли бы её изменить. Но я не встретил такого класса памяти к K&R и в стандарте Этот "класс памяти" называется аргумент функции :) Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 14:48 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Оптимизации различные рассмотреть. Что будет после la_sum("12345678", "0"); Можно ли вернуть ccылку на первый аргумент? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 15:01 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
только пришёл. mayton, мы все знакомы с разряженными матрицами:) У программистов вероятно возникает вопрос как бы их хранить. Anatoly Moskovsky, я вас понял, потому привёл пример выше. Мои выводы касаемо разделения алгоритма и работы с памятью верны ? Спасибо всем за предложения по оптимизации. Завтра исправлю код. Мне пора : ( Доброго времени суток, Сообщество :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 16:05 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Это выкинуть. Если матрица - квадратная то не нужно аллоцировать отдельно строки. SashaMercury//выделение памяти на матрицу nxn Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Вот так правильно Код: plaintext 1. 2. 3. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 16:43 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
SashaMercury, Стесняюсь спросит, когда уже компилятор С-шный будете использовать? :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.10.2014, 19:13 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Anatoly Moskovsky, поискал в настройках VS 2013 Express, и не нашёл как это сделать. Потом 'погуглил', и ответа на вопрос также не нашёл. Видимо плохо искал. Вообще это я стесняюсь такие вопросы задавать, потому не спросил тут, как это сделать тут. mayton, это я понимаю. Просто мне захотелось сделать так как я сделал. честно:) А вот раз вы привели такой пример, то у меня вопрос. Ваш пример выигрывает в скорости, и это очевидно ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.10.2014, 01:46 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
SashaMercury, Переименуйте файл из .cpp в .c :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.10.2014, 02:07 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Спасибо.. перестал работать тернарный оператор : ( ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.10.2014, 02:30 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
говорит что левый операнд должен быть L-value. В Си, тернарный оператор используется только для присваивания.., правильно догадался? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.10.2014, 02:31 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Исправил Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. что вы имеете ввиду под словом "in-place" ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.10.2014, 03:31 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
SashaMercuryперестал работать тернарный оператор : ( Потому что вы его используете невпопад. Он предназначен для вычисления условных выражений, а не для записи оператора if в одну строку. SashaMercuryчто вы имеете ввиду под словом "in-place" ? Что результат записывается в переданный аргумент ("по месту"), а не выделяется память. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.10.2014, 04:03 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Понятно. Кстати, никто так и не ответил. Используете ли вы сейчас эти функции в своей работе ? memcpy, memset, memmove, или они не устраивают вас как и fscanf ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.10.2014, 04:23 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
SashaMercury, Используем. И scanf тоже, где это уместно :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.10.2014, 05:06 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
SashaMercurymayton, это я понимаю. Просто мне захотелось сделать так как я сделал. честно:) А вот раз вы привели такой пример, то у меня вопрос. Ваш пример выигрывает в скорости, и это очевидно ? Для обычных (неразрежённых) матриц, кубов, гиперкубов мой пример выигрывает в скорости, простоте кодирования, в быстром доступе к элементу по индексу. Мой пример также уменьшает нагрузку на аллокатор памяти ОС и не флудит ненужными транзакциями на выделение-освобождение. Но в данном конкретном кейсе самое главное преимущество - дуракоустойчивость. Он прост как АК-47 и его невозможно поломать или испортить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.10.2014, 09:54 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Хорошо. Я всё запомнил. Спасибо всем :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.10.2014, 14:04 |
|
||
|
Длинная арифметика. Вопросы по реализации/оптимизации
|
|||
|---|---|---|---|
|
#18+
Кстати, олимпиада проходила по математике, может кому-нибудь будет интересно, привожу пару простых задач: 1. На доске написаны 10 чисел: единица и 9 нулей. Разрешается выбрать любые два числа, и заменить каждое из них средним арифметическим. Какое наименьшее число может получиться на месте единицы после серии(сколь угодного количества) таких операций ? 2. Докажите что функция нечётная. Прошу прощение за офтоп, но сегодня ведь пятница, и может быть кто-нибудь захочет размяться немножко перед 4 днями высыпания и отдыха C:. Тем более задачи не сложные. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.10.2014, 14:28 |
|
||
|
|

start [/forum/topic.php?fid=57&msg=38792447&tid=2019209]: |
0ms |
get settings: |
8ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
47ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
56ms |
get tp. blocked users: |
1ms |
| others: | 11ms |
| total: | 155ms |

| 0 / 0 |
