powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика. Вопросы по реализации/оптимизации
25 сообщений из 207, страница 3 из 9
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790989
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я вот летом для себя исследовал сложение в системе
Фибоначчи. Интересно так вышло. Отпишу если не забуду.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791298
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.

Anatoly MoskovskySashaMercury,

Алгоритм использующий malloc не может быть оптимальным :)
Начните с того что отделите выделение памяти от собственно вычислений.
Всегда можно сделать функцию поверх них, которая их совместит.


Лучше было бы передать в функцию адрес по которому будет записан результат ? Т.о. функция должна нести функционал только касаемо алгоритма, и не должна решать вопросы касаемо аллоцирования ? Прототип такой функции будет выглядеть следующим образом.

Код: plaintext
1.
char* la_sum(char* sum, const char* s0, const char* s1)



Вывод выделенный красным нужно использовать и в дальнейшем при проектировании функций и разработке алгоритмов в целом ? То есть существует негласное правило о том, что нужно отделять алгоритм, от работы с памятью ? Я раньше всегда задумывался об этом, но почему-то выбирал тот вариант, по которому вы сделали замечание. Хотя мне ваше замечание нравится, оно вполне обоснованно, и я буду рад его использовать, если вы подтвердите то, что я написал выше.


Anatoly Moskovskymemmove в вашем алгоритме не нужна, т.к. нет пересекающихся областей памяти, memcpy - быстрее в теории.

разве в данном случае нет пересекающихся областей ?
Код: plaintext
1.
2.
3.
4.
		for (int i = 0; i < len_res-1; ++i)
		{
			*(res + i) = *(res + i + 1);
		}



Почему memcpy быстрее в теории ? Это не макрозамена, как например getchar()?

Anatoly MoskovskyНу и если речь зашла про оптимальность, то хранить и обрабатывать числа в виде десятичных цифр - это далеко не оптимально. Храните в виде 32- или 64-битных двоичных цифр размером в машинное слово.
В этом случае ускорятся вычисления, но затормозится отображение (что практически никогда не является критичным)
то есть сейчас я использую 1 байт на 1 знак, а если буду хранить числа в массиве int, и получить результирующее число как результат контактенции этих чисел, то я буду тратить хм..4 Байта,2^32<10^10, значит 9 знаков на 4 Байта, т.о. выигрываю где-то в два раза,1 знак-4/9 байта.
Я вас правильно понял ?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791299
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЯ вот летом для себя исследовал сложение в системе
Фибоначчи. Интересно так вышло. Отпишу если не забуду.

отпишите, будем ждать :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791304
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Допустим я разделяю алгоритм и работу с памятью. Тогда я не буду знать сколько нужно памяти выделять на сумму. Значит мне нужно, для реализации всего, реализовать две функции и одну статическую внешнюю переменную, в которую функция будет передавать длину результата, и только потом будет запускаться вторая функция, и выделять память для результат.
И мне мало того что она статическая внешняя. Хочется сделать чтобы она была видна только двум этим функциям, и никакие другие функции не могли бы её изменить. Но я не встретил такого класса памяти к K&R и в стандарте
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791410
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сегодня разминался, нужно было считать данные из файла. Первая строка количество строк квадратной матрицы, затем все элементы матрицы по строкам.

Вот так организовал чтение данных

Код: 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.
#include <stdio.h>
#include <stdlib.h>

static int n;

//выделение памяти на матрицу nxn
int** allocate_memory(int n)
{
	int** res = NULL;
	res = (int**)malloc(sizeof(int*)*n);
	for (int i = 0; i < n; ++i)
	{
		*(res + i) = NULL;
		*(res + i) = (int*)malloc(sizeof(int)*n);
	}
	return res;
}

//получение данных из файла согласно задачи 126 acmp.ru
int** get_data(FILE* in)
{
	fscanf(in, "%i", &n);
	int** m = allocate_memory(n);

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			fscanf(in, "%i", &m[i][j]);
		}
	}
	return m;
}

int main(int argc,char** argv)
{
	FILE* in = fopen("input.txt", "r");
	if (!in)
		printf("File 'input.txt' not found.\n");
	int** m = get_data(in);
	view_sq_matrix(m,n);
	return 0;
}



Разделил чтение данных, и выделение памяти
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791528
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury, сходу закину тебе поток тегов для размышления.
В математической физике при решении дифуров часто нужны
офигенские матрицы заполненные в основном нулями. И лишь
на диагонали лежат значимые коэффициенты. И еще где-то
децл ненулевых элементов. Причём еще и зеркальны относительно
диагонали. Вобщем тут на англичанской мове основные тезисы:

http://en.wikipedia.org/wiki/Sparse_matrix

Подумай над этим.

P.S. Ну как закинул?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791549
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury
Код: plaintext
1.
2.
3.
4.
		for (int i = 0; i < len_res-1; ++i)
		{
			*(res + i) = *(res + i + 1);
		}



Тут я-бы по другому переписал
Код: plaintext
1.
2.
3.
      temp=*res;
      res--;
      *res=temp;


Ну и цикл естественно в обратную сторону развернуть.

Кстати это может быть объяснением по поводу отсутствия в API
memcpy копирующей на символ назад. Возможно по соображениям
неэффективной хардварной реализации.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791680
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury//установка стартового значения
//пишем в конец результирующей строки минимальное число
Скопировав в результат длиннейшее число ты сэкономишь время как на копировании, так и на сложении.

SashaMercury//сдвиг
return res;
Вернув res+1 ты сэкономишь время на сдвиге.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791728
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если создать класс - "цепочка операций" (OperationChain)
то можно некоторые действия сокращать.

К примеру в следующем примере арифметика
сокращается законами алгебры.

Код: plaintext
1.
x + y + z - y - x = z



Ну или если Саша допилит умножение то учитывать
умножение не ноль в конце цепочки.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791761
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryДопустим я разделяю алгоритм и работу с памятью. Тогда я не буду знать сколько нужно памяти выделять на сумму. Значит мне нужно, для реализации всего, реализовать две функции и одну статическую внешнюю переменную, в которую функция будет передавать длину результата, и только потом будет запускаться вторая функция, и выделять память для результат.
И мне мало того что она статическая внешняя. Хочется сделать чтобы она была видна только двум этим функциям, и никакие другие функции не могли бы её изменить. Но я не встретил такого класса памяти к K&R и в стандарте
Этот "класс памяти" называется аргумент функции :)

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
char* la_sum(const char* s0, const char* s1)
{
   // compute lengths
   
   // allocate memory
 
   // calculate in-place
   la_sum_inplace(sum, len, s0, len0, s1, len1);
   return sum;
}

void la_sum_inplace(char* sum, size_t len, const char* s0, size_t len0, const char* s1, size_t len1)
{
}
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791787
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Оптимизации различные рассмотреть. Что будет после la_sum("12345678", "0");
Можно ли вернуть ccылку на первый аргумент?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791880
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
только пришёл.

mayton, мы все знакомы с разряженными матрицами:) У программистов вероятно возникает вопрос как бы их хранить.
Anatoly Moskovsky, я вас понял, потому привёл пример выше. Мои выводы касаемо разделения алгоритма и работы с памятью верны ?

Спасибо всем за предложения по оптимизации. Завтра исправлю код. Мне пора : (
Доброго времени суток, Сообщество :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38791948
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это выкинуть. Если матрица - квадратная то не нужно аллоцировать отдельно строки.
SashaMercury//выделение памяти на матрицу nxn
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
int** allocate_memory(int n)
{
	int** res = NULL;
	res = (int**)malloc(sizeof(int*)*n);
	for (int i = 0; i < n; ++i)
	{
		*(res + i) = NULL;
		*(res + i) = (int*)malloc(sizeof(int)*n);
	}
	return res;
}


Вот так правильно

Код: plaintext
1.
2.
3.
int* allocate_memory(int n){
        return (int*)malloc(sizeof(int)*n*n);
}
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792184
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

Стесняюсь спросит, когда уже компилятор С-шный будете использовать? :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792423
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky,

поискал в настройках VS 2013 Express, и не нашёл как это сделать. Потом 'погуглил', и ответа на вопрос также не нашёл. Видимо плохо искал. Вообще это я стесняюсь такие вопросы задавать, потому не спросил тут, как это сделать тут.

mayton, это я понимаю. Просто мне захотелось сделать так как я сделал. честно:) А вот раз вы привели такой пример, то у меня вопрос. Ваш пример выигрывает в скорости, и это очевидно ?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792428
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

Переименуйте файл из .cpp в .c :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792434
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо..
перестал работать тернарный оператор : (
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792435
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
говорит что левый операнд должен быть L-value. В Си, тернарный оператор используется только для присваивания.., правильно догадался?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792444
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Исправил

Код: 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.
#define MAX_POW 1001+1

//выделение len Байт
char* allocate_memory(size_t len)
{
	return (char*)malloc(len*sizeof(char));
}

//s1-большее число, s2-минимальное число
int la_sum_inplace(char* sum, size_t len, const char* s1, size_t len1, const char* s2, size_t len2)
{
	memset(sum, '0', len);//установка стартового значения
	memcpy(sum + len1 - len2 + 1, s2, len2);//пишем в конец результирующей строки минимальное число
	//основная часть алгоритма
	int d = 0;
	for (int i = len - 2; i > 0; i--)
	{
		int t0 = *(sum + i) + *(s1 + i - 1) + d - 2 * '0';
		int t1 = t0 % 10;
		*(sum + i) = t1 + '0';
		d = (t0 >= 10) ? 1 : 0;
	}
	*(sum + len - 1) = '\0';
	if (!d)
	{
		memmove(sum, sum + 1, len - 1);
	}
	else
	{
		*(sum + 0) = d + '0';
	}
	return 1;
}

//сумма двух целых неотрицательных чисел s1,s2>=0
char* la_sum(const char* s0, const char* s1)
{
	// compute lengths
	size_t len[2] = { strlen(s0), strlen(s1) };
	int max_i = (len[0] > len[1]) ? 0 : 1; //индекс максимальной строки
	int min_i = 1 - max_i;//индекс минимальной строки
	const char* max_s = (max_i == 0) ? s0 : s1;
	const char* min_s = (min_i == 0) ? s0 : s1;

	if (len[max_i] > MAX_POW - 1)
	{
		printf("Incorrect size of the string(s).\n");
		return NULL;
	}
	int len_res = len[max_i] + 1 + 1;//просим на 1 Байт больше чтобы исключить вероятность повторного аллоцирования
	// allocate memory
	char* res = allocate_memory(len_res);
	// calculate in-place
	la_sum_inplace(res, len_res, max_s, len[max_i], min_s, len[min_i]);	
	return res;
}



что вы имеете ввиду под словом "in-place" ?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792446
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryперестал работать тернарный оператор : (
Потому что вы его используете невпопад.
Он предназначен для вычисления условных выражений, а не для записи оператора if в одну строку.
SashaMercuryчто вы имеете ввиду под словом "in-place" ?
Что результат записывается в переданный аргумент ("по месту"), а не выделяется память.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792447
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Понятно.
Кстати, никто так и не ответил. Используете ли вы сейчас эти функции в своей работе ? memcpy, memset, memmove, или они не устраивают вас как и fscanf ?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792451
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

Используем. И scanf тоже, где это уместно :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792576
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercurymayton, это я понимаю. Просто мне захотелось сделать так как я сделал. честно:) А вот раз вы привели такой пример, то у меня вопрос. Ваш пример выигрывает в скорости, и это очевидно ?
Для обычных (неразрежённых) матриц, кубов, гиперкубов мой пример выигрывает в скорости,
простоте кодирования, в быстром доступе к элементу по индексу. Мой пример также
уменьшает нагрузку на аллокатор памяти ОС и не флудит ненужными транзакциями
на выделение-освобождение.

Но в данном конкретном кейсе самое главное преимущество - дуракоустойчивость.
Он прост как АК-47 и его невозможно поломать или испортить.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792951
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хорошо. Я всё запомнил.
Спасибо всем :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38792988
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати, олимпиада проходила по математике, может кому-нибудь будет интересно, привожу пару простых задач:
1. На доске написаны 10 чисел: единица и 9 нулей. Разрешается выбрать любые два числа, и заменить каждое из них средним арифметическим. Какое наименьшее число может получиться на месте единицы после серии(сколь угодного количества) таких операций ?
2. Докажите что функция нечётная.

Прошу прощение за офтоп, но сегодня ведь пятница, и может быть кто-нибудь захочет размяться немножко перед 4 днями высыпания и отдыха C:. Тем более задачи не сложные.
...
Рейтинг: 0 / 0
25 сообщений из 207, страница 3 из 9
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика. Вопросы по реализации/оптимизации
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]