0

Для массивов данных в C++? Интересуют больше всего массивы строк именно.

1
  • @pol500, если Вы о вчерашнем поиске в словаре из 15000 слов, то IMHO проблема не в поиске, конечно если Вы не применяли линейный поиск или в случае хэширования очень маленькую таблицу и разрешение коллизий цепочками.
    – avp
    26 мар 2012 в 20:03

3 ответа 3

8

Из вариантов специализированных структур данных:

Radix tree и Prefix tree. Оба дерева выполняют операцию lookup за O(k), где k - максимальная длина строки.

Из вариантов, всегда доступных под рукой в C++03 / C++11:

Сортированный std::vector + std::binary_search, std::set (или std::map), boost::unordered_set.

Обычно производительности стандартных контейнеров хватает для эффективного решения большинства практических задач.

7

Самые быстрые для чего и где? Если отсортированных данных - бинарный поиск и его модификации.

Неотсортированных - хешмап.

Очень больших - mapreduce (это когда данные разделяются между несколькими серверами и каждый делает поиск в своей порции. Потом результаты объединяются).

А ещё можно вначале загрузить данные в какую-нибудь базу данных и пусть это будут ее проблемы:)

2
  • А как вы оцените бинарный поиск по отсортированному в порядке возрастания массиву (коллекции) хеш-ключей? Или так делают только быдло-кодеры?
    – PaulD
    26 мар 2012 в 18:59
  • у бинарного поиска очень хорошая скорость (максимальное кол-во сравнений - двоичный логарифм от размера данных). Если сделать нормальный массив хешключей, то поиск можно сделать ещё быстрее. Все очень сильно зависит от задачи.
    – KoVadim
    26 мар 2012 в 19:02
0

Совсем недавно делал такую штуку. Сделал очень просто. Для строки рассчитывается хэш-сумма. Потом берем остаток от деления хэш-суммы на вместимость массива строк. И пытаемся пихнуть эту строку сначала именно в эту ячейку! Если она занята - идем вправо, пока не найдем свободную. Соответственно, при поиске строки в массиве используем тот же алгоритм. Это проще, чем сортировать хэши и использовать бинарный поиск, и эффективнее, чем просматривать массив хэшей с начала до конца. Хотя в худшем случае, конечно, именно этим все и кончится, но этот случай маловероятен, особенно если сделать массив больше, чем надо, а не впритык. То есть если надо хранить 15000 строк, делаем массив 20000-30000.

Надеюсь, я понятно объяснил. Вот С-подобный псевдокод для иллюстрации идеи (операции со строками, конечно, я делал иначе, через свои велосипеды, мне просто лень расписывать):

struct string {
    char symbols[20];
    unsigned long hash;
}

struct string strings[15000]; // Надо инициализировать symbols пустыми строками.

int put_string(char* s)
{
    unsigned long h = hash(s);
    int i = h % 15000;
    while( strings[i].symbols == "" ) {
        if( ++i == 15000 ) i = 0;
    } // Здесь возможно зацикливание, если вместимости массива strings не хватит.
    strings[i].symbols = s;
    return i;
}

int get_string(char* s)
{
    unsigned long h = hash(s);
    int i = h % 15000;
    while( strings[i].symbols != "" ) {
        if( strings[i].hash == h && strings[i].symbols == s ) return i;
        if( ++i == 15000 ) i = 0;
    } // Здесь тоже может произойти зацикливание. Либо нужно использовать цикл for, либо массив strings должен быть гарантированно больше, чем нужно, хотя бы на один элемент. Мне нравится второе.
    return -1;
}
2
  • 1
    @VadimTukaev, это идея называется хэширование методом с открытой адресацией. На самом деле там еще есть тонкие моменты (например с удалением). -- Кстати, а Вы вообще-то свой код хотя бы компилировать пробовали?
    – avp
    1 апр 2014 в 11:19
  • > идея называется хэширование методом с открытой адресацией. Идея была не в алгоритме, а в том, чтобы посоветовать человеку использовать его. Я знал, что такое уже есть, просто забыл название. > На самом деле там еще есть тонкие моменты (например с удалением). Признаком отсутствия строки является тот факт, что строка пустая. Поэтому удалять элементы можно, просто присваивая пустую строку. > Кстати, а Вы вообще-то свой код хотя бы компилировать пробовали? Конкретно этот - нет. Я же предупредил, что это всего лишь псевдокод для демонстрации идеи. Но аналогичный пробовал не далее как вчера. 1 апр 2014 в 16:31

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.