Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Прекращается работа программы При запуске в Visual Studio 2019 программа не работает и появляется сообщение "Прекращена работа программы". Подскажите, пожалуйста, как исправить ошибку? #include<iostream> #include<stack>... https://www.cyberforum.ru/ cpp-beginners/ thread2489832.html Перебор элементов в массиве C++
Условие задачи: Написать отдельную функцию, которая принимает 2 параметра (char, int sum). Дано: 3 * (21 + 17)) / (3 - 1) + 43, если ошибок нет, функция должна вернуть значение 100, а если есть...
C++ Как сделать динамический массив глобальным https://www.cyberforum.ru/ cpp-beginners/ thread2489817.html
Нужно что бы создание, ввод и вывод были в разных функциях #include "pch.h" #include <iostream> using namespace std; int main(){ setlocale(LC_ALL,"Russian");
C++ Побитовые логические выражения https://www.cyberforum.ru/ cpp-beginners/ thread2489805.html
Пишу программу для побитовых логических операций. Приоритет ! = 4, ~ = 4, & = 3, ^ = 2, | = 1. Мои комментарии на русском. '=' показывает результат. Найденные проблемы: 1) x|y^z, это она...
C++ Можно ли так делать ?
Я пока что начинающий, поэтому хочу спросить, можно ли так делать ? #include<iostream> #include<cstdlib> using namespace std; int Factorial(int k) { if(k==1)
C++ Перегруженный оператор ввода Почему ошибка при попытке вывести результат сложения двух матриц? #include <iostream> using namespace std; class Matrix { private: https://www.cyberforum.ru/ cpp-beginners/ thread2489782.html
C++ C++ int to an array Здравствуйте ребята мне нужна ваша помощь по созданию программы, которая получает на вход три целых числа и возвращает true только тогда, когда произведение последних цифр двух введенных чисел равно... https://www.cyberforum.ru/ cpp-beginners/ thread2489726.html Как реализовать функцию? C++
Подскажите как организовать нижеприведенную функцию, чтобы при вызове в main а и b каждый раз генерировали новые числа, у меня она почему-то вообще не работает, не пойму что не так int rand(int a,...
C++ 1001. Обратный корень - Wrong Answer: 3 На Timus Online Judge мое решение не проходит задачу 1001 - Обратный корень. На 3-ем тесте пишет Wrong Answer Вот задача: 1001. Обратный корень Ограничение времени: 2.0 секунды Ограничение... https://www.cyberforum.ru/ cpp-beginners/ thread2489698.html C++ Указатель на константную строку и имя массива как указатель Изучаю C. У меня есть указатель на константную строку, и я хочу его изменить путем передачи в функцию. Это работает без проблем: #include <stdio.h> void incriment(char**); main() { https://www.cyberforum.ru/ cpp-beginners/ thread2489674.html
C++ Подскажите в чем причина предупреждения в функции
int click_F(int ch){ int a; if ((ch == 160) || (ch == 128) || (ch == 70) || (ch == 102)){ return a = 1;} return a;} вот что она пишет на это warning: 'a' may be used uninitialized in...
C++ Модуль ядра и драйвер устройства https://www.cyberforum.ru/ cpp-beginners/ thread2489637.html
Здравствуйте, чем отличается модуль ядра от драйвера устройства? Само понятие. Если я правильно понимаю то модуль ядра это более обширное понятие, а в определённой ситуации драйвер и является модулем...
221 / 148 / 79
Регистрация: 14.03.2016
Сообщений: 459
10.08.2019, 15:29 0

Ускорение кода - C++ - Ответ 13763288

10.08.2019, 15:29. Показов 2107. Ответов 4
Метки (Все метки)

Ответ

Вероятно, ТС'у, который решил, что всем все известно о его задаче, нужно найти количество одинаковых элементов в двух массивах, а поиск по 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);


Вернуться к обсуждению:
Ускорение кода C++
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.08.2019, 15:29
Готовые ответы и решения:

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

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

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

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

4
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.08.2019, 15:29

Ускорение програмы на с++
Здраствуйте!Нужно ускорить программу по возможности. #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;...

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