циклическое планирование java итераторов

Question

У меня есть список хостов в массиве, которые представляют серверы, доступные для выполнения определенной работы. В настоящее время я просто перебираю список и устанавливаю связь с хостом, чтобы проверить, не занят ли он. Если нет, я отправлю на него работу. Этот подход означает, что первый хост в списке имеет тенденцию постоянно нагреваться при нагрузке, не сбалансированной должным образом с остальными доступными хостами.

в псевдокоде ..

for (Host h : hosts) {

    //checkstatus
    if status == job accepted break;

}

Я бы хотел правильно распределить эту нагрузку между хостами, т. Е. При первом использовании хоста 2 раза при использовании метода хоста 2. Просто интересно, что наиболее элегантным решением для этого является ??

Спасибо W

Answer 1

Google collection имеет служебный метод Iterators.cycle(Iterable<T> iterable), который делает то, что вы хотите.

Answer 2

Вы можете создать новый тип Iterable, который обеспечивает циклическую итерацию:

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();
            }

        };
    }
}

Вам нужно определить ваши хосты как RoundRobin<Host>.

[ИСПРАВЛЕНО по комментарию Мирко]

Answer 3

Если список изменчив и стоимость редактирования незначительна по сравнению с вводом / выводом с хостами, вы можете просто повернуть его:

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

Answer 4

ИМХО, стандартный Java API уже обеспечивает простой способ сделать это, не прибегая к внешним библиотекам и даже не требуя реализации собственного итератора. Просто используйте Deque, где вы тянете первый сервер, используете или отбрасываете его, а затем добавляете обратно в конец Deque. Вот пример кода:

// 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...    
}

Это просто пример, в котором вы всегда пингуете хосты в циклическом порядке в цикле, который заканчивается только тогда, когда один из них доступен и выполняет задание. Вы можете легко повозиться с ним, чтобы обойти очередь только один раз (использовать счетчик с максимальным значением, равным размеру очереди), или несколько раз, прежде чем выдавать исключение, или спать в перерывах между раундами, чтобы избежать стука по хостам, когда все заняты ,

Answer 5

    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;
        }
    }

Где фильтр

    public interface Filter<T> {

        public boolean accept(T t);

    }

Answer 6

Моя реализация RoundRobin, основанная на реализации 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");
            }
        };
    }
}

И 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

Если вы создаете итератор, лучше всего сначала создать защитную копию и заставить итератор работать с этим.

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