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

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

Восстановить пароль Регистрация
 
 
Тамика
Котовчанин
 Аватар для Тамика
859 / 439 / 129
Регистрация: 16.02.2010
Сообщений: 2,538
Записей в блоге: 27
30.01.2014, 16:32     Быстрый поиск элемента #1
Добрый день всем! Такой вопрос - есть у меня строка из 64-х чаров. Мне приходит новый чар и нужно найти какой индекс у такого же чара в массиве. Но переберивать ифом все элементы очень затратно(в плане производительности). Есть ли какие-то способы? Можно ли сделать массив, у которых индексы будут чары?
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gng
605 / 451 / 122
Регистрация: 08.09.2013
Сообщений: 1,152
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
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,409
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++ Как сделать быстрый поиск по массиву разнотипных данных?
Быстрый поиск C++
C++ Быстрый поиск минимального числа

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

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

Текущее время: 23:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru