что автор nedtries подразумевает под "на месте"?

Question

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

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

Answer 1

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

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

<code>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;</p>

<p>static size_t fookeyfunct(const foo_t *RESTRICT r)
{
  return r->key;
}</p>

<p>NEDTRIE_GENERATE(static, foo_tree_s, foo_s, link, fookeyfunct, NEDTRIE_NOBBLEZEROS(foo_tree_s));</p>

<p>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 finds next largest. Invert the key function to invert this */
  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);
  return 0;
}

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

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

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

   Следовательно нет, недр не нуждается в Распределитель памяти. Он хранит все данные, необходимые для NEDTRIE_ENTRY и расширения макроса NEDTRIE_HEAD. Другими словами, когда вы выделяете ваша структура foo_s, вы делаете все выделение памяти для недр.

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

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

Найл

Answer 2

Я взглянул на исходный код nedtrie.h.Кажется, причина того, что это «на месте», заключается в том, что вы должны добавить данные бухгалтерии для элементов, которые вы хотите сохранить.parent / child / next / prev связывается с вашей структурой данных, и вы можете затем передать эту структуру данных различным подпрограммам trie, которые будут извлекать и использовать эти добавленные элементы.

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

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

Answer 3

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

Answer 4

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