Transférer des éléments sans modifier les rangs de tous les éléments

Question

J'ai une liste d'éléments, dont chacun a un rang associé.

Item 1, Rank=1 
Item 2, Rank=2 
Item 3, Rank=3 
Item 4, Rank=4 
Item 5, Rank=5 

Je veux concevoir une méthode qui gère re-classement des articles avec peu ou pas de changement dans les rangs des autres articles.

Une solution à laquelle je pensais était de tirer parti des décimales et d'utiliser le type de variable double de Java. Ainsi, par exemple si je item5 Jonglez entre item2 et item3, ce serait la sortie -

Item 1, Rank=1 
Item 2, Rank=2 
Item 5, Rank=2.5 
Item 3, Rank=3 
Item 4, Rank=4 

Et ainsi de suite,

Item 1, Rank=1 
Item 2, Rank=2 
Item 4, Rank=2.25 
Item 5, Rank=2.5 
Item 3, Rank=3 

Cette solution fonctionne, mais après un moment donné (~ 55 se déplace à la même position, j'atteins la double limite variable et je vais probablement devoir réinitialiser tous les rangs à ce point)

Je me demandais juste s'il y avait une meilleure façon de résoudre ce problème?

Quelques points à garder à l'esprit.

• J'ai besoin de stocker cette structure de données dans une base de données (Point, Rank) et je construirai un service Web qui obtient tous les éléments dans un ordre de tri en fonction de rang donc je rendrais un appel DB pour obtenir tous les articles triés par le champ de classement.
• Je vais utiliser Java, donc je ne peux traiter qu'avec des variables Java.

Answer 1

Qu'en est-il de l'écriture d'une petite routine qui distribue uniformément les valeurs de rang d'une plage d'éléments dans le tableau (ou la liste ou autre)?

Si vous insérez un nouvel élément à la position x, vous passez les éléments de la plage x-1 .. x+1 dans le sous-programme. les valeurs de rang au début et à la fin de la course restent les mêmes, les autres sont calculés avec une distance égale. En cas de succès, renvoyez true. Maintenant, si la distance devient trop petite, vous renvoyez false, l'appelant étend la plage à x-2 .. x+2 et entre à nouveau dans le sous-programme.

Vous devriez prendre soin de contourner les limites de la matrice ou même de manquer complètement d'espace-valeur.

Answer 2

Il y a plusieurs solutions pourraient être, voici celle que je préfère

Je partagerai ce problème dans plusieurs des cas isolés:

1. Dans votre back-end Java que vous voulez avoir la liste d'articles, triés d'une manière ou d'une autre, avec possibilité de faire des changements rapides dans l'ordre O (1).

La meilleure structure - liste double liée. Vous devrez utiliser hashmap pour trouver rapidement les objets par nom d'élément/identifiant dans cette liste.

Vous pouvez stocker une telle structure dans une base de données facilement, il suffit d'ajouter deux clés étrangères à la table des éléments. Pendant le stockage, vous devrez mettre à jour uniquement les lignes affectées (en ayant à l'esprit que les éléments prev/next sont également affectés lorsque vous déplacez l'élément). Cela va ressembler à plusieurs

2. Dans votre service java, vous voulez afficher la liste triée des articles aussi vite que possible, probablement paginée.

La meilleure structure - matrice pré-triée.

Pour stocker une telle structure dans la base de données, vous avez besoin d'une colonne où la position sera stockée (rang). Bien sûr, vous avez besoin d'index sur cette colonne.

Pour récupérer une telle structure, vous allez utiliser une requête très simple, rapide et efficace, comme select item from table order by rank limit ?,?.

---

Maintenant, vous avez contradiction, votre structure de données pour modifier ne correspond pas à votre structure de données pour la récupération et toute tentative d'utiliser la structure de données unique pour les deux problèmes se traduira par degrade de performance dans une partie, permet de résoudre ce problème de façon indépendante :

3. Vous allez créer un service asynchrone séparé (cron job), qui va lire les données d'une table, convertir (rang recalculer pour tous les articles) et stocker dans une autre table.

Ici, vous aurez deux options: soit remplacer complètement les données dans la 2ème table après calculer ou trouver diff et mettre à jour uniquement les lignes modifiées. Je crois que le remplacement complet est plus facile à mettre en œuvre et en fait, il pourrait être beaucoup plus rapide. Ainsi, avec cette approche, les parties visibles de votre système sont performantes (la partie de gestion des données et la partie d'affichage des données fonctionnent aussi vite que possible).

Le seul problème est la propagation de changement, qui est habituellement bien et la plupart des utilisateurs l'accepteront comme un compromis raisonnable.