循环调度java迭代器

round robin scheduling java iterators

提问by wmitchell

I have a list of hosts in an array which represnt the servers available to do a particular job. Currently I simply iterate thru the list looking and establish comms with a host to check its not busy. If not I will send a job to it. This approach tends to mean that the first host in the list tends to get hot constanly with the load not balanced properly with the rest of the available hosts.

我有一个阵列中的主机列表，它代表可用于执行特定工作的服务器。目前，我只是遍历列表查找并与主机建立通信以检查其不忙。如果没有，我会向它发送一份工作。这种方法往往意味着列表中的第一个主机往往会变得很热，而负载没有与其余可用主机正确平衡。

in pseudocode ..

在伪代码..

for (Host h : hosts) {

    //checkstatus
    if status == job accepted break;

}

I'd like to balance this load properly between the hosts i.e first time host one is used 2nd time the method is used host 2. Just wondering that the most elegant solution to this is ??

我想在主机之间适当地平衡这个负载，即第一次使用主机 1 第二次使用主机 2 的方法。只是想知道最优雅的解决方案是 ??

Thanks W

谢谢 W

采纳答案by Itay Maman

You can create a new kind of Iterable that provides round-robin iteration:

您可以创建一种新的 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();
            }

        };
    }
}

You need to define your hosts as RoundRobin<Host>.

您需要将主机定义为RoundRobin<Host>.

[FIXED based on Mirko's comment]

[根据 Mirko 的评论修复]

回答by McDowell

If the list is mutable and the cost of editing it is negligible compared to I/O with the hosts, you can just rotate it:

如果列表是可变的，并且与主机的 I/O 相比，编辑它的成本可以忽略不计，您可以旋转它：

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

回答by Buhb

Google collectionshas a utility method Iterators.cycle(Iterable<T> iterable)that does what you want.

Google collections有一个实用方法Iterators.cycle(Iterable<T> iterable)可以满足您的需求。

回答by gpampara

If you are creating an Iterator, best to create a defensive copy first and have the iterator work on that.

如果您正在创建一个迭代器，最好先创建一个防御性副本，然后让迭代器处理它。

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

回答by Jordi Hernández

IMHO the standard Java API already provides an easy way to accomplish this, without resorting to external libraries or even the need to implement a custom Iterator. Simply use a Deque where you'd pull the first server, use or discard it, then append it back to the end of the Deque. Here's some sample code:

恕我直言，标准 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...    
}

This is just a sample where you always ping hosts in round robin order in a loop that only ends when one of them is available and takes the job. You could tinker with it easily to go only around the queue once (use a counter with a max set to the queue's size) or a number of times beofre throwing an exception, or sleeping in between rounds to avoid banging the hosts when all are busy.

这只是一个示例，您总是在循环中以循环顺序 ping 主机，只有当其中一个可用并接受工作时才结束。您可以轻松地修改它，只在队列中运行一次（使用设置为队列大小的最大值的计数器）或多次在抛出异常之前，或在两轮之间睡觉以避免在所有人都忙时撞到主机.

回答by Mirko

My RoundRobin implementation, based upon the implementation of https://stackoverflow.com/a/2041772/1268954

我的 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");
            }
        };
    }
}

And the Junit TestCase

和 Junit 测试用例

/**
 * 
 * @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);
        }
    }
}

回答by FrederikH

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

Where Filter is

过滤器在哪里

    public interface Filter<T> {

        public boolean accept(T t);

    }