Как проверить вхождение элемента в массив эффективным образом?

@fanfuntik · Регистрация: 08.09.2018

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

Встала задача:
Даны два массива, элементы которых упорядочены по возрастанию (и зачем это дали?). Найти количество уникальных элементов, то есть, которые входят в один массив, но не входят в другой.

Пример
a[5] = {1,2,3,4,5,6}
b[6] = {3,4,5,6,7,8,9}
результатом будет 5 (1,2,7,8,9)

Сначала решил через множества:
нашел разность a-b; b-a; затем объединил их и получил количество уникальных элементов.

но вроде не пахнет эффективным решением, да и без массивов.. не думаю, что зачтут такую задачу..

Помогите с идеями, как подойти к задаче?)

Спасибо всем большое.

@stu4ent · 23.09.2018, 19:56

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

Ваш код вообще не выполняет поставленную задачу.

Решается добавлением пары строчек:

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
#include <iostream>
#include <algorithm>
 
int
count_unique_elements(int* a, size_t size_a, int* b, size_t size_b) {
    int counter = 0;
    
    for (int i = 0; i < size_a; i++) {
        if ((a[i] < b[0]) or (a[i] > b[size_b - 1])
                or (std::find(b, b + size_b, a[i]) == (b + size_b))) {
            counter++;
        }
    }
    
    return counter;
}
 
int main() {
    int a[] = {1,2,3,4,5,6};
    int b[] = {3,4,5,6,7,8,9};
    
    auto count1 = count_unique_elements(a, sizeof(a)/sizeof(int), b, sizeof(b)/sizeof(int));
    auto count2 = count_unique_elements(b, sizeof(b)/sizeof(int), a, sizeof(a)/sizeof(int));
    std::cout << (count1 + count2) << std::endl;
    
    return 0;
}

Croessmah · 23.09.2018, 20:27

stu4ent, я не зря отметил, что мой код это решает за линейное время, в отличие от Вашего.
Ну и для моего шаблона достаточно однонаправленных итераторов.

@New man · 23.09.2018, 21:47

zss, map же даёт nlogn.
n элементов массива * logn вставку.
Тут уже быстрее бинарным поиском без траты лишней памяти.

Вот запихнуть в unordered_map будет эффективно O(n+m) по скорости, O(min(n,m)) по памяти.

Добавлено через 7 минут
Croessmah, красиво.
Утянул на ideone к себе.

@stu4ent · 23.09.2018, 22:37

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

я не зря отметил, что мой код это решает за линейное время, в отличие от Вашего.

Если важно время, то можно воспользоваться стандартной функцией https://en.cppreference.com/w/... difference, а не строить "велосипеды"

C++
1
2
3
4
5
size_t
count_unique_elements(int* a, size_t size_a, int* b, size_t size_b) {
    std::vector<int> v(size_a + size_b);
    return std::set_symmetric_difference(a, a + size_a, b, b + size_b, v.begin()) - v.begin();
}

Croessmah · 23.09.2018, 22:45

stu4ent, она выполняет не ту работу, что требуется.

Она одинаковые элементы в одном последовательности запихнет как уникальные.
Кстати, этим и твой алгоритм страдает - он не выкидывает одинаковые элементы из последовательности.

@stu4ent · 23.09.2018, 22:49

По условию не сказано, что могут быть одинаковые элементы

.

Croessmah · 23.09.2018, 22:52

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>
 
size_t
count_unique_elements(int* a, size_t size_a, int* b, size_t size_b) {
    std::vector<int> v(size_a + size_b);
    return std::set_symmetric_difference(a, a + size_a, b, b + size_b, v.begin()) - v.begin();
}
 
int main() {
    int a[] = {1,1,1};
    int b[] = {1,2,};
    
    auto count = count_unique_elements(a, sizeof(a)/sizeof(int), b, sizeof(b)/sizeof(int));
    std::cout << count << std::endl;
    
    return 0;
}

http://rextester.com/NHIRQ6666
ответ: 3

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

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

По условию не сказано, что могут быть одинаковые элементы

Даны упорядоченные массивы. Никто не говорит, что элементы в каждом массиве уникальны.

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

Найти количество уникальных элементов, то есть, которые входят в один массив, но не входят в другой.

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

Croessmah · 23.09.2018, 22:56

Затестил алгоритмы:

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <chrono>
#include <random>
#include <stdexcept>
#include <iterator>
 
void stu4ent_unique_difference(int* a, size_t size_a, int* b, size_t size_b, std::vector<int> & result) {   
    for (size_t i = 0; i < size_a; i++) {
        if ((a[i] < b[0]) or (a[i] > b[size_b - 1])
                or (std::find(b, b + size_b, a[i]) == (b + size_b))) {
            result.push_back(a[i]);
        }
    }
}
 
 
template<typename ForwardIterator>
ForwardIterator skip_equal(ForwardIterator first, ForwardIterator last)
{    
    if (first != last) {
        ForwardIterator prev = first++;
        while (first != last && *first == *prev) {
            ++prev;
            ++first;
        }
    }
    return first;
}
 
template<typename ForwardIterator, typename OutputIterator>
OutputIterator croessmah_unique_difference(
    ForwardIterator f_begin, ForwardIterator f_end, 
    ForwardIterator s_begin, ForwardIterator s_end, 
    OutputIterator out)
{    
    while (f_begin != f_end && s_begin != s_end) {
        if (*f_begin < *s_begin) {
            *out = *f_begin;
            f_begin = skip_equal(f_begin, f_end);
        } else if (*s_begin < *f_begin) {
            *out = *s_begin;
            s_begin = skip_equal(s_begin, s_end);
        } else {
            f_begin = skip_equal(f_begin, f_end);
            s_begin = skip_equal(s_begin, s_end);
        }
    }
    while (f_begin != f_end) {
        *out = *f_begin;
        f_begin = skip_equal(f_begin, f_end);
    }
    while (s_begin != s_end) {
        *out = *s_begin;
        s_begin = skip_equal(s_begin, s_end);
    }
    return out;
}
 
 
std::vector<int> generate_vector(size_t count)
{
    static std::mt19937 gen/*(std::chrono::system_clock::now().time_since_epoch().count())*/;
    std::uniform_int_distribution<int> dist(0, 100000);
    std::vector<int> result(count);
    for (auto & e: result) {
        e = dist(gen);
    }
    return result;
}
 
 
int main() {
    std::vector<int> first = generate_vector(1000000);
    std::vector<int> second = generate_vector(1000000);
    std::sort(first.begin(), first.end());
    std::sort(second.begin(), second.end());
 
    std::vector<int> result;
    result.reserve(first.size() + second.size());
    std::cout << "start..." << std::endl;
    auto start_tp = std::chrono::high_resolution_clock::now();
#ifndef CROESSMAH
    stu4ent_unique_difference(
        first.data(), first.size(), 
        second.data(), second.size(), 
        result);
    stu4ent_unique_difference(
        second.data(), second.size(), 
        first.data(), first.size(), 
        result);
#else
    croessmah_unique_difference(
        first.begin(), first.end(), 
        second.begin(), second.end(), 
        std::back_inserter(result));
#endif
    auto diff_time = std::chrono::high_resolution_clock::now() - start_tp;
    std::cout << "finish" << std::endl;
 
    std::cout << "unique before erase: " << result.size();
    std::sort(result.begin(), result.end());
    result.erase(std::unique(result.begin(), result.end()), result.end());
    
    std::cout << "\nunique: " << result.size()
              << "\nexecution time: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(diff_time).count() 
              << " ms" << std::endl;
    return 0;
}

g++ -o main -std=c++14 -O3 main.cpp
...
execution time: 359893 ms

g++ -o main -std=c++14 -O3 -DCROESSMAH main.cpp
...
execution time: 2 ms

Как проверить вхождение элемента в массив эффективным образом?

@stu4ent · 23.09.2018, 22:56

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

Даны упорядоченные массивы. Никто не говорит, что элементы в каждом массиве уникальны.

Ели нужны уникальные, то вот:

C++
1
2
3
4
5
6
7
size_t
count_unique_elements(int* a, size_t size_a, int* b, size_t size_b) {
    std::set<int> s1(a, a + size_a);
    std::set<int> s2(b, b + size_b);
    std::vector<int> v(size_a + size_b);
    return std::set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), v.begin()) - v.begin();
}

Такая версия немного медленнее, но зато реализуется в N раз быстрее.

Croessmah · 23.09.2018, 23:01

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

Всё равно быстрее твоей версии, можешь померить с помощью clock

Замерил:

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <chrono>
#include <random>
#include <stdexcept>
#include <iterator>
#include <set>
 
size_t
stu4ent_unique_difference(int* a, size_t size_a, int* b, size_t size_b) {
    std::set<int> s1(a, a + size_a);
    std::set<int> s2(b, b + size_b);
    std::vector<int> v(size_a + size_b);
    return std::set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), v.begin()) - v.begin();
}
 
template<typename ForwardIterator>
ForwardIterator skip_equal(ForwardIterator first, ForwardIterator last)
{    
    if (first != last) {
        ForwardIterator prev = first++;
        while (first != last && *first == *prev) {
            ++prev;
            ++first;
        }
    }
    return first;
}
 
template<typename ForwardIterator, typename OutputIterator>
OutputIterator croessmah_unique_difference(
    ForwardIterator f_begin, ForwardIterator f_end, 
    ForwardIterator s_begin, ForwardIterator s_end, 
    OutputIterator out)
{    
    while (f_begin != f_end && s_begin != s_end) {
        if (*f_begin < *s_begin) {
            *out = *f_begin;
            f_begin = skip_equal(f_begin, f_end);
        } else if (*s_begin < *f_begin) {
            *out = *s_begin;
            s_begin = skip_equal(s_begin, s_end);
        } else {
            f_begin = skip_equal(f_begin, f_end);
            s_begin = skip_equal(s_begin, s_end);
        }
    }
    while (f_begin != f_end) {
        *out = *f_begin;
        f_begin = skip_equal(f_begin, f_end);
    }
    while (s_begin != s_end) {
        *out = *s_begin;
        s_begin = skip_equal(s_begin, s_end);
    }
    return out;
}
 
 
std::vector<int> generate_vector(size_t count)
{
    static std::mt19937 gen/*(std::chrono::system_clock::now().time_since_epoch().count())*/;
    std::uniform_int_distribution<int> dist(0, 100000);
    std::vector<int> result(count);
    for (auto & e: result) {
        e = dist(gen);
    }
    return result;
}
 
 
int main() {
    std::vector<int> first = generate_vector(10000000);//Добавил еще нолик
    std::vector<int> second = generate_vector(10000000);//Добавил еще нолик
    std::sort(first.begin(), first.end());
    std::sort(second.begin(), second.end());
 
    std::vector<int> result;
    result.reserve(first.size() + second.size());
    std::cout << "start..." << std::endl;
    auto start_tp = std::chrono::high_resolution_clock::now();
#ifndef CROESSMAH
    std::size_t s = stu4ent_unique_difference(
        first.data(), first.size(), 
        second.data(), second.size());
#else
    croessmah_unique_difference(
        first.begin(), first.end(), 
        second.begin(), second.end(), 
        std::back_inserter(result));
    std::size_t s = result.size();
#endif
    auto diff_time = std::chrono::high_resolution_clock::now() - start_tp;
    std::cout << "finish" << std::endl;
 
    std::cout << "unique before erase: " << s;
    std::sort(result.begin(), result.end());
    result.erase(std::unique(result.begin(), result.end()), result.end());
    
    std::cout << "\nunique: " << result.size()
              << "\nexecution time: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(diff_time).count() 
              << " ms" << std::endl;
    return 0;
}

Только моя еще при этом в вектор вставляет. Повеселил на ночь, спасибо.

@stu4ent · 23.09.2018, 23:10

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

Только моя еще при этом в вектор вставляет. Повеселил на ночь, спасибо.

А моя по твоему в вектор ничего не вставляет?. Если нужен вектор, то надо лишь изменить "return", по заданию нужно число элементов. Видимо кто-то сегодня перетрудился.

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

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

Всё равно быстрее твоей версии, можешь померить с помощью clock

Я исправил это, тут немного обманул, случайно.

Croessmah · 23.09.2018, 23:16

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

А моя по твоему в вектор ничего не вставляет?

Вставляет-то вставляет, только зачем?
Будет лучше организовать итератор, который просто посчитает, сколько раз был вставлен элемент.
Но не суть, ведь это всё равно будет медленнее.

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

Если нужен вектор, то надо лишь изменить "return", по заданию нужно число элементов.

set_symmetric_difference работает примерно с такой же сложностью, как и мой алгоритм,
поэтому как только ты его применил, ты уже практически сравнял алгоритмы по сложности,
а все остальные операции делают сложность твоего алгоритма еще больше.

Применение set здесь - это вообще накладно, как по памяти, так и по времени.

@stu4ent · 23.09.2018, 23:20

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

все остальные операции делают сложность твоего алгоритма еще больше

Новая версия

:

C++
1
2
3
4
5
6
7
size_t
count_unique_elements(int* a, size_t size_a, int* b, size_t size_b) {
    std::vector<int> v(size_a + size_b);
    auto it = std::set_symmetric_difference(a, a + size_a, b, b + size_b, v.begin());
    v.resize(it - v.begin());
    return std::unique(v.begin(), v.end()) - v.begin();
}

Выполняется практически с такой же скоростью как и твоя версия. Реализация её тоже проще. Скорость на массиве из 1000000 элементов:
1) моя версия 13: мс;
2) твоя версия 10: мс.

Croessmah · 23.09.2018, 23:20

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

а не строить "велосипеды"

Если велосипед, написанный за 10-20 минут работает в тысячу раз быстрее, то я предпочту написать велосипед.

@stu4ent · 23.09.2018, 23:23

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

тысячу раз быстрее,

проверь новую версию

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

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

Будет лучше организовать итератор, который просто посчитает, сколько раз был вставлен элемент.

Да, наверно, в этом случае с памятью будет всё лучше, но его же ещё реализовать надо. Это требует, видимо, чуть-чуть больше времени.

Croessmah · 23.09.2018, 23:46

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

проверь новую версию

Это уже хорошо, я рассматривал такой вариант.
Правда, всё равно чуть медленнее из-за unique, но эта разница уже не велика.
Однако, у нас есть еще одно требование:

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

кто-нибудь знает, эффективнее перебора и без использования библиотек что может быть?

я так понимаю, использовать алгоритмы из стандартной библиотеки нельзя.
Но это уже другая история. Теперь просто сравните производительность своего первого варианта и последнего. )))

Добавлено через 13 минут
stu4ent, тут, кстати, есть еще одно НО.
Если считать просто количество, то в моем алгоритме вектор и дополнительная память не нужны вообще:

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
template<typename ForwardIterator>
std::size_t count_unique(
    ForwardIterator f_begin, ForwardIterator f_end, 
    ForwardIterator s_begin, ForwardIterator s_end)
{    
    std::size_t result = 0;
    while (f_begin != f_end && s_begin != s_end) {
        if (*f_begin < *s_begin) {
            ++result;
            f_begin = skip_equal(f_begin, f_end);
        } else if (*s_begin < *f_begin) {
            ++result;
            s_begin = skip_equal(s_begin, s_end);
        } else {
            f_begin = skip_equal(f_begin, f_end);
            s_begin = skip_equal(s_begin, s_end);
        }
    }
    while (f_begin != f_end) {
        ++result;
        f_begin = skip_equal(f_begin, f_end);
    }
    while (s_begin != s_end) {
        ++result;
        s_begin = skip_equal(s_begin, s_end);
    }
    return result;;
}

Просто я сначала искал не количество, а сами элементы.

@New man · 23.09.2018, 23:48

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

без использования библиотек

Мне кажется, это относится ко всяким бустам и прочим сторонним, стандартная библиотека же есть часть языка.

Croessmah · 23.09.2018, 23:51

Сообщение от New man

стандартная библиотека же есть часть языка.

Это еще нужно доказать преподавателю...
Думаю, его интересует именно разработка алгоритма, а не использование готовых. Это же обучение.

@stu4ent · 23.09.2018, 23:54

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

Если считать просто количество, то в моем алгоритме вектор и дополнительная память не нужны вообще:

В своих тестах я использовал именно эту версию, только вместо "result" был "counter"

.

@sourcerer · 24.09.2018, 07:45

Не по теме:

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

-DCROESSMAH

Это что такое? о_О

Новые блоги и статьи Все статьи Все блоги /
Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .

@fanfuntik 1 / 0 / 1 Регистрация: 08.09.2018 Сообщений: 46

	Как проверить вхождение элемента в массив эффективным образом? 15.09.2018, 18:58. Показов 16826. Ответов 55 Метки нет (Все метки) Встала задача: Даны два массива, элементы которых упорядочены по возрастанию (и зачем это дали?). Найти количество уникальных элементов, то есть, которые входят в один массив, но не входят в другой. Пример a[5] = {1,2,3,4,5,6} b[6] = {3,4,5,6,7,8,9} результатом будет 5 (1,2,7,8,9) Сначала решил через множества: нашел разность a-b; b-a; затем объединил их и получил количество уникальных элементов. но вроде не пахнет эффективным решением, да и без массивов.. не думаю, что зачтут такую задачу.. Помогите с идеями, как подойти к задаче?) Спасибо всем большое. 0

Croessmah Неэпический 18150 / 10732 / 2067 Регистрация: 27.09.2012 Сообщений: 27,047 Записей в блоге: 1
	23.09.2018, 20:27
	stu4ent, я не зря отметил, что мой код это решает за линейное время, в отличие от Вашего. Ну и для моего шаблона достаточно однонаправленных итераторов. 1

@New man 309 / 221 / 74 Регистрация: 23.05.2011 Сообщений: 981
	23.09.2018, 21:47
	zss, map же даёт nlogn. n элементов массива * logn вставку. Тут уже быстрее бинарным поиском без траты лишней памяти. Вот запихнуть в unordered_map будет эффективно O(n+m) по скорости, O(min(n,m)) по памяти. Добавлено через 7 минут Croessmah, красиво. Утянул на ideone к себе. 0

Croessmah Неэпический 18150 / 10732 / 2067 Регистрация: 27.09.2012 Сообщений: 27,047 Записей в блоге: 1
	23.09.2018, 22:45
	stu4ent, она выполняет не ту работу, что требуется. Она одинаковые элементы в одном последовательности запихнет как уникальные. Кстати, этим и твой алгоритм страдает - он не выкидывает одинаковые элементы из последовательности. 1

@stu4ent 30 / 21 / 8 Регистрация: 23.09.2018 Сообщений: 186
	23.09.2018, 22:49
	По условию не сказано, что могут быть одинаковые элементы . 0

Как проверить вхождение элемента в массив эффективным образом?

Решение