<?php // Полная загрузка сервисных книжек, создан 2024-01-05 12:44:55
global $wpdb2;
global $failure;
global $file_hist;
///// echo '<H2><b>Старт загрузки</b></H2><br>';
$failure=FALSE;
//подключаемся к базе
$wpdb2 = include_once 'connection.php'; ; // подключаемся к MySQL
// если не удалось подключиться, и нужно оборвать PHP с сообщением об этой ошибке
if (!empty($wpdb2->error))
{
///// echo '<H2><b>Ошибка подключения к БД, завершение.</b></H2><br>';
$failure=TRUE;
wp_die( $wpdb2->error );
}
$m_size_file=0;
$m_mtime_file=0;
$m_comment='';
/////проверка существования файлов выгрузки из 1С
////файл выгрузки сервисных книжек
$file_hist = ABSPATH.'/_1c_alfa_exchange/AA_hist.csv';
if (!file_exists($file_hist))
{
///// echo '<H2><b>Файл обмена с сервисными книжками не существует.</b></H2><br>';
$m_comment='Файл обмена с сервисными книжками не существует';
$failure=TRUE;
}
/////инициируем таблицу лога
/////если не существует файла то возврат и ничего не делаем
if ($failure){
///включает защиту от SQL инъекций и данные можно передавать как есть, например: $_GET['foo']
///// echo '<H2><b>Попытка вставить запись в лог таблицу</b></H2><br>';
$insert_fail_zapros=$wpdb2->insert('vin_logs', array('time_stamp'=>time(),'last_mtime_upload'=>$m_mtime_file,'last_size_upload'=>$m_size_file,'comment'=>$m_comment));
wp_die();
///// echo '<H2><b>Возврат в начало.</b></H2><br>';
return $failure;
}
/////проверка лога загрузки, что бы не загружать тоже самое
$masiv_data_file=stat($file_hist); ////передаем в массив свойство файла
$m_size_file=$masiv_data_file[7]; ////получаем размер файла
$m_mtime_file=$masiv_data_file[9]; ////получаем дату модификации файла
////создаем запрос на получение последней удачной загрузки
////выбираем по штампу времени создания (редактирования) файла загрузки AA_hist.csv, $m_mtime_file
///// echo '<H2><b>Размер файла: '.$m_size_file.'</b></H2><br>';
///// echo '<H2><b>Штамп времени файла: '.$m_mtime_file.'</b></H2><br>';
///// echo '<H2><b>Формирование запроса на выборку из лога</b></H2><br>';
////препарируем запрос
$text_zaprosa=$wpdb2->prepare("SELECT * FROM `vin_logs` WHERE `last_mtime_upload` = %s", $m_mtime_file);
$results=$wpdb2->get_results($text_zaprosa);
if ($results)
{ foreach ( $results as $r)
{
////если штамп времени и размер файла совпадают, возврат
if (($r->last_mtime_upload==$m_mtime_file) && ($r->last_size_upload==$m_size_file))
{////echo '<H2><b>Возврат в начало, т.к. найдена запись в логе.</b></H2><br>';
$insert_fail_zapros=$wpdb2->insert('vin_logs', array('time_stamp'=>time(),'last_mtime_upload'=>$m_mtime_file,'last_size_upload'=>$m_size_file,'comment'=>'Загрузка отменена, новых данных нет, т.к. найдена запись в логе.'));
wp_die();
return $failure;
}
}
}
////если данные новые, пишем в лог запись о начале загрузки
/////echo '<H2><b>Попытка вставить запись о начале загрузки в лог таблицу</b></H2><br>';
$insert_fail_zapros=$wpdb2->insert('vin_logs', array('time_stamp'=>time(),'last_mtime_upload'=>0, 'last_size_upload'=>$m_size_file, 'comment'=>'Начало загрузки'));
////очищаем таблицу
$clear_tbl_zap=$wpdb2->prepare("TRUNCATE TABLE %s", 'vin_history');
$clear_tbl_zap_repl=str_replace("'","`",$clear_tbl_zap);
$results=$wpdb2->query($clear_tbl_zap_repl);
///// echo '<H2><b>Очистка таблицы сервисных книжек</b></H2><br>';
if (empty($results))
{
///// echo '<H2><b>Ошибка очистки таблицы книжек, завершение.</b></H2><br>';
//// если очистка не удалась, возврат
$failure=TRUE;
wp_die();
return $failure;
}
////загружаем данные
$table='vin_history'; // Имя таблицы для импорта
//$file_hist Имя CSV файла, откуда берется информация // (путь от корня web-сервера)
$delim=';'; // Разделитель полей в CSV файле
$enclosed='"'; // Кавычки для содержимого полей
$escaped='\
27. Округление в большую сторону
Есть более универсальный способ округлить в большую (или меньшую) сторону, который можно использовать в запросах, в коде и даже в вычисляемых полях СКД. По ссылке на ветку мисты есть упоминание о нем, но мне показалось что не очень внятно описано. Идея состоит в добавлении (или вычитании) числа близкого к 0.5 и округления по математическим правилам. Для запроса округление в большую и меньшую сторону будет выглядеть так:
ВЫБРАТЬ ВЫРАЗИТЬ (&Значение+0.499999 КАК Число(15,0) ) КАК ОкругленноеВБольшуюСторону,
ВЫРАЗИТЬ (&Значение-0.499999 КАК Число(15,0) ) КАК ОкругленноеВМеньшуюСторону
Для отрицательных чисел можно предусмотреть условие с отдельной веткой если не устраивает округление по данной формуле
К минимализму 34. Ещё бы пример как свернуть ТЗ а текстовые строки сложить конкатенацией…. Вчера как раз бился над этим.
Ну и буква «ё» в коде это моветон.
(2) TODD22, свернуть строки конкатенацией можно так:
Показать
Но я бы не стал объединять этот прием с другими. В 34 можно находить агрегатные максимум, минимум и так далее для части полей НАРЯДУ с обычным суммированием для других полей. А при конкатенации ненужные строки приходится жестко удалять, поэтому по смыслу прием другой, хотя тоже короткий и полезный.
(2) TODD22, по поводу буквы «ё». Хотелось бы разобраться откуда растут ноги у этого убеждения. Здесь уже был спор на эту тему. Да, 1С когда-то в каких-то замшелых инструкциях не рекомендовала эту букву. Но почему? -Не является ли это просто нездоровым консерватизмом человека, написавшего инструкцию, позицией КакБыЧегоНеВышло? Не пора ли ее пересмотреть? Буква ё очень нарядная и украшает код, особенно в качестве итератора. Как i или j.
Многие на партнерском форуме реабилитировать эту букву.
(4)
5 человек на форуме это далеко не многие:)
Я например считаю что если есть требование и это стандарт то нужно его придерживаться. Не зависимо от того есть технические сложности или нет.
А то что «кто то считает» букву нарядной это же не аргумент.
Я видел код людей которые считали нарядным делать счётчики i j в коде 1С. И вообще кто только как свой код не наряжает.
А хотелось бы видеть код приближенный максимально к стилю в типовых. Что бы потом того кто наряжал добрым словом не вспоминать.
(4)
Как только в соглашениях по написанию кода не будет написано что нельзя использовать букву ё тогда можно будет и пересмотреть.
А так получается что ты пересмотрел в одностороннем порядке 🙂
(1) Synoecium, тут я с вами поспорю:
1) Правильное выражение для округления в меньшую строну (взятие целого) вот такое:
Это все кругом используют, а вам нужно будет пересмотреть свой код в продакшен, так как на значении 0.999999 у вас будет получаться не 0 как правильно, а 1, что может вызывать трудноуловимые ошибки;
2) Выражение
вроде бы работает, но не правильно обрабатывает значение 0.0000009 и меньше — будет округлять их в меньшую строну, а не в большую. Поэтому в том обсуждении, на которое вы ссылались девяток было больше (помните — «не спортивно»). Хотя это дело вкуса, но мне кажется легче контролировать диапазон значений (выбором М), чем точность (числом девяток), с которой иногда случаются всякие фокусы.
За 37. Генератор вариантов формул особое спасибо!
Маэстро вообще любит переменные с именами ж, ё, й и подобные. Сильно помогает в попытках разобраться с кодом 🙂
(9) Evil Beaver, Так про «й, щ, ы» ничего не сказано в соглашении 🙂 А вот про ё сказано явно.
Единственное, что может быть как претензия к букве «ё» — это то, что она стоит отдельно от основного алфавитного ряда в таблице ASCII-символов. Ну и ёщё — не любят эту букву в печатных изданиях (это очень-очень давняя история). Я за то, чтобы реабилитировать Ё. Но вот, как счётчик цикла… Читаем код в стиле рэпа 🙂
Автору в очередной раз — Респект!
Не могу понять, как работает запрос из «35. Выбрать в запросе одну запись из нескольких»?
(7) Вы за мой продакшен не беспокойтесь, мы здесь обсуждаем вашу статью.
дает неправильное решение для значения 0 например (получится -1 что неверно), но для положительных чисел соглашусь, такой вариант позволяет повысить точность. Предложенный метод нужно применять понимая ограничения накладываемые точностью вычислений, точность будет не менее, чем количество девяток в сдвиге (в приведенной формуле до 5 знаков).
так и задумано, нужно применять метод, зная про ограничения.
В запросе «35. Выбрать в запросе одну запись из нескольких» не хватает «РАЗЛИЧНЫЕ». Например если в конце таблицы добавить ещё одну запись Петя 1 1 1 1, то появится дубляж. «Различные» это исправит.
(12) Synoecium, для избежания коллизии [0] -> -1 лично я пишу в запросе
Что касается 27, то речь там идет прежде всего о коде, а не о запросе. В запросе мне как-то не приходилось пока с округлением в бОльшую сталкиваться, но добавлять 0.499999 лично я бы не стал, впрочем, ваши аргументы я услышал.
(13) klinval, согласен, поправлю в статье
Минимализм 35. Интересное решение через коррелированный запрос, не знал про такой. По условию задачи предполагается, что нам неважно какая именно из записей с одинаковыми ключами (ключом в данном случае выступает поле Ф) попадет в результирующую выборку. Однако на практике часто необходимо выбрать записи согласно какому то порядку, тогда можно использовать следующий метод, при условии, что неключевые поля можно сравнивать по условию <,>:
ВЫБРАТЬ
Дано.Ф,
Дано.К1,
Дано.К2,
Дано.К3,
Дано.К4
ИЗ
Дано КАК Дано
ВНУТРЕННЕЕ СОЕДИНЕНИЕ Дано КАК Дано1
ПО Дано.Ф = Дано1.Ф
И (ВЫБОР
КОГДА Дано.К1 > Дано1.К1
ТОГДА ИСТИНА
КОГДА Дано.К1 = Дано1.К1
И Дано.К2 > Дано1.К2
ТОГДА ИСТИНА
КОГДА Дано.К1 = Дано1.К1
И Дано.К2 = Дано1.К2
И Дано.К3 > Дано1.К3
ТОГДА ИСТИНА
КОГДА Дано.К1 = Дано1.К1
И Дано.К2 = Дано1.К2
И Дано.К3 = Дано1.К3
И Дано.К4 >= Дано1.К4
ТОГДА ИСТИНА
ИНАЧЕ ЛОЖЬ
КОНЕЦ)
СГРУППИРОВАТЬ ПО
Дано.Ф,
Дано.К1,
Дано.К2,
Дано.К3,
Дано.К4
ИМЕЮЩИЕ
КОЛИЧЕСТВО(Дано1.Ф) = 1
При использовании следует учесть, что среди записей не должно быть полных дубликатов, так как они будут исключены из выборки.
ildarovich, интересно узнать, можно ли в коррелированном запросе использовать упорядочивание, для решения такой задачи?
Большое спасибо за статью. Однозначно +.
Вот еще очень нужная функция, помещает таблицу значений, или табличную часть, в менеджер временных таблиц.
Функция ПоместитьТаблицуВМенеджерВременныхТаблиц(Знач ТаблицаИсточник, ИмяТаблицы = «ТЗ», МенеджерВТ = Неопределено, Колонки = Неопределено) Экспорт
Если ТипЗнч(ТаблицаИсточник) <> Тип(«ТаблицаЗначений») Тогда
Сообщить(«Ошибка таблицы источника данных!», СтатусСообщения.Внимание);
Возврат Неопределено;
КонецЕсли;
Если МенеджерВТ = Неопределено Тогда
МенеджерВТ = Новый МенеджерВременныхТаблиц;
КонецЕсли;
ТекстЗапроса = «»;
Если Колонки = Неопределено Тогда
ТаблицаРез = ТаблицаИсточник;
Для каждого стр Из ТаблицаРез.Колонки Цикл
Если ПустаяСтрока(ТекстЗапроса) Тогда
ТекстЗапроса = «Выбрать » +ИмяТаблицы +».»+ стр.Имя + » как » +стр.Имя +»,
|»;
Иначе
ТекстЗапроса = ТекстЗапроса +ИмяТаблицы +».»+ стр.Имя + » как » +стр.Имя +»,
|»;
КонецЕсли;
КонецЦикла;
Иначе
ТаблицаРез = ТаблицаИсточник.Скопировать();
МассивКолонок = ОбщегоНазначения.РазложитьСтрокуВМассивПодстрок(Колонки,»,»);
Сч = 0;
Пока Сч < ТаблицаРез.Колонки.Количество() Цикл
Стр = ТаблицаРез.Колонки[Сч];
Если МассивКолонок.Найти(Стр.Имя) <> Неопределено Тогда
Если ПустаяСтрока(ТекстЗапроса) Тогда
ТекстЗапроса = «Выбрать » +ИмяТаблицы +».»+ стр.Имя + » как » +стр.Имя +»,
|»;
Иначе
ТекстЗапроса = ТекстЗапроса +ИмяТаблицы +».»+ стр.Имя + » как » +стр.Имя +»,
|»;
КонецЕсли;
Сч = Сч + 1;
Иначе
ТаблицаРез.Колонки.Удалить(Стр);
КонецЕсли;
КонецЦикла;
КонецЕсли;
ТекстЗапроса = Лев(ТекстЗапроса, СтрДлина(ТекстЗапроса)-3);
ТекстЗапроса = ТекстЗапроса + » поместить «+ ИмяТаблицы +»
| из &» + ИмяТаблицы + » как » + ИмяТаблицы
+» ;»;
Запрос = Новый Запрос;
Запрос.МенеджерВременныхТаблиц = МенеджерВТ;
Запрос.Текст = ТекстЗапроса;
Запрос.УстановитьПараметр(ИмяТаблицы,ТаблицаРез);
Попытка
Запрос.Выполнить();
Исключение
Сообщить(«»+ОписаниеОшибки(), СтатусСообщения.Внимание);
МенеджерВТ = Неопределено;
КонецПопытки;
Возврат МенеджерВТ;
КонецФункции
(16) Synoecium, нет, не прокатывает, только если не множественные операнды — то есть уникальное поле еще нужно. А так вот такое сообщение появляется:
(17) igormiro, да, полезная функция. Давно хочу этот функционал к своей функции добавить.
Минимализм 35 на 1С 8.2 не работает, в том числе и на SQL,
т.е. если набрать, то выдаст изначальную таблицу
Показать
(20) manlak, У меня всё работает (см. прикрепленный файл). В консоль запросов кинул полностью ваш запрос без изменений, в результирующей таблице 3 строки!
(21) klinval, это если открывать в стандартном 8.2 «упп-демо» консоле отчетов (операции — обработка — Консоль отчетов), то выйдет 5 строк.
Если создать новый внешний отчет и скопировать код, тоже самое, будет 5 строк. Задачу можно решить через «максимум» в запросе на полях «К *»
Минимализм 27. Округление в большую сторону
Я пользуюсь таким методом:
Окр(Ч + 0.5, 0); Окр(Ч + 0.05, 1); и т.п.
(23) arithmometr, почитайте обсуждение по ссылке, там было много разных методов, которые не все выдерживали критику. Ваш метод не соответствует пониманию округления в бОльшую в том смысле, что Окр(1+0.5, 0) дает 2, а по идее эта операция должна давать 1. Из тех предложений к предлагаемому вами методу ближе «неспортивный» (его так сам автор обозвал) метод Окр(Ч + 0.4999999999).
(22) manlak, выполнение такого запроса не должно зависеть от конфигурации. Хоть на пустой БД — везде должно быть одинаково! Возможно есть какая-нибудь зависимость от версии платформы? У меня на 8.3.7.1845 3 строчки! А у вас какая версия платформы?
(0) К п. 36 пустой элемент массива я бы все же из результата убрал.
алгоритм в прикладных задачах имеет смысл использовать для множества не повторяющихся элементов.
Хотя с математической точки зрения все безукоризненно.
(26) pm74, думал над этим: …с одной стороны лишняя запись в результате…с другой стороны ничему не мешает, совпадает с определением, текст программы короче, кому нужно допишет проверку… Вот эти рассуждения и перевесили, поэтому оставил элемент с пустым списком значений в результирующем массиве.
(20), (21). Действительно, п.35 на 8.2 не работает, а на 8.3. работает. Есть идеи, как заставить работать на 8.2?
К задаче 31
Более быстрый и правильный код
ВЫБРАТЬ А, Б, КОЛИЧЕСТВО(*)
ИЗ (ВЫБРАТЬ А, Б ИЗ Дано ГДЕ А <= Б
ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ Б, А ИЗ Дано ГДЕ А > Б) КАК ВЗ
28 постановка задачи бредовая. Не могу предположить кому это нужно
Хотя запросы и решают поставленную задачу
Задача 23. Оптимизация подбора кусков заданного суммарного метража методом ветвей и границ
Не правильно решена: (как минимум не достаточно быстро)
Согласно решению есть цикл с реурсией. т.е. сложность задачи это n!
На самом деле требуется отобрать К кусков из N. В самом худшем случае к-во вариантов (по биному ньютона) 2#k8SjZc9DxkN (два в степени N) Откуда легко видеть , что сложность задачи слишком преувеличена.
В общем случае задачу лучше решать стандартным методом перебора вариантов:
1. Все куски, которые можно разделить, разделить и записать в массив (т.е. не строка с 4 кусками по 50 ,а 4 отдельных куска по 50)
2. Написать алгоритм, который выполнить перестановку кусков.
3. Для каждой перестановки простым способом посчитать разбиение (например суммировать куски в порядке возрастания номеров до набора нужной суммы)
Желательно объединить алгоритмы 2 и 3 чтобы не вычислять перестановку, которая не изменит результата, получаемого в 3.
Я считаю. что написать оптимизацию перестановок более чем по 1-му условию будет очень сложно (т.е. либо оптимизировать по количеству кусков, либо по кол-ву строк . если нужно оба условия — то отбирать полученные варианты по первой оптимизации и выбирать из них оптимальный по второму условию)
(29) Ovrfox, превосходное решение! Очевидно, лучше приведенного в статье. В общем-то, обсуждения для этого и нужны, чтобы находить такие решения.
Для себя вижу урок в том, что не потратил достаточно времени на улучшение решения задачи 31. А чувство неудовлетворенности путанностью условий в запросе было.
(30) Ovrfox, мне постановка задачи бредовой не кажется. Да и ссылка говорит о том, что задача не придуманная. Этот запрос устраняет избыточность. А вообще с избыточностью приходится сталкиваться на каждом шагу. Взять хотя бы тоже кодирование RLE.
По сути, эта задача обратная по отношению к задаче «цены на каждый день», где избыточность намеренно вводится. Если там «распаковка», то тут «сжатие».
Сценариев использования довольно много.
Вот, например, возьмите сериализованные версии объектов, постройте методом из хэши версий, да и уберите повторяющиеся версии. Ну и тому подобное.
(31) Ovrfox, думаю, тут вы не до конца разобрались в коде.
Никакого n! там нет. Порядок использования кусков в разных вариантах одинаков и перестановок тут нет.
Оценка количества перебираемых вариантов: К1хК2хК3х…xKn, где К1 — увеличенное на 1 число кусков первого индекса и так далее.
Если все вытянуть в строку, как вы предлагаете, то в блоках кусков одного индекса будет лишний перебор из-за одинаковости вариантов 1000, 0100, 0010, 0001 (для четырех кусков первого индекса). А в целом 2#k8SjZc9Dxk(К1+К2+К3+…+Kn) >> К1хК2хК3х…xKn, когда К > 2.
А вообще в целом решение выполнено в том же направлении мыслей, которые у вас описаны. Шаги 2 и 3 именно что объединены. Двухкритериальная оптимизация там неявная и именно последовательная: главный-второстепенный критерий. Вместо перестановки на каждом уровне рекурсии выбирается различное число кусков. Почитайте обсуждение по ссылке. Там были еще разные варианты совмещения критериев.
Это решение несколько раз проверено на двух конкретных практических задачах. Но мне оно ничем, кроме своей краткости не интересно.
Кстати, я тут ошибся с классификацией метода. Это метод сокращенного перебора, но не метод ветвей и границ. У МВГ должна быть структура данных для хранения множества не просмотренных вариантов с их оптимистичными оценками. Тут такой структуры нет, хотя и ветвления и отсечение и присутствуют.
А вообще для этой задачи есть чуть более сложный и не переборный метод.
Надеюсь, найду время и допишу статью с обработкой на эту тему.
Для продолжения спора на тему «недостаточно быстро» умозрительных построений недостаточно — нужно будет реализовать свое решение. Можно будет сравнить.
К задаче 36. Алгоритм перебора всех возможных сочетаний элементов
Касается задачи 23
Хранить в массиве все варианты — достаточно грубо, особенно когда вариантов много , а решение можно найти в первой тысяче вариантов.
Например такой код получения вариантов значительно проще
Показать
Где в качестве начального варианта нужно использовать либо специальный массив с 0, либо просто первый вариант (массив , содержащий индекс 1)
Приведенный код получает следующий вариант на основе предыдущего и НЕ Повторяет варианты, идентичные за исключением перестановки элементов.
2(34)
Предположим что все отрезы разные, и нам нужны два наименьших отреза. При этом сумма двух наименьших больше длинны каждого куска
Число кусков 10
Предложенный вариант решения выполнится
на первом уровне 9 раз
на втором уровне вложенности 8 раз
и т.д
Т.е. , не N!, а (N-1)!
Если воспользоваться решением из 35-го поста или даже набором вариантов из 23-й задачи
То в худшем случае это будет 2 в степени N минус 1 вариант. Уверяю Вас, это значительно меньше.
(4)
;-))
Просто ассоциировалось…
Сафронова Наталья Григорьевна
1
У творчества немало бед.
И не возможно не предвидеть;
Писать стихи, других обидеть.
А не писать — себе во вред.
2(34) (36) Оценил алгоритм еще раз. Получил оценку 2 в степени N
Делаю вывод, что алгоритм скорее всего правильный. Но не верю.
Привести пример, когда он неправильный не могу.
(35) Ovrfox, код Грэя? — Мне он очень нравится, согласен. Но когда мне это понадобится, постараюсь написать сам.
(38) AnryMc, вот это тоже подходит к случаю (Анна Ахматова):
Растут стихи, не ведая стыда.
Как желтый одуванчик у забора,
Как лопухи и лебеда.
Сердитый окрик, дегтя запах свежий,
Таинственная плесень на стене…
И стих уже звучит, задорен, нежен.
На радость всем и мне.
(36) Ovrfox, вот еще ссылка на тему, где применялась это решение .
Задал в своей обработке (прилагается) ваши данные (смотрите скриншот). При входе в функцию там стоит сообщить
Из скриншота видно, что шагов подбора выполнилось 28. Это не факториал.
(42) Да. я уже писал, что я пересчитал ряд и худшая оценка совпадает со всеми вариантами, а именно 2 в степени N минус 1
Код перебора мой, написал специально под задачу. Когда использую сам — обычно совмещаю 2 и 3-й шаги, поэтому код совсем другой. Идея — таже.
(43) Ovrfox, если вторая часть про мой ответ в (40), то я имел ввиду «код Грэя» . Он является математической основой алгоритма, который вы привели в (35).
(44) Было интересно читать о коде Грея. Не могу утверждать, что алгиртмы чем-то похожи — я не нашел похожего алгоритма генерации кода Грея.
Но согласно определению кода грея — мой алгоритм генерит последовательность, которая им не является. Т.е. на определенных шагах алгоритма следующее значение отличается от предыдущего более чем на один элемент.
(45) Ovrfox, да, я уже понял, что поторопился с выводами. Нужно будет повнимательнее рассмотреть код, приведенный в (35). Беглый взгляд не помог мне прояснить идею.
Все же кажется, что если ставится задача просто перебрать все варианты подряд по одному, то код должен быть короче.
Нужно просто ввести счетчик вариантов, а вхождение элемента в вариант определять наличием единицы в двоичном представлении счетчика.
Показать
Зато запрограммировал перебор в коде Грэя (чуть позже покажу), решил новым способом обработку битовых строк. Для меня обсуждение оказалось полезным.
(46) Для простого перебора — конечно. Но идея в том, что следующий вариант берется из текущего. А текущий может быть получен специальным способом.
Для перебора отрезов: отрезы уже упорядочены по величине. Первый вариант мы набираем в лоб, начиная с больших кусков. И можем продолжить перебор, пропустив все меньшие варианты. При этом мы не храним все полученные варианты — т.е. не тратим на них память. Для больших чисел (а 20 — это уже большое, т.к. к-во вариантов миллион) это может кардинально улучшить процесс перебора (если для хранения вариантов оперативной памяти будет недостаточно).
(35) (39) (43) И кстати, алгоритм действительно перебирает все варианты. Но происходит это в лоб оценка О(2#k8SjZc9DxkN-1)
+(46) (45) Ovrfox, вот новая статья . На идеи, изложенные в ней, меня натолк
(49) Я взял свой код из практики решений как раз аналогично вида задач, как с отрезами.
Как вы догадываетесь, простой перебор это слишком много вариантов. Их количество нужно уменьшать.
Код грея нельзя согласовать с отбором очередного начального варианта, а мой код можно. Именно соединение этих алгоритмов приводит к значительной эффективности общего алгоритма.
Спасибо за ссылку на интересную статью.
(50) Ovrfox, мне кажется, мы потеряли нить рассуждений…
Мне казалось, что первоначально код из (35) предлагался для задачи 36, чтобы не хранить варианты, а проверять их сразу.
Если хотите применить этот код к задаче 23, то доработайте его для нее! И попробуйте найти им решение задачи как на картинке в (42). Вы увидите, что чисто переборный метод здесь не годится. Метод из 23 не чисто переборный. Он отсекает в процессе перебора множество решений.
Предлагать код из (35) к решению задачи 23 очень и очень неправильно.
Когда вы попробуете его доработать, то пройдете длинный путь и придете таки к варианту наподобие предложенного в статье.
Чтобы в этом убедиться, нужно взять из (42) обработку. Я ее уже приготовил для вас. Встроить туда свой код. И попытаться переиграть по времени мою функцию. У вас ничего не получится. Следовательно, все, что вы говорили и говорите (?) о якобы неэффективности решения задачи 23, об оценках его трудоемкости и о каких-либо преимуществах перебора из (35) — бездоказательно.
(51) Хорошо, я напишу
А Вы пока исправьте ошибку
Алгоритм в вашей обработке не возвращает результат, если в него входит максимальное значение (т.е. строка с наибольшими кусками)
(52) Ovrfox, ОК, вот поправленная обработка из (42). Поменял местами проверку условий промаха и фиксации решения. В статье поменяю позже, когда еще раз всесторонне проверю.
(53) Добавил алгоритм подбора кусков, добавил также поиск следующего варианта (Кнопка продолжить).
Исходный алгоритм перенес на кнопку «Перебор»
Кстати, Ваш алгоритм выполняет отбор меньшими кусками, а в условии задачи, как я понял, требуется отбор большими кусками. Исправить просто — изменить порядок сортировки на противоположный.
Алгоритмы можно сравнивать просто зрительно, настолько сильно отличается время работы алгоритмов. Для замедления «переборного» алгоритма нужно увеличить кол-во кусков. И количество требуемых кусков в отборе.
По к-ву шагов сравнивать нельзя, это «попугайные» показатели.
(54) Ovrfox, посмотрел, спасибо, буду все это объяснять, но чуть позже.
(55) Как я уже говорил, но повторю еще раз. Основная идея предложенного мной алгоритма в том, что текущего варианта достаточно для продолжения поиска следующих вариантов.
Ну и конечно то, что нет рекурсии или предварительного создания всех возможных вариантов.
Хотя, конечно же , при плохих начальных условиях алгоритм будет все же перебирать варианты.
(56) Ovrfox, я это понял.
Я не согласен с тем, что вы подаете свой алгоритм как лучший. Сейчас я думаю, что они, по крайней мере, равноценны. Основная разница между ними — в том, что «мой» принципиально основан на рекурсии. А ваш — на цикле. В результате мой гораздо короче, а ваш проще останавливать и продолжать с прерванного места. Но и тот и другой можно подстроить на примерно одинаковую трудоемкость.
Хочу также объяснить почему получилась разница в быстродействии в обработке из (54) (не в пользу моего решения). Дело в том, что рекурсия перебирает все варианты, не худшие уже найденных. Она не останавливается, найдя первое решение. То есть в одной кнопке две ваших: остановить и продолжить, продолжить, продолжить.
Поэтому честнее было бы сравнивать скорость до попадания на фрагмент
Также у вас (как я понял) только один критерий — число кусков. Это — классическая задача о ранце. И вариант, как вы правильно и делаете, нужно развивать, беря максимально возможное количество самых больших кусков.
В моем решении «заказчик» (не настоящий, а собеседник на форуме) еще хотел обойтись минимальным количеством типоразмеров и по возможности выбирать типоразмеры до нуля. Поэтому у меня перебор не идет так круто в сторону решения из минимального количества кусков. Это также его задерживает. Но это можно перенастроить, поменяв на обратный порядок в цикле:
Но все же в данной статье я делал акцент на краткости кода и демонстрации того, что сложные задачи (без ущерба для производительности) можно решать иногда несколькими строчками. Пример именно об этом. Ваше решение буду иметь ввиду. Если придется использовать, постараюсь записать его короче.
(57) Решение, которое я предоставил все же лучше, потому что объеденены в нем два этапа
2-й (Подбор кусков в лоб с наибольших кусков) и
3-й Собственно перебор вариантов.
Из-за этого пересечения часть неподходящих варинатов отсеивается на каждом проходе
А именно — когда мы уменьшаем к-во в i-той строке — мы не перебираем все варианты для кусков с i+1 по n , а начинаем с уже ограниченного оставшимся метражом подбором кусков.
Поэтому к-во вариантов, которые отсеиваются без проверки значительно превышает кол-во проверяемых вариантов.
PS: Меня просто смутило то, что задача с порядком сложности 2#k8SjZc9DxkN решается путем прямого перебора.
Я считаю, выкладывать подобный код нужно для того, чтобы его не использовали. Как , например, алгоритм сортировки пузырьком.
Обязательно посмотрю новый алгоритм.
Жаль, что рекурсивный алгорим скорее всего не позволит продолжить перебор вариантов.
(60) Ovrfox, вот, можете посмотреть, что пока получается. Это рекурсия с ПРОДОЛЖЕНИЕМ перебора вариантов. Пока не могу решить, стоит ли логику продолжения оставлять для статьи, поскольку код все таки усложняется (это все, связанное с переменной ОК, которая равна ИСТИНА с момента нахождения очередного решения: чтобы вернуться из рекурсии, а затем зайти на те же места).
Но все равно код ОЧЕНЬ короткий:
Показать
(61) Здравствуйте
Я немного упростил (для понимания) ваш алгоритм рекурсии и заодно дополнил нерекурсивной функцией
После чего возник вопрос — в чем смысл рекурсии для подобного алгоритма? Цикл лень написать?
Показать
(62) Ovrfox, Спасибо за код. Он поучительный. Соображений по его поводу у меня довольно много. Поэтому разобью их на несколько комментариев.
Внешне код (я сейчас про цикл) мне нравится. Своей эффективностью. Отсутствием избыточности. Если бы играл в команде «против рекурсии», постарался написать бы именно такой. Очень понравились манипуляции с суммой «околоноля».
Но я здесь играю за рекурсию. И приведенный код как нельзя лучше подчеркивает ее необходимость.
Именно рекурсивная форма записи (и только она, как предполагаю) позволит обосновать (доказать) корректность приведенного не рекурсивного кода. А именно то, что он 1) не зациклится, 2) не пропустит никакого варианта. А также оценить количество выполняемых операций. А доказательство необходимо, одних тестовых просчетов просчетов обычно не достаточно. Тем более в комбинаторных задачах, где тестов не нагенерируешься.
Или скажите, как вы для себя надежно обосновывали то, что беготня вверх-вниз курсора по стеку дает нужный результат.
Если взять две формы одной и той же программы: рекурсивную и не рекурсивную, то рекурсивная будет обладать большей степенью абстракции, позволяющей легче обосновать ее правильность. Как будто написана на языке более высокого уровня. Взамен она более затратна (для большинства языков).
Поэтому правильный путь, как я считаю — это изначально записывать алгоритм в рекурсивной (более компактной и самодоказываемой) форме. А затем, при необходимости, раскрывать рекурсию, чтобы добиться большей скорости работы.
(62) Ovrfox, +(63)
Ну и теперь о конкретике:
Ваш вариант рекурсии и мой принципиально отличаются. У меня в одном уровне рекурсии работа ведется принципиально с одной строкой рабочей таблицы, с одним метражом. А переход на другой уровень рекурсии ограничивает область поиска оставшейся частью таблицы. Что и нужно для доказательства сходимости.
Думаю, поэтому вы и задали себе такой вопрос: а зачем такая (хвостовая) рекурсия (как у вас) вообще нужна.
У вас не проверяется ситуация исчерпанности метража в оставшейся зоне поиска, поэтому для задачи подбора 1023 из кусков 1-2-4-8-16-32-64-128-256-512 после варианта 1-1-1-1-1-1-1-1-1-1 программа будет перебирать все 1022 возможностей, чтобы убедиться, что вариантов больше нет. Тогда как «моя» рекурсия, да и ваша предыдущая редакция на это время тратить не будет.
Это я к тому, что ваш вариант «упрощения» привел к утрате кое-каких полезных свойств. По сути, это раскрытая рекурсия в исправленном варианте из статьи, если перебирать от большего к меньшему. Он был в моих комментариях. Вы же сами его критиковали за избыточный перебор.
Кстати, цикломатическая сложность у нас одинакова, а число строк у меня меньше. Это объективные показатели сложности. Ну, а субъективная понимаемость в моем коде, очевидно, похуже.
Поэтому я думаю отказаться от выхода-захода при нахождении варианта. Видимо, вернусь к варианту фиксации решения без прерывания поиска. Ведь это бывает нужно только при интерактивном выборе, которым все варианты использования алгоритма не ограничиваются. Это улучшит понимаемость. Также хочу делать отсечку при наборе числа кусков больше текущего рекорда при движении вниз, чтобы поиск велся строго в порядке улучшения достижений, а то сейчас число кусков сильно прыгает. Ну и из спортивного интереса сейчас смотрю вариант вообще без цикла (с его заменой на еще одну рекурсию). Может, еще короче получится. Это ведь «минимализмы».
Вы ошиблись, оба мои варианта тождественны и , хотя отличаются от Вашего, но созданы на основе одного алгоритма.
Более того, если на вход обоих функций подать неправильно упорядоченную таблицу элементов — то жадный алгоритм подбора вариантов может отбросить варианты, которые могли быть правильными. (т.е. не все варинаты будут перебраны). И , кстати, ваш алгоритм поведет себя точно также.
Что касается защиты решения. Во первых, я утверждаю, что решение одно в трех лицах. Во вторых, при анализе алгоритма, что в рекурсии, что в цикле будет анализироваться один шаг. Т.е. доказательство сходимости алгоритма одно и тоже. Просто представлены две реализации. Шаг как тело цикла и шаг как тело рекурсивной функции.
Что касается оптимальности кода. Накладные расходы на рекурсию достаточно велики. В моем и вашем случае — это составит один вызов рекурсивной функции на одну строку таблицы данных. Каждый вызов — это дубль внутренних переменных и передаваемых по значению переменных. Поэтому с точки зрения быстродействия я считаю цикл более оптимальным.
Что касается красоты кода, то я считаю красивым не более короткий код, а тот код, который приятно читать, т.е. понятный код, а уже во вторых — более короткий (но именно потому, что тратиться меньше времени на его восприятие). Именно поэтому я не считаю рекурсию красивой.
(65) Ovrfox, давайте разберемся по порядку, начиная с конкретики, с кода:
— какие это варианты? Если вы про два варианта в (62) — согласен.
Я имел ввиду разницу в поведении вашего варианта из (54) и из (62). И имел ввиду как ведет себя поиск в задаче: 1-2-4-8-16-32-64-128-256-512 (все куски по одному), если требуется подобрать кусок 1023.
Первый вариант 1-1-1-..-1 найдется жадным алгоритмом очень быстро. Но, чтобы убедиться в том, что других вариантов нет, ваш алгоритм из (62) будет перебирать все (сколько?) вариантов, а мой нет.
Вот трассировка (начало, всего 1024 строки) вариантов, проверяемых в вашем цикле из (62):
0111111111
1011111111
0011111111
1101111111
0101111111
1001111111
0001111111
1110111111
0110111111
1010111111
0010111111
1100111111
0100111111
1000111111
0000111111
1111011111
0111011111
1011011111
0011011111
1101011111
0101011111
1001011111
0001011111
1110011111
0110011111
1010011111
0010011111
1100011111
0100011111
1000011111
0000011111
1111101111
…
Показать
По какой системе идет перебор видно только из трассировки! — А много ли людей смогут увидеть это, глядя только на код? На мой взгляд, код в (62) только выглядит просто, но на самом деле вообще непонятен. Это классная головоломка. Можно даже эксперимент провести.
И давайте вот сюда
уже не лезть. Проблем с пониманием хватает и с правильно упорядоченными таблицами.
Действительно, когда я разбирал Ваш алгоритм, я ошибся , откат происходит неоптимально.
Но, к сожалению, главный посыл до Вас не дошел. Я ведь просто хотел показать, что цикл более читабельный и более эффективный.
Я пытался Ваш алгоритм преобразовать в цикл, стараясь внести как можно меньше изменений. К сожалению. у меня не получилось.
Как я теперь понял потому, что он просто не правильный
Просто попытайтесь побобрать 3 из массива 1,2,3 . Второй вариант алгоритм не находит ( в отличии от того, который я предложил на основе Вашего)
Вы уж извините меня, что я так небрежно подошел к анализу предложенных алгоритмов. Но я просто хотел указать на то, ИМХО, что рекурсия не самый оптимальный способ для расчетов. Особенно связанных с большими массивами данных.
Какая-то странная функция в запросе п.28 :
МАКСИМУМ(ВЫБОР Слева.Цена КОГДА Дано.Цена ТОГДА Слева.Дата КОНЕЦ)
Похоже, ошибка, или я что-то не знаю про синтаксис функции ВЫБОР.
(68) bulpi, ошибки нет, вот ссылка: . Удобный прием, я часто его использую.
Автору спасибо за 28. Движения периодического регистра сведений без повторов. Попробую применить на практике
(4) «1С когда-то в каких-то замшелых инструкциях не рекомендовала эту букву.»
Достаточно вспомнить приснопамятный Счётчик() в 77
32. Определение длины строки в запросе методом половинного деления
На СУБД MSSQL попытка выполнить запрос выдает ошибку (слишком сложный запрос)
Microsoft SQL Server Native Client 11.0: Internal error: An expression services limit has been reached. Please look for potentially complex expressions in your query, and try to simplify them. HRESULT=80040E14, SQLSrvr: SQLSTATE=42000, state=2, Severity=11, native=8632, line=1
Надо подумать о решении с меньшей вложенностью запросов.
(29) Ругается что поля А и Б не входят в группу
Весь мой запрос:
Показать
(73) Вы правы, в запросе в 29 не хватает последней строчки СГРУППИРОВАТЬ ПО А,Б.
В итоге текст запроса должен выглядеть так:
(72) я переделал вложенные запросы в пакеты. Изящность конечно утеряно но работает:
Показать
В методе минимализма 32 есть ошибка.
Длинна строки : «АБВГ Д» определяется как 4. «АБВГДЕЖЗ И» как 8 и так далее.
Проблема в том, что ПОДСТРОКА(«АБВГ Д», 5, 1) = «», хотя на самом деле там » «.
(76) К сожалению, пропустил ваше замечание. Теперь, когда на эту ошибку мне еще раз указали в исходной статье, нашел и исправил. Использую проверку
Либо
Разница есть, поэтому приведены оба варианта.
В минимализме №25 в первой временной таблице не хватает условий во внутреннем соедининии, а именно
«Дано.Гостиница = ДаноСлева.Гостиница И
Дано.ФизическоеЛицо = ДаноСлева.ФизическоеЛицо»
(79) Поправил, спасибо за внимательность.
Опубликована очередная серия «минимализмов» — Минимализмы — 3 [].