Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Тамика
Котовчанин
870 / 450 / 143
Регистрация: 16.02.2010
Сообщений: 2,954
Записей в блоге: 27
#1

Быстрый поиск элемента - C++

30.01.2014, 16:32. Просмотров 1130. Ответов 22
Метки нет (Все метки)

Добрый день всем! Такой вопрос - есть у меня строка из 64-х чаров. Мне приходит новый чар и нужно найти какой индекс у такого же чара в массиве. Но переберивать ифом все элементы очень затратно(в плане производительности). Есть ли какие-то способы? Можно ли сделать массив, у которых индексы будут чары?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.01.2014, 16:32     Быстрый поиск элемента
Посмотрите здесь:

Быстрый поиск - C++
Здравствуйте. Нужно выполнить поиск i-го вхождения заданного элемента в исходном наборе чисел. Написал такой поиск, но работает...

Быстрый поиск совершенных чисел - C++
Чтобы легко можно было отсылать вопрошающих по этому вопросу, создаю новую тему. Напомню, что Доказано, что все четные совершенные...

Быстрый поиск супернатуральных чисел - C++
Натуральное число будем называть супернатуральным, если в своем десятичном виде оно не содержит единиц, а произведение всех его цифр равно...

Быстрый поиск минимального числа - C++
подскажите быстрый алгоритм поиска второго минимального числа в массиве?

Быстрый поиск по полям в коллекции - C++
Есть коллекция объектов класса с разными полями. Нужно организовать быстрый поиск первого элемента (может потом множества элементов) по...

Быстрый поиск в векторе из pair - C++
Пытаюсь сделать вектор: vector< pair<string, string> > myVect; По идее, проще воспользоваться чем-то вроде map или unordered_map,...

Быстрый поиск ip адреса в текстовом файле - C++
Нужно найти конкретный ip-адрес в текстовом файле (он может попасться несколько раз). На каждой строчке по 1 ip-адресу. Всего строк ~300...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gng
634 / 480 / 131
Регистрация: 08.09.2013
Сообщений: 1,280
30.01.2014, 20:31     Быстрый поиск элемента #21
Цитата Сообщение от zelim Посмотреть сообщение
Что-то мне подсказывает, что в таком случае мы будем впустую расходовать память
C++
1
2
3
4
5
6
7
8
9
#include <iostream>
#include <map>
using namespace std;
 
main() {
  int s[256];      // даже не char s[256]
  map <char, int> mp[64];
  cout << sizeof (s) << '\t' << sizeof (mp) << '\n';
}
Результат предсказуем
1024 3072
Часть памяти в случае массива чаров, действительно, расходуется впустую, а не на наполненные смыслом "прибомбасы" stl.
По скорости отрыв, думаю, только увеличится.

Добавлено через 18 минут
Цитата Сообщение от zelim Посмотреть сообщение
не должно быть проигрыша в скорости: при компилировании на более-менее вменяемом компиляторе, скорость доступа к элементам контейнера и статического массива - одинакова.
Совершенно не подтверждается практикой. Скорость доступа различается примепно в 4 раза и эта пропорция сохраняется даже при оптимизации -O3.
PS. Я имел в виду массив против вектора при доступе по индексу.
MrGluck
Модератор
Эксперт CЭксперт С++
7157 / 4323 / 630
Регистрация: 29.11.2010
Сообщений: 11,743
30.01.2014, 20:38     Быстрый поиск элемента #22
А теперь предположим, что нам нужно пробежаться по всем элементам, которые использовались.
Для массива это будет пробег по всем элементам с проверкой, в случае же с контейнером map (хз зачем тут вектор вообще и какой с него профит) это делается обычным пробегом. Вот тут и экономия на будущее.
P.S. gng, сравните доступ в заполненном unordered_map по индексу и в массиве.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.01.2014, 21:18     Быстрый поиск элемента
Еще ссылки по теме:

Подскажите быстрый поиск количества интервалов в отрезке - C++
Есть массив H Есть отрезок x+dx. Задача найти количество интервалов на которое делится отрезок x+dx массивом H. Наверняка с такой...

Быстрый поиск наиболее близких вершин графа - C++
Всем привет, у меня имеется некая задача и её суть состоит в том, что мне нужно найти расстояние между двумя наиболее близкими вершинами...

Как сделать быстрый поиск по массиву разнотипных данных? - C++
Как сделать быстрый поиск по массиву и разнотипных данных?

Быстрый поиск подстроки в строке (Кнута-Морриса-Пратта) - C++
Всем здрасьте. Преподаватель дал задание, найти подстроку в строке. Я задание это выполнил. Он сказал что мой алгоритм будет работать...

Поиск элемента - C++
Программа считает сколько минимально раз подряд встречается элемент х в массиве #include &lt;iostream&gt; using namespace std; int...


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

Или воспользуйтесь поиском по форуму:
gng
634 / 480 / 131
Регистрация: 08.09.2013
Сообщений: 1,280
30.01.2014, 21:18     Быстрый поиск элемента #23
Цитата Сообщение от MrGluck Посмотреть сообщение
gng, сравните доступ в заполненном unordered_map по индексу и в массиве.
Чтение по int индексу
array[10000000] - 0.02s
map - 2.80s
Есть немало примеров, где применение хэшированного списка оправдано, но к задаче ТС это если и относится, то только как дань привычке.
Yandex
Объявления
30.01.2014, 21:18     Быстрый поиск элемента
Ответ Создать тему
Опции темы

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