Кодирование на С++. Мне нужна структура данных для группы отсортированных строк. Я буду вставлять все строки в него за один раз и не обновлять его, но я буду искать строки очень часто. Все, что мне нужно, чтобы увидеть, существует ли строка-указатель в структуре или нет. Я ожидаю, что в списке будет около 100 строк. Что будет более быстрой структурой? Сначала я думал о хэшмапе, но я где-то видел, что для такого небольшого количества элементов бинарный поиск по вектору будет работать лучше (поскольку они отсортированы).
С++ - самая быстрая структура данных для многократного поиска
Ответ 1
Предполагая, что вы говорите о "полноразмерных" процессорах 1 бинарный поиск по строкам, даже с только 100 элементами, скорее всего, будет довольно медленным, по крайней мере, по сравнению с другими решениями. Вы можете столкнуться с несколькими неверными предсказаниями отрасли для каждого поиска и, вероятно, в конечном итоге рассмотрите каждый символ в строке ввода несколько раз (так как вам нужно повторно strcmp в каждом node в двоичном поиске).
Как уже указывал кто-то, единственный реальный способ узнать - это измерить, но для этого вам все равно нужно выяснить, в чем состоят кандидаты! Кроме того, не всегда можно измерить реалистичный сценарий, поскольку может даже не знать такой сценарий (представьте, например, создание библиотечной функции, которая широко используется во многих разных случаях).
Наконец, понимание того, что может быть быстрым, позволяет обеим устранить кандидатов, которых вы знаете, будет плохо работать, и позволяет вам дважды проверить результаты теста с помощью вашей интуиции: если что-то намного медленнее, чем вы ожидали, стоит проверить, почему (сделал ли компилятор что-то глупое), и если что-то намного быстрее, возможно, настало время обновить вашу интуицию.
Итак, я попытаюсь нанести удар по тому, что будет быстро - если бы скорость действительно имела значение здесь, и вы можете потратить некоторое время на проверку сложного решения. В качестве базовой линии простая реализация, вероятно, займет 100 нс и действительно оптимизирована, возможно, на 10 нс. Поэтому, если вы потратите на это 10 часов инженерного времени, вам придется называть эту функцию 400 миллиардов раз, чтобы заработать 10 часов назад 5. Когда вы подвергаете риску ошибки, сложность обслуживания и другие накладные расходы, вы захотите убедиться, что вы вызываете эту функцию много триллионов раз, прежде чем пытаться ее оптимизировать. Такие функции редки, но они, безусловно, существуют 4.
Тем не менее, вам не хватает информации, необходимой для разработки очень быстрого решения, например:
- Входит ли ваш вход в функцию поиска a
std::stringилиconst char *или что-то еще? - Какова средняя и максимальная длина строки?
- Будет ли большинство ваших запросов успешным или неудачным?
- Можете ли вы принять ложные срабатывания?
- Является ли набор строк известным во время компиляции, или вы в порядке с длинной фазой инициализации?
Ответы, приведенные выше, помогут вам разделить пространство дизайна, как описано ниже.
Фильтры цветка
Если на (4) вы можете принять (контролируемое) количество ложных срабатываний 2 или за (3) большую часть вашего поиск будет неудачным, тогда вы должны рассмотреть Bloom Filter. Например, вы можете использовать 1024-битный (128-байтовый) фильтр и использовать 60-битный хэш строки для индексации в него с 6 10-битными функциями. Это дает < 1% ложноположительная ставка.
Это имеет то преимущество, что за пределами вычисления хеша он не зависит от длины строк и не зависит от поведения сопоставления (например, поиск, который опирается на повторное сравнение строк, будет медленнее, если строки будут иметь тенденцию иметь давние общие префиксы).
Если вы можете принимать ложные срабатывания, вы все сделали - но в случае, если вам нужно, чтобы он всегда был правильным, но ожидайте в основном неудачных поисков, вы используете его как фильтр: если фильтр цветка возвращает false (обычный случай) вы делаете, но если он возвращает true, вам нужно дважды проверить одну из всегда правильных структур, рассмотренных ниже. Таким образом, общий случай выполняется быстро, но правильный ответ всегда возвращается.
Perfect Hash
Если во время компиляции известно множество строк ~ 100, или вы хорошо выполняете одноразовую тяжелую работу по предварительной обработке строк, вы можете рассмотреть идеальный хеш. Если у вас есть определенный набор поиска в режиме компиляции, вы можете просто пощекотать строки в gperf, и он выплюнет хэш-функцию и поиск Таблица.
Например, я просто накопил 100 случайных английских слов 3 в gperf, и он сгенерировал хэш-функцию, которая должна только смотреть на два символа, чтобы однозначно различать каждое слово, например:
static unsigned int hash (const char *str, unsigned int len)
{
static unsigned char asso_values[] =
{
115, 115, 115, 115, 115, 81, 48, 1, 77, 72,
115, 38, 81, 115, 115, 0, 73, 40, 44, 115,
32, 115, 41, 14, 3, 115, 115, 30, 115, 115,
115, 115, 115, 115, 115, 115, 115, 16, 18, 4,
31, 55, 13, 74, 51, 44, 32, 20, 4, 28,
45, 4, 19, 64, 34, 0, 21, 9, 40, 70,
16, 0, 115, 115, 115, 115, 115, 115, 115, 115,
/* most of the table omitted */
};
register int hval = len;
switch (hval)
{
default:
hval += asso_values[(unsigned char)str[3]+1];
/*FALLTHROUGH*/
case 3:
case 2:
case 1:
hval += asso_values[(unsigned char)str[0]];
break;
}
return hval;
}
Теперь ваша хеш-функция быстрая и, вероятно, хорошо спрогнозирована (если у вас не слишком много строк длиной 3 или меньше). Чтобы найти строку, вы просто индексируете в хеш-таблицу (также генерируемую gperf) и сравниваете то, что получаете с входной строкой.
В некоторых разумных предположениях это будет примерно так же быстро, как вы можете получить - clang генерирует такой код:
in_word_set: # @in_word_set
push rbx
lea eax, [rsi - 3]
xor ebx, ebx
cmp eax, 19
ja .LBB0_7
lea ecx, [rsi - 1]
mov eax, 3
cmp ecx, 3
jb .LBB0_3
movzx eax, byte ptr [rdi + 3]
movzx eax, byte ptr [rax + hash.asso_values+1]
add eax, esi
.LBB0_3:
movzx ecx, byte ptr [rdi]
movzx edx, byte ptr [rcx + hash.asso_values]
cdqe
add rax, rdx
cmp eax, 114
ja .LBB0_6
mov rbx, qword ptr [8*rax + in_word_set.wordlist]
cmp cl, byte ptr [rbx]
jne .LBB0_6
add rdi, 1
lea rsi, [rbx + 1]
call strcmp
test eax, eax
je .LBB0_7
.LBB0_6:
xor ebx, ebx
.LBB0_7:
mov rax, rbx
pop rbx
ret
Это тонна кода, но с разумным количеством ILP. Критический путь - через 3 зависимых доступа к памяти (искать char значение в str → искать хеш-значение для char в таблице хэш-функции → искать строку в фактической хеш-таблице), вы может ожидать, что это займет, возможно, 20 циклов (плюс время strcmp, конечно).
Trie
"Классическим" решением compsci для этой проблемы является trie. Trie может быть разумным подходом к вашей проблеме, особенно многие неудачные совпадения могут быть быстро отвергнуты в пределах первых нескольких символов (это зависит в основном от содержания набора совпадений и строк, которые вы проверяете).
Для выполнения этой работы вам нужна быстрая реализация trie. В целом я считаю, что этот подход будет ограничен программным обеспечением, зависящим от серийного доступа, - каждый node, скорее всего, будет посещаться в виде подхода, использующего указатель, так что вы будете страдать от латентности доступа L1.
Оптимизация strcmp
Почти все из вышеперечисленных решений в какой-то момент зависят от strcmp - исключением является фильтр цветения, который допускает ложные срабатывания. Поэтому вы хотите сделать так, чтобы эта часть вашего кода была быстрой.
В частности, компиляторы иногда могут встроить "встроенные" версии strcmp вместо вызова библиотечной функции: в quick test icc была сделана inlining, но clang и gcc решили вызвать библиотечную функцию. Нет простого правила, для которого один будет быстрее, но в целом библиотечные процедуры часто оптимизируются SIMD и могут быть более быстрыми для длинных строк, в то время как встроенные версии избегают служебных вызовов функций и могут быть быстрее для коротких строк. Вы можете протестировать оба подхода и в основном заставить компиляторы делать то, что быстрее в вашем случае.
Еще лучше, вы можете использовать свой контроль над входами, чтобы сделать намного лучше - если вы можете убедиться, что, например, строки ввода будут заполнены нулями, так что их длина будет кратной 8, то вы можете сделать то же самое для ссылочных строк в своей хеш-таблице (или любой другой структуре), и вы можете сравнить строки по 8 байт за раз. Это не только значительно ускоряет совпадение, но и резко сокращает вероятность неправильного использования ветки, поскольку она по существу квантует поведение цикла (все строки из 1-8 символов цикла один раз и т.д.).
1 Здесь я имею в виду настольные компьютеры, серверы, ноутбуки или даже современные процессоры для смартфонов, а не встроенные MCU или что-то в этом роде.
2 Разрешение ложных срабатываний означает, что он ОК, если ваш "находится в наборе" иногда возвращает true, даже если строка ввода не находится в наборе. Обратите внимание, что он никогда не ошибается в обратном направлении: он всегда возвращает true, когда строка находится в наборе, - нет ложных негативов.
3 В частности, awk 'NR%990==0' /usr/share/dict/american-english > words.
4 Например, сколько раз вы делаете strcmp в истории вычислений? Сколько времени было бы сохранено, если бы оно было на 1 нс быстрее?
5 Такой подход приравнивает время процессора к инженерному времени, которое, вероятно, отключается более чем в 1000 раз: Amazon AWS заряжает примерно $0,02 за час процессорного времени, а хороший инженер может ожидать, возможно, 50 долларов в час (в первом мире). Таким образом, (очень грубое!) Метрическое время разработки на 2500 раз больше, чем время процессора. Так что, возможно, вам нужны квадриллионы звонков на 10 часов работы, чтобы окупиться...
Ответ 2
Лучший (и единственный) способ рассказать, какая структура является наиболее быстрой для определенной ситуации, - это фактически сравнивать/измерять ее с помощью разных структур данных. Затем выберите самый быстрый.
Или, другими словами: измерение вашего кода дает вам преимущество перед теми людьми, которые считают, что они слишком умны для измерения.;)
Для довольно небольших списков, таких как 100 элементов, которые вы упомянули в своем вопросе, не имеет большого значения, какую структуру/алгоритм вы используете, потому что время, вероятно, незначительное - если этот поиск не выполняется очень часто вашей программой.
Ответ 3
Это интересный вопрос, потому что он очень близок к понятию JAVA String Pool. Java использует JNI вызывает собственный соответствующий метод, который реализуется С++
Пул строк - это конкретная реализация JVM концепции интернирование строк:
В информатике интернирование строк - это метод хранения только одной копии каждого отдельного строкового значения, которое должно быть неизменным. Внутренние строки делают некоторые задачи обработки строк более экономными по времени или пространству за счет того, что требуется больше времени при создании или интернировании строки. Разные значения хранятся в пуловом пуле строк.
Посмотрите, как реализовать пул строк внутри Java 7
/**
* Returns a canonical representation for the string object.
* <p>
* A pool of strings, initially empty, is maintained privately by the
* class <code>String</code>.
* <p>
* When the intern method is invoked, if the pool already contains a
* string equal to this <code>String</code> object as determined by
* the {@link #equals(Object)} method, then the string from the pool is
* returned. Otherwise, this <code>String</code> object is added to the
* pool and a reference to this <code>String</code> object is returned.
* <p>
* It follows that for any two strings <code>s</code> and <code>t</code>,
* <code>s.intern() == t.intern()</code> is <code>true</code>
* if and only if <code>s.equals(t)</code> is <code>true</code>.
* <p>
* All literal strings and string-valued constant expressions are
* interned. String literals are defined in section 3.10.5 of the
* <cite>The Java™ Language Specification</cite>.
*
* @return a string that has the same contents as this string, but is
* guaranteed to be from a pool of unique strings.
*/
public native String intern();
Когда вызывается метод intern, если пул уже содержит строку, равную этому объекту String, как определено равным объектом, возвращается строка из пула. В противном случае этот объект добавляется в пул и возвращается ссылка на этот строковый объект.
Использование Java JNI вызывает собственный метод StringTable.intern, который реализуется С++
\ openjdk7\JDK\SRC\доля\родной\Java\языки\String.c
Java_java_lang_String_intern(JNIEnv *env, jobject this)
{
return JVM_InternString(env, this);
}
\ openjdk7\точка доступа\SRC\доля\ут\примы\jvm.h
/*
* java.lang.String
*/
JNIEXPORT jstring JNICALL
JVM_InternString(JNIEnv *env, jstring str);
\ openjdk7\точка доступа\SRC\доля\Vm\примы\jvm.cpp
// String support ///////////////////////////////////////////////////////////////////////////
JVM_ENTRY(jstring, JVM_InternString(JNIEnv *env, jstring str))
JVMWrapper("JVM_InternString");
JvmtiVMObjectAllocEventCollector oam;
if (str == NULL) return NULL;
oop string = JNIHandles::resolve_non_null(str);
oop result = StringTable::intern(string, CHECK_NULL);
return (jstring) JNIHandles::make_local(env, result);
JVM_END
\ openjdk7\точка доступа\SRC\доля\ут\файлов классов \symbolTable.cpp
oop StringTable::intern(Handle string_or_null, jchar* name,
int len, TRAPS) {
unsigned int hashValue = java_lang_String::hash_string(name, len);
int index = the_table()->hash_to_index(hashValue);
oop string = the_table()->lookup(index, name, len, hashValue);
// Found
if (string != NULL) return string;
// Otherwise, add to symbol to table
return the_table()->basic_add(index, string_or_null, name, len,
hashValue, CHECK_NULL);
}
\ openjdk7\точка доступа\SRC\доля\ут\файлов классов \symbolTable.cpp
oop StringTable::lookup(int index, jchar* name,
int len, unsigned int hash) {
for (HashtableEntry<oop>* l = bucket(index); l != NULL; l = l->next()) {
if (l->hash() == hash) {
if (java_lang_String::equals(l->literal(), name, len)) {
return l->literal();
}
}
}
return NULL;
}
Если вы хотите узнать больше о том, как инженеры oracle меняют логику пула строк в Java 7, ссылка будет полезна для вас. Отчет об ошибках: настройте размер таблицы строк. Пул String реализуется как фиксированная емкость с картой с каждым ведром, содержащим список строк с тем же кодом. Размер пула по умолчанию - 1009.
Для вашего вопроса вы можете написать тестовую программу для сравнения с этим методом, чтобы собрать структуру данных и определить, какой из них лучше.
Ответ 4
Если вы не выполняете сотни миллионов поисковых запросов в секунду, вы не сможете сказать разницу. Если вы выполняете сотни миллионов поисковых запросов в секунду, попробуйте дерево radix. Это очень дорого в памяти, но с этим небольшим набором данных, который не имеет значения.
Как только вы напишете его, профайл.
Ответ 5
Вопрос немного расплывчатый, но самым быстрым алгоритмом согласования строк является машина конечного состояния, то есть алгоритм aho-corasick. Это обобщение алгоритма соответствия кнута-Морриса-Пратта. Если вы просто хотите простой поиск, вы можете попробовать тройное trie или сжатое trie (radix-tree), если пространство имеет значение или даже двоичный поиск.
Ответ 6
Это зависит от того, насколько различны ваши строки или какая у них форма.
Я думаю, что хэш-карта - хорошая идея, если вы готовы взять накладную память. Для всего около 100 строк достаточно первого символа:
String* myStrings[256];
Вы просто посмотрите на первую char вашей строки, чтобы определить, в каком массиве она может быть.
Если ваши строки достаточно гетерогенные (т.е. они обычно не начинаются с одной буквы), коэффициент усиления теоретически равен 256х. Потери a - дополнительные 257 указателей (257 * 64 = 16448 бит) в памяти. Вы можете компенсировать эту потерю, удалив первый символ из фактических сохраненных строк.
Если вы решите масштабировать до двух символов и более, то и преимущества, и неудобства экспоненциальны.
String* myStrings[256][256][256];
Однако, если ваши строки являются специальными и не могут, например, начинаться с любого char или содержать любой char, тогда вы можете уменьшить массив и сопоставить используемые символы с слотом.
char charToSlot[256];
String* myStrings[3];
Например, в этом случае, если ваши строки могут начинаться только с символов 100, 235 и 201, тогда charToSlot [100] = 0, charToSlot [235] = 1 и charToSlot [201] = 2.
Поиск индекса немного медленнее, но влияние памяти минимально. Это может помочь вам, если строки, которыми вы управляете, могут содержать только алфавит в нижнем регистре. Тогда ваша идеальная структура для одного персонажа будет:
char charToSlot[256];
String* myStrings[26];
И его можно упростить:
char charToSlot[256];
String* myStrings[26][26][26];
Если вы не хотите делать какие-либо предположения о своих строках (т.е. они могут содержать что-либо), вы можете реализовать некоторую динамическую индексацию (индексы добавляются, как только они понадобятся, и массив необходимо повторно перенастраивать).
char charToSlot[256];
String**** myStrings;
Другой трюк, если ваши строки различаются по длине и довольно маленькие (длина 5-30), вы можете добавить дополнительный индекс, который снова умножит скорость, только поиск строк с одинаковой длиной.
String* myStrings[30][256][256]...
Если вы считаете, что эти решения слишком тяжелые, вы можете использовать более статистический подход. Вы можете передать одну ветвь нескольким символам. Например, "a", "b", "c" и "d" будут идти одинаково, и у вас будет в 4 раза меньше ветвей. Затем вы вернетесь к списку и еще раз проверьте char на char, если строка равна, с большим шансом получить то, что вы хотите.
Например, если строки могут содержать все 256 символов, но вы не хотите 256, а скорее 8 ветвей, у вас будет:
String* myStrings[8];
И для любого персонажа вы просто разделите его на 32 (очень быстро), чтобы выбрать ветку. Вероятно, это решение, которое я бы рекомендовал для вашей проблемы, поскольку у вас всего около 100 строк, и вам, вероятно, не нужен огромный массив.
Кроме того, этот показатель масштабируется более красиво:
String* myStrings[8][8][8][8]...
Но тогда хранимые массивы могут содержать в 32 раза больше строк, а контент не детерминирован.
Опять же, все зависит от конкретных свойств ваших строк и, что более важно, от того, сколько строк у вас есть. Для действительно огромной строковой базы данных никто не заботится о том, чтобы даже Terabit отображал накладные расходы, если он улучшает скорость поиска с помощью гигантского фактора и удаляет 99,99% повторения.
Ответ 7
Используйте std::unordered_set<std::string>, который хорошо подходит для вашего дела. Вы можете иметь std::set<std::string> вокруг, если вам также нужно выполнить итерацию в порядке.
Если после профилирования вы узнаете, что тратите все свое время на структуру данных, тогда пришло время задать другой вопрос (с точным кодом, который вы будете использовать).
Ответ 8
Trie - лучшее решение для вас.
Я говорю это, потому что у вас мало струн, поэтому идти таким путем было бы лучше.
Вы можете посмотреть мою реализацию trie здесь, на моей ссылке github
https://github.com/prem-ktiw/Algorithmic-Codes/blob/master/Trie/char_trie.cpp
Код хорошо прокомментирован и позволит вам вставлять строку в линейное время, а также искать в линейном времени. Никаких проблем с конфликтами, которые наблюдаются при хешировании.
Динамическое распределение было использовано, поэтому память не будет проблемой.
Единственное, что вы не можете иметь несколько дубликатов одной и той же строки в моей реализации, и нет записи о том, сколько копий строки есть в trie.
Я хотел бы услышать от вас об этом, если потребуется какая-либо помощь.
Ответ 9
Вы можете попробовать двоичный индексный массив, это поле типа c index index struct.
Учебный блог здесь https://minikawoon.quora.com/How-to-search-data-faster-on-big-amount-of-data-in-C-C++
Пример: -
Шаг 1. Определите структуру
typedef struct {
char book_name[30];
char book_description[61];
char book_categories[9];
int book_code;
} my_book_t;
// 160000 size, 10 index field slot
bin_array_t *all_books = bin_array_create(160000, 10);
Шаг 2. Добавьте индекс
if (bin_add_index(all_books, my_book_t, book_name, __def_cstr_sorted_cmp_func__)
&& bin_add_index(all_books, my_book_t, book_categories, __def_cstr_sorted_cmp_func__)
&& bin_add_index(all_books, my_book_t, book_code, __def_int_sorted_cmp_func__)
) {
Шаг 3. Инициализация ваших данных
my_book_t *bk = malloc(sizeof(my_book_t));
strcpy(bk->book_name, "The Duck Story"));
....
...
bin_array_push(all_books, bk );
Шаг 4. Результат поиска eq, lt (меньше), gt (больше)
int data_search = 100;
bin_array_rs *bk_rs= (my_book_t*) ba_search_eq(all_books, my_book_t,
book_code, &data_search);
my_book_t **bks = (my_book_t**)bk_rs->ptrs; // Convert to pointer array
// Loop it
for (i = 0; i < bk_rs->size; i++) {
address_t *add = bks[i];
....
}
Шаг 5. Множественный поиск и внутреннее объединение или объединение
// Join Solution
bin_array_rs *bk_rs=bin_intersect_rs(
bin_intersect_rs(ba_search_gt(...), ba_search_lt(...), true),
bin_intersect_rs(ba_search_gt(...), ba_search_lt(....), true),
true);
// Union Solution
bin_array_rs *bk_rs= bin_union_rs(
bin_union_rs(ba_search_gt(...), ba_search_lt(...), true),
bin_union_rs(ba_search_gt(...), ba_search_lt(....), true),
true);