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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений	сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .
сукцессия 13. Питон модель трехзонного мицелия, пока что в основном арбускулярного anaschu 28.06.2026 ## Разработка агентной модели микоризной сукцессии: от выявления артефактов к созданию комплексной системы ### Аннотация Представлено исследование по разработке агентной модели микоризной. . .	сукцессия 12. краткий список проверок модели перед запуском. anaschu 27.06.2026 Скрытые отказы в моделях систем динамики (SD-models) экологических систем: два случая из практики Контекст Разбирался прототип модели систем динамики (SD-модели) микоризной сукцессии: пять. . .	Сукцессия 11. Проверка орудий перед войной: разработка через тестирование anaschu 27.06.2026 Как не дать модели соврать самой себе: проверки для симуляции микоризной сукцессии Введение Когда вы строите математическую модель живой системы — грибов, растений, почвы — главная опасность. . .	10 сукцессия. Питон код войны грибов и растений anaschu 27.06.2026 import numpy as np class PlantAgent: def __init__(self, name, strategy, initial_biomass): self. name = name self. strategy = strategy # "greedy" (широколиственные) или. . .

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

	Как проверить вхождение элемента в массив эффективным образом? 15.09.2018, 18:58. Показов 16610. Ответов 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 Неэпический 18149 / 10731 / 2067 Регистрация: 27.09.2012 Сообщений: 27,038 Записей в блоге: 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 Неэпический 18149 / 10731 / 2067 Регистрация: 27.09.2012 Сообщений: 27,038 Записей в блоге: 1
	23.09.2018, 22:45
	stu4ent, она выполняет не ту работу, что требуется. Она одинаковые элементы в одном последовательности запихнет как уникальные. Кстати, этим и твой алгоритм страдает - он не выкидывает одинаковые элементы из последовательности. 1

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

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

Решение