|
Решение разреженных СЛУ | ☑ | ||
---|---|---|---|---|
0
Tateossian
28.06.16
✎
12:26
|
Привет, форумчане! Нужна ваша помощь. Решил реализовать некий функционал с помощью решения системы линейных уравнений. В УПП в РАУЗе считается себестоимость методом Гаусса-Зейделя, но мне этот метод (и общие итерационные, Якоби, Гаусс) и прочие не подходят, так как матрица сильно разреженная. Стал гуглить, нашел вот такую ссылку http://dxdy.ru/topic9158.html, здесь перечисляются пакеты, но все они на C/c++ в основном и для них нужна обертка, как dll из 1С не подключить. Кто нибудь сталкивался с такой проблемой, а именно: решение в 1С разреженных матриц.
|
|||
1
H A D G E H O G s
28.06.16
✎
12:29
|
(0) А можно имя модуля и процедуры в упп, где это решается?
|
|||
2
Tateossian
28.06.16
✎
12:31
|
Ну и такой нюанс: 1С на матрицах размерностью более 1000 уходит в глубокую задумчивость. Кроме того, эксперемнтально установлено, обращение к произвольной области памяти (элементу массива) достаточно долгая операция при числе элементов более 1000000.
Если инициализировать массив нулями, то на это уходит в 4 (!) раза больше времени, чем создать таблицу значений с 1000 строк с типом число и использовать метод таблицы значений ВыгрузитьКолонку() |
|||
3
Tateossian
28.06.16
✎
12:31
|
(1) Набери в поиске по конфигурации Гаусс.
|
|||
4
H A D G E H O G s
28.06.16
✎
12:32
|
(2) Да, все так и есть и это - логично.
|
|||
5
H A D G E H O G s
28.06.16
✎
12:37
|
" В УПП в РАУЗе считается себестоимость методом Гаусса-Зейделя, но мне этот метод (и общие итерационные, Якоби, Гаусс) и прочие не подходят, так как матрица сильно разреженная."
https://ru.wikipedia.org/wiki/Метод_Гаусса_%E2%80%94_Зейделя Хорошо подходит для разреженных матриц. |
|||
6
Tateossian
28.06.16
✎
12:39
|
(5) Долго считает, вот в чем беда, а когда сильная разреженность нужно много итераций.
|
|||
7
Tateossian
28.06.16
✎
12:40
|
(5) И самый главный косяк - если на диагонали будет ноль, то как быть? Вот это место:
a[i][i] |
|||
8
H A D G E H O G s
28.06.16
✎
12:44
|
(7) А что там такого?
|
|||
9
Tateossian
28.06.16
✎
12:46
|
(8) Не ясно выразился. Есть такой кусок кода:
x[i] = (b[i] - var) / a[i][i] который определяет искомый X, но что, если a[i][i] = 0, а на ноль делить нельзя. |
|||
10
H A D G E H O G s
28.06.16
✎
12:48
|
(9) Открой ссылку, которую я привел.
|
|||
11
Tateossian
28.06.16
✎
12:48
|
(10) Так это оттуда я и скопипастил
|
|||
12
H A D G E H O G s
28.06.16
✎
12:50
|
Давай я напишу ВК-шечку, которая будет решать эти ваши СЛУ быстро. С тебя - база с данными.
|
|||
13
H A D G E H O G s
28.06.16
✎
12:50
|
(11) Ты не на реализацию смотри, а на алгоритм в формулах.
|
|||
14
Tateossian
28.06.16
✎
12:53
|
(13) Вот, запусти вот этот алгоритм:
МатрицаКоэффициентов = Новый Массив(3,3); МатрицаКоэффициентов[0][0]=4; МатрицаКоэффициентов[0][1]=-1; МатрицаКоэффициентов[0][2]=0; МатрицаКоэффициентов[1][0]=-1; МатрицаКоэффициентов[1][1]=4; МатрицаКоэффициентов[1][2]=-1; МатрицаКоэффициентов[2][0]=0; МатрицаКоэффициентов[2][1]=-1; МатрицаКоэффициентов[2][2]=4; СтолбецПравыхЧастей = Новый Массив(3); СтолбецПравыхЧастей[0]=2; СтолбецПравыхЧастей[1]=6; СтолбецПравыхЧастей[2]=2; Глубина = МатрицаКоэффициентов.Количество(); ТЗН = Новый ТаблицаЗначений; ТЗН.Колонки.Добавить("Нумератор", Новый ОписаниеТипов("Число")); Для Инд = 1 По Глубина Цикл Стр = ТЗН.Добавить(); Стр.Нумератор = 0; КонецЦикла; a = МатрицаКоэффициентов; b = СтолбецПравыхЧастей; p = ТЗН.ВыгрузитьКолонку("Нумератор"); x = ТЗН.ВыгрузитьКолонку("Нумератор"); //for (int i = 0; i < n; i++) // p[i] = x[i]; //for (int i = 0; i < n; i++) //{ // double var = 0; // for (int j = 0; j < i; j++) // var += (a[i][j] * x[j]); // for (int j = i + 1; j < n; j++) // var += (a[i][j] * p[j]); // x[i] = (b[i] - var) / a[i][i]; //} Для Инд = 1 По 10 Цикл Для i = 0 По Глубина-1 Цикл p[i] = x[i]; КонецЦикла; Для i=0 По Глубина-1 Цикл Сум = 0; Для j = 0 По i-1 Цикл Сум = Сум + (a[i][j] * x[j]); КонецЦикла; Для j= i+1 По Глубина-1 Цикл Сум = Сум + (a[i][j] * p[j]); КонецЦикла; x[i] = (b[i] - Сум) / a[i][i]; КонецЦикла; КонецЦикла |
|||
15
Tateossian
28.06.16
✎
12:54
|
(13) А потом сделай, скажем, вот так:
МатрицаКоэффициентов[2][2]=0 И скажи, что получится? |
|||
16
Tateossian
28.06.16
✎
12:58
|
(12) Я тебе могу скинуть файл 3000х3000 в любом виде. Пойдет? Заинтриговал, на чем писать будешь?
|
|||
17
Bigbro
28.06.16
✎
12:58
|
получится что у тебя система уравнений кривая. если ты без последнего неизвестного (n-ого) имеешь n уравнений.
|
|||
18
Bigbro
28.06.16
✎
12:59
|
прежде чем автоматизировать бардак, наведите порядок, иначе получите автоматизированный бардак (с)
|
|||
19
H A D G E H O G s
28.06.16
✎
12:59
|
(16) Дельфи.
|
|||
20
H A D G E H O G s
28.06.16
✎
12:59
|
(16) csv
|
|||
21
Tateossian
28.06.16
✎
13:02
|
(17) Я тебе скажу больше, у меня не квадратная матрица, а прямоугольная и я сделал изврат, дописав нулевых строк:) На самом деле это ситуация называется Недоопределеенная матрица.
У нее либо нет решений, либо бесконечно много решений. Мне надо получить одно любое решение из бесконечного множества. https://ru.wikipedia.org/wiki/Недоопределённая_система А может быть, наоборот, переопределенная система. |
|||
22
Bigbro
28.06.16
✎
13:13
|
ну с такими решениями ничего не скажу... хотя сомнения в правильности выбора инструмента появились.
|
|||
23
H A D G E H O G s
28.06.16
✎
13:13
|
Файлик то будет?
|
|||
24
Tateossian
28.06.16
✎
13:16
|
(23) Будет, подожди немного.
|
|||
25
Tateossian
28.06.16
✎
13:17
|
(22) Экспериментирую
|
|||
26
Кирпич
28.06.16
✎
13:18
|
(0) а lpsolve умеет такое решать? не в курсе?
|
|||
27
Tateossian
28.06.16
✎
13:21
|
(26) Не в курсе, но, судя по описанию, это несколько иной класс задач.
|
|||
28
Кирпич
28.06.16
✎
13:24
|
(27) я помню, соседи по парте в него какие то матрицы загружали пару лет назад и говорили типа мощная штука.
|
|||
29
Tateossian
28.06.16
✎
13:27
|
||||
30
Кирпич
28.06.16
✎
13:30
|
(29) это я к тому, что у него есть COM dll, можно из 1С пользовать.
|
|||
31
rphosts
28.06.16
✎
13:35
|
ТС решил переписать расчёт себестоимости для РАУЗ?
|
|||
32
Tateossian
28.06.16
✎
13:38
|
(31) Типа того, точнее, свой расчет себестоимости.
|
|||
33
rphosts
28.06.16
✎
13:42
|
(32) и что дальше? Свою УПП городить? И самое главное - зачем тебе РАУЗ который будет иметь подпространство решений? Ты это собираешься выдать экономистам/финансистам/руководителям?
|
|||
34
Tateossian
28.06.16
✎
13:54
|
(33) Затем, что специфика такая. Возможно другие варианты, но я пробую именно так, потому что считаю, что это будет не тривиальное и хорошее решение. Если взлетит.
А РАУЗом вообще не пользуемся. В программе исторически свой расчет себестоимости и он живет! Работает, цифры экономистов устраивают, сто раз все проверено. Немного приходится допиливать для поддержки, а я решил оптимизировать ибо стал тормозить. |
|||
35
Tateossian
28.06.16
✎
13:55
|
(23) Давай тебе эксель скину, ибо csv весит 10 Мб, а эксель 120Кб?
|
|||
36
kauksi
28.06.16
✎
13:55
|
(0) Главное использовать CUDA, у них очень хорошо оптимизированные бибилиотеки для решения линейных уравнений, ускорение раз в 20, я еще в 2011 году об этом думал...
|
|||
37
Tateossian
28.06.16
✎
13:56
|
||||
38
Кирпич
28.06.16
✎
14:00
|
(35) эксель, видимо, догадался зазиповать, а те нет :)
|
|||
39
H A D G E H O G s
28.06.16
✎
14:01
|
||||
40
Tateossian
28.06.16
✎
14:03
|
(39) Я ошибку нашел у себя благодаря рассуждениям в этой ветке.
Но то, что ты видишь - это нормально. Там 90% ячеек - нули. |
|||
41
Tateossian
28.06.16
✎
14:07
|
(39) Попробую сейчас быстро исправления сделать, там меньше нулевых ячеек должно быть. Я потерял коэффициенты. Не смотри в этот файл.
|
|||
42
Tateossian
28.06.16
✎
14:10
|
(38) Да понятно, что текст ужимается в 98%. Xml сжимается очень хорошо. csv это текст без сжатия.
|
|||
43
Михаил Козлов
29.06.16
✎
11:13
|
Если матрица прямоугольная и число строк мало по сравнению с числом столбцов, то можно преобразованиями Жордана-Гаусса привести матрицу к трапециевидному типу и получить общее решение (или убедиться в отсутствии такового). Трудоемкость или O(n^3) или O(n^2*m) (не уверен. n - число строк, m - число столбцов).
Наверняка, в библиотеках линейной алгебры это есть. Но можно и в 1С такое сделать. По моему опыту (гонял матрицы до 100 строк), матрицу с числом строк - несколько десятков, можно привести за приемлемое время. Для общего сведения: 1. Довольно активно разрабатывались методы решения "полосатых" СЛУ (3,5,7-диагональных) в целях численного решения задач мат. физики по разностным схемам. 2. Для матриц, которые можно привести к виду: относительно небольшие по размеру квадратные подматрицы по диагонали и небольшое количество общих связывающих уравнений, общий подход был описан в книге В.И.Цурков "Декомпозиция в задачах большой размерности", Наука, 1981. Содержательно такая структура уравнений описывает "изолированные" подсистемы, связанные небольшим числом общих уравнений. |
|||
44
Tateossian
07.07.16
✎
18:23
|
Возвращаясь к этой теме.
После долгого и кропотливого анализа формируемых матриц нашел пару ошибок, устранив которые получилось их нормализовать, приведя к квадратному виду. Но это еще не все, самое интересное было впереди: матрица размерностью 6000x6000 силами 1С решалась 3700 секунд. 90% львиной доли ушло вот на это место, a[i][j] = a[i][j] / t. Такое время нельзя считать приемлемым, хоть и задача решена - уравнение считается правильно. Тогда пришлось пойти на изврат в легкой форме и написать нативную dll на срр. Результат такой - решение матрицы составляет 420 секунд, что почти на порядок(!) быстрее. Такова цена за неявную типизацию... |
|||
45
Cyberhawk
07.07.16
✎
21:56
|
Куда и какой код внести в типовую, чтобы на порядок быстрее решалось там?
|
|||
46
Tateossian
07.07.16
✎
22:30
|
(45) Никуда, 1С не может в большие вычисления, так как плохо работает с произвольным доступом к памяти.
|
|||
47
H A D G E H O G s
07.07.16
✎
22:38
|
(46) Дай тестовый набор
|
|||
48
H A D G E H O G s
08.07.16
✎
21:01
|
||||
49
H A D G E H O G s
08.07.16
✎
21:08
|
Обычный массив 1С - это связный список, так он добавляемый. Таким образом, это не массив в классическом понимании, он не лежит в памяти непрерывно и доступ к нему происходит через поиск нужного элемента. Со Структурой таже херь.
Есть надежда, что ФиксированныйМассив - это классический, непрерывный в памяти массив с быстрым доступом к элементу. |
|||
50
H A D G E H O G s
08.07.16
✎
21:09
|
так он добавляемый-> так как он добавляемый
|
|||
51
Tateossian
08.07.16
✎
21:09
|
Вот, держи.
Но у меня не получилось сделать 6000 элементов, как в прошлый раз - я нормализовал систему до этапа расчетов, в итоге на 2000 элементов уходит 150 секунд. http://rgho.st/6dTRdxcSx |
|||
52
H A D G E H O G s
08.07.16
✎
21:10
|
(51) ок, спасибо.
|
|||
53
Tateossian
08.07.16
✎
21:14
|
Вот такое практическое наблюдение. Нужна была таблица значений (в которой хранились ключи, или иксы) и постоянно в ней вести поиск по уникальному значению. Более быстрым вариантом оказалось подсовывать таблицу в параметр запроса и запросом искать, но самый быстрый способ оказался создать древовидную сущность из вложенных соответствий - работает в 4 раза быстрее, некое бинарное дерево.
|
|||
54
H A D G E H O G s
08.07.16
✎
21:18
|
(53) колонку индексировал?
|
|||
55
Garykom
гуру
08.07.16
✎
21:32
|
(53) Соответствие заново изобрел?
|
|||
56
orefkov
04.08.16
✎
09:01
|
(44)
Насчёт зависимости скорости доступа к элементам массива от его размера - вы ошибаетесь. В штатном Массиве от 1С это операция O(1). Ну и штатный Массив 1С не умеет a[i][j], то есть надо смотреть, как вы реализовали эту операцию - скорее всего массив массивов, в этом случае тоже доступ к элементу должен быть O(1). Более вероятно, что тормозит здесь операция деления - числа в 1С не простые int/double как в С++, а реализуют свой вариант чисел с потенциально неограниченной длиной и точностью. Соответственно, операция деления реализована внутри 1С программно, и считает насколько я помню с точностью до 27 знаков после запятой (double в С++ гарантируют только 15 значащих цифр на всё число). Если t константна, я бы рекомендовал предварительно вычислить t1 = 1/t (возможно еще и округлив до желаемой точности) и заменить "/ t" на "* t1". |
|||
57
Ildarovich
04.08.16
✎
09:44
|
Интересная тема. Было бы интересно увидеть несколько разных тестовых примеров больших разреженных матриц с замерами времени решения. Можно было бы попробовать оптимизировать применяемые методы и код.
Согласен с (56), что основным фактором, влияющим на время решения, здесь может быть длинная арифметика. Нужно регулировать не только точность, но и число знаков в решении. Иначе оно будет неконтролируемо расти. Из-за способа представления длинных чисел при росте числа знаков вдвое время выполнения умножения и деления растет в четыре раза (в квадрате). Вот здесь это делается http://catalog.mista.ru/public/319421/ (при нахождении обратной матрицы). |
|||
58
orefkov
04.08.16
✎
09:53
|
+(56)
Каюсь, штатно 1С сама для многомерных массивов создает массив массивов. |
|||
59
Кирпич
04.08.16
✎
09:55
|
(57) да нафиг париться с 1с, если можно просто на другом, быстром языке реализовать и забыть.
|
|||
60
orefkov
04.08.16
✎
10:06
|
(57)
Да, это важно, что если заменять деление умножением (да и вообще массовое умножение нецелых чисел), то обязательно результат округлять до желаемой точности, чтобы отбрасывать растущий хвост после точки. А то 1С будет считать все цифры после точки, пока памяти хватит. Или пока деление не подрежет хвост до 27 цифр после точки. (59) То же самое хотел написать. Имхо проще для спецефичной задачи написать решение не на 1С, а на более заточенных для этого языках. Если хочется непременно длинной арифметики на С++ - то есть куча библиотек для этого, что позволит добиться точности вычислений не хуже, чем в 1С, но всё-равно гораздо быстрее. |
|||
61
Ildarovich
04.08.16
✎
10:20
|
(60) Легче сказать, чем сделать. Задачи и методы решения задач СЛУ только на поверхностный взгляд похожие, там масса деталей и подводных камней, связанных с точностью, сходимостью и тому подобное. Даже из готовой проверенной библиотеки подобрать метод может быть не просто. А если в нем что-то нужно будет "подкрутить". Есть риск оказаться не на своем поле не только с языком, но и с методом.
Поэтому разработчики и использовали метод, который реализован на 1С и, таким образом, лучше контролируется. |
|||
62
orefkov
04.08.16
✎
10:32
|
(61)
Резонно. Но тогда разработчик на 1С должен чётко понимать механизм работы 1С с числами. |
|||
63
Михаил Козлов
17.08.16
✎
19:44
|
(60) "...все цифры после точки, пока памяти хватит" - разве нельзя типизовать до нужной точности?
|
|||
64
Balabass
18.08.16
✎
04:04
|
(63) Типизация происходит после операции деления.
|
|||
65
Злопчинский
18.08.16
✎
04:31
|
интересно.
|
|||
66
Злопчинский
18.08.16
✎
04:33
|
...лучше нарисовали бы мне алгоритм нахождения оптимального пути для обхода ячеек в линейном складе...
|
|||
67
Михаил Козлов
18.08.16
✎
09:58
|
(64) Это для элемента массива. Если использовать таблицу значений, то типизовать можно. Или проблема в том, что для ТЗ в 1С нет прямого доступа к ее элементам по индексам?
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |