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


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

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

Источник

4 ответа

Решение

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

Макрос NEDTRIE_ENTRY используется для добавления родительских / дочерних / следующих / предысторий в вашу структуру данных, а затем вы можете передать эту структуру данных различным подпрограммам Trie, которые будут извлекать и использовать эти добавленные элементы.

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

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

Источник

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

  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 *RESTRICT 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 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 байтов, т.е. не будет использовать дополнительные метаданные. или выделить некоторую дополнительную память, или действительно записать в глобальное состояние. Хорошим примером является реализация сортировки "на месте", где затрагивается только сортируемая коллекция (и, я полагаю, стек потоков).

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

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

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

Найл

Источник

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

Источник

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

Источник
Другие вопросы по тегам