Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.64/11: Рейтинг темы: голосов - 11, средняя оценка - 4.64
0 / 0 / 0
Регистрация: 09.06.2019
Сообщений: 35
1

Ускорение кода

10.08.2019, 12:51. Показов 2039. Ответов 4
Метки нет (Все метки)

Как ускорить код:

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
#include <iostream>
using namespace std;
 
 
 
int main(){
 
int n, q, c = 0;
 
cin >> n;
int a[n];
for(int i = 0; i < n; i++)
    cin >> a[i];
 
cin >> q;
int b[q];
for(int i = 0; i < q; i++)
    cin >> b[i];
 
for(int i = 0; i < q; i++){
  for(int w = 0; w < n; w++){
    if(b[i] == a[w])
        c++;
 
  }
    cout << c << endl;
    c = 0;
}
return 0;
}
Пример:
ввод
4
1 2 2 4
4
1 4 3 2
вывод
1
1
0
2
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.08.2019, 12:51
Ответы с готовыми решениями:

Ускорение кода
Ребят помогите ускорить код. Создаётся вектор на 100000001. Далее приходит n пар - начало и конец....

Многократное ускорение кода[литература]
Здравствуйте, я дилетант в ЯП C++ перешёл на него после достаточно долгого изучения C# с целью...

Ускорение
Здраствуйте, есть код: #include &lt;stdio.h&gt; #define MAX 1000010 long long h; int i, n,...

Ускорение алгоритма
Привет, всем! Помогите, пожалуйста, ускорить работу алгоритма. При вводе примерно вот таких чисел:...

4
6277 / 4261 / 2454
Регистрация: 18.12.2017
Сообщений: 13,286
10.08.2019, 14:10 2
kerb4k, сформулируйте условие задачи
0
221 / 148 / 79
Регистрация: 14.03.2016
Сообщений: 459
10.08.2019, 15:29 3
Вероятно, ТС'у, который решил, что всем все известно о его задаче, нужно найти количество одинаковых элементов в двух массивах, а поиск по O(sizeA * sizeB) его не устраивает. Ввиду отсутствия условия, первое, что мне пришло в голову для решения подобной задачи, это использовать set'ы. В таком случае сложность получиться как минимум O(sizeB * log(sizeA)).

Не претендую на самое быстрое и лучшее решение данной задачи, однако по моим измерениям, представленный мною способ работает примерно в 32 раза быстрее чем тот, который изначально предложил ТС.
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
#include <iostream> //cout
#include <set>      //multiset
#include <chrono>   //time
using namespace std;
 
//hold console window
int progEnd() { std::cout << "\nEND\n"; system("pause>nul"); return 0; }
 
//return random value in range [from, to]
int randInt(int from, int to) { return rand() % ( to - from + 1 ) + from; }
 
int main() {
    unsigned int simArr = 0, simSet = 0;
 
    size_t sizeA, sizeB;
 
    //set size
    sizeA = 50'000, sizeB = 100'000;
 
    //create arrays and multisets
    int *arrA = new int[sizeA];
    int *arrB = new int[sizeB];
    multiset<int> setA, setB;
 
    //messages about filling arrays
    cout << "Filling A..." << endl;
 
    //fill A array and multiset
    for(size_t i = 0; i < sizeA; i++) {
        int randValue = randInt(0, 1000);
        arrA[i] = randValue;
        setA.insert(randValue);
    }
 
    cout << "Filling B..." << endl;
 
    //fill B array and multiset
    for(size_t i = 0; i < sizeB; i++) {
        int randValue = randInt(0, 1000);
        arrB[i] = randValue;
        setB.insert(randValue);
    }
 
    cout << "Starting default array test..." << endl;
 
    //create time point
    auto startTest = chrono::high_resolution_clock::now();
    
    //begin numbers compair in array
    for(size_t i = 0; i < sizeA; i++)
        for(size_t j = 0; j < sizeB; j++)
            if(arrA[i] == arrB[j])
                simArr++;
 
    //create stop point
    auto endTest = chrono::high_resolution_clock::now();
 
    //calculate time
    chrono::duration<double> elapsedTime = endTest - startTest;
 
    //output info about elapsed time
    cout << "Default array search elapsed " << elapsedTime.count() << " seconds" << endl;
 
    cout << "Starting multiset test..." << endl;
    //create new start point
    startTest = chrono::high_resolution_clock::now();
 
    //begin search in set
    for(auto elB : setB)
        if(setA.find(elB) != setA.end())
            simSet++;
 
    //create new end point
    endTest = chrono::high_resolution_clock::now();
 
    //calculate time
    elapsedTime = endTest - startTest;
    
    //output info about elapsed time
    cout << "Multiset search elapsed " << elapsedTime.count() << " seconds" << endl;
 
    //erase all used memory by arrays
    delete arrA;
    delete arrB;
    return progEnd();
}
Добавлено через 24 минуты
А нет, ошибся я несколько. Сложность получиться более O(sizeB * log(sizeA)), однако это все равно будет много быстрые линейного поиска.
C++
1
2
3
4
5
6
7
8
9
10
//заменить это:
//begin search in set
    for(auto elB : setB)
        if(setA.find(elB) != setA.end())
            simSet++;
 
//на это:
//begin search in set
    for(auto elB : setB)
    simSet += setA.count(elB);
0
6 / 10 / 2
Регистрация: 08.08.2019
Сообщений: 63
12.08.2019, 10:08 4
Это Бинарный поиск-2
Решать, как не удивительно, надо через бинпоиск..
Я проверил наличие этого числа, нашел правый край таких чисел и левый. В питоне есть bisect - там удобнее.
Отметь, если помог чем-нибудь
0
812 / 500 / 210
Регистрация: 19.01.2019
Сообщений: 1,196
12.08.2019, 13:49 5
Лучший ответ Сообщение было отмечено kerb4k как решение

Решение

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
#include <iostream>
#include <map>
 
int main()
{
    int buff;
 
    size_t s1;
    std::cin >> s1;
    std::map<int, size_t> map;
    for (size_t i = 0; i < s1; ++i) {
        std::cin >> buff;
        ++map[buff];
    }
 
    size_t s2;
    std::cin >> s2;
    for (size_t i = 0; i < s2; ++i) {
        std::cin >> buff;
        std::cout << map[buff] << '\n';
    }
 
    return 0;
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.08.2019, 13:49

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Ускорение програмы на с++
Здраствуйте!Нужно ускорить программу по возможности. #include &lt;iostream&gt; #include &lt;vector&gt;...

Ускорение ввода
#include &lt;bits/stdc++.h&gt; #define ll long long using namespace std; bool ar; int main() { ...

Ускорение програмки
#include &lt;stdio.h&gt; #include &lt;string.h&gt; #include &lt;stdlib.h&gt; struct Tree { char s; ...

Ускорение алгоритмов
Имеется код, нужно его ускорить. (Помогите тупому!!!!!!!) #include &lt;stdio.h&gt; #include &lt;iostream&gt;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.