round robin ordonnancement des itérateurs Java

Question

J'ai une liste d'hôtes dans un tableau qui représente les serveurs disponibles pour faire un travail particulier. Actuellement, je simplement itérer à travers la liste regardant et établir des communications avec un hôte pour vérifier son pas occupé. Sinon, je vais envoyer un travail. Cette approche tend à signifier que le premier hôte de la liste a tendance à devenir constamment chaud, la charge n'étant pas équilibrée correctement avec le reste des hôtes disponibles.

à .. pseudocode

for (Host h : hosts) { 

    //checkstatus 
    if status == job accepted break; 

} 

Je voudrais équilibrer cette charge correctement entre les hôtes ie première fois hôte un est utilisé 2 fois la méthode est utilisée hôte 2. Il suffit de demander que la solution la plus élégante à ceci est ??

Merci W

Answer 1

Vous pouvez créer un nouveau type de Iterable qui fournit des round-robin itération:

public class RoundRobin<T> implements Iterable<T> { 
     private List<T> coll; 

     public RoundRobin(List<T> coll) { this.coll = coll; } 

     public Iterator<T> iterator() { 
     return new Iterator<T>() { 
      private int index = 0; 

      @Override 
      public boolean hasNext() { 
       return true; 
      } 

      @Override 
      public T next() { 
       T res = coll.get(index); 
       index = (index + 1) % coll.size(); 
       return res; 
      } 

      @Override 
      public void remove() { 
       throw new UnsupportedOperationException(); 
      } 

     }; 
    } 
} 

Vous devez définir vos hôtes comme RoundRobin<Host>.

[fixe basé sur le commentaire de Mirko]

Answer 2

Si la liste est mutable et le coût de la modification est négligeable par rapport à E/S avec les hôtes, vous pouvez simplement faire pivoter:

List<String> list = Arrays.asList("one", "two", "three"); 
Collections.rotate(list, -1); 
System.out.println(list); 

Answer 3

Google collections a une méthode utilitaire Iterators.cycle(Iterable<T> iterable) qui fait ce que vous voulez.

Answer 4

Si vous créez un Iterator, il est préférable de créer d'abord une copie défensive et de faire en sorte que l'itérateur fonctionne.

return new MyIterator(ImmutableList.<T>copyOf(list)); 

Answer 5

IMHO l'API standard Java fournit déjà un moyen facile d'y arriver, sans avoir recours à des bibliothèques externes ou même la nécessité de mettre en œuvre un itérateur personnalisé. Utilisez simplement un Deque où vous tirez le premier serveur, utilisez-le ou jetez-le, puis ajoutez-le à la fin du Deque. Voici quelques exemples de code:

// Initialize the Deque. This might be at your class constructor. 
Deque<Host> dq = new ArrayDeque<Host>(); 
dq.addAll(Arrays.asList(hosts)); 

void sendJob(Job myJob) { 
    boolean jobInProcess = false; 
    do { 
     Host host = dq.removeFirst(); // Remove the host from the top 
     if(!host.isBusy()) { 
      host.sendJob(myJob); 
      jobInProcess = true; 
     } 
     dq.addLast(host); // Put the host back at the end 
    } 
    while(!jobInProcess); // Might add another condition to prevent an infinite loop...  
} 

Ceci est juste un exemple où vous avez toujours des hôtes de ping dans l'ordre tournoi à la ronde dans une boucle qui se termine que lorsque l'un d'entre eux est disponible et prend le travail. Vous pouvez le bricoler facilement pour ne passer qu'une seule fois autour de la file (utiliser un compteur dont la taille est au maximum) ou plusieurs fois avant de lancer une exception ou de dormir entre deux tours pour éviter de frapper les hôtes lorsque tous sont occupés .

Answer 6

Ma mise en œuvre RoundRobin, basée sur la mise en œuvre de https://stackoverflow.com/a/2041772/1268954

/** 
* 
* @author Mirko Schulze 
* 
* @param <T> 
*/ 
public class RoundRobin<T> implements Iterable<T> { 

    private final List<T> coll; 

    public RoundRobin(final List<T> coll) { 
     this.coll = NullCheck.throwExceptionIfNull(coll, "collection is null"); 
    } 

    @Override 
    public Iterator<T> iterator() { 
     return new Iterator<T>() { 

      private int index; 

      @Override 
      public boolean hasNext() { 
       return true; 
      } 

      @Override 
      public T next() { 
       this.index = this.index % RoundRobin.this.coll.size(); 
       final T t = RoundRobin.this.coll.get(this.index); 
       this.index++; 
       return t; 
      } 

      @Override 
      public void remove() { 
       throw new IllegalArgumentException("remove not allowd"); 
      } 
     }; 
    } 
} 

Et JUnit TestCase

/** 
* 
* @author Mirko Schulze 
* 
*/ 
@RunWith(JUnit4.class) 
public class RoundRobinTest extends TestCase { 

    private List<Integer> getCollection() { 
     final List<Integer> retval = new Vector<Integer>(); 
     retval.add(Integer.valueOf(1)); 
     retval.add(Integer.valueOf(2)); 
     retval.add(Integer.valueOf(3)); 
     retval.add(Integer.valueOf(4)); 
     retval.add(Integer.valueOf(5)); 
     return retval; 
    } 

    @Test 
    public void testIteration() { 
     final List<Integer> l = this.getCollection(); 
     final Integer frst = l.get(0); 
     final Integer scnd = l.get(1); 
     final Integer thrd = l.get(2); 
     final Integer frth = l.get(3); 
     final Integer last = l.get(4); 
     Assert.assertEquals("die Collection hat für diesen Test nicht die passende Größe!", 5, l.size()); 
     final RoundRobin<Integer> rr = new RoundRobin<Integer>(l); 
     final Iterator<Integer> i = rr.iterator(); 
     for (int collectionIterations = 0; collectionIterations < 4; collectionIterations++) { 
      final Integer i1 = i.next(); 
      Assert.assertEquals("nicht das erste Element", frst, i1); 
      final Integer i2 = i.next(); 
      Assert.assertEquals("nicht das zweite Element", scnd, i2); 
      final Integer i3 = i.next(); 
      Assert.assertEquals("nicht das dritte Element", thrd, i3); 
      final Integer i4 = i.next(); 
      Assert.assertEquals("nicht das vierte Element", frth, i4); 
      final Integer i5 = i.next(); 
      Assert.assertEquals("nicht das letzte Element", last, i5); 
     } 
    } 
} 

Answer 7

public class RoundRobinIterator<T> implements Serializable { 

     private static final long serialVersionUID = -2472203060894189676L; 
     // 
     private List<T> list; 
     private Iterator<T> it; 
     private AtomicInteger index = new AtomicInteger(0); 

     public RoundRobinIterator(List<T> list) throws NullPointerException { 
      super(); 
      if (list==null) { 
       throw new NullPointerException("List is null"); 
      } 
      this.list=Collections.unmodifiableList(list); 
     } 
     public RoundRobinIterator(Collection<T> values) { 
      this(new ArrayList<T>(values)); 
     } 
     public RoundRobinIterator(Iterator<T> values) { 
      this(copyIterator(values)); 
     } 
     public RoundRobinIterator(Enumeration<T> values) { 
      this(Collections.list(values)); 
     } 



     private final List<T> getList() { 
      return list; 
     } 
     private final Iterator<T> getIt() { 
      return it; 
     } 
     public final int size() { 
      return list.size(); 
     } 
     public final synchronized T getNext(Filter<T> filter) { 
      int start = index.get(); 
      T t = getNext(); 
      T result = null; 
      while ((result==null) && (start!=getIndex())) { 
       if (filter.accept(t)) { 
        result=t; 
       } else { 
        t = getNext(); 
       } 
      } 
      return result; 
     } 

     public final synchronized T getNext() { 
      if (getIt()==null) { 
       if (getList().size()==0) { 
        index.set(0); 
        return null; 
       } else { 
        it = getList().iterator(); 
        index.set(0); 
        return it.next(); 
       } 
      } else if (it.hasNext()) { 
       index.incrementAndGet(); 
       return it.next(); 
      } else { 
       if (list.size()==0) { 
        index.set(0); 
        return null; 
       } else { 
        index.set(0); 
        it = list.iterator();    
        return it.next(); 
       } 
      } 
     } 

     public final synchronized int getIndex() { 
      return index.get(); 
     } 


     private static <T> List<T> copyIterator(Iterator<T> iter) { 
      List<T> copy = new ArrayList<T>(); 
      while (iter.hasNext()) { 
       copy.add(iter.next()); 
      } 
      return copy; 
     } 
    } 

Où filtre est

public interface Filter<T> { 

     public boolean accept(T t); 

    }