Как ускорить логику цикла? [for experts]

@alexbmd · Регистрация: 03.06.2013

Студворк — интернет-сервис помощи студентам

Приветсвую.
Есть рабочий код для простой задачи. На входе имеем начало и конец отрезкОВ надо определить какие области эти отрезки НЕ перекрыли. Грубо говоря какие доски забора остались НЕ покрашены.
Например

C
1
2
3
4
5
6
7
8
9
На входе:
10 //длина забора
2 //сколько отрезков
1 4 //начало конец отрезка
5 6 //начало конец отрезка
На выходе:
0 1
4 5
6 10

Вот сама программа

Кликните здесь для просмотра всего текста

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
 
int main()
{
    int L, start = -1, count = 0;
    scanf("%d", &L);
    unsigned int *fence = (int *)calloc((L >> 5) + 1, sizeof(int)); //set memory to 0
    if (!fence) perror("calloc failed");
 
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        int st; //starting point
        int ed; //ending point
        scanf("%d%d", &st, &ed);
        
        // for (int i = st; i < ed; i++) fence[i] = 1;
        for (int i = st; i < ed; i++) fence[i>>5] |= (1 << (i & 31));
 
    }
    
    for (int i = 0; i < L; i++) {
 
        if (!fence[i>>5] && ((i + 32) < L)) {
            if (count == 0) {start = i; printf ("%d ",i);}
            count += 32; i += 31; continue;
        }
        else {
 
            // if ((fence[i] || i+1 == L) && count > 0)
            if (fence[i>>5] & (1 << (i & 31))) {
                if (count > 0) {printf ("%d\n",start+count); count = 0;}
            }
            else {
                if (count == 0) {start = i; printf ("%d ",i);}
                count++;
            }
        }
    }
    
    if (count > 0) printf ("%d\n",start+count);
    if (start < 0) puts("All painted");
    free (fence);
 
    return 0;
}

//битовое расположение используется для уменьшения памяти (отведенно максимум 2Гб для нашей задачи) и (надеюсь) увеличения скорости

Но стоит задача его "ускорить". Т.к. например с такими входными данными этот код делается неприемлимо долго

Кликните здесь для просмотра всего текста

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
2000000000 //Длина
72 //Отрезки
51 57
566 4234
598149 834729
5122 6160
17 46
165271503 259311575
288436131 1932691397
75 78
343 393
41 45
204 479
74 92
207 490
49 56
964644464 1887812645
136 420
429742458 1053501121
195 393
232 1608
184 6763
13 33
60169371 1162580884
774423404 797664100
1381580035 1668522412
190444 284746
112880052 1389027745
196 279
117760 859558
121381 236758
40 83
51 74
4048 6191
32 82
1 65
37 148
0 73
591646 893422
224008 649271
3150 8259
951966787 1627123054
318604 604539
81 97
781864601 1390933683
17 124
1030908877 1796833002
39 45
82739 363091
2571 3239
156 333
4930 7479
996706325 1268325988
19 90
26667 108371
52581129 803126065
1833231690 1908070559
783093028 807124796
154115 347846
1731 6452
12 78
3 33
462351 1805485861
271 460
1282262829 1424278575
5787 8055
3759 4011
87992 288855
245938 797316
3128 7514
42 80
398695717 864069801
43 44
1223 3675

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

а чтоб программа быстро крутилась) решить данную задачу ?

@Renji · 25.01.2021, 21:15

Сообщение от TheCalligrapher

На большом тесте выдает {0,0} как некрашеный. Неаккуратненько..

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

@alexbmd · 25.01.2021, 21:16 **[ТС]**

господа всем спасибо - переварю всё написанное

PS: у кого есть свободная минутка - а если усложнить чуть задачу и использовать чистый Си ?

@TheCalligrapher · 26.01.2021, 00:59

Сообщение от alexbmd

у кого есть свободная минутка - а если усложнить чуть задачу и использовать чистый Си ?

Единственный существенный элемент C++ в этих алгоритмах - std::sort, который в лоб заменяется на qsort

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Point 
{ 
  int x, delta;
} Point;
 
int cmp_points(const void *p1, const void *p2)
{
  const Point *pnt1 = p1, *pnt2 = p2;
  return (pnt1->x > pnt2->x) - (pnt1->x < pnt2->x);
}
 
int main(void)
{
  int length = 0;
  scanf("%d", &length);
 
  unsigned n_segments = 0;
  scanf("%u", &n_segments);
 
  unsigned n_points = n_segments * 2 + 1;
  Point *points = malloc(n_points * sizeof *points);
 
  unsigned i_point = 0;
 
  while (i_point < n_segments * 2)
  {
    int xl = 0, xr = 0;
    scanf("%d%d", &xl, &xr);
    points[i_point++] = (Point) { xl, +1 };
    points[i_point++] = (Point) { xr, -1 };
  }
 
  points[i_point] = (Point) { length, +1 };
 
  qsort(points, n_points, sizeof *points, cmp_points);
 
  int n_coverage = 0;
  int prev_x = 0;
 
  for (i_point = 0; i_point < n_points; ++i_point)
  {
    if (n_coverage == 0 && prev_x != points[i_point].x)
      printf("%d %d\n", prev_x, points[i_point].x);
 
    prev_x = points[i_point].x;
    n_coverage += points[i_point].delta;
  }
 
  free(points);
}

@XLAT · 26.01.2021, 03:52

Сообщение от alexbmd

Как ускорить логику цикла? [for experts]

мой дизайн:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <map>
 
typedef int T;
 
///----------------------------------------------------------------------------|
/// Старт.
///----------------------------------------------------------------------------:
int main()
{
    T n, l; std::cin >> l >> n;
    std::map<T, T> fence;
 
    for(T i = 0; i < n; ++i)
    {   T s; std::cin >> s; fence[s]++;
             std::cin >> s; fence[s]--;
    }
                 
    T    cnt   = 1;
    bool intro = true,
         all   = true;
                 fence[l]++;
                 fence[0]--;
 
    for(auto& [i, val] : fence)
    {   cnt += val;
 
             if(0 == cnt &&  intro){   intro = false; std::cout << i << ' ' ; all = false;}
        else if(0 <  cnt && !intro){   intro = true ; std::cout << i << '\n';             }
    }
    if(all) std::cout << "All painted";
}

GRAFFITI ON THE FENCE
100%

@alexbmd · 27.01.2021, 19:45 **[ТС]**

посидел еще поработал над свои дизайном "в лоб" (ради практики и интереса)... изменил/упростил логику цикла и на 2 млрд элементов смог улучшить время на 1 секунду , с 7 до 6 секунд

на этом думаю можно остановиться, врядли кто сможет сделать еще лучше (а надо лучше)...

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

всем спасибо за подсказки и за ваше время

Не по теме:

я не программист и даже не учусь на программиста. это моё хоби. не судите строго

@SmallEvil · 27.01.2021, 19:52

Сообщение от alexbmd

на 2 млрд элементов

количество отрезков ?

Добавлено через 3 минуты

Сообщение от alexbmd

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

Скопировать код и протестить 5 минут,

Как минимум три запустится, ну да еще стандарт с++ 11+ желательно.

@alexbmd · 27.01.2021, 20:13 **[ТС]**

Сообщение от SmallEvil

количество отрезков ?

Кликните здесь для просмотра всего текста

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
2000000000 //длина
/* отрезки: */
51 57
566 4234
598149 834729
5122 6160
17 46
165271503 259311575
288436131 1932691397
75 78
343 393
41 45
204 479
74 92
207 490
49 56
964644464 1887812645
136 420
429742458 1053501121
195 393
232 1608
184 6763
13 33
60169371 1162580884
774423404 797664100
1381580035 1668522412
190444 284746
112880052 1389027745
196 279
117760 859558
121381 236758
40 83
51 74
4048 6191
32 82
1 65
37 148
0 73
591646 893422
224008 649271
3150 8259
951966787 1627123054
318604 604539
81 97
781864601 1390933683
17 124
1030908877 1796833002
39 45
82739 363091
2571 3239
156 333
4930 7479
996706325 1268325988
19 90
26667 108371
52581129 803126065
1833231690 1908070559
783093028 807124796
154115 347846
1731 6452
12 78
3 33
462351 1805485861
271 460
1282262829 1424278575
5787 8055
3759 4011
87992 288855
245938 797316
3128 7514
42 80
398695717 864069801
43 44
1223 3675
8259 26667
1932691397 2000000000

Сообщение от SmallEvil

Скопировать код и протестить 5 минут

я не сомневаюсь что у вас работает , я хочу вначале сам подумать, своей головой

@SmallEvil · 27.01.2021, 20:36

alexbmd, тогда могу лишь пожелать удачи, и заниматься такими вещами на свежую голову.

@Folian · 28.01.2021, 18:45

Может как-то так еще, без оптимизации, в качестве идеи, что-то вроде std::set:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <vector>
#include <fstream>
 
enum { BEGIN, END };
 
struct Node
{
    bool kind;
    int pos;
    Node* next;
};
 
struct MyList
{
    Node* head;
    Node* it;
 
    void add_segment(Node* A, Node* B)
    {
        it = head;
        Node* temp = nullptr;
 
        while(it->next && it->next->pos < A->pos) it = it->next;
 
        temp = it->next;
        it->next = ((it->next->kind) ? B : A );
 
        if(it->next->kind)
        {
            it->next = B;
        }
        else
        {
            it->next = A;
            it = it->next;
        }
 
        while(temp->next && temp->pos < B->pos) temp = temp->next;
        if(temp->kind)
        {
            it->next = temp;
        }
        else
        {
            if(B->pos == temp->pos)
            {
                std::cout << "in";
                it->next = temp->next;
            }
            else
            {
                it->next->next = temp;
            }
        }
    }
 
    void show()
    {
        it = head->next;
        while(it->next)
        {
            if(it->kind) std::cout << "\n";
            std::cout << it->pos << " ";
            it = it->next;
        }
    }
};
 
int main()
{
    int len;
    int n;
 
    std::ifstream file("fence_input1.txt");
 
    if(file.is_open())
    {
        //  std::cin >> len >> n;
        file >> len >> n;
 
        std::vector<std::pair<Node, Node>> node_list(n);
 
        Node B_end = { END, len + 1, nullptr };
        Node B_beg = { BEGIN, len, &B_end };
        Node A_end = { END, 0, &B_beg };
        Node A_beg = { BEGIN, -1, &A_end };
 
        MyList Fence;
        Fence.head = &A_beg;
 
        for(int i=0; i<n; ++i)
        {
            node_list[i].first.kind = BEGIN;
            node_list[i].second.kind = END;
            node_list[i].first.next = &node_list[i].second;
            node_list[i].second.next = nullptr;
 
            //  std::cin >> node_list[i].first.pos >> node_list[i].second.pos;
            file >> node_list[i].first.pos >> node_list[i].second.pos;
 
//          std::cout << "\n" << node_list[i].first.pos << " : " << node_list[i].second.pos;
 
            Fence.add_segment(&node_list[i].first, &node_list[i].second);
        }
 
        std::cout << "\n\n";
        Fence.show();
 
        file.close();
    }
 
    return 0;
}

@TheCalligrapher · 28.01.2021, 19:18

Сообщение от Folian

Может как-то так еще, без оптимизации, в качестве идеи, что-то вроде std::set:

В off-lline задаче всегда эффективнее будет сначала накопить все входные данные, а затем отсортировать их, чем поддерживать данные в отсортированном виде "на лету".

@XLAT · 28.01.2021, 19:56

Сообщение от Folian

в качестве идеи

можете проверить свою идею здесь в валидаторе:
https://www.codingame.com/trai... -the-fence

@TheCalligrapher · 28.01.2021, 20:09

Сообщение от XLAT

можете проверить свою идею здесь в валидаторе:
https://www.codingame.com/trai... -the-fence

Только там еще надо уметь "All painted" выводить, чего здесь в условии упомянуть "забыли".

@XLAT · 28.01.2021, 20:22

Сообщение от TheCalligrapher

Только там еще надо уметь "All painted" выводить

ваш #23 во французской обработке:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdlib.h>
#include <stdio.h>
// -------------------------------------------------------
typedef struct
{   int a, b;
} segment;
 
segment segments[101];
int f(const void * ss1, const void * ss2)
{   const segment *s1 = (const segment *)ss1;
    const segment *s2 = (const segment *)ss2;
    return s1->a - s2->a;
}
// -------------------------------------------------------
main()
{   int L,N;
    scanf("%d%d", &L,&N);
    for (int i = 0; i < N; i++)
    {   scanf("%d%d", &segments[i].a, &segments[i].b );
    }
    qsort(segments, N, sizeof(segment), f);
    segments[N].a = segments[N].b = L;
 
    int position = 0;
    int unpainted = 0;
 
    for (int i = 0 ; i <= N ; i++ )
    {   if (segments[i].a > position )
        {   printf("%d %d\n", position, segments[i].a );
            unpainted++;
        }
        if ( position < segments[i].b )
            position = segments[i].b;
    }
    if (unpainted==0)
        printf("All painted");
}

@Folian · 28.01.2021, 20:23

Сообщение от XLAT

можете проверить свою идею здесь в валидаторе:

Вот оно откуда, значит

@TheCalligrapher · 28.01.2021, 20:38

Не по теме:

Сообщение от XLAT

ваш #23 во французской обработке:

Не вижу, как это связано с моим #23, и не понимаю, чего тут французского.

@XLAT · 28.01.2021, 20:41

Сообщение от TheCalligrapher

не понимаю

это не обязательно

@alexbmd · 29.01.2021, 13:14 **[ТС]**

Приветсвую.

в своей логике по работе с отрезками упёрся в qsort точне что он не сортирует двумерный массив.

я в своей логике использую двумерный массив для хранения начала и конца отрезка. и всё работает хорошо если отрезки отсортированны по началу. но немогу передать свой НЕ отсортированный двумерный массив qsort-у (по понятным причинам)

как то можно в Си выкрутится из этой ситуации ?

@TheCalligrapher · 29.01.2021, 13:19

Сообщение от alexbmd

но немогу передать свой НЕ отсортированный двумерный массив qsort-у

"Немогу" (sic)? Надо себя заставлять.

Сообщение от alexbmd

(по понятным причинам)

Никаких "понятных причин" я тут не вижу. О чем речь вообще?

@alexbmd · 29.01.2021, 14:52 **[ТС]**

кажется туплю.. сейчас подумаю еще..

Добавлено через 1 час 31 минуту
TheCalligrapher,
да, в чём туплю я понял, но без интернета фиг бы я правильно написал компоратор (ааар почему моя голова сама не додумывается до всех этих приведений типа, разименовываний и пр.)...
вроде лёд тронулся... щяз чуть подшлифую и буду проверять на инпут дате...

хотел вас спросить почему все использую разный вариант ретурна (если они вроде эквивалентны) ?

return (arg1 > arg2) - (arg1 < arg2);
return arg1 - arg2;

@Folian · 29.01.2021, 16:12

Сообщение от alexbmd

все использую разный вариант ретурна (если они вроде эквивалентны) ?

компаратор должен вернуть int, отсюда может происходить всякое.

Новые блоги и статьи Все статьи Все блоги /
Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .

@alexbmd 61 / 5 / 1 Регистрация: 03.06.2013 Сообщений: 355 Записей в блоге: 3
	25.01.2021, 21:16 [ТС]
	господа всем спасибо - переварю всё написанное PS: у кого есть свободная минутка - а если усложнить чуть задачу и использовать чистый Си ? 0

@alexbmd 61 / 5 / 1 Регистрация: 03.06.2013 Сообщений: 355 Записей в блоге: 3
	27.01.2021, 19:45 [ТС]
	посидел еще поработал над свои дизайном "в лоб" (ради практики и интереса)... изменил/упростил логику цикла и на 2 млрд элементов смог улучшить время на 1 секунду , с 7 до 6 секунд на этом думаю можно остановиться, врядли кто сможет сделать еще лучше (а надо лучше)... приступаю за обдумывании логики с отрезками (ваши не смотрел) потом посматрю на чьи моё похоже, если заработает конечно всем спасибо за подсказки и за ваше время Не по теме: я не программист и даже не учусь на программиста. это моё хоби. не судите строго 0

@SmallEvil 4086 / 2975 / 813 Регистрация: 29.06.2020 Сообщений: 11,000
	27.01.2021, 20:36
	alexbmd, тогда могу лишь пожелать удачи, и заниматься такими вещами на свежую голову. 0

@alexbmd 61 / 5 / 1 Регистрация: 03.06.2013 Сообщений: 355 Записей в блоге: 3
	29.01.2021, 13:14 [ТС]
	Приветсвую. в своей логике по работе с отрезками упёрся в `qsort` точне что он не сортирует двумерный массив. я в своей логике использую двумерный массив для хранения начала и конца отрезка. и всё работает хорошо если отрезки отсортированны по началу. но немогу передать свой НЕ отсортированный двумерный массив qsort-у (по понятным причинам) как то можно в Си выкрутится из этой ситуации ? 0

@alexbmd 61 / 5 / 1 Регистрация: 03.06.2013 Сообщений: 355 Записей в блоге: 3
	29.01.2021, 14:52 [ТС]
	кажется туплю.. сейчас подумаю еще.. Добавлено через 1 час 31 минуту TheCalligrapher, да, в чём туплю я понял, но без интернета фиг бы я правильно написал компоратор (ааар почему моя голова сама не додумывается до всех этих приведений типа, разименовываний и пр.)... вроде лёд тронулся... щяз чуть подшлифую и буду проверять на инпут дате... хотел вас спросить почему все использую разный вариант ретурна (если они вроде эквивалентны) ? return (arg1 > arg2) - (arg1 < arg2); return arg1 - arg2; 0