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

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

Восстановить пароль Регистрация
 
 
Тамика
Котовчанин
 Аватар для Тамика
859 / 439 / 129
Регистрация: 16.02.2010
Сообщений: 2,538
Записей в блоге: 27
30.01.2014, 16:32     Быстрый поиск элемента #1
Добрый день всем! Такой вопрос - есть у меня строка из 64-х чаров. Мне приходит новый чар и нужно найти какой индекс у такого же чара в массиве. Но переберивать ифом все элементы очень затратно(в плане производительности). Есть ли какие-то способы? Можно ли сделать массив, у которых индексы будут чары?
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
 Аватар для Байт
13993 / 8824 / 1231
Регистрация: 24.12.2010
Сообщений: 15,990
30.01.2014, 16:36     Быстрый поиск элемента #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
(Если я правильно понял, что тебе нужно)
C
1
2
char X[256];
if (X['a']) ...
Такая конструкция совершенно законна.
Тамика
Котовчанин
 Аватар для Тамика
859 / 439 / 129
Регистрация: 16.02.2010
Сообщений: 2,538
Записей в блоге: 27
30.01.2014, 16:47  [ТС]     Быстрый поиск элемента #3
Да, об этом и спрашивала! Спасибо.
some_name
Вежливость-главное оружие
 Аватар для some_name
219 / 219 / 55
Регистрация: 19.02.2013
Сообщений: 1,419
30.01.2014, 17:00     Быстрый поиск элемента #4
Можно попробывать еще "Метод бисекции"
Тамика
Котовчанин
 Аватар для Тамика
859 / 439 / 129
Регистрация: 16.02.2010
Сообщений: 2,538
Записей в блоге: 27
30.01.2014, 17:05  [ТС]     Быстрый поиск элемента #5
А можно подробнее?..
Байт
 Аватар для Байт
13993 / 8824 / 1231
Регистрация: 24.12.2010
Сообщений: 15,990
30.01.2014, 17:17     Быстрый поиск элемента #6
Цитата Сообщение от Тамика Посмотреть сообщение
А можно подробнее?..
Ну, еще это называется "Метод половинного деления". Надеюсь, из названия уже понятно о чем идет речь.
Массив имеющихся значений упорядочивается. При определении того, существует ли в массиве какое-то значение, он делится пополам. Выясняется, больше или меньше его середина этого значения. На основании этого принимается решение, в какой половине искать дальше.... Так за 10 вопросом угадывают задуманное число от 1 до 1000. Но вставка нового значения в массив оказывается дорогой. В вашем случае, когда возможных значений всего 256, удобнее и эффективнее работать с "прямым" массивом, организованным по принципу "ключ=адрес"
Тамика
Котовчанин
 Аватар для Тамика
859 / 439 / 129
Регистрация: 16.02.2010
Сообщений: 2,538
Записей в блоге: 27
30.01.2014, 17:19  [ТС]     Быстрый поиск элемента #7
Ааа... Не знала, что он так называется. Поняла о чем речь, спасибо! Но думаю, что способ с массивом[чар] будет удобнее...
some_name
Вежливость-главное оружие
 Аватар для some_name
219 / 219 / 55
Регистрация: 19.02.2013
Сообщений: 1,419
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;
}
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;
}
Т.е. работа с ним аналогична работе с простым массивом, предложенным Байт.
Тамика
Котовчанин
 Аватар для Тамика
859 / 439 / 129
Регистрация: 16.02.2010
Сообщений: 2,538
Записей в блоге: 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' ... '+', '/' ", а в разнобой.
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
30.01.2014, 18:22     Быстрый поиск элемента #11
Цитата Сообщение от zelim Посмотреть сообщение
впустую расходовать память
Вы серьезно?

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

Добавлено через 7 минут
gazlan, кода может и больше, но зато выигрыш в отказоустойчивости + не должно быть проигрыша в скорости: при компилировании на более-менее вменяемом компиляторе, скорость доступа к элементам контейнера и статического массива - одинакова.
Но что будет, если мы выйдем за границы статического массива? Программа выкинет исключение и завершит работу, если перехват такового не реализован (компилятор не всегда способен предсказать такие ситуации). В то же время map - гарантирует, что значение с таким ключом будет адекватно добавлено.
Тамика
Котовчанин
 Аватар для Тамика
859 / 439 / 129
Регистрация: 16.02.2010
Сообщений: 2,538
Записей в блоге: 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;
    }
Почему массив не заполнен значениями этими, а заполнен мусором?
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;
    }
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
30.01.2014, 19:09     Быстрый поиск элемента #15
Цитата Сообщение от zelim Посмотреть сообщение
что будет, если мы выйдем за границы статического массива
Это вы о чем? У вас в байте больше 8 бит?
zelim
77 / 77 / 4
Регистрация: 26.12.2011
Сообщений: 217
30.01.2014, 19:15     Быстрый поиск элемента #16
Цитата Сообщение от gazlan Посмотреть сообщение
Это вы о чем? У вас в байте больше 8 бит?
Я об индексации. Если будет выход за границы массива, можем переписать не ту память, либо получить исключение - в зависимости от настроек компилятора.
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
30.01.2014, 19:35     Быстрый поиск элемента #17
Еще раз: при 8 битах в байте весь диапазон 0..255. Никакой "выход за границы массива" невозможен по определению.

Более того, именно табличные решения - лучший выбор для всех подобных задач.
Байт
 Аватар для Байт
13993 / 8824 / 1231
Регистрация: 24.12.2010
Сообщений: 15,990
30.01.2014, 19:39     Быстрый поиск элемента #18
Цитата Сообщение от Тамика Посмотреть сообщение
Ребят, опять проблема... То ли после работы уже плохо соображаю, то ли просто ума не хватает. Вот что тут не так?
base64[0] = 'A' = 65
Это вам о чем-нибудь говорит?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
30.01.2014, 19:41     Быстрый поиск элемента #19
Можно использовать неупорядоченный ассоцитативный массив std::unordered_map. В среднем доступ за константное время.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.01.2014, 19:55     Быстрый поиск элемента
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
30.01.2014, 19:55     Быстрый поиск элемента #20
Цитата Сообщение от MrGluck Посмотреть сообщение
доступ за константное время
Именно в данном случае, сама константа будет больше - за счет (избыточного) хэширования.
Yandex
Объявления
30.01.2014, 19:55     Быстрый поиск элемента
Ответ Создать тему
Опции темы

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