Дня доброго.
Есть возрастающий числовой массив.
Необходимо его разбить на диапазоны, на которых он непрерывен.

Например, массив из элементов
1,3,4,5,7,8,9,10
должен выглядеть как таблица
НачалоДиапазона    КонецДиапазона
1            1
3            5
7            10

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

(22) нах...я усложнять код только ради повыпендриваться рекурсией? Да и выигрыша я там не вижу, скорее проигрыш. И в скорости, и в памяти. Есть многократный поиск в ТЗ, читай - многократный цикл. Плюс из-за рекурсии неконтролируемо растущий стек. В то время как задача прекрасно решается за один обход массива, без каких-либо поисков

Вроде бы во всех книжках написано, что рекурсия это ненужно и вредно. Накой она тебе тут сдалась?
Тупо прошел по массиву и всё.

(29) нет, не ФСИН, а нормальный отдел разработки , который контроллирует качество разработки. К сожалению на некоторых разработчиков действуют только такие методы убеждения.

(32) Просто некоторые задачи органично и понятно для человека решаются рекурсивными алгоритмами их не рекурсивные аналоги конечно эффективнее, но как правило очень сложные и как следствие плохо сопровождаемые

(34) Но тут то примитив, а рекурсия не для понятности, а чтобы рекурсия.

(32) В данном случае от рекурсии вреда немного. Разве что накладные расходы по времени вызовов будут расти пропорционально неоднородности. Зато она позволяет относительно красиво объединить двоичный поиск с разбитием на диапазоны. Относительно - потому что вот это слитие диапазонов выглядит как костыль.
Поэтому я за простой проход с автоподбором размера шага. А двоичным поиском уже внутри "шага" границу находить.

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

У в алгоритме из 10 строчек можно без рекурсии обойтись


    МассивСтарт = Новый Массив();
    МассивСтоп = Новый Массив();
    
    Индекс = 0;
    Конец = МассивДанных.ВГраница();
    Старт  = МассивДанных[0];
    Стоп = Старт;
    Пока Истина Цикл
        Индекс = Индекс + 1;
        Если Индекс > Конец Тогда
            МассивСтарт.Добавить(Старт);
            МассивСтоп.Добавить(Стоп);
            Прервать;
        КонецЕсли;
        Следующий = МассивДанных[Индекс];
        Если Стоп + 1 = Следующий Тогда
            Стоп = Следующий;
        Иначе
            МассивСтарт.Добавить(Старт);
            МассивСтоп.Добавить(Стоп);
            Старт = Следующий;
            Стоп = Следующий;
        КонецЕсли;
    КонецЦикла;
    
    //вывод результата
    Для а = 0 по МассивСтарт.ВГраница() Цикл
        Сообщить(СтрШаблон("%1 : %2",МассивСтарт[а], МассивСтоп[а]));
    КонецЦикла;

Если я правильно понял задачу

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

(37) ну начинается...пфф школа, такие задачки, мы за завтраком в детском саду решали, а в обед обсуждали теорию струн и проблему 3x+1

(39) это полный перебор.
У меня массив будет в 99% случаев однороден.

(40) Задача без полного перебора не решается в принципе

(40) Ты хочешь перебрать массив без перебора что ли? Так же не бывает.

какая нафиг рекурсия, тут в цикле за один проход всё делается

(2)Алгоритм работает.Но блин без рекурсии все же надежнее.И проще.
И ясно даже джуну, железобетонно короче.

(44) Это Хак.
<1c>    
РазмерДиапазона=ПоследнийЭлемент-ПервыйЭлемент;
    РазмерДанных=ИндексПоследнегоЭлемента-ИндексПервогоЭлемента;
    Возврат РазмерДанных=РазмерДиапазона;
</1c>

(44) Ладно Гариком, ему простительно, но от тебя такое слышать!

(42) у тебя там все хорошо? переработок по 23 часа не было случаем? высыпаешься хорошо и здоровье не подводит?

а то какой то бред пишешь, точно все в порядке?

Видимо ТС и тех, кто Фибаначчи рекурсией делает.
Зашел в тему, думал надо запросом (где-то уже решал подобное), а тут такое..

(43) Как не решается? Методом половинного деления как у H A D G E H O G s вполне себе разрывы ищутся.

(44) см (23).

(47) это не хак это хуже полного перебора

(51) на отсортированном предварительно массиве!!!

+ (51) Вполне без перебора.

(54)+ сортировка без перебора полного каким местом делается?

Ждем тестов

(56) сортировка на скл делается

(40) Ты зря боишься перебора. Тебе ли не знать, что такое cache-friendly алгоритм?
В реальности выигрыша не будет или будет минимальный.

(58) тогда там же и разрывы искать будет самое быстрое в этом конкретном случае

(54) Причем здесь отсортированный или нет. Просто заранее известно, что в массиве есть непрерывные области. Все.

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

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

(63) сам и попроси.

Во избежание рекурсии я бы сначала определил границы разрывов. Просто каждый раз начиная поиск с индекса последней краевой точки. А потом уже исходный массив делил на области. Тем более, что количество разрывов на промежутке находится простой арифметикой.

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

Зачем усложнять то?У автора порядка 100000 элементов.При большем и неблагоприятном вероятно рекурсия свалится.Простейший алгоритм найдет очень быстро решение.
Экономить нужно время программистов.

(64) https://infostart.ru/public/402534/

(68) там 12 коммент глянь

(67) не свалится. Подели 100000 на 2, пока результат больше единицы. Ты получишь 18 делений - вот твоя максимальная глубина стека.

Я пробовал на полностью разорванном массиве в 100000 эл - ничего не валится.

Не знаю как на реальных данных, но вот на таком

    Для а = 1 по 100000 Цикл
        Для б = 1 по 10 Цикл
            МассивДанных.Добавить(б);
        КонецЦикла;    
    КонецЦикла;

100000 последовательностей по 10 чисел
(0) работал 52 сек
(39) работал 13 сек

(71) быстрее только нечто внешнее

А если данных мало, то и разницы не будет почти.
Тут один хрен будет перебор. Если не полный, то почти полный.

Ибо начало и конец последовательности могут быть в любой ячейке

+(66) упс, код не смотрел, так автор примерно это и сделал...(

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

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

Выбери все номера которых нет, отсортируй и получишь левые и правые границы.

(77) >Выбери все номера которых нет
полным перебором?

Я конечно может чего не понимаю, но мне кажется скорость О(n) для алгоритма - это нормально. Даже если массив данных - миллионный.
Это кнечно, если имеется в виду практическое применение алгоритма.

(71)Такой массив не удовлетворяет требованиям задачи.

(79) Миллионный нормально, а если трилионный — уже маловато.

Но ТС имхо просто хотел выпендриться.

алгоритм похож на сортировку слиянием (merge sort)

(80) Ибо там по 10000 единичек,двоек и тп

(76) может быть 1 разрыв длиною в тыщу

надо объявить конкурс на лучшее решение задачи. как раньше была на удаление строк в тз

(80) Ну покажи какой удовлетворяет

(85) по результатом которой выяснилось что всегда надо не удалять строки из ТЗ
создать новую ТЗ и копировать туда только нужные строки

(87) в 77 был хак с установить размер тз. он и выигрывал.
непосредственное удаление было конечно хуже всех

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

(86) должны быть все разные числа

(12) и передача всего пакета данных в 1Е5 элементов каждый раз... любая рекурсия не сложно трансформируется в цикл.

(91) массивы по ссылке передаются

(86) И с разными пробовал. Если не под отладкой запускать, то там вообще (0) за 5 сек всё перелопачивает, а (39) за 1 сек
так что нет смысла ломать голову

(92) тогда пофиг если рекурсия реально не глубока

(40) Ниже чисто концептуальный блок для демонстрации идеи. Стопудово с ошибками (без ошибок я такое писать сходу не умею):

ТаблицаРезультата=Новый ТаблицаЗначений;
ТаблицаРезультата.Колонки.Добавить("НачалоДиапазона", "Число");
ТаблицаРезультата.Колонки.Добавить("КонецДиапазона", "Число");

РазмерМассива = ИсходныйМассив.Количество();
ШагОбхода = Окр(РазмерМассива / 10 + 0.5);
ШагОбхода = ?(ШагОбхода = 0, 1, ШагОбхода);

ТекущийИндекс = СтартовыйШаг;
СтрокаДиапазона = ТаблицаРезультата.Добавить();
ОбщаяНепрерывность = 0;
Пока ТекущийИндекс < РазмерМассива Цикл
    
    // найдем верхнюю границу конца непрерывного диапазона с точностью до шага обхода
    ИндексНачалаПоискаКонцаНепрерывногоДиапазона = СтрокаДиапазона.НачалоДиапазона;
    Пока ТекущийИндекс < РазмерМассива И НетРазрывов(ИсходныйМассив, ИндексНачалаПоискаКонцаНепрерывногоДиапазона, ТекущийИндекс) Цикл
        ИндексНачалаПоискаКонцаДиапазона = ТекущийИндекс;
        ТекущийИндекс = ИндексНачалаПоискаКонцаДиапазона + ШагОбхода;
    КонецЦикла;
    
    // найдем точную границу конца непрерывного диапазона внутри шага
    КонецДиапазона = НайтиКонецНепрерывногоДиапазонаДвоичнымПоиском(ИсходныйМассив, ИндексНачалаПоискаКонцаНепрерывногоДиапазона, ТекущийИндекс);
    СтрокаДиапазона.КонецДиапазона = КонецДиапазона;
    ОбщаяНепрерывность = ОбщаяНепрерывность + СтрокаДиапазона.КонецДиапазона - СтрокаДиапазона.КонецДиапазона + 1;
    
    // инициализируем итерацию следующего непрерывного диапазона
    Если СтрокаДиапазона.КонецДиапазона < РазмерМассива - 1 Тогда
        СтрокаДиапазона = ТаблицаРезультата.Добавить();
        СтрокаДиапазона.НачалоДиапазона = КонецДиапазона + 1;
    КонецЕсли;
    
    // адаптация размера шага обхода
    СреднийРазмерНепрерывногоДиапазона = Окр(ОбщаяНепрерывность / ТаблицаРезультата.Количество() + 0.5);
    ШагОбхода = Окр(СреднийРазмерНепрерывногоДиапазона / 3 + 0.5);
    
    ТекущийИндекс = ТекущийИндекс + ШагОбхода;
    
КонецЦикла;

Если СтрокаДиапазона.КонецДиапазона = 0 Тогда
    СтрокаДиапазона.КонецДиапазона = РазмерМассива - 1;
КонецЕсли;


в худшем случае будет обход + 2-поиск для каждой строки

И там не может быть без полного перебора. Есть полный перебор и полный перебор с помощью ухищрений и рекурсии.

(97) в худшем случае конечно. но расчет на то что таких случаев бывает мало

(95) Что-то я затупил насчет ОбщейНепрерывности. Оно же и так все суммарно непрерывно :) Достаточно количества блоков для вычисления среднего размера непрерывного блока.

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

это ветка обсуждения, как обойти массив не за 10сек, а за 7?)

(101) остальное все летает за 0.1 сек

(101) Ты так говоришь, как будто в этом есть что-то плохое.

(103) да все хорошо и полезно, но главное, чтобы труд приносил реальную пользу, а не так, чтобы оптимизация ради оптимизации.

(104) Тогда всем закрыть браузеры и работать нах. Солнце еще высоко.

(105) ты не понимаешь, это другое))

(34) тут ни разу не такой случай, без рекурсии будет проще

Хмм если "на JS одна строка" а в 1С есть JS внутри ПолеHTML кто возьмется затестить?

(21)
+100

(110) предложи уже микросервис написать, там есть куда более быстрые библиотеки для этого дела)

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

В 1С это тоже в итоге будет одна строка :)
Ну а хвастаться тем, что в каком-то языке более богатая стандартная библиотека - это такое. Да, неплохо. Но это же не твоя заслуга, как разработчика.
Вот чем мне импонируют относительно низкоуровневые языки, так это тем, что там фактически вся стандартная библиотека на них же и написана и можно элементарно сорцы смотреть. То есть там нет принципиальной разницы для рантайма - это твоя функция или библиотечная. Все примерно на одном языке друг с другом разговаривают. А не вот это странное "пффф! Я такой крутой, что в одну строку написать могу на своем настоящем языке, а не на вот этом вот!" Допустим, можешь. Но если твоей заслуги в этом никакой, то какой смысл в этом оффтопике?

(114) Кто мешал тоже самое сделать на 1С?

(115) тоже легко )) написал процу и вызвал ее одной строкой ))))

(114) а кто тут хвастается? По мне так полезно знать разные сторонние библиотеки и уметь их применять в 1с для оптимизации и расширения функционала.

(115) Как кто мешал? Концепция низкого порога входа и необходимого минимума.
ЗЫ. Так "обожаю" вопрос "кто мешал", кто бы знал. Не люблю пассивно-агрессивных. Требуешь идеальных решений - попробуй сам их создать и "продать". Выслушай в ответ килотонну "кто мешал" и попустись.

(118) 1С имеет свой ЯП
Почему саму платформу не стали писать на своем же ЯП?

(119) А еще я не люблю ввязываться в манипуляционные диалоги на риторических вопросах.

(119) Ага, почему JVM не написали на жабе?

(121) библиотеки (кроме отдельных методов) и компилятор уже давно на Java, вот JVM оно на разных может быть

(122) БСП тоже на 1С

(123) в одной конфе 1С каким образом одновременно несколько разных версий "библиотек" БСП использовать?

(124) Зачем?

эй! ты тут помощь зала собираешь
так не честно

(126) а ты за кого болеешь?