Два практически идентичных кода, но один почему-то работает медленней

@SaynorPRO · Регистрация: 05.10.2016

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

Почему мой код работает намного медленнее? Ведь по сути одно и то же!

Мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int ans = 0;
  set<int> check;
  for (set<int>::iterator it = val.begin(); it != val.end(); it++) { //val - сет
    for (int j = 0; j < k; j++) {
      check.insert(*it + a[j]); //a - вектор
    }
    for (set<int>::iterator it2 = b.begin(); it2 != b.end(); it2++) {//b - сет
      if (check.find(*it2) == check.end()) {
        ans--;
        break;
      }
    }
    ans++;
    check.clear();
  }

Чужой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
set<int> p2;
   int ans = 0;
   for (auto p : points) { //points  - сет
      p2.clear();
      for (int i=1; i<=k; i++) {
         p2.insert(p+s[i]); //s - вектор 
      }
      int j=1;
      bool vf = true;
      while (j<=n and vf) {
         vf = false;
         if (p2.find(b[j]) != p2.end()) { //b - вектор
            vf = true; 
         }
         j++;
      }
      ans += vf;
   }

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

@nmcf · 17.07.2017, 20:51

Только из-за замены vector на set?

@SaynorPRO · 17.07.2017, 21:10 **[ТС]**

nmcf, я тоже так подумал, хотя это и странно: не может же программа работать в два раза медленнее просто из-за того, что вектор сменили на сет. Я пробовал менять, результат тот же.

@nmcf · 17.07.2017, 21:28

Количество элементов одинаковое в обоих вариантах? Может, проблема вообще не здесь?

@SaynorPRO · 17.07.2017, 22:59 **[ТС]**

nmcf, ну конечно одинаковое. Сейчас скину полностью коды.

Чужой код:

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
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
   int   n, k;
   vector<int>    a, b;
   cin >> k >> n;
   a.assign(k+1, 0);
   for (int i=1; i<=k; i++) {
      cin >> a[i];
   }
   b.assign(n+1, 0);
   for (int i=1; i<=n; i++) {
      cin >> b[i];
   }
 
   vector<int> s(k+1, 0);
   for (int i=1; i<=k; i++) {
      s[i] = s[i-1] + a[i];
   }
 
   set<int> points;
   for (int j=1; j<=k; j++) {
      points.insert(b[1] - s[j]);    
   }
 
   set<int> p2;
   int ans = 0;
   for (auto p : points) {
      p2.clear();
      for (int i=1; i<=k; i++) {
         p2.insert(p+s[i]);
      }
      int j=1;
      bool vf = true;
      while (j<=n and vf) {
         vf = false;
         if (p2.find(b[j]) != p2.end()) {
            vf = true; 
         }
         j++;
      }
      ans += vf;
   }
 
   cout << ans << endl;
 
   return 0;
}

Мой код:

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
#include <bits/stdc++.h>
 
using namespace std;
 
 
vector<int> a;
set<int> val, b;
int k, n;
 
int main () {
  cin >> k >> n;
  a.resize(k, 0);
  cin >> a[0];
  for (int i = 1; i < k; i++) {
    cin >> a[i];
    a[i] += a[i-1];
  }
  for (int i = 0; i < n; i++) {
    int tmp;
    cin >> tmp;
    b.insert(tmp);
  }
  for (set<int>::iterator it = b.begin(); it != b.end(); it++) {
    for (int j = 0; j < k; j++) {
      val.insert(*it - a[j]);
    }
  }
  int ans = 0;
  set<int> check;
  for (set<int>::iterator it = val.begin(); it != val.end(); it++) {
    for (int j = 0; j < k; j++) {
      check.insert(*it + a[j]);
    }
    for (set<int>::iterator it2 = b.begin(); it2 != b.end(); it2++) {
      if (check.find(*it2) == check.end()) {
        ans--;
        break;
      }
    }
    ans++;
    check.clear();
  }
  cout << ans << endl;
  return 0;
}

Добавлено через 1 час 22 минуты
Проблема решена. Вот тут наши программы различались.

C++
1
2
3
4
set<int> points;
   for (int j=1; j<=k; j++) {
      points.insert(b[1] - s[j]);    
   }

C++
1
2
3
4
5
for (set<int>::iterator it = b.begin(); it != b.end(); it++) {
    for (int j = 0; j < k; j++) {
      val.insert(*it - a[j]);
    }
  }

Здесь нужен был один цикл, я недоглядел в задаче.

Новые блоги и статьи Все статьи Все блоги /
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	17.07.2017, 20:51
	Только из-за замены vector на set? 0

@SaynorPRO 11 / 11 / 5 Регистрация: 05.10.2016 Сообщений: 122
	17.07.2017, 21:10 [ТС]
	nmcf, я тоже так подумал, хотя это и странно: не может же программа работать в два раза медленнее просто из-за того, что вектор сменили на сет. Я пробовал менять, результат тот же. 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	17.07.2017, 21:28
	Количество элементов одинаковое в обоих вариантах? Может, проблема вообще не здесь? 0