Привет, форумчане! Нужна ваша помощь. Решил реализовать некий функционал с помощью решения системы линейных уравнений. В УПП в РАУЗе считается себестоимость методом Гаусса-Зейделя, но мне этот метод (и общие итерационные, Якоби, Гаусс) и прочие не подходят, так как матрица сильно разреженная. Стал гуглить, нашел вот такую ссылку http://dxdy.ru/topic9158.html, здесь перечисляются пакеты, но все они на C/c++ в основном и для них нужна обертка, как dll из 1С не подключить. Кто нибудь сталкивался с такой проблемой, а именно: решение в 1С разреженных матриц.

(0) А можно имя модуля и процедуры в упп, где это решается?

Ну и такой нюанс: 1С на матрицах размерностью более 1000 уходит в глубокую задумчивость. Кроме того, эксперемнтально установлено, обращение к произвольной области памяти (элементу массива) достаточно долгая операция при числе элементов более 1000000.

Если инициализировать массив нулями, то на это уходит в 4 (!) раза больше времени, чем создать таблицу значений с 1000 строк с типом число и использовать метод таблицы значений ВыгрузитьКолонку()

(1) Набери в поиске по конфигурации Гаусс.

(2) Да, все так и есть и это - логично.

" В УПП в РАУЗе считается себестоимость методом Гаусса-Зейделя, но мне этот метод (и общие итерационные, Якоби, Гаусс) и прочие не подходят, так как матрица сильно разреженная."

https://ru.wikipedia.org/wiki/Метод_Гаусса_%E2%80%94_Зейделя

Хорошо подходит для разреженных матриц.

(5) Долго считает, вот в чем беда, а когда сильная разреженность нужно много итераций.

(5) И самый главный косяк - если на диагонали будет ноль, то как быть? Вот это место:
a[i][i]

(7) А что там такого?

(8) Не ясно выразился. Есть такой кусок кода:
x[i] = (b[i] - var) / a[i][i]

который определяет искомый X, но что, если a[i][i] = 0, а на ноль делить нельзя.

(9) Открой ссылку, которую я привел.

(10) Так это оттуда я и скопипастил

Давай я напишу ВК-шечку, которая будет решать эти ваши СЛУ быстро. С тебя - база с данными.

(11) Ты не на реализацию смотри, а на алгоритм в формулах.

(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];
    КонецЦикла;
    
КонецЦикла

(13) А потом сделай, скажем, вот так:

МатрицаКоэффициентов[2][2]=0

И скажи, что получится?

(12) Я тебе могу скинуть файл 3000х3000 в любом виде. Пойдет? Заинтриговал, на чем писать будешь?

получится что у тебя система уравнений кривая. если ты без последнего неизвестного (n-ого) имеешь n уравнений.

прежде чем автоматизировать бардак, наведите порядок, иначе получите автоматизированный бардак (с)

(16) Дельфи.

(16) csv

(17) Я тебе скажу больше, у меня не квадратная матрица, а прямоугольная и я сделал изврат, дописав нулевых строк:) На самом деле это ситуация называется Недоопределеенная матрица.

У нее либо нет решений, либо бесконечно много решений. Мне надо получить одно любое решение из бесконечного множества.

https://ru.wikipedia.org/wiki/Недоопределённая_система

А может быть, наоборот, переопределенная система.

ну с такими решениями ничего не скажу... хотя сомнения в правильности выбора инструмента появились.

Файлик то будет?

(23) Будет, подожди немного.

(22) Экспериментирую

(0) а lpsolve умеет такое решать? не в курсе?

(26) Не в курсе, но, судя по описанию, это несколько иной класс задач.

(27) я помню, соседи по парте в него какие то матрицы загружали пару лет назад и говорили типа мощная штука.

(28) https://sourceforge.net/projects/lpsolve/

Судя по всему, умеет:)

(29) это я к тому, что у него есть COM dll, можно из 1С пользовать.

ТС решил переписать расчёт себестоимости для РАУЗ?

(31) Типа того, точнее, свой расчет себестоимости.

