1 | ||||||||||||||||
Как ускорить логику цикла? [for experts]25.01.2021, 16:21. Показов 4574. Ответов 62
Приветсвую.
Есть рабочий код для простой задачи. На входе имеем начало и конец отрезкОВ надо определить какие области эти отрезки НЕ перекрыли. Грубо говоря какие доски забора остались НЕ покрашены. Например
Кликните здесь для просмотра всего текста
//битовое расположение используется для уменьшения памяти (отведенно максимум 2Гб для нашей задачи) и (надеюсь) увеличения скорости Но стоит задача его "ускорить". Т.к. например с такими входными данными этот код делается неприемлимо долго Кликните здесь для просмотра всего текста
Жду от уважаемого сообщества один из двух варианта ответа А) как еще можно ускорить данную логику ? Б) если существенно ускорения выше обозначенной логики не возможно, подскажите алгоритм (словесный код) как можно быстро (всмысле не написать код быстро а чтоб программа быстро крутилась) решить данную задачу ?
0
|
25.01.2021, 16:21 | |
Ответы с готовыми решениями:
62
Как ускорить работу цикла? Как ускорить выполнение цикла Как ускорить выполнение цикла на Update Можно ли как нибудь ускорить работу цикла for? |
2817 / 2325 / 703
Регистрация: 29.06.2020
Сообщений: 8,577
|
|
25.01.2021, 16:34 | 2 |
На больших объемах битовые операции сильно загрузят проц.
Никогда не писали кодирование файлов ?
0
|
2782 / 1935 / 570
Регистрация: 05.06.2014
Сообщений: 5,600
|
|
25.01.2021, 16:37 | 3 |
Отсортируйте список отрезков по их левому концу. Повторяйте до посинения цикл "Пока отрезок А пересекает идущий за ним отрезок Б, объединяй отрезки. Иначе переходи к Б и начинай сначала". На выходе получите массив не пересекающихся отрезков, отсортированных по их расположению на заборе. Оставшаяся часть элементарна.
1
|
2817 / 2325 / 703
Регистрация: 29.06.2020
Сообщений: 8,577
|
|
25.01.2021, 16:41 | 5 |
Если отрезки идут упорядоченно , и ввод не с клавиатуры,не то и массив не нужен.
пример посл: 20 3 1-5 7-9 19-20
0
|
25.01.2021, 16:51 [ТС] | 6 |
SmallEvil, отрезки идут в перемешку... возможно и перекрытие и накрытие
Добавлено через 3 минуты это всмысле если правый край больше ? а как быть если А 5-10 Б 8-15 ? я понимаю что надо объеденить до 5-15 но я про то что вроде как одного вашего условия нехватает для всех случаев или я туплю
0
|
6091 / 3449 / 1402
Регистрация: 07.02.2019
Сообщений: 8,768
|
|
25.01.2021, 16:57 | 7 |
alexbmd, похожая задача(одна из многих на отрезки), описание решения там есть, нужно только подправить алгоритм.
Игнорируйте отрезок
2
|
2817 / 2325 / 703
Регистрация: 29.06.2020
Сообщений: 8,577
|
|||||||||||
25.01.2021, 17:49 | 8 | ||||||||||
map сразу сортирует, что плюс Добавлено через 1 минуту минус что проверяет абсолютно все интервалы, можно еще доработать Добавлено через 2 минуты ммда, надо доработать ... Добавлено через 7 минут проблема только в подпоследовательностях например , ss<<10<<endl<<3<<endl<<"5 6"<<endl<<"1 2"<<endl<<"4 9"; 5 6 входит в 4 9, с кандачка не идет. подумать надо Добавлено через 10 минут при добавлении в map придется таки объединять последовательности ... исправил обьединением последовательносте при формировании map прошу протестировать Кликните здесь для просмотра всего текста
0
|
Вездепух
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,052
|
|
25.01.2021, 18:04 | 9 |
Бессмысленное занятие. Любой подход, пытающийся буквально моделировать "забор" и его "покраску", является тупиковым.
Однако если вы в какой-то другое задаче вам понадобилось заполнять диапазон в битовом массиве единицами, то естественный способ "ускорения цикла" очевиден: выполнять заполнение целыми словами (unsigned) -1 в тех частях диапазона, где "закрашено" целое слово.Классический off-line алгоритм вам уже подсказал Renji. Ваша задача - как раз off-line. Для on-line задачи существуют структуры данных вроде interval tree, которые делают именно то, что вам нужно.
0
|
2782 / 1935 / 570
Регистрация: 05.06.2014
Сообщений: 5,600
|
|
25.01.2021, 19:10 | 10 |
Это в смысле в отсортированном массиве отрезков А и Б следуют друг за другом. А пересекаются если левый конец Б попадает внутрь А.
0
|
2817 / 2325 / 703
Регистрация: 29.06.2020
Сообщений: 8,577
|
||||||
25.01.2021, 20:33 | 11 | |||||
еще бы был правильный ответ на его пример, ...
Добавлено через 6 минут оказалось проще чем я думал, сначала намудрил три тома Добавлено через 28 минут результат на приведенном файле, в 1 посте код: Кликните здесь для просмотра всего текста
0
|
25.01.2021, 20:39 [ТС] | 12 |
блин 502 ошибка похерила мой комент пишу вкратце-
ну на малых инпут массивах всё отлично а так да согласен, если не тупиковый то не разумно затратный как минимум. НО как ни страно у меня проблемный не первый цикл (красящий) а второй (подсчитывающий) и это несмотря даже на ускорение ввиде перебора целыми int-ами, и ни как не могу понять почему он это делает так медленно :/ остальные алгоритмы посматрю спасибо PS: Renji подсказал но я не понял как одним условием "Пока отрезок А пересекает идущий за ним отрезок Б, объединяй отрезки" покрыть все возможные варианты
0
|
2817 / 2325 / 703
Регистрация: 29.06.2020
Сообщений: 8,577
|
|
25.01.2021, 20:42 | 13 |
это только для отсортированных отрезков
мой код ("вроде") рабочий, только последний
0
|
2782 / 1935 / 570
Регистрация: 05.06.2014
Сообщений: 5,600
|
|
25.01.2021, 20:43 | 14 |
Пока Аmin<=Бmin<=Аmax, сливать А и Б в Amin,max(Аmax,Бmax). Ну и как выше напомнили, отрезки должны быть отсортированы по значению левого конца.
0
|
25.01.2021, 20:44 [ТС] | 15 |
они то следуют но левый край может равняться а может быть больше + правый может иметь три варианта... НО даже если этосделать (хотя я не доконца понял что вы имеете виду) то это первая часть задачи если я правильно понял - окрашивание. моё хоть и "в лоб" но затык всёже во второй части - подсчёт
0
|
1352 / 851 / 365
Регистрация: 26.02.2015
Сообщений: 3,799
|
|
25.01.2021, 20:44 | 16 |
Первый отрезок в массиве лежит такой (после сортировки отрезков): 1 4 Второй отрезок в массиве лежит такой (после сортировки отрезков): 3 79 Ты можешь сделать отрезок новый: 1 79 сразу и проверять со следующим отрезком.
0
|
Вездепух
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,052
|
|
25.01.2021, 20:48 | 17 |
Существенно более простая реализация получится, если хранить в отсортированном списке не
отрезки , а индивидуальные концы отрезков, с одной координатой и пометкой левый-правый.После этого достаточно пройтись по списку со счетчиком, делая +1 на каждом левом конце и -1 на каждом правом. Те диапазоны, на которых счетчик равен 0 - это не крашеные участки забора. Возможно это будет чуть менее эффективно по памяти...
0
|
2782 / 1935 / 570
Регистрация: 05.06.2014
Сообщений: 5,600
|
||||||
25.01.2021, 21:00 | 19 | |||||
Да Господи...
1
|
Вездепух
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,052
|
||||||
25.01.2021, 21:07 | 20 | |||||
Реализация через точки (особо не тестировал)
На большом тесте выдает {0,0} как некрашеный. Неаккуратненько..
0
|
25.01.2021, 21:07 | |
25.01.2021, 21:07 | |
Помогаю со студенческими работами здесь
20
Ускорить работу вложенного цикла for() C# Welcome to experts C++! Minsk.BelHard.vacancies: Java Experts, Team Lead, PM Как из цикла вывести данные для другого цикла? Program1.pas(7): Параметр цикла for в PascalABC.NET должен описываться в заголовке цикла. Как исправить? Как проверить логику и ОУ ? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |