¿Nombra una estructura de diccionario que almacena claves en un orden predecible?

https://stackoverflow.com/questions/1022269

06-07-2019
|

Pregunta

Nota: Aunque mi contexto particular es Objective-C, mi pregunta en realidad trasciende la elección del lenguaje de programación. Además, lo etiqueté como "subjetivo". ya que alguien se quejará de otra manera, pero personalmente creo que es casi completamente objetivo. Además, soy consciente de esta pregunta SO relacionada , pero dado que este era un problema mayor , Pensé que era mejor hacer esta pregunta por separado. Por favor, no critique la pregunta sin leerla y comprenderla completamente. Gracias!

La mayoría de nosotros estamos familiarizados con el diccionario tipo de datos abstractos que almacena asociaciones clave-valor, ya sea que lo llamemos un mapa, diccionario, matriz asociativa, hash, etc., según nuestro idioma de elección. Una definición simple de un diccionario se puede resumir en tres propiedades:

Se accede a los valores por clave (en lugar de por índice, como una matriz).
Cada clave está asociada a un valor.
Cada clave debe ser única.

Se puede decir que cualquier otra propiedad es una conveniencia o especialización para un propósito particular. Por ejemplo, algunos lenguajes (especialmente los lenguajes de secuencias de comandos como PHP y Python) difuminan la línea entre los diccionarios y las matrices y proporcionan el orden para los diccionarios. Tan útil como puede ser, tales adiciones no son características fundamentales de un diccionario. En un sentido puro, los detalles de implementación reales de un diccionario son irrelevantes.

Para mi pregunta, la observación más importante es que el orden en que se enumeran las claves no está definido & # 8212; un diccionario puede proporcionar claves en el orden que le resulte más conveniente, y depende del cliente organizarlas como desee.

He creado diccionarios personalizados que imponen órdenes de teclas específicas, incluyendo orden natural ordenado (basado en comparaciones de objetos) y orden de inserción . Es obvio nombrar al anterior alguna variante en SortedDictionary (que en realidad ya he implementado), pero el último es más problemático. He visto LinkedHashMap y LinkedMap (Java), < a href = "http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx" rel = "nofollow noreferrer"> OrderedDictionary (.NET), OrderedDictionary (Flash), OrderedDict (Python) y OrderedDictionary (Objetivo-C). Algunos de estos son más maduros, otros son más pruebas de concepto.

LinkedHashMap se nombra según la implementación en la tradición de las colecciones de Java & # 8212; " vinculado " porque usa una lista doblemente vinculada para rastrear el orden de inserción, y '' hash '' porque subclasifica HashMap. Además del hecho de que el usuario no debería tener que preocuparse por eso, el nombre de la clase ni siquiera indica lo que hace. El uso de ordenado parece ser el consenso entre el código existente, pero las búsquedas en la web sobre este tema también revelaron una confusión comprensible entre " ordenado " y "ordenado", y siento lo mismo. La implementación de .NET incluso tiene un comentario sobre el nombre incorrecto aparente, y sugiere que debería ser "IndexedDictionary". en su lugar, debido al hecho de que puede recuperar e insertar objetos en un punto específico del pedido.

Estoy diseñando un framework y API y quiero nombrar la clase de la manera más inteligente posible. Desde mi punto de vista, indexado probablemente funcionaría (dependiendo de cómo la gente lo interprete, y según la funcionalidad anunciada del diccionario), ordenado es impreciso y tiene demasiado potencial para confusión, y vinculado " está justo fuera " (disculpas a Monty Python). ;-)

Como usuario, ¿qué nombre tendría más sentido para usted? ¿Hay un nombre en particular que diga exactamente lo que hace la clase? (No soy reacio a usar nombres un poco más largos como InsertionOrderDictionary si corresponde).

Editar: Otra gran posibilidad (discutida en mi respuesta a continuación) es IndexedDictionary . Realmente no me gusta " orden de inserción " porque no tiene sentido si permite que el usuario inserte claves en un índice específico, reordene las claves, etc.

Solución

Voto OrderedDictionary, por las siguientes razones:

" Indexado " nunca se usa en las clases de Cocoa, excepto en una instancia. Siempre aparece como un sustantivo (NSIndexSet, NSIndexPath, objectAtIndex :, etc.). Solo hay una instancia cuando " Index " aparece como un verbo, que está en NSPropertyDescription's '' indexado '' propiedad: isIndexed y setIndexed. NSPropertyDescription es más o menos análogo a una columna de tabla en una base de datos, donde '' indexación '' se refiere a la optimización para acelerar los tiempos de búsqueda. Por lo tanto, tendría sentido que con NSPropertyDescription sea parte del marco de Core Data, que '' está indexado '' y "setIndexed" sería equivalente a un índice en una base de datos SQL. Por lo tanto, llamarlo "IndexedDictionary" parecería redundante, ya que los índices en las bases de datos se crean para acelerar el tiempo de búsqueda, pero un diccionario ya tiene O (1) tiempo de búsqueda. Sin embargo, para llamarlo "IndexDictionary" también sería un nombre inapropiado, ya que un " índice " en cacao se refiere a la posición, no al orden. Los dos son semánticamente diferentes.

Entiendo su preocupación por "OrderedDictionary", pero el precedente ya se ha establecido en Cocoa. Cuando los usuarios desean mantener una secuencia específica, usan " ordenado " ;: - [NSApplicationpedDocuments], - [NSWindowledIndex], - [NSApplicationledWindows], etc. Entonces, John Pirie tiene sobre todo la idea correcta.

Sin embargo, no desea que la inserción en el diccionario sea una carga para sus usuarios. Querrán crear un diccionario una vez y luego hacer que mantenga un orden apropiado. Ni siquiera querrán solicitar objetos en un orden específico. La especificación del pedido debe hacerse durante la inicialización.

Por lo tanto, recomiendo convertir OrderedDictonary en un grupo de clases, con subclases privadas de InsertionOrderDictionary y NaturalOrderDictionary y CustomOrderDictionary. Luego, el usuario simplemente crea un OrderedDictionary de esta manera:

OrderedDictionary * dict = [[OrderedDictionary alloc] initWithOrder:kInsertionOrder];
//or kNaturalOrder, etc

Para un CustomOrderDictionary, puede hacer que le den un selector de comparación, o incluso (si están ejecutando 10.6) un bloque. Creo que esto proporcionaría la mayor flexibilidad para una futura expansión y al mismo tiempo mantendría un nombre apropiado.

Otros consejos

Yo voto por InsertionOrderDictionary . Lo has clavado.

Fuerte voto por OrderedDictionary.

La palabra " ordenado " significa exactamente lo que está anunciando: que al iterar a través de una lista de artículos, hay un orden definido para la selección de esos artículos. " Indexado " es una palabra de implementación: habla más sobre cómo se logra el pedido. Índice, lista vinculada, árbol ... al usuario no le importa; ese aspecto de la estructura de datos debe estar oculto. " Pedido " es la palabra exacta para la función adicional que está ofreciendo, independientemente de cómo lo haga.

Además, parece que la opción de ordenar podría ser a elección del usuario. ¿Alguna razón por la que no pudo crear métodos en su tipo de datos que le permitan al usuario cambiar, por ejemplo, el orden alfabético al orden de inserción? En el caso predeterminado, un usuario elegiría un pedido particular y se apegaría a él, en cuyo caso la implementación no sería menos eficiente que si creara subclases especializadas para cada método de pedido. Y en algunos casos menos utilizados, el desarrollador podría desear utilizar cualquiera de una variedad de ordenaciones diferentes para los mismos datos, dependiendo del contexto de la aplicación. (Puedo pensar en proyectos específicos en los que he trabajado donde me hubiera encantado tener una estructura de datos disponible).

Llámelo OrderedDictionary, porque eso es precisamente lo que es. (Francamente, tengo más problemas con el uso de la palabra '' Diccionario '', porque esa palabra implica en gran medida ordenar, donde las implementaciones populares de la misma no lo proporcionan, pero esa es mi molestia. Realmente deberías poder decir "Diccionario" y saber que el orden es alfabético, porque eso es lo que es un diccionario, pero ese argumento es demasiado tarde para las implementaciones existentes en los idiomas populares. Y permitir que el usuario acceda en el orden que elija.

Desde que publiqué esta pregunta, estoy empezando a inclinarme hacia algo como IndexedDictionary o IndexableDictionary . Si bien es útil poder mantener el orden de las claves arbitrarias, limitar eso al orden de inserción solo parece una restricción innecesaria. Además, mi clase ya es compatible con indexOfKey: y keyAtIndex: , que son (deliberadamente) análogos al indexOfObject: y objectAtIndex de <<>> de NSArray. / código>. Estoy considerando agregar insertObject: forKey: atIndex : que coincide con el insertObject: atIndex: de NSMutableArray



 Todos saben que insertar en el medio de una matriz es ineficiente, pero eso no significa que no se nos debería permitir en las raras ocasiones que sea realmente útil. (Además, la implementación podría usar secretamente una lista doblemente vinculada o cualquier otra estructura adecuada para rastrear el pedido si es necesario ...) 

 La gran pregunta: está " indexado " o "indexable" tan vago o potencialmente confuso como " ordenado " ;? ¿La gente pensaría en índices de bases de datos, o índices de libros, etc.? ¿Sería perjudicial si asumieran que se implementó con una matriz, o podría simplificar la comprensión del usuario de la funcionalidad? 



  Editar:  este nombre tiene aún más sentido dado el hecho de que estoy considerando agregar métodos que funcionen con un  NSIndexSet  en el futuro. (NSArray tiene   -objectsAtIndexes:  , así como métodos para agregar / eliminar observadores de objetos en índices dados.)



	
		
	
	
			 ¿Qué pasa con KeyedArray? 
	


	
		
	
	
			 Como dijiste en tu último párrafo, creo que InsertionOrder (ed) Dict (ionary) es bastante inequívoco; No veo cómo se podría interpretar de otra manera que no sea que las claves se devolverían en el orden en que se insertaron. 
	


	
		
	
	
			 Al desacoplar el orden indexado del orden de inserción, ¿no se reduce a mantener una matriz y un Diccionario en un solo objeto? Supongo que mi voto para este tipo de objeto es IndexedKeyDictionary 

 En C #: 

public class IndexedKeyDictionary<TKey, TValue> { 

  List<TKey> _keys;
  Dictionary<TKey, TValue> _dictionary;
  ...

  public GetValueAtIndex(int index) {
    return _dictionary[_keys[index]];
  }

  public Insert(TKey key, TValue val, int index) {
    _dictionary.Add(key, val);

    // do some array massaging (splice, etc.) to fit the new key
    _keys[index] = key;
  }

  public SwapKeyIndexes(TKey k1, TKey k2) {
    // swap the indexes of k1 and k2, assuming they exist in _keys
  }
}


 Lo que sería realmente genial son los valores indexados ... así que tenemos una manera de ordenar los valores y obtener el nuevo orden de las claves. Como si los valores fueran coordenadas de gráfico, y pudiéramos leer las claves (nombres de bin) a medida que avanzamos / descendemos a lo largo del plano de coordenadas. ¿Cómo llamarías a esa estructura de datos? Un IndexedValueDictionary? 
	


	
		
	
	
			 A primera vista estoy con la primera respuesta: InsertionOrderDictionary, aunque es un poco ambiguo en cuanto a qué " InsertionOrder " significa a primera vista. 

 Lo que estás describiendo me suena casi exactamente como un mapa C ++ STL. Por lo que entiendo, un mapa es un diccionario que tiene reglas adicionales, incluido el pedido. El STL simplemente lo llama "mapa", que creo que es bastante adecuado. El truco con el mapa es que no se puede dar un guiño a la herencia sin hacerla redundante, es decir, '' MapDictionary ''. Eso es demasiado redundante. " Mapa " es un poco demasiado básico y deja mucho espacio para malas interpretaciones. 

 Aunque " CHMap " podría no ser una mala elección después de mirar su enlace de documentación. 

 Tal vez " CHMappedDictionary " ;? =) 

 La mejor de las suertes. 

 Editar: Gracias por la aclaración, aprendes algo nuevo todos los días. =) 
	


	
		
	
	
			 ¿Es la única diferencia que  allKeys  devuelve claves en un orden específico? Si es así, simplemente agregaría los métodos  allKeysSorted  y  allKeysOrderdByInsertion  a la API estándar  NSDictionary . 

 ¿Cuál es el objetivo de este diccionario de orden de inserción? ¿Qué beneficios le da al programador frente a una matriz?



	
		
			Licenciado bajo: CC-BY-SA con atribución
			No afiliado a StackOverflow