Вход | Регистрация
    1  2   

Разбить числовой массив на диапазоны

Разбить числовой массив на диапазоны
Я
   H A D G E H O G s
 
06.10.21 - 23:13
Дня доброго.
Есть возрастающий числовой массив.
Необходимо его разбить на диапазоны, на которых он непрерывен.

Например, массив из элементов
1,3,4,5,7,8,9,10
должен выглядеть как таблица
НачалоДиапазона    КонецДиапазона
1            1
3            5
7            10
   H A D G E H O G s
 
1 - 06.10.21 - 23:14
У меня получилась вот такая обработка

https://disk.yandex.ru/d/5gcAqwEYTrvsig

Все ли верно? Можно ли сделать лучше?
Массив будет многотысячным.
   H A D G E H O G s
 
2 - 06.10.21 - 23:15
В виде кода:

&НаСервере
Функция ДиапазонНепрерывен(МассивДанных,ИндексПервогоЭлемента,ИндексПоследнегоЭлемента)
    ПервыйЭлемент=МассивДанных[ИндексПервогоЭлемента];
    ПоследнийЭлемент=МассивДанных[ИндексПоследнегоЭлемента];
    РазмерДиапазона=ПоследнийЭлемент-ПервыйЭлемент;
    РазмерДанных=ИндексПоследнегоЭлемента-ИндексПервогоЭлемента;
    Возврат РазмерДанных=РазмерДиапазона;
КонецФункции

&НаСервере
Процедура РазбитьМассив(МассивДанных,ПервыйЭлемент,ПоследнийЭлемент, ТаблицаРезультата)
    Если ДиапазонНепрерывен(МассивДанных,ПервыйЭлемент,ПоследнийЭлемент) Тогда
        НачалоДиапазона=МассивДанных[ПервыйЭлемент];
        КонецДиапазона=МассивДанных[ПоследнийЭлемент];
        СтрокаТаблицы=ТаблицаРезультата.Найти(НачалоДиапазона-1,"КонецДиапазона")//Попробуем объединить диапазон

        Если СтрокаТаблицы=Неопределено Тогда
            СтрокаТаблицы=ТаблицаРезультата.Добавить();
            СтрокаТаблицы.НачалоДиапазона=НачалоДиапазона;
        КонецЕсли;
        СтрокаТаблицы.КонецДиапазона=КонецДиапазона;
        Возврат;
    КонецЕсли;
    СерединаДиапазона=Цел((ПоследнийЭлемент-ПервыйЭлемент)/2)+ПервыйЭлемент;
    РазбитьМассив(МассивДанных,ПервыйЭлемент,СерединаДиапазона, ТаблицаРезультата);
    РазбитьМассив(МассивДанных,СерединаДиапазона+1,ПоследнийЭлемент, ТаблицаРезультата);    
КонецПроцедуры

&НаСервере
Процедура КомандаНаСервере()
    ТаблицаРезультата=Новый ТаблицаЗначений;
    ТаблицаРезультата.Колонки.Добавить("НачалоДиапазона");
    ТаблицаРезультата.Колонки.Добавить("КонецДиапазона");
    ТаблицаРезультата.Индексы.Добавить("КонецДиапазона");
    РазбитьМассив(МассивДанных,0,МассивДанных.Количество()-1,ТаблицаРезультата);

КонецПроцедуры
   RomanYS
 
3 - 06.10.21 - 23:30
Ожидается что массив будет очень плотным?
Иначе непонятно зачем такая оптимизация с рекурсией. Один линейный проход будет в среднем быстрее и понятнее. Если конечно массив не содержит 99% значений диапазона
.
   RomanYS
 
4 - 06.10.21 - 23:33
Массив будет многотысячным
Если без обращений к базе, то не страшно. Или тебе прямо миллисекунды важны?
   серый КТУЛХУ
 
5 - 07.10.21 - 00:15
ВЫБРАТЬ
    МИНИМУМ(втДляСвертки.ТекЧисло) КАК ЛеваяГраницаДиавазона,
    втДляСвертки.ТекЧислоСлева КАК ПраваяГраницаДиавазона
ИЗ    (ВЫБРАТЬ втЧисла.ТекЧисло, МИНИМУМ(ПеГраницы.ТекЧислоСлева) КАК ТекЧислоСлева
    ИЗ втЧисла КАК втЧисла
    ВНУТРЕННЕЕ СОЕДИНЕНИЕ ПеГраницы КАК ПеГраницы ПО втЧисла.ТекЧисло <= ПеГраницы.ТекЧислоСлева
    СГРУППИРОВАТЬ ПО втЧисла.ТекЧисло) КАК втДляСвертки
СГРУППИРОВАТЬ ПО втДляСвертки.ТекЧислоСлева
(само собой загнать сначала через парметр в втЧисла все свои числа отсортированные по возрастанию)
   серый КТУЛХУ
 
6 - 07.10.21 - 00:18
паардон не целиком... воть:
ВЫБРАТЬ втЧислаСлева.ТекЧисло КАК ТекЧислоСлева
ПОМЕСТИТЬ втГраницы
ИЗ втЧисла КАК втЧислаСлева
    ЛЕВОЕ СОЕДИНЕНИЕ втЧисла КАК втЧислаСправа
    ПО (втЧислаСлева.ТекЧисло + 1 = втЧислаСправа.ТекЧисло)
ГДЕ втЧислаСправа.ТекЧисло ЕСТЬ NULL
;

////////////////////////////////////////////////////////////////////////////////

ВЫБРАТЬ
    МИНИМУМ(втДляСвертки.ТекЧисло) КАК ЛеваяГраницаДиавазона,
    втДляСвертки.ТекЧислоСлева КАК ПраваяГраницаДиавазона
ИЗ    (ВЫБРАТЬ втЧисла.ТекЧисло, МИНИМУМ(ПеГраницы.ТекЧислоСлева) КАК ТекЧислоСлева
    ИЗ втЧисла КАК втЧисла
    ВНУТРЕННЕЕ СОЕДИНЕНИЕ ПеГраницы КАК ПеГраницы ПО втЧисла.ТекЧисло <= ПеГраницы.ТекЧислоСлева
    СГРУППИРОВАТЬ ПО втЧисла.ТекЧисло) КАК втДляСвертки
СГРУППИРОВАТЬ ПО втДляСвертки.ТекЧислоСлева
   серый КТУЛХУ
 
7 - 07.10.21 - 00:20
даблин.
ВЫБРАТЬ втЧислаСлева.ТекЧисло КАК ТекЧислоСлева
ПОМЕСТИТЬ втГраницы
ИЗ втЧисла КАК втЧислаСлева
    ЛЕВОЕ СОЕДИНЕНИЕ втЧисла КАК втЧислаСправа
    ПО (втЧислаСлева.ТекЧисло + 1 = втЧислаСправа.ТекЧисло)
ГДЕ втЧислаСправа.ТекЧисло ЕСТЬ NULL
;

////////////////////////////////////////////////////////////////////////////////


ВЫБРАТЬ
    МИНИМУМ(втДляСвертки.ТекЧисло) КАК ЛеваяГраницаДиавазона,
    втДляСвертки.ТекЧислоСлева КАК ПраваяГраницаДиавазона
ИЗ    (ВЫБРАТЬ втЧисла.ТекЧисло, МИНИМУМ(втГраницы.ТекЧислоСлева) КАК ТекЧислоСлева
    ИЗ втЧисла КАК втЧисла
    ВНУТРЕННЕЕ СОЕДИНЕНИЕ втГраницы КАК втГраницы ПО втЧисла.ТекЧисло <= втГраницы.ТекЧислоСлева
    СГРУППИРОВАТЬ ПО втЧисла.ТекЧисло) КАК втДляСвертки
СГРУППИРОВАТЬ ПО втДляСвертки.ТекЧислоСлева
   amiga 600
 
8 - 07.10.21 - 00:20
»
   серый КТУЛХУ
 
9 - 07.10.21 - 00:22
(8): запрос (7) можно и в одну строку.
   H A D G E H O G s
 
10 - 07.10.21 - 00:27
Естественно, никаких запросов.
Массив почти всегда без разрывов, но иногда случаются.

Надо проверить на большом массиве с множественными разрывами ближе к началу и концу - хватит ли стека на рекурсию. Но завтра.
   серый КТУЛХУ
 
11 - 07.10.21 - 00:30
(10): почему "никаких запросов"?.. вполне себе компактненько получилось.
а рекурсия на больших массивах данных - зло. вылет практически обеспечен. каждая рекурсия - полный дубликат контекста с навесами-свистелками-перделками
   H A D G E H O G s
 
12 - 07.10.21 - 00:53
А тут нечего и думать.
Для 100000 элементов максимальная глубина стека будет равна 18 уровням.
   Смотрящий
 
13 - 07.10.21 - 00:58
(11) А где написано про дубляж контекста при рекурсвном вызове и прочие свистоперделки ?
   Конструктор1С
 
14 - 07.10.21 - 07:04
(2) шибка сложна решаешь, рекурсия тут нафиг не нужна
   NorthWind
 
15 - 07.10.21 - 07:12
(14) Норм он все делает. По скорости дихотомия даст самый лучший результат.
(2) хорошо.
   Конструктор1С
 
16 - 07.10.21 - 07:23
(15) нет там никакого прироста скорости, только ресурсы больше жрутся. Плюс код запутанный. Это дело прекрасно решается за один цикл
   pechkin
 
17 - 07.10.21 - 07:28
Что будет в самом плохом варианте когда через 1 пропуски?
   NorthWind
 
18 - 07.10.21 - 08:33
(16) будет прирост, вернее, его не будет только в случае большого количества дырок.
У него нет полного перебора массива, диапазон проверяется через хак - путем вычитания последнего элемента от первого.
   NorthWind
 
19 - 07.10.21 - 08:35
на в основном непрерывном массиве прирост будет очень большой
   toypaul
 
20 - 07.10.21 - 08:51
Что-то я не очень понял. Зачем тут рекурсия?

если м[н+1] <> м[н] + 1, то заканчиваем текущий интервал и начинаем новый

это если последовательность возрастающая
   Garykom
 
21 - 07.10.21 - 08:55
(2) профдеформация
имхо можешь успешно идти в саму 1С на типовые
   NorthWind
 
22 - 07.10.21 - 09:03
(20) А чтобы не делать проход массива от начала и до конца. Он проверяет непрерывность диапазона от начального до конечного элемента без прохода этого диапазона - сравнивая разницу индексов и разницу элементов. Если равно, то диапазон непрерывный.
   NorthWind
 
23 - 07.10.21 - 09:03
Вся мякотка вот здесь
    ПервыйЭлемент=МассивДанных[ИндексПервогоЭлемента];
    ПоследнийЭлемент=МассивДанных[ИндексПоследнегоЭлемента];
    РазмерДиапазона=ПоследнийЭлемент-ПервыйЭлемент;
    РазмерДанных=ИндексПоследнегоЭлемента-ИндексПервогоЭлемента;
    Возврат РазмерДанных=РазмерДиапазона;
   Галахад
 
24 - 07.10.21 - 09:06
Хм. Программистам растолковывать как работает код? :-)
   Почему 1С
 
25 - 07.10.21 - 09:22
Классическое решение задачки, которую любят давать на собеседованиях.
   toypaul
 
26 - 07.10.21 - 09:32
(22) понял. ну чтобы мозги потренировать ОК. а если сравнить по времени тупой перебор и эту рекурсию. хотя бы сколько-то секунд выигрыш будет?
   fisher
 
27 - 07.10.21 - 09:34
(2) Хвастаешься? :)
   fisher
 
30 - 07.10.21 - 09:42
Можно без рекурсии сделать алгоритм с адаптивным шагом, который будет пытаться подстраиваться под характер разрывов.
 
 
   Конструктор1С
 
31 - 07.10.21 - 09:47
(22) нах...я усложнять код только ради повыпендриваться рекурсией? Да и выигрыша я там не вижу, скорее проигрыш. И в скорости, и в памяти. Есть многократный поиск в ТЗ, читай - многократный цикл. Плюс из-за рекурсии неконтролируемо растущий стек. В то время как задача прекрасно решается за один обход массива, без каких-либо поисков
   Кирпич
 
32 - 07.10.21 - 09:50
Вроде бы во всех книжках написано, что рекурсия это ненужно и вредно. Накой она тебе тут сдалась?
Тупо прошел по массиву и всё.
   Малыш Джон
 
33 - 07.10.21 - 09:57
(29) нет, не ФСИН, а нормальный отдел разработки , который контроллирует качество разработки. К сожалению на некоторых разработчиков действуют только такие методы убеждения.
   Почему 1С
 
34 - 07.10.21 - 09:57
(32) Просто некоторые задачи органично и понятно для человека решаются рекурсивными алгоритмами их не рекурсивные аналоги конечно эффективнее, но как правило очень сложные и как следствие плохо сопровождаемые
   Кирпич
 
