¿Cómo comunicar que el orden de inserción es importante en un mapa?

24

Estoy buscando un conjunto de tuplas de la base de datos y poniéndolo en un mapa. La consulta de la base de datos es costosa.

No existe un orden natural obvio de los elementos en el mapa, pero el orden de inserción es importante. Ordenar el mapa sería una operación pesada, por lo que quiero evitar hacerlo, dado que el resultado de la consulta ya está ordenado de la manera que lo quiero. Por lo tanto, solo almaceno el resultado de la consulta en a LinkedHashMapy devuelvo el mapa desde un método DAO:

public LinkedHashMap<Key, Value> fetchData()

Tengo un método processDataque debería procesar un poco en el mapa: modificar algunos valores y agregar nuevas claves / valores. Se define como

public void processData(LinkedHashMap<Key, Value> data) {...}

Sin embargo, varios linters (Sonar, etc.) se quejan de que el tipo de 'datos' debería ser una interfaz como 'Map' en lugar de la implementación "LinkedHashMap" ( squid S1319 ).
Básicamente está diciendo que debería tener

public void processData(Map<Key, Value> data) {...}

Pero quiero que la firma del método diga que el orden del mapa es importante , es importante para el algoritmo processData, para que mi método no se pase a cualquier mapa aleatorio.

No quiero usarlo SortedMapporque (del javadoc dejava.util.SortedMap ) "se ordena de acuerdo con el orden natural de sus claves, o por un Comparador que normalmente se proporciona en el momento de la creación del mapa ordenado".

Mis claves no tienen un orden natural , y crear un Comparador para no hacer nada parece detallado.

Y todavía quisiera que fuera un mapa, para aprovecharlo puty evitar claves duplicadas, etc. Si no, datapodría haber sido un List<Map.Entry<Key, Value>>.

Entonces, ¿cómo puedo decir que mi método quiere un mapa que ya está ordenado ? Lamentablemente, no hay java.util.LinkedMapinterfaz, o habría usado eso.

Vidar S. Ramdal
fuente

Respuestas:

56

Así que usa LinkedHashMap.

, debe usar Mapuna implementación específica siempre que sea posible, y , esta es la mejor práctica.

Dicho esto, esta es una situación extrañamente específica en la que la implementación de Maprealmente importa. Esto no será cierto para el 99.9% de los casos en su código cuando lo use Map, y aún aquí está, en esta situación de 0.1%. Sonar no puede saber esto, por lo que Sonar simplemente le dice que evite usar la implementación específica porque sería correcta en la mayoría de los casos.

Yo diría que si puede defender el uso de una implementación específica, no intente poner lápiz labial en un cerdo. Necesitas un LinkedHashMap, no un Map.

Dicho esto, si eres nuevo en programación y te topas con esta respuesta, no pienses que esto te permite ir en contra de las mejores prácticas porque no es así. Pero cuando reemplazar una implementación por otra no es aceptable, lo único que puede hacer es usar esa implementación específica y ser condenado a Sonar.

Neil
fuente
1
Enfoque pragmático, que me gusta.
Vidar S. Ramdal
20
Estoy casi completamente de acuerdo con la respuesta. Solo diría que no estás condenado a Sonar. Siempre puede configurarlo para ignorar ese error / advertencia en particular. Ver stackoverflow.com/questions/10971968/…
Vladimir Stokic
11
if you are new to programming and stumble upon this answer, don't think this allows you to go against best practice because it doesn't.- Un buen consejo, si existiera la "mejor práctica". Un mejor consejo: aprenda a tomar las decisiones correctas. Siga la práctica si tiene sentido, pero deje que las herramientas y las autoridades guíen su proceso de pensamiento, no lo dicten.
Robert Harvey
13
Nota: cuando el sonar le informe algo, puede cerrarlo como "no se resolverá" y dejar una nota de por qué no lo hará. Como tal, no solo el sonar se detendrá para molestarte, sino que tendrás un rastreador de por qué lo hiciste.
Walfrat
2
Creo que el aspecto que hace de esto una excepción al principio general es que LinkedHashMap tiene un contrato que es específico para esa implementación y no se expresa en ninguna interfaz. Este no es el caso habitual. Entonces, la única forma de expresar la dependencia de ese contrato es usar el tipo de implementación.
Dana
21

Estás luchando contra tres cosas:

Primero es la biblioteca de contenedores de Java. Nada en su taxonomía le brinda una forma de determinar si la clase itera o no en un orden predecible. No hay una IteratesInInsertedOrderMapinterfaz que pueda implementarse LinkedHashMap, lo que hace que la verificación de tipos (y el uso de implementaciones alternativas que se comporten de la misma manera) sea imposible. Probablemente sea por diseño, porque el espíritu es que realmente se supone que debes ser capaz de lidiar con objetos que se comportan como lo abstracto Map.

En segundo lugar, está la creencia de que lo que dice tu linter debe ser tratado como un evangelio y que ignorar todo lo que dice es malo. Al contrario de lo que pasa por las buenas prácticas en estos días, no se supone que las advertencias de linter sean barreras para llamar a su código correctamente. Son indicaciones para razonar sobre el código que ha escrito y utilizar su experiencia y criterio para determinar si la advertencia está justificada o no. Las advertencias injustificadas son la razón por la cual casi todas las herramientas de análisis estático proporcionan un mecanismo para decirle que ha examinado el código, cree que lo que está haciendo está bien y que no deberían quejarse en el futuro.

Tercero, y esto es probablemente el meollo de esto, LinkedHashMappuede ser la herramienta incorrecta para el trabajo. Los mapas están destinados al acceso aleatorio, no ordenado. Si processData()simplemente itera sobre los registros en orden y no necesita encontrar otros registros por clave, está obligando a una implementación específica de Maphacer el trabajo de a List. Por otro lado, si necesita ambos, LinkedHashMapes la herramienta adecuada porque se sabe que hace lo que quiere y está más que justificado para solicitarlo.

Blrfl
fuente
2
"LinkedHashMap puede ser la herramienta incorrecta para el trabajo". Si quizas. Cuando digo que necesito un OrderedMap, también podría decir UniqueList. Siempre que se trate de algún tipo de colección con un orden de iteración definido, que sobrescribe los duplicados en la inserción.
Vidar S. Ramdal
2
@ VidarS.Ramdal La consulta de la base de datos sería el lugar ideal para eliminar los duplicados. Si su base de datos no puede hacer eso, siempre puede mantener un temporario Setde solo las claves mientras construye la lista como una forma de detectarlas.
Blrfl
Oh, veo que he causado confusión. Sí, el resultado de la consulta de la base de datos no contiene duplicados. Pero processDatamodifica el mapa, reemplaza algunos valores e introduce nuevas claves / valores. Por processDatalo tanto, podría introducir duplicados si estaba operando en algo diferente a a Map.
Vidar S. Ramdal
77
@ VidarS.Ramdal: Parece que necesitas escribir tu propio UniqueList(o OrderedUniqueList) y usarlo. Es bastante fácil y hace que su uso previsto sea más claro.
TMN
2
@ TMN Sí, he comenzado a pensar en esa dirección. Si desea publicar su sugerencia como respuesta, sin duda obtendrá mi voto positivo.
Vidar S. Ramdal
15

Si todo lo que está obteniendo LinkedHashMapes la capacidad de sobrescribir duplicados, pero realmente lo está usando como un List, entonces sugeriría que es mejor comunicar ese uso con su propia Listimplementación personalizada . Puede basar en una clase de colecciones Java existente y simplemente ignorar cualquiera addy removemétodos para actualizar el almacén de respaldo y no perder de vista la clave para garantizar la unicidad. Darle a este un nombre distintivo como ProcessingListdejará en claro que los argumentos presentados a su processDatamétodo deben manejarse de una manera particular.

TMN
fuente
55
Esta puede ser una buena idea de todos modos. De hecho, incluso puede tener un archivo de una línea que se cree ProcessingListcomo un alias para LinkedHashMap: siempre puede decidir reemplazarlo por algo más tarde, siempre que mantenga intacta la interfaz pública.
CompuChip
11

Te escucho decir: "Tengo una parte de mi sistema que produce un LinkedHashMap, y en otra parte de mi sistema necesito aceptar solo objetos LinkedHashMap que fueron producidos por la primera parte, ya que los producidos por algún otro proceso ganaron" no funciona correctamente ".

Eso me hace pensar que el problema aquí es en realidad que estás tratando de usar LinkedHashMap, ya que se ajusta principalmente a los datos que estás buscando, pero en realidad no se puede sustituir por ninguna otra instancia que las que creas. Lo que realmente quiere hacer es crear su propia interfaz / clase, que es lo que crea su primera parte y consume su segunda parte. Puede envolver el LinkedHashMap "real" y proporcionar un captador de mapas o implementar la interfaz del mapa.

Esto es un poco diferente de la respuesta de CandiedOrange, ya que recomendaría encapsular el Mapa real (y delegar llamadas según sea necesario) en lugar de extenderlo. A veces es una de esas guerras santas de estilo, pero seguro que me parece que no es "Un mapa con algunas cosas adicionales", es "Mi bolsa de información de estado útil, que puedo representar internamente con un mapa".

Si tuviera dos variables que necesitara transmitir de esta manera, probablemente habría hecho una clase sin pensar demasiado en ello. Pero a veces es útil tener una clase incluso si es solo una variable miembro, solo porque es lógicamente la misma cosa, no un "valor" sino "el resultado de mi operación con la que necesito hacer cosas más adelante".


fuente
Me gusta pensar - He estado allí :) MyBagOfUsefulInformationnecesitaría un método (o constructor) para poblarlo: MyBagOfUsefulInformation.populate(SomeType data). Pero datatendría que ser el resultado de la consulta ordenada. Entonces, ¿qué sería SomeType, si no LinkedHashMap? No estoy seguro de poder romper esta captura 22.
Vidar S. Ramdal
¿Por qué MyBagOfUsefulInformationel DAO no puede crearlo o lo que sea que esté generando los datos en su sistema? ¿Por qué necesita exponer el mapa subyacente al resto de su código fuera del productor y consumidor de la Bolsa?
Dependiendo de su arquitectura, es posible que pueda usar un constructor privado / protegido / solo paquete para asegurar que el objeto solo pueda ser creado por el productor que desea. O puede que solo necesite hacerlo como una convención, que solo puede ser creado por la "fábrica" ​​correcta.
Sí, terminé haciendo algo similar, pasando MyBagOfUsefulInformationcomo parámetro al método DAO: softwareengineering.stackexchange.com/a/360079/52573
Vidar S. Ramdal el
4

LinkedHashMap es el único mapa de Java que tiene la función de orden de inserción que está buscando. Por lo tanto, descartar el principio de inversión de dependencia es tentador y quizás incluso práctico. Primero, sin embargo, considere lo que se necesitaría para seguirlo. Esto es lo que SOLID le pediría que haga.

Nota: reemplace el nombre Ramdalcon un nombre descriptivo que comunique que el consumidor de esta interfaz es el propietario de esta interfaz. Lo que lo convierte en la autoridad que decide si el orden de inserción es importante. Si solo llamas a esto InsertionOrderMap, realmente has perdido el punto.

public interface Ramdal {
    //ISP asks for just the methods that processData() actually uses.
    ...
}

public class RamdalLinkedHashMap extends LinkedHashMap implements Ramdal{} 

Ramdal<Key, Value> ramdal = new RamdalLinkedHashMap<>();

ramdal.put(key1, value1);
ramdal.put(key2, value2);

processData(ramdal);

¿Es este un gran diseño por adelantado? Tal vez, depende de la probabilidad de que creas que necesitarás una implementación además LinkedHashMap. Pero si no está siguiendo DIP solo porque sería un gran dolor, no creo que la placa de la caldera sea más dolorosa que esto. Este es el patrón que uso cuando deseo que el código intocable implemente una interfaz que no lo hace. La parte más dolorosa es pensar en buenos nombres.

naranja confitada
fuente
2
Me gusta el nombre!
Vidar S. Ramdal
1

Gracias por muchas buenas sugerencias y reflexiones.

Terminé extendiendo la creación de una nueva clase de mapa, haciendo processDataun método de instancia:

class DataMap extends LinkedHashMap<Key, Value> {

   processData();

}

Luego refactoré el método DAO para que no devuelva un mapa, sino que tome un targetmapa como parámetro:

public void fetchData(Map<Key, Value> target) {
  ...
  // for each result row
  target.put(key, value);
}

Por lo tanto, rellenar DataMapy procesar los datos ahora es un proceso de dos pasos, lo cual está bien, ya que hay algunas otras variables que forman parte del algoritmo, que proviene de otros lugares.

public DataMap fetchDataMap() {
  var dataMap = new DataMap();
  dao.fetchData(dataMap);
  return dataMap;
}

Esto permite que la implementación de mi mapa controle cómo se insertan las entradas en él y oculta el requisito de pedido; ahora es un detalle de implementación DataMap.

Vidar S. Ramdal
fuente
0

Si desea comunicar que la estructura de datos que utilizó está allí por algún motivo, agregue un comentario sobre la firma del método. Si otro desarrollador en el futuro se encuentra con esta línea de código y nota una advertencia de herramienta, también podrían notar el comentario y abstenerse de "solucionar" el problema. Si no hay ningún comentario, nada les impedirá cambiar la firma.

Suprimir advertencias es inferior a comentar en mi opinión, porque la supresión en sí misma no indica la razón por la cual se suprimió la advertencia. Una combinación de supresión de advertencia y comentario también estará bien.

Kapol
fuente
0

Entonces, déjame tratar de entender tu contexto aquí:

... el orden de inserción importa ... Ordenar el mapa sería una operación pesada ...

... el resultado de la consulta ya está ordenado como lo quiero

Ahora, lo que estás haciendo actualmente:

Estoy buscando un conjunto de tuplas de la base de datos y poniéndolo en un mapa ...

Y aquí está tu código actual:

public void processData(LinkedHashMap<Key, Value> data) {...}

Mi sugerencia es hacer lo siguiente:

  • Use la inyección de dependencia e inyecte un poco de MyTupleRepository en el método de procesamiento (MyTupleRepository es una interfaz implementada por objetos que recuperan sus objetos de tupla, generalmente de DB);
  • internamente al método de procesamiento, coloque los datos del repositorio (también conocido como DB, que ya devuelve datos ordenados) en la colección LinkedHashMap específica, porque este es un detalle interno del algoritmo de procesamiento (porque depende de cómo se organizan los datos en la estructura de datos) );
  • Tenga en cuenta que esto es más o menos lo que ya está haciendo, pero en este caso esto se haría dentro del método de procesamiento. Su repositorio se instancia en otro lugar (ya tiene una clase que devuelve datos, este es el repositorio en este ejemplo)

Ejemplo de código

public interface MyTupleRepository {
    Collection<MyTuple> GetAll();
}

//Concrete implementation of data access object, that retrieves 
//your tuples from DB; this data is already ordered by the query
public class DbMyTupleRepository implements MyTupleRepository { }

//Injects some abstraction of repository into the processing method,
//but make it clear that some exception might be thrown if data is not
//arranged in some specific way you need
public void processData(MyTupleRepository tupleRepo) throws DataNotOrderedException {

    LinkedHashMap<Key, Value> data = new LinkedHashMap<Key, Value>();

    //Represents the query to DB, that already returns ordered data
    Collection<MyTuple> myTuples = tupleRepo.GetAll();

    //Optional: this would throw some exception if data is not ordered 
    Validate(myTuples);

    for (MyTupleData t : myTuples) {
        data.put(t.key, t.value);
    }

    //Perform the processing using LinkedHashMap...
    ...
}

Supongo que esto eliminaría la advertencia de Sonar y también especificaría en el diseño específico de datos de la firma requerido por el método de procesamiento.

Emerson Cardoso
fuente
Hmm, pero ¿cómo se instanciaría el repositorio? ¿No sería esto simplemente mover el problema a otro lugar (a dónde MyTupleRepositoryse crea?)
Vidar S. Ramdal
Creo que tendré el mismo problema que con la respuesta de Peter Cooper .
Vidar S. Ramdal 01 de
Mi sugerencia implica la aplicación del principio de inyección de dependencia; en este ejemplo; MyTupleRepository es una interfaz que define la capacidad de recuperar las tuplas que mencionó (que consulta DB). Aquí, inyecta este objeto en el método de procesamiento. Ya tienes alguna clase que devuelve los datos; esto solo lo abstrae en una interfaz, e inyecta el objeto en el método 'processData', que internamente usa LinkedHashMap porque esto es parte intrínseca del proceso.
Emerson Cardoso
Edité mi respuesta, tratando de ser más claro sobre lo que estoy sugiriendo.
Emerson Cardoso
-1

