Что является лучшим, автоматически заполняют/предлагают алгоритм, datastructure [C++/C]
@Keith,
я соглашаюсь со всеми Вашими правилами кроме № 4. Добавление финализатора должно только быть сделано при очень определенных обстоятельствах. Если класс использует неуправляемые ресурсы, те должны быть очищены в Вашем Располагать (bool) функцию. Эта та же функция должна только управляемые ресурсы очистки, когда bool верен. Добавление финализатора добавляет стоимость сложности для использования Вашего объекта как каждый раз, когда Вы создаете новый экземпляр, это должно также быть помещено в очередь завершения, которая проверяется каждый раз, когда GC выполняет цикл сбора. Эффективно, это означает, что Ваш объект переживает один цикл/поколение дольше, чем это должно так, финализатор может быть выполнен. Финализатор не должен считаться "системой поддержки".
GC только выполнит цикл сбора, когда он решит, что существует недостаточно доступной памяти в "куче" Gen0 для выполнения следующего выделения, если Вы не "помогаете" ему путем вызова GC.Collect () для принуждения внеполосного набора.
нижняя строка - то, что, неважно, что, только знает GC, как высвободить средства путем вызова Расположить метода (и возможно финализатор, если Вы реализованы). Это до того метода, чтобы "сделать правильную вещь" и очистить любые используемые неуправляемые ресурсы и дать любым другим управляемым ресурсам команду называть их Располагающего метод. Очень эффективно в том, что это делает и может самооптимизировать в большой степени, пока этому не помогают внеполосные циклы сбора. Однако за исключением вызова GC.Collect явно Вы не имеете никакого контроля, когда и в том, от каких объектов порядка избавятся и память освобождена.
3 ответа
trie - это структура данных, которая может использоваться для быстрого поиска слов, соответствующих префиксу.
Изменить: вот пример, показывающий, как использовать один для реализации autocomplete http://rmandvikar.blogspot.com/2008/10/trie-examples.html
Вот сравнение 3 различных реализаций автозаполнения (хотя это на Java, а не на C ++) .
* In-Memory Trie
* In-Memory Relational Database
* Java Set
При поиске ключей дерево немного быстрее, чем реализация Set. И дерево, и набор работают немного быстрее, чем решение для реляционной базы данных.
Стоимость установки набора ниже, чем у решения на основе дерева или базы данных. Вам нужно будет решить, будете ли вы часто создавать новые «наборы слов» или скорость поиска будет более приоритетной.
Эти результаты находятся на Java,
For large datasets, a good candidate for the backend would be Ternary search trees. They combine the best of two worlds: the low space overhead of binary search trees and the character-based time efficiency of digital search tries.
See in Dr. Dobbs Journal: http://www.ddj.com/windows/184410528
The goal is the fast retrieval of a finite resultset as the user types in. Lets first consider that to search "computer science" you can start typing from "computer" or "science" but not "omputer". So, given a phrase, generate the sub-phrases starting with a word. Now for each of the phrases, feed them into the TST (ternary search tree). Each node in the TST will represent a prefix of a phrase that has been typed so far. We will store the best 10 (say) results for that prefix in that node. If there are many more candidates than the finite amount of results (10 here) for a node, there should be a ranking function to resolve competition between two results.
The tree can be built once every few hours, depending on the dynamism of the data. If the data is in real time, then I guess some other algorithm will give a better balance. In this case, the absolute requirement is the lightning-fast retrieval of results for every keystroke typed which it does very well.
More complications will arise if the suggestion of spelling corrections is involved. In that case, the edit distance algorithms will have to be considered as well.
For small datasets like a list of countries, a simple implementation of Trie will do. If you are going to implement such an autocomplete drop-down in a web application, the autocomplete widget of YUI3 will do everything for you after you provide the data in a list. If you use YUI3 as just the frontend for an autocomplete backed by large data, make the TST based web services in C++, and then use script node data source of the autocomplete widget to fetch data from the web service instead of a simple list.
For a simple solution : you generate a 'candidate' with a minimum edit (Levenshtein) distance (1 or 2) then you test the existence of the candidate with a hash container (set will suffice for a simple soltion, then use unordered_set from the tr1 or boost).
Example: You wrote carr and you want car. arr is generated by 1 deletion. Is arr in your unordered_set ? No. crr is generated by 1 deletion. Is crr in your unordered_set ? No. car is generated by 1 deletion. Is car in your unordered_set ? Yes, you win.
Of course there's insertion, deletion, transposition etc...
You see that your algorithm for generating candidates is really where you’re wasting time, especially if you have a very little unordered_set.