Что автор Nedtries означает «на месте»?

Question

I. Только что реализовал своего рода бить Trie (на основе Nedtries), но мой код делает много распределения памяти (для каждого узла). Вопреки моей реализации, претенденты на то, чтобы быть быстрым, среди отдельных вещей, из -за их небольшого количества распределения памяти (если таковые имеются). Автор утверждает, что его реализация «на месте», но что это на самом деле означает в этом контексте? И как Недтрии достигают такого небольшого количества динамического распределения памяти?

PS: я знаю, что источники доступны, но код довольно сложно следовать, и я не могу понять, как он работает

Answer 1

Я посмотрел на исходный код Nedtrie.h. Кажется, что причина, по которой это «на месте», заключается в том, что ты Придется добавить данные о бухгалтерии Trie к предметам, которые вы хотите хранить.

Вы используете макрос Nedtrie_entry, чтобы добавить ссылки на родитель/ребенок/следующий/Preving в структуру данных, и затем вы можете передать эту структуру данных в различные процедуры TRIE, которые будут извлекать и использовать эти добавленные участники.

Таким образом, это «на месте» в том смысле, что вы дополняете свои существующие структуры данных и код Trie Code Piggybacks на это.

По крайней мере, это то, на что это выглядит. В этом коде есть много макрога, чтобы я мог запутаться (:

Answer 2

Я автор, так что это в интересах многих в соответствии с Google, у которых также возникают трудности с использованием Nedtries. Я хотел бы поблагодарить людей здесь, на Stackflow за то, что они не сделали неприятные комментарии обо мне лично, что делают некоторые другие дискуссии о Недтриях.

1. Я боюсь, что не понимаю трудностей с тем, чтобы узнать, как его использовать. Использование исключительно просто - просто скопируйте пример в файле readme.html:

typedef struct foo_s foo_t;
struct foo_s {
  NEDTRIE_ENTRY(foo_t) link;
  size_t key;
};
typedef struct foo_tree_s foo_tree_t;
NEDTRIE_HEAD(foo_tree_s, foo_t);
static foo_tree_t footree;


static size_t fookeyfunct (const foo_t *ограничить r) {return r-> key; }

Nedtrie_generate (static, foo_tree_s, foo_s, link, fookeyfunct, nedtrie_nobblezeros (foo_tree_s));

int main (void) {foo_t a, b, c, *r; Nedtrie_init (& footree); A.Key = 2; Nedtrie_insert (foo_tree_s, & footree, & a); B.Key = 6; Nedtrie_insert (foo_tree_s, & footree, & b); r = nedtrie_find (foo_tree_s, & footree, & b); assert (r == & b); C.Key = 5; r = nedtrie_nfind (foo_tree_s, & footree, & c); assert (r == & b); /* Nfind находит следующего крупнейшего. Инвертировать функцию ключа, чтобы инвертировать это */ nedtrie_remove (foo_tree_s, & footree, & a); Nedtrie_foreach (r, foo_tree_s, & footree) {printf (" %p, %u  n", r, r-> key); } Nedtrie_prev (foo_tree_s, & footree, & a); возврат 0; }

Вы объявляете свой тип элемента - вот это struct foo_s. Вам нужен Nedtrie_Entry () внутри него, иначе он может содержать все, что вам нравится. Вам также нужна функция генерирования ключей. Кроме этого, это довольно шаблон.

Я бы сам не выбрал эту систему инициализации на основе макросов! Но это для совместимости с BSD rbtree.h таким образом, что Nedtries очень легко заменить на все, используя BSD rbtree.h.

1. Что касается моего использования алгоритмов «на месте», ну, я думаю, что у меня отсутствие обучения информатике показывает здесь. То, что я бы назвал «на месте», - это когда вы используете только память, передаваемую в кусок кода, поэтому, если вы передадите 64 байта на алгоритм на месте, это будет касаться только 64 байта, то есть он не будет использовать дополнительные метаданные , или распределить дополнительную память или писать в глобальное состояние. Хорошим примером является реализация сортировки «на месте», в которой сортируется только коллекция (и я полагаю, стек потоков) касается.

   Следовательно, нет, Nedtries не нужен распределитель памяти. В нем хранится все данные, которые ему нужны в расширении макросов Nedtrie_entry и Nedtrie_head. Другими словами, когда вы распределяете свою структуру foo_s, вы делаете все распределение памяти для Nedtries.

2. Что касается понимания «макрога», гораздо легче понять логику, если вы составляете ее как C ++, а затем отлаживать ее :). Сборка C ++ использует шаблоны, и отладчик будет чисто показывать вас в любой момент времени. На самом деле, вся отладка с моей стороны происходит в сборке C ++, и я тщательно транскрибирую изменения C ++ в макрос. C.

3. Наконец, перед новым выпуском я ищу Google для людей, имеющих проблемы с моим программным обеспечением, чтобы увидеть, смогу ли я что -то исправить, и я обычно поражаю то, что кто -то говорит обо мне и моем бесплатном программном обеспечении. Во -первых, почему у этих людей не было трудности прямо за помощью? Если я знаю, что с документами что -то не так, то я могу их исправить - в равной степени, спрашивая на Stackoverflow не сразу сообщить мне, что есть проблема с документами, скорее полагаясь на то, чтобы найти его в следующем выпуске. Поэтому, я бы сказал, это то, что если кто -то найдет проблему с моими документами, пожалуйста, напишите мне и скажите об этом, даже если есть обсуждение, как здесь, на Stackflow.

Найл

Answer 3

На месте означает, что вы работаете на исходных (входных) данных, поэтому входные данные становятся выходными данными. Не на месте означает, что у вас есть отдельные входные и выходные данные, а входные данные не изменяются. На месте Операции имеют ряд преимуществ - меньше следов кэша/памяти, более низкая полоса пропускания памяти, следовательно, обычно лучшая производительность и т. Д., Но они имеют недостаток, что они разрушительны, то есть вы теряете исходные входные данные (которые могут или не могут иметь значение, в зависимости от в случае использования).

Answer 4

На месте означает работать на входных данных и (возможно) обновить их. Подразумевается, что нет копирования и/перемещения входных данных. Это может привести к потере исходных значений входных данных, которые вам необходимо рассмотреть, если это актуально для вашего конкретного случая.