Esta pregunta es en realidad un montón de problemas con su modelo de datos en uno. Debes comenzar a desenredarlos, uno a la vez. Las soluciones más naturales e intuitivas desaparecerán a medida que intente simplificar cada pieza del rompecabezas.

Problema 1: no puede depender del pedido de DB

Sus descripciones para ordenar sus datos no son claras.

  • El mayor problema potencial es que no está especificando un tipo explícito en su base de datos, a través de una ORDER BYcláusula. Si no lo eres porque parece demasiado caro, tu programa tiene un error . Las bases de datos pueden devolver resultados en cualquier orden si no especifica uno; no puede depender de que coincida devolviendo datos en el orden solo porque ejecutó la consulta varias veces y se ve de esa manera. El orden puede cambiar porque las filas se reorganizan en el disco, o algunas se eliminan y otras nuevas toman su lugar, o se agrega un índice. Usted debe especificar una ORDER BYcláusula de algún tipo. La velocidad no tiene valor sin corrección.
  • Tampoco está claro a qué se refiere con importancia en el orden de inserción. Si está hablando de la base de datos en sí, debe tener una columna que realmente rastree esto, y debe estar incluida en su ORDER BYcláusula. De lo contrario, tienes errores. Si dicha columna aún no existe, entonces debe agregar una. Las opciones típicas para columnas como esta serían una columna de marca de tiempo de inserción o una clave de incremento automático. La clave de incremento automático es más confiable.

Problema 2: hacer que la memoria sea eficiente

Una vez que se asegure de que se garantiza que devolverá los datos en el orden que espera, puede aprovechar este hecho para hacer que los tipos de memoria sean mucho más eficientes. Simplemente agregue una columna row_number()odense_rank() (o el equivalente de su base de datos) al conjunto de resultados de su consulta. Ahora cada fila tiene un índice que le dará una indicación directa de lo que se supone que es el orden, y puede ordenarlo en memoria de manera trivial. Solo asegúrese de darle al índice un nombre significativo (como sortedBySomethingIndex).

Viola. Ahora ya no tiene que depender del orden del conjunto de resultados de la base de datos.

Problema 3: ¿Necesitas hacer este procesamiento en código?

SQL es realmente realmente poderoso. Es un lenguaje declarativo sorprendente que le permite realizar muchas transformaciones y agregaciones en sus datos. La mayoría de los DB incluso admiten operaciones de fila cruzada hoy en día. Se llaman ventanas o funciones analíticas:

¿Incluso necesita extraer sus datos en la memoria de esta manera? ¿O podría hacer todo el trabajo en la consulta SQL utilizando funciones de ventana? Si puede hacer todo (o tal vez solo una parte importante) del trabajo en el DB, ¡fantástico! ¡Su problema de código desaparece (o se vuelve mucho más simple)!

Problema 4: ¿Estás haciendo qué data?

Asumiendo que no puedes hacerlo todo en el DB, déjame aclarar esto. Está tomando los datos como un mapa (que está codificado por cosas por las que no desea ordenar), luego está iterando sobre ellos en orden de inserción y modificando el mapa en su lugar reemplazando el valor de algunas teclas y agregando ¿nuevos?

Lo siento, pero ¿qué diablos?

Las personas que llaman no deberían tener que preocuparse por todo esto . El sistema que ha creado es extremadamente frágil. Solo se necesita un error tonto (tal vez incluso hecho por usted mismo, como todos hemos hecho) para hacer un pequeño cambio incorrecto y todo se derrumba como una baraja de cartas.

Aquí quizás una mejor idea:

  • Haga que su función acepte a List.
  • Hay un par de formas en que puede manejar el problema de pedidos.
    1. Aplicar Fail Fast. Lanza un error si la lista no está en el orden que requiere la función. (Nota: puede usar el índice de clasificación del problema 2 para saber si es así).
    2. Cree una copia ordenada usted mismo (nuevamente utilizando el índice del problema 2).
    3. Encuentre una manera de construir el mapa en sí mismo en orden.
  • Construya el mapa que necesita internamente para la función, para que la persona que llama no tenga que preocuparse por eso.
  • Ahora repite lo que sea en orden de representación que tengas y haz lo que tengas que hacer.
  • Devuelve el mapa o transfórmalo en un valor de retorno apropiado

Una posible variación podría ser construir una representación ordenada y luego crear un mapa de clave para indexar . Esto le permitiría modificar su copia ordenada en su lugar, sin crear duplicados accidentalmente.

O tal vez esto tiene más sentido: deshacerse del dataparámetro y hacer que processDatarealmente obtenga sus propios datos. Luego puede documentar que está haciendo esto porque tiene requisitos muy específicos sobre la forma en que se obtienen los datos. En otras palabras, haga que la función sea propietaria de todo el proceso, no solo de una parte; Las interdependencias son demasiado fuertes para dividir la lógica en fragmentos más pequeños. (Cambie el nombre de la función en el proceso).

Quizás estos no funcionen para su situación. No lo sé sin todos los detalles del problema. Pero sí conozco un diseño frágil y confuso cuando escucho uno.

Resumen

Creo que el problema aquí es, en última instancia, que el diablo está en los detalles. Cuando empiezo a tener problemas como este, generalmente es porque tengo una representación inapropiada de mis datos para el problema que estoy tratando de resolver. La mejor solución es encontrar una mejor representación , y luego mi problema se vuelve simple (tal vez no fácil, pero sencillo) de resolver.

Encuentre a alguien que obtenga ese punto: su trabajo es reducir su problema a un conjunto de problemas simples y directos. Entonces puede construir código robusto e intuitivo. Habla con ellos. Un buen código y un buen diseño te hacen pensar que cualquier idiota podría haberlos pensado, porque son simples y directos. Tal vez hay un desarrollador senior que tiene esa mentalidad con la que puedes hablar.

jpmc26
fuente
"¿Qué quieres decir con que no hay un orden natural, pero el orden de inserción importa? ¿Estás diciendo que importa el orden en que se insertaron los datos en la tabla DB, pero no tienes una columna que pueda decirte en qué orden se insertaron las cosas? - la pregunta dice esto: "Ordenar el mapa sería una operación pesada, por lo que quiero evitar hacer eso, dado que el resultado de la consulta ya está ordenado". Es claro que esto significa que no es un orden definido calculable a los datos, porque de lo contrario la clasificación sería imposible en lugar de pesado, pero ese orden definido es diferente al orden natural de las llaves.
Jules
2
En otras palabras, OP está trabajando en los resultados de una consulta como select key, value from table where ... order by othercolumn, y necesita mantener el orden en su procesamiento. El orden de inserción al que se refieren es el orden de inserción en su mapa , definido por el orden utilizado en su consulta, no el orden de inserción en la base de datos . Esto queda claro por su uso de LinkedHashMap, que es una estructura de datos que tiene las características tanto de a Mapcomo de a Listde pares clave-valor.
Jules
@Jules Voy a limpiar esa sección un poco, gracias. (Realmente recordaba haber leído eso, pero cuando estaba revisando las cosas mientras escribía la pregunta, no pude encontrarla. Jajaja. Me metí demasiado en la maleza). Pero la pregunta no está clara sobre qué están haciendo con el DB consulta y si tienen un tipo explícito o no. También dicen que "el orden de inserción es importante". El punto es que, incluso si la ordenación es pesada, no puede confiar en que el DB solo ordene las cosas mágicamente si no se lo indica explícitamente. Y si lo está haciendo en la base de datos, puede usar un "índice" para que sea eficiente en el código.
jpmc26
* escribiendo la respuesta (Creo que debería irme a la cama pronto.)
jpmc26
Sí, @Jules tiene razón. No es una order bycláusula en la consulta, pero no es trivial ( no solo order by column), por lo que quiero evitar reimplementar la clasificación en Java. Aunque SQL es poderoso (y estamos hablando de una base de datos Oracle 11g aquí), la naturaleza del processDataalgoritmo hace que sea mucho más fácil de expresar en Java. Y sí, "orden de inserción" significa " orden de inserción del mapa ", es decir, orden de resultado de la consulta.
Vidar S. Ramdal