(32) и что дальше? Свою УПП городить? И самое главное - зачем тебе РАУЗ который будет иметь подпространство решений? Ты это собираешься выдать экономистам/финансистам/руководителям?

(33) Затем, что специфика такая. Возможно другие варианты, но я пробую именно так, потому что считаю, что это будет не тривиальное и хорошее решение. Если взлетит.

А РАУЗом вообще не пользуемся. В программе исторически свой расчет себестоимости и он живет! Работает, цифры экономистов устраивают, сто раз все проверено.

Немного приходится допиливать для поддержки, а я решил оптимизировать ибо стал тормозить.

(23) Давай тебе эксель скину, ибо csv весит 10 Мб, а эксель 120Кб?

(0) Главное использовать CUDA, у них очень хорошо оптимизированные бибилиотеки для решения линейных уравнений, ускорение раз в 20, я еще в 2011 году об этом думал...

(20) http://dropmefiles.com/ELAWm

(35) эксель, видимо, догадался зазиповать, а те нет :)

(37) Вот как видит его мой ексель
http://s019.radikal.ru/i631/1606/c9/bfbddce61852.png

(39) Я ошибку нашел у себя благодаря рассуждениям в этой ветке.
Но то, что ты видишь - это нормально. Там 90% ячеек - нули.

(39) Попробую сейчас быстро исправления сделать, там меньше нулевых ячеек должно быть. Я потерял коэффициенты. Не смотри в этот файл.

(38) Да понятно, что текст ужимается в 98%. Xml сжимается очень хорошо. csv это текст без сжатия.

Если матрица прямоугольная и число строк мало по сравнению с числом столбцов, то можно преобразованиями Жордана-Гаусса привести матрицу к трапециевидному типу и получить общее решение (или убедиться в отсутствии такового). Трудоемкость или O(n^3) или O(n^2*m) (не уверен. n - число строк, m - число столбцов).
Наверняка, в библиотеках линейной алгебры это есть. Но можно и в 1С такое сделать. По моему опыту (гонял матрицы до 100 строк), матрицу с числом строк - несколько десятков, можно привести за приемлемое время.
Для общего сведения:
1. Довольно активно разрабатывались методы решения "полосатых" СЛУ (3,5,7-диагональных) в целях численного решения задач мат. физики по разностным схемам.
2. Для матриц, которые можно привести к виду: относительно небольшие по размеру квадратные подматрицы по диагонали и небольшое количество общих связывающих уравнений, общий подход был описан в книге В.И.Цурков "Декомпозиция в задачах большой размерности", Наука, 1981.
Содержательно такая структура уравнений описывает "изолированные" подсистемы, связанные небольшим числом общих уравнений.

Возвращаясь к этой теме.
После долгого и кропотливого анализа формируемых матриц нашел пару ошибок, устранив которые получилось их нормализовать, приведя к квадратному виду. Но это еще не все, самое интересное было впереди: матрица размерностью 6000x6000 силами 1С решалась 3700 секунд. 90% львиной доли ушло вот на это место, a[i][j] = a[i][j] / t.

Такое время нельзя считать приемлемым, хоть и задача решена - уравнение считается правильно. Тогда пришлось пойти на изврат в легкой форме и написать нативную dll на срр. Результат такой - решение матрицы составляет 420 секунд, что почти на порядок(!) быстрее. Такова цена за неявную типизацию...

Куда и какой код внести в типовую, чтобы на порядок быстрее решалось там?

(45) Никуда, 1С не может в большие вычисления, так как плохо работает с произвольным доступом к памяти.

(46) Дай тестовый набор

Tateossian

В типовом решении 1С замени
Массивы
на
ФиксированныеМассивы

Обычный массив 1С - это связный список, так он добавляемый. Таким образом, это не массив в классическом понимании, он не лежит в памяти непрерывно и доступ к нему происходит через поиск нужного элемента. Со Структурой таже херь.

Есть надежда, что ФиксированныйМассив - это классический, непрерывный в памяти массив с быстрым доступом к элементу.

так он добавляемый-> так как он добавляемый

Вот, держи.

Но у меня не получилось сделать 6000 элементов, как в прошлый раз - я нормализовал систему до этапа расчетов, в итоге на 2000 элементов уходит 150 секунд.

http://rgho.st/6dTRdxcSx

(51) ок, спасибо.

Вот такое практическое наблюдение. Нужна была таблица значений (в которой хранились ключи, или иксы) и постоянно в ней вести поиск по уникальному значению. Более быстрым вариантом оказалось подсовывать таблицу в параметр запроса и запросом искать, но самый быстрый способ оказался создать древовидную сущность из вложенных соответствий - работает в 4 раза быстрее, некое бинарное дерево.

(53) колонку индексировал?

(53) Соответствие заново изобрел?

(44)
Насчёт зависимости скорости доступа к элементам массива от его размера - вы ошибаетесь. В штатном Массиве от 1С это операция O(1). Ну и штатный Массив 1С не умеет a[i][j], то есть надо смотреть, как вы реализовали эту операцию - скорее всего массив массивов, в этом случае тоже доступ к элементу должен быть O(1). Более вероятно, что тормозит здесь операция деления - числа в 1С не простые int/double как в С++, а реализуют свой вариант чисел с потенциально неограниченной длиной и точностью. Соответственно, операция деления реализована внутри 1С программно, и считает насколько я помню с точностью до 27 знаков после запятой (double в С++ гарантируют только 15 значащих цифр на всё число). Если t константна, я бы рекомендовал предварительно вычислить t1 = 1/t (возможно еще и округлив до желаемой точности) и заменить "/ t" на "* t1".

Интересная тема. Было бы интересно увидеть несколько разных тестовых примеров больших разреженных матриц с замерами времени решения. Можно было бы попробовать оптимизировать применяемые методы и код.
Согласен с (56), что основным фактором, влияющим на время решения, здесь может быть длинная арифметика. Нужно регулировать не только точность, но и число знаков в решении. Иначе оно будет неконтролируемо расти. Из-за способа представления длинных чисел при росте числа знаков вдвое время выполнения умножения и деления растет в четыре раза (в квадрате).
Вот здесь это делается http://catalog.mista.ru/public/319421/ (при нахождении обратной матрицы).

+(56)
Каюсь, штатно 1С сама для многомерных массивов создает массив массивов.

(57) да нафиг париться с 1с, если можно просто на другом, быстром языке реализовать и забыть.

(57)
Да, это важно, что если заменять деление умножением (да и вообще массовое умножение нецелых чисел), то обязательно результат округлять до желаемой точности, чтобы отбрасывать растущий хвост после точки. А то 1С будет считать все цифры после точки, пока памяти хватит. Или пока деление не подрежет хвост до 27 цифр после точки.
(59)
То же самое хотел написать. Имхо проще для спецефичной задачи написать решение не на 1С, а на более заточенных для этого языках. Если хочется непременно длинной арифметики на С++ - то есть куча библиотек для этого, что позволит добиться точности вычислений не хуже, чем в 1С, но всё-равно гораздо быстрее.

(60) Легче сказать, чем сделать. Задачи и методы решения задач СЛУ только на поверхностный взгляд похожие, там масса деталей и подводных камней, связанных с точностью, сходимостью и тому подобное. Даже из готовой проверенной библиотеки подобрать метод может быть не просто. А если в нем что-то нужно будет "подкрутить". Есть риск оказаться не на своем поле не только с языком, но и с методом.
Поэтому разработчики и использовали метод, который реализован на 1С и, таким образом, лучше контролируется.

(61)
Резонно. Но тогда разработчик на 1С должен чётко понимать механизм работы 1С с числами.

(60) "...все цифры после точки, пока памяти хватит" - разве нельзя типизовать до нужной точности?

(63) Типизация происходит после операции деления.

интересно.

...лучше нарисовали бы мне алгоритм нахождения оптимального пути для обхода ячеек в линейном складе...

(64) Это для элемента массива. Если использовать таблицу значений, то типизовать можно. Или проблема в том, что для ТЗ в 1С нет прямого доступа к ее элементам по индексам?