35 - 07.10.21 - 09:58
(34) Но тут то примитив, а рекурсия не для понятности, а чтобы рекурсия.
   fisher
 
36 - 07.10.21 - 09:59
(32) В данном случае от рекурсии вреда немного. Разве что накладные расходы по времени вызовов будут расти пропорционально неоднородности. Зато она позволяет относительно красиво объединить двоичный поиск с разбитием на диапазоны. Относительно - потому что вот это слитие диапазонов выглядит как костыль.
Поэтому я за простой проход с автоподбором размера шага. А двоичным поиском уже внутри "шага" границу находить.
   Жан Пердежон
 
37 - 07.10.21 - 10:00
(0) в школе такие задачки были, это максимум для собеседования джуна, зачем так на мисте позориться?
   Кирпич
 
38 - 07.10.21 - 10:00
У в алгоритме из 10 строчек можно без рекурсии обойтись
   Кирпич
 
39 - 07.10.21 - 10:01
    МассивСтарт = Новый Массив();
    МассивСтоп = Новый Массив();
    
    Индекс = 0;
    Конец = МассивДанных.ВГраница();
    Старт  = МассивДанных[0];
    Стоп = Старт;
    Пока Истина Цикл
        Индекс = Индекс + 1;
        Если Индекс > Конец Тогда
            МассивСтарт.Добавить(Старт);
            МассивСтоп.Добавить(Стоп);
            Прервать;
        КонецЕсли;
        Следующий = МассивДанных[Индекс];
        Если Стоп + 1 = Следующий Тогда
            Стоп = Следующий;
        Иначе
            МассивСтарт.Добавить(Старт);
            МассивСтоп.Добавить(Стоп);
            Старт = Следующий;
            Стоп = Следующий;
        КонецЕсли;
    КонецЦикла;
    
    //вывод результата

    Для а = 0 по МассивСтарт.ВГраница() Цикл
        Сообщить(СтрШаблон("%1 : %2",МассивСтарт[а], МассивСтоп[а]));
    КонецЦикла;

Если я правильно понял задачу
   H A D G E H O G s
 
40 - 07.10.21 - 10:02
(37) мне для работы надо.
(36) давай без реккурсии, но и чтобы без полного перебора.
   Kassern
 
41 - 07.10.21 - 10:04
(37) ну начинается...пфф школа, такие задачки, мы за завтраком в детском саду решали, а в обед обсуждали теорию струн и проблему 3x+1
   H A D G E H O G s
 
42 - 07.10.21 - 10:05
(39) это полный перебор.
У меня массив будет в 99% случаев однороден.
   Garykom
 
43 - 07.10.21 - 10:05
(40) Задача без полного перебора не решается в принципе
   Кирпич
 
44 - 07.10.21 - 10:05
(40) Ты хочешь перебрать массив без перебора что ли? Так же не бывает.
   Жан Пердежон
 
45 - 07.10.21 - 10:05
какая нафиг рекурсия, тут в цикле за один проход всё делается
   bolder
 
46 - 07.10.21 - 10:05
(2)Алгоритм работает.Но блин без рекурсии все же надежнее.И проще.
И ясно даже джуну, железобетонно короче.
   bolder
 
47 - 07.10.21 - 10:07
(44) Это Хак.
<1c>    
РазмерДиапазона=ПоследнийЭлемент-ПервыйЭлемент;
    РазмерДанных=ИндексПоследнегоЭлемента-ИндексПервогоЭлемента;
    Возврат РазмерДанных=РазмерДиапазона;
</1c>
   H A D G E H O G s
 
48 - 07.10.21 - 10:07
(44) Ладно Гариком, ему простительно, но от тебя такое слышать!
   Garykom
 
49 - 07.10.21 - 10:07
(42) у тебя там все хорошо? переработок по 23 часа не было случаем? высыпаешься хорошо и здоровье не подводит?

а то какой то бред пишешь, точно все в порядке?
   Жан Пердежон
 
50 - 07.10.21 - 10:07
Видимо ТС и тех, кто Фибаначчи рекурсией делает.
Зашел в тему, думал надо запросом (где-то уже решал подобное), а тут такое..
   Василий Алибабаевич
 
51 - 07.10.21 - 10:07
(43) Как не решается? Методом половинного деления как у H A D G E H O G s вполне себе разрывы ищутся.
   H A D G E H O G s
 
52 - 07.10.21 - 10:08
(44) см (23).
   Garykom
 
53 - 07.10.21 - 10:08
(47) это не хак это хуже полного перебора
   Garykom
 
54 - 07.10.21 - 10:08
(51) на отсортированном предварительно массиве!!!
   Василий Алибабаевич
 
55 - 07.10.21 - 10:08
+ (51) Вполне без перебора.
   Garykom
 
56 - 07.10.21 - 10:08
(54)+ сортировка без перебора полного каким местом делается?
   pechkin
 
57 - 07.10.21 - 10:08
Ждем тестов
   pechkin
 
58 - 07.10.21 - 10:09
(56) сортировка на скл делается
   mistеr
 
59 - 07.10.21 - 10:09
(40) Ты зря боишься перебора. Тебе ли не знать, что такое cache-friendly алгоритм?
В реальности выигрыша не будет или будет минимальный.
   Garykom
 
60 - 07.10.21 - 10:09
(58) тогда там же и разрывы искать будет самое быстрое в этом конкретном случае
 
 
   Василий Алибабаевич
 
61 - 07.10.21 - 10:10
(54) Причем здесь отсортированный или нет. Просто заранее известно, что в массиве есть непрерывные области. Все.
   H A D G E H O G s
 
62 - 07.10.21 - 10:10
(56) у меня уже отсортированный массив, который приполз из базы
   Garykom
 
63 - 07.10.21 - 10:10
(62) попроси из базы несколько массивов, каждый без разрывов
   H A D G E H O G s
 
64 - 07.10.21 - 10:11
(63) сам и попроси.
   Василий Алибабаевич
 
65 - 07.10.21 - 10:16
Во избежание рекурсии я бы сначала определил границы разрывов. Просто каждый раз начиная поиск с индекса последней краевой точки. А потом уже исходный массив делил на области. Тем более, что количество разрывов на промежутке находится простой арифметикой.
   Bigbro
 
66 - 07.10.21 - 10:22
если массив с небольшим числом дырок, то можно попробовать жадные стратегии
по считанному значению пытаться угадать адрес следующей дырки в данных (либо если кусок достался без дырки - едем дальше, уменьшая шаг за счет пропущенного непрерывного куска)
обычный поиск золотым сечением или типа того.
   bolder
 
67 - 07.10.21 - 10:24
Зачем усложнять то?У автора порядка 100000 элементов.При большем и неблагоприятном вероятно рекурсия свалится.Простейший алгоритм найдет очень быстро решение.
Экономить нужно время программистов.
   Garykom
 
68 - 07.10.21 - 10:25
   Garykom
 
69 - 07.10.21 - 10:27
(68) там 12 коммент глянь
   H A D G E H O G s
 
70 - 07.10.21 - 10:33
(67) не свалится. Подели 100000 на 2, пока результат больше единицы. Ты получишь 18 делений - вот твоя максимальная глубина стека.

Я пробовал на полностью разорванном массиве в 100000 эл - ничего не валится.
   Кирпич
 
71 - 07.10.21 - 10:34
Не знаю как на реальных данных, но вот на таком
    Для а = 1 по 100000 Цикл
        Для б = 1 по 10 Цикл
            МассивДанных.Добавить(б);
        КонецЦикла;    
    КонецЦикла;

100000 последовательностей по 10 чисел
(0) работал 52 сек
(39) работал 13 сек
   Garykom
 
72 - 07.10.21 - 10:35
(71) быстрее только нечто внешнее
   Кирпич
 
73 - 07.10.21 - 10:36
А если данных мало, то и разницы не будет почти.
Тут один хрен будет перебор. Если не полный, то почти полный.
   Кирпич
 
74 - 07.10.21 - 10:37
Ибо начало и конец последовательности могут быть в любой ячейке
   Bigbro
 
75 - 07.10.21 - 10:43
+(66) упс, код не смотрел, так автор примерно это и сделал...(
   Garykom
 
76 - 07.10.21 - 10:50
(75) если массив уже отсортирован то найти разницу между кол-во элементов и значением последнего элемента - аля кол-во разрывов
далее если разрывов минимально есть смысл разбить весь массив на подмассивы по кол-ву разрывов
и проверить может эти подмассивы цельные
если цельные то получаем некий возможный выигрыш что перебирать уже сильно меньше

на практике можно получить проигрыш относительно одного полного последовательного сканирования - перебора
   ILM
 
77 - 07.10.21 - 10:50
Выбери все номера которых нет, отсортируй и получишь левые и правые границы.
   Garykom
 
78 - 07.10.21 - 10:50
(77) >Выбери все номера которых нет
полным перебором?
   Малыш Джон
 
79 - 07.10.21 - 10:51
Я конечно может чего не понимаю, но мне кажется скорость О(n) для алгоритма - это нормально. Даже если массив данных - миллионный.
Это кнечно, если имеется в виду практическое применение алгоритма.
   bolder
 
80 - 07.10.21 - 10:52
(71)Такой массив не удовлетворяет требованиям задачи.
   mistеr
 
81 - 07.10.21 - 10:53
(79) Миллионный нормально, а если трилионный — уже маловато.

Но ТС имхо просто хотел выпендриться.
   pechkin
 
82 - 07.10.21 - 10:54
алгоритм похож на сортировку слиянием (merge sort)
   bolder
 
83 - 07.10.21 - 10:55
(80) Ибо там по 10000 единичек,двоек и тп
   pechkin
 
84 - 07.10.21 - 10:55
(76) может быть 1 разрыв длиною в тыщу
   pechkin
 
85 - 07.10.21 - 10:57
надо объявить конкурс на лучшее решение задачи. как раньше была на удаление строк в тз
   Кирпич
 
86 - 07.10.21 - 10:57
(80) Ну покажи какой удовлетворяет
   Garykom
 
87 - 07.10.21 - 10:58
(85) по результатом которой выяснилось что всегда надо не удалять строки из ТЗ
создать новую ТЗ и копировать туда только нужные строки
   pechkin
 
88 - 07.10.21 - 11:01
(87) в 77 был хак с установить размер тз. он и выигрывал.
непосредственное удаление было конечно хуже всех
   МихаилМ
 
89 - 07.10.21 - 11:02
быстро обсчитать такие данные можно с помощью механизма решениеслау.
но тогда предстоит задача по подготовке самой слау.
   pechkin
 
90 - 07.10.21 - 11:03
(86) должны быть все разные числа
   rphosts
 
91 - 07.10.21 - 11:03
(12) и передача всего пакета данных в 1Е5 элементов каждый раз... любая рекурсия не сложно трансформируется в цикл.
   pechkin
 
92 - 07.10.21 - 11:04
(91) массивы по ссылке передаются
   Кирпич
 
93 - 07.10.21 - 11:05
(86) И с разными пробовал. Если не под отладкой запускать, то там вообще (0) за 5 сек всё перелопачивает, а (39) за 1 сек
так что нет смысла ломать голову
   rphosts
 
94 - 07.10.21 - 11:05
(92) тогда пофиг если рекурсия реально не глубока
   fisher
 
95 - 07.10.21 - 11:08
(40) Ниже чисто концептуальный блок для демонстрации идеи. Стопудово с ошибками (без ошибок я такое писать сходу не умею):
ТаблицаРезультата=Новый ТаблицаЗначений;
ТаблицаРезультата.Колонки.Добавить("НачалоДиапазона", "Число");
ТаблицаРезультата.Колонки.Добавить("КонецДиапазона", "Число");

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

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

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

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

    Если СтрокаДиапазона.КонецДиапазона < РазмерМассива - 1 Тогда
        СтрокаДиапазона = ТаблицаРезультата.Добавить();
        СтрокаДиапазона.НачалоДиапазона = КонецДиапазона + 1;
    КонецЕсли;
    
    // адаптация размера шага обхода

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

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

   pechkin
 
96 - 07.10.21 - 11:13
в худшем случае будет обход + 2-поиск для каждой строки
   Кирпич
 
97 - 07.10.21 - 11:13
И там не может быть без полного перебора. Есть полный перебор и полный перебор с помощью ухищрений и рекурсии.
   pechkin
 
98 - 07.10.21 - 11:13
(97) в худшем случае конечно. но расчет на то что таких случаев бывает мало
   fisher
 
99 - 07.10.21 - 11:16
(95) Что-то я затупил насчет ОбщейНепрерывности. Оно же и так все суммарно непрерывно :) Достаточно количества блоков для вычисления среднего размера непрерывного блока.
   fisher
 
100 - 07.10.21 - 11:24
Оптимизация размера шага обхода, так сказать, неоптимальна для краевых случаев, но дальше понятно куда оптимизации прикручивать.
  1  2   

Список тем форума
 
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.