Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Тамика
Котовчанин
917 / 461 / 145
Регистрация: 16.02.2010
Сообщений: 3,239
Записей в блоге: 27
#1

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

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

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

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

Быстрый поиск в мапе - C++
Есть мапа вида : std::map<size_t, std::string> Нужно найти элемент меньший или равный элементу из rbf с конца мапы. Есть ли быстрый...

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

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

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

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

22
Байт
Диссидент
Эксперт C
16825 / 11090 / 1743
Регистрация: 24.12.2010
Сообщений: 21,775
30.01.2014, 16:36 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
(Если я правильно понял, что тебе нужно)
C
1
2
char X[256];
if (X['a']) ...
Такая конструкция совершенно законна.
2
Тамика
Котовчанин
917 / 461 / 145
Регистрация: 16.02.2010
Сообщений: 3,239
Записей в блоге: 27
30.01.2014, 16:47  [ТС] #3
Да, об этом и спрашивала! Спасибо.
0
some_name
Вежливость-главное оружие
227 / 225 / 55
Регистрация: 19.02.2013
Сообщений: 1,441
30.01.2014, 17:00 #4
Можно попробывать еще "Метод бисекции"
1
Тамика
Котовчанин
917 / 461 / 145
Регистрация: 16.02.2010
Сообщений: 3,239
Записей в блоге: 27
30.01.2014, 17:05  [ТС] #5
А можно подробнее?..
0
Байт
Диссидент
Эксперт C
16825 / 11090 / 1743
Регистрация: 24.12.2010
Сообщений: 21,775
30.01.2014, 17:17 #6
Цитата Сообщение от Тамика Посмотреть сообщение
А можно подробнее?..
Ну, еще это называется "Метод половинного деления". Надеюсь, из названия уже понятно о чем идет речь.
Массив имеющихся значений упорядочивается. При определении того, существует ли в массиве какое-то значение, он делится пополам. Выясняется, больше или меньше его середина этого значения. На основании этого принимается решение, в какой половине искать дальше.... Так за 10 вопросом угадывают задуманное число от 1 до 1000. Но вставка нового значения в массив оказывается дорогой. В вашем случае, когда возможных значений всего 256, удобнее и эффективнее работать с "прямым" массивом, организованным по принципу "ключ=адрес"
1
Тамика
Котовчанин
917 / 461 / 145
Регистрация: 16.02.2010
Сообщений: 3,239
Записей в блоге: 27
30.01.2014, 17:19  [ТС] #7
Ааа... Не знала, что он так называется. Поняла о чем речь, спасибо! Но думаю, что способ с массивом[чар] будет удобнее...
0
some_name
Вежливость-главное оружие
227 / 225 / 55
Регистрация: 19.02.2013
Сообщений: 1,441
30.01.2014, 17:28 #8
Цитата Сообщение от Тамика Посмотреть сообщение
А можно подробнее?..
Каждому символу ставится в соответствие число(его код). Поэтому любую строку можно отсортировать как массив чисел и работать и ними.

Доп. инф. : Мето половинного деления

Вот реализация бинарного поиска :

Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
/////////////////////////////////////////////////////////////////
int bin_search(int *M, int n, int k);
int shell(int *A, int n);
int print(int *A, int n);
/////////////////////////////////////////////////////////////////
int main()
{
    const int n=10;
    int A[n];
    int k;
 
    srand(time(0));
 
    for (int i=0; i<n; i++)
        A[i] = rand()%90+10;
    
    cout << "Default array: ";
    print(A, n);
    
    shell(A, n);
    cout << "Sort Array:    ";
    print(A, n);
 
    cout << "\nInput find element: ";
    cin >> k;
    
    cout << "Index = " << bin_search(A, n, k) << endl;
 
    system("pause");
    return 0;
}
/////////////////////////////////////////////////////////////////
int bin_search(int *arr, int n, int k)
{
    int u = 0;
    int v = n;
 
    int m;
    int z = 0;
 
    while (u < v)
    {
        z++;
        m = (u + v) / 2;
        if (k > arr[m]) u = m;
        if (k < arr[m]) v = m;
        if (k == arr[m]) break;
    }
 
    cout << endl << "Iterations: " << z << endl;
 
    return m;
}
/////////////////////////////////////////////////////////////////
int shell(int *arr, int n)
{
    int h = n / 2;
 
    while (h > 0)
    {
        for (int i = 0; i < n - h; ++i)
        {
            int j = i;
        
            while (j >= 0)
            {
                if (arr[j] > arr[j + h])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j + h];
                    arr[j + h] = tmp;
                    j = j - h;
                } 
                else j--;
            } 
        }
        h = h/2;
    }
 
    return 0;
}
/////////////////////////////////////////////////////////////////
int print(int *arr, int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
  
    cout << "\n";
    return 0;
}
0
zelim
77 / 77 / 4
Регистрация: 26.12.2011
Сообщений: 217
30.01.2014, 17:50 #9
Цитата Сообщение от Байт Посмотреть сообщение
(Если я правильно понял, что тебе нужно)
C
1
2
char X[256];
if (X['a']) ...
Такая конструкция совершенно законна.
Что-то мне подсказывает, что в таком случае мы будем впустую расходовать память (т.е. под элементы массива 0-255 выделится порядка 256 байт).

Тамика, вам будет проще использовать ассоциативный контейнер map из стандартной библиотеки STL:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <map>
 
int main()
{
    using namespace std;
 
    setlocale(LC_ALL, "rus");
    map<char, int> mp;
 
    mp['a'] = 1;
    mp['b'] = 2;
    char x = 'a';
    
    if(mp[x])
        cout << "Такой элемент есть";
 
    cout << endl;
    system("pause");
    return 0;
}
Т.е. работа с ним аналогична работе с простым массивом, предложенным Байт.
1
Тамика
Котовчанин
917 / 461 / 145
Регистрация: 16.02.2010
Сообщений: 3,239
Записей в блоге: 27
30.01.2014, 18:12  [ТС] #10
Попробовала через мап, но значения, почему-то, заполняются не ровно!
C++
1
2
3
4
5
6
7
    
static const std::string base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    std::map<char, int> base_64;
    for (int i = 0; i < base64.size(); ++i)
    {
        base_64[base64[i]] = i;
    }
В итоге, в мапе не последовательно " 'A', 'B', 'C' ... '+', '/' ", а в разнобой.
0
gazlan
3133 / 1909 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
30.01.2014, 18:22 #11
Цитата Сообщение от zelim Посмотреть сообщение
впустую расходовать память
Вы серьезно?

Один только код контейнера займет много больше, не говоря уже о проигрыше в скорости (дерево против хэша).
0
zelim
77 / 77 / 4
Регистрация: 26.12.2011
Сообщений: 217
30.01.2014, 18:48 #12
Тамика, если важен порядок, то тут уже map немного не подходит, так как он оптимизирован под быстрый поиск элемента в коллекции, и поэтому реализуется в виде хэш-таблиц.
Здесь уже либо вариант Байт, либо своя обертка над vector с перегрузкой операции доступа по индексу.

Добавлено через 7 минут
gazlan, кода может и больше, но зато выигрыш в отказоустойчивости + не должно быть проигрыша в скорости: при компилировании на более-менее вменяемом компиляторе, скорость доступа к элементам контейнера и статического массива - одинакова.
Но что будет, если мы выйдем за границы статического массива? Программа выкинет исключение и завершит работу, если перехват такового не реализован (компилятор не всегда способен предсказать такие ситуации). В то же время map - гарантирует, что значение с таким ключом будет адекватно добавлено.
0
Тамика
Котовчанин
917 / 461 / 145
Регистрация: 16.02.2010
Сообщений: 3,239
Записей в блоге: 27
30.01.2014, 18:50  [ТС] #13
Ребят, опять проблема... То ли после работы уже плохо соображаю, то ли просто ума не хватает. Вот что тут не так?

C++
1
2
3
4
5
6
7
    static const std::string base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    int base_64[64];
    
    for (int i = 0; i < base64.size(); ++i)
    {
        base_64[base64[i]] = i;
    }
Почему массив не заполнен значениями этими, а заполнен мусором?
0
zelim
77 / 77 / 4
Регистрация: 26.12.2011
Сообщений: 217
30.01.2014, 18:55 #14
Тамика, массив побольше нужен, дабы коды char-ов не укладываются в 0-64.
C++
1
2
3
4
5
6
static const std::string base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    int base_64[1024] = {0}; 
    for (int i = 0; i < base64.size(); ++i)
    {
        base_64[base64[i]] = i;
    }
0
gazlan
3133 / 1909 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
30.01.2014, 19:09 #15
Цитата Сообщение от zelim Посмотреть сообщение
что будет, если мы выйдем за границы статического массива
Это вы о чем? У вас в байте больше 8 бит?
0
30.01.2014, 19:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.01.2014, 19:09
Привет! Вот еще темы с ответами:

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

Вставка элемента в заданную позицию, удаление элемента по заданной позиции, поиск заданного элемента - C++
Добавить в класс &quot;Односвязный список&quot; следующие функции: вставка элемента в заданную позицию, удаление элемента по заданной позиции, поиск...

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

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


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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