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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026	Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .	Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .

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

	Как проверить вхождение элемента в массив эффективным образом? 15.09.2018, 18:58. Показов 16699. Ответов 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,046 Записей в блоге: 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,046 Записей в блоге: 1
	23.09.2018, 22:45
	stu4ent, она выполняет не ту работу, что требуется. Она одинаковые элементы в одном последовательности запихнет как уникальные. Кстати, этим и твой алгоритм страдает - он не выкидывает одинаковые элементы из последовательности. 1

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

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

Решение