lo que el autor de los medios nedtries por “in situ”?

Question

I. Sólo se aplicó un tipo de trie bit a bit (basado en nedtries), pero mi código hace mucho De la asignación de memoria (para cada nodo). En contra de mi Implementación, nedtries son reclamados para ser rápido, entre las cosas othet, Debido a su pequeño número de asignación de memoria (si los hay). El autor reclamar su aplicación para estar "in situ", pero ¿qué es lo que realmente significa en este contexto? Y cómo nedtries lograr un pequeño número de asignación de memoria dinámica tal?

PS: Yo sé que las fuentes están disponibles, pero el código es bastante difícil de seguir y no puedo cifra cómo funciona

Answer 1

Me tomó un vistazo al código fuente nedtrie.h. Parece que la razón es "in situ" es que que añadir los datos de contabilidad trie a los objetos que desea almacenar.

Se utiliza la macro NEDTRIE_ENTRY añadir padre / hijo / siguientes enlaces / Prev a la estructura de datos y, a continuación, puede pasar que la estructura de datos para las diversas rutinas trie, que extraer y utilizar aquellos miembros agregados.

Por lo que es "in situ" en el sentido de que aumentar sus estructuras de datos existentes y los códigos de lengüeta trie en eso.

Al menos eso es lo que parece. Hay un montón de bondad macro en ese código así que podría haber conseguido yo confundido (:

Answer 2

Soy el autor, así que esto es para el beneficio de la mayoría de acuerdo con Google que están teniendo dificultades en el uso de manera similar nedtries. Me gustaría agradecer a la gente aquí en stackflow por no hacer comentarios desagradables sobre mí, personalmente, que algunas otras discusiones sobre nedtries hacen.

1. Me temo que no entiendo las dificultades con saber cómo usarlo. El uso es excepcionalmente fácil - simplemente copiar el ejemplo en el archivo 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;
}

declarar su tipo de elemento - aquí Es foo_s struct. Es necesario el NEDTRIE_ENTRY () dentro de lo contrario, puede contener lo que quiera. También es necesario una función clave de generación. Aparte de eso, es bastante repetitivo.

Yo no habría elegido este sistema de macro basada inicialización a mí mismo! Pero es por compatibilidad con el rbtree.h BSD por lo nedtries es muy fácil de cambiar de a cualquier cosa usando rbtree.h BSD.

1. En cuanto a mi uso de "en su lugar" algoritmos, así que supongo que mi falta de espectáculos de formación de informática aquí. Lo que yo llamaría "en su lugar" es cuando sólo se utiliza la memoria pasó a una pieza de código, por lo que si de entregar 64 bytes a una en su lugar algoritmo que sólo tocará que el 64 bytes es decir, que no hará uso de metadatos extra, o asignar parte memoria adicional, o incluso a escribir estado global. Un ejemplo es un buen "En el lugar" donde la aplicación especie Sólo se está ordenando la colección (Y supongo que la pila de hilo) obtiene tocado.

   Por lo tanto, no, nedtries no necesita una asignador de memoria. Almacena toda la datos que necesita en el NEDTRIE_ENTRY y NEDTRIE_HEAD macro expansiones. En otras palabras, cuando usted asigna sus foo_s struct, que hacen todo el asignación de memoria para nedtries.

2. En cuanto a la comprensión de la "macro bondad", es mucho más fácil entender la lógica si se compila como C ++ y luego depurarlo :). los C ++ plantillas de los usos y la construcción depurador se limpia mostrarle Estado en cualquier momento dado. De hecho, todos depuración de mi extremo ocurre en una C ++ acumulación y meticulosamente transcribir cambios el C ++ en macroised C.

3. Por último, antes de que un nuevo lanzamiento, I buscar en Google para las personas que tienen problemas con mi software para ver si Puedo arreglar las cosas y estoy normalmente sorprendido lo que alguien dice la gente de yo y mi software libre. En primer lugar, ¿por qué no las personas que tienen dificultades me pregunta directamente para ¿ayuda? Si sé que hay algo mal con los documentos, a continuación, Puedo solucionarlos - igualmente, preguntar en stackoverflow no me hizo saber inmediatamente que hay un docs problema de fresa en lugar confía en mí encontrarlo próxima versión. Así que todo lo que lo haría es decir que si alguien encuentra una problema con mis documentos, por favor contacta conmigo y decirlo, aunque no haya es un ejemplo de discusión como aquí en stackflow.

Niall

Answer 3

in-situ medios que operan sobre los datos originales (entrada), por lo que los datos de entrada se convierte en los datos de salida. No en el lugar significa que usted tiene datos de entrada y de salida separados, y los datos de entrada no se modifica. in-situ Las operaciones tienen una serie de ventajas - menor huella de caché / memoria, menor ancho de banda de memoria, por lo tanto, por lo general un mejor rendimiento, etc, pero tienen la desventaja de que son destructivos, es decir que pierden la entrada original datos (que puede o puede no importar, dependiendo del caso de uso).

Answer 4

medios en el lugar para operar en los datos de entrada y (posiblemente) actualizarlo. La implicación es que no hay ninguna copia y / traslado de los datos de entrada. Esto puede resultar en pérdida de los datos de entrada valores originales que se tendrá que considerar si es relevante para su caso particular.