在不使用时钟的情况下用Java实现“基于任务”程序

A friend of mine was asked in an job interview for Java developer to implement a program which receives tasks, which are basically objects which have a "to do" method and a time field that represents seconds (say an integer). The program should perform the "to do" method of the task - in X seconds from the moment that task arrived to the program (where X is the time defined in this task object as the time field).

我的一位朋友在面试时被要求让Java开发人员实现一个接收任务的程序,这些程序基本上是具有“待办事项”方法的对象和表示秒(例如整数)的时间字段。程序应该执行任务的“待办事项”方法 - 从任务到达程序的那一刻起X秒(其中X是在此任务对象中定义的时间作为时间字段)。

for instance, if the program received a task which has a "to do" method that prints "hello I am a task" and has a time field which is 20, then 20 minutes after this task will be received in the program - a "hello I am a task" message will be printed to the consol.

例如,如果程序收到一个具有“待办事项”方法的任务,该方法打印“你好我是一个任务”并且时间字段为20,那么在该程序中将收到该任务后20分钟 - “你好,我是一个任务“消息将被打印到consol。

you cannot use a clock or timers, but you do have some kind of "build in scheduler" which runs every second and can check the status of each one of the tasks and execute them if needed.

您不能使用时钟或计时器,但您确实拥有某种“内置调度程序”,它每秒运行一次,可以检查每个任务的状态并在需要时执行它们。

I thought that a good solution will be that the scheduler will subtract one from each "tasks time" and if that time will be equal to 0, then the scheduler will execute it and remove it from the tasks list. the problem with that is that in case of a long task list this could take a long time to be executed and until the scheduler will finally finish with all the tasks - the time will not be accurate.

我认为一个好的解决方案是调度程序将从每个“任务时间”中减去一个,如果该时间将等于0,则调度程序将执行它并将其从任务列表中删除。问题是,在长任务列表的情况下,这可能需要很长时间才能执行,直到调度程序最终完成所有任务 - 时间将不准确。

from what I understood this is a modeling question, so it might be related to some design pattern or something like that.

从我的理解这是一个建模问题,所以它可能与某些设计模式或类似的东西有关。

does anyone have any idea to what will be a good optional solution to this problem? Thanks guys...

有没有人知道什么是这个问题的一个很好的可选解决方案?多谢你们...

3 个解决方案

#1

If this was an interview question then it most probably goes into the direction of sorting and data structures.

如果这是一个面试问题,那么它很可能会进入排序和数据结构的方向。

First of all, abstract from the whole clock-ticking and scheduler. This is not a problem here. It ticks every time interval (say second) so every second you'll need to find out which tasks to execute.

首先,从整个时钟滴答和调度程序中抽象出来。这不是问题。它记录每个时间间隔(比如秒),所以你需要每秒钟找出要执行的任务。

So you actually need a data structure, where for x of passed seconds you could find out which tasks to execute. What else do you need? The problem says "receiving the tasks" so you must be also able to insert new objects at some point y. It is also probably reasonable to be able to remove executed tasks. Next, I don't think it is wise to check just for equality t == x since it may be that tast execution took longer that a time interval. If executed tasks are removed on execution then you can safely take all the tasks with t <= x.

所以你实际上需要一个数据结构,对于传递秒数的x你可以找出要执行的任务。你还需要什么?问题是“接收任务”,因此您必须也能够在某个时刻插入新对象y。能够删除已执行的任务也是合理的。接下来,我认为仅检查等式t == x是明智的,因为可能是执行时间间隔更长。如果在执行时删除了执行的任务,那么您可以安全地执行t <= x的所有任务。

To sum up, you need the following operations (I'll assume time to be long integer):

总而言之,您需要以下操作(我假设时间为长整数):

• insertTask(int time, Task t)

insertTask(int time,Task t)

• Collection<Task> getTasksScheduledBefore(int time)

集合 getTasksScheduledBefore(int time)

• removeTasksScheduledBefore(t)

What should one use for it? The answer to this question depends on where you have your interview. :)

应该用什么呢?这个问题的答案取决于你的面试地点。 :)

The simplest would be to use something like a TreeMap>:

最简单的方法是使用类似TreeMap>的东西:

• insertTask is trivial with put

insertTask与put很简单

• getTasksScheduledBefore - headMap(t).values()

getTasksScheduledBefore - headMap(t).values()

• removeTasksScheduledBefore - headMap(t).clear()

removeTasksScheduledBefore - headMap(t).clear()

If you're interviewing for Google and Co. then they'll probably think out something that will force you invent your own data structures. Trees are good here, but with some assumptions you could also do tricks with arrays, linked lists and so on. For instance, if you only need to plan one day ahead, an Set<Task>[86400] would be also fine. :)

如果您正在为Google和Co.进行面试,那么他们可能会想出一些会迫使您发明自己的数据结构的东西。树在这里很好,但有一些假设你也可以用数组,链表等做技巧。例如,如果您只需提前一天计划,Set [86400]也可以。 :)

With Google also watch out for things like integer overflows etc. You might need to use BigIntegers instead of long. Make sure you check your assumptions with the interviewer (like that time is actually integer, how you should react on invalid values etc).

Google也会注意整数溢出等问题。您可能需要使用BigIntegers而不是long。确保你与面试官一起检查你的假设(就像那个时间实际上是整数,你应该如何对无效值做出反应等)。

#2

First, store the starting time in a variable. At every tick of the scheduler, increment it by 1.

首先,将开始时间存储在变量中。在调度程序的每个tick处,将其递增1。

When a new task is scheduled, wrap it in an object which stores the task and the tick at which to execute it (currentTick + task schedule time). Put the wrapper in a list and sort the list by starting time (or put it in the correct spot right away).

计划新任务时,将其包装在存储任务的对象和执行该任务的刻度中(currentTick +任务计划时间)。将包装器放在一个列表中,然后按开始时间对列表进行排序(或立即将其放在正确的位置)。

Then, at every tick, you only have to check the first task in the list to see if it should be executed. If it is, check the next one, otherwise, you are done.

然后,在每个tick,你只需要检查列表中的第一个任务,看看是否应该执行它。如果是,请检查下一个,否则,您已完成。

This way, it takes a bit more effort to add new tasks, but you minimize the work you need to do every tick of the scheduler (which will happen a LOT more often).

这样,添加新任务需要花费更多的精力,但是您最小化了调度程序的每个滴答所需的工作(这将更频繁地发生)。

#3

Seems like I had the same idea as David ten Hove. I use a map todos with the scheduled time as the key, so I don't need to sort it, just check if it contains the current time.

好像我和David ten Hove有同样的想法。我使用带有预定时间的地图待办事项作为密钥,因此我不需要对其进行排序,只需检查它是否包含当前时间。

The currentCounter is initialised with 0 and incremented every second (thanks to the scheduled). We don't need to know the actual current time and the subject of the question mentioned "without a clock".

currentCounter初始化为0并且每秒递增一次(由于计划的)。我们不需要知道实际的当前时间和“没有时钟”提到的问题的主题。

package org.conffusion.taskmgr;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Taskmanager {

    /**
     * map of scheduled tasks. For a single moment in time multiple tasks can be
     * scheduled, so a Collection structure of Tasks is necessary.
     */
    private Map<Long, Collection<Task>> todos = new HashMap<Long, Collection<Task>>();

    /**
     * increased every second since the startup of the Manager
     */
    private static long currentCounter = 0;

    /**
     * Use this method to add a new task to the manager.
     * @param task
     */
    public void addTask(Task task) {
        long key=currentCounter + task.getDelay();
        if(todos.containsKey(key))
        {
            // there is already a task for this time, so just add it to the existing list.
            todos.get(key).add(task);
        } else
        {
            List<Task> tasklist=new ArrayList<Task>();
            tasklist.add(task);
            todos.put(key, tasklist);
        }
    }

    /**
     * called by the scheduler every second
     */
    public void schedulerCallback() {
        currentCounter++;
        // Do we have tasks for the current time ?
        if(todos.containsKey(currentCounter))
        {
            // Loop over the scheduled tasks and execute them.
            for(Task t:todos.get(currentCounter))
            {
                // Run every task in a separate thread so our manager does not get blocked by the tasks.
                new Thread(new TaskRunner(t)).start();
            }
            // Clean up of launched tasks
            todos.remove(currentCounter);
        }
    }

    private class TaskRunner implements Runnable {
        private Task task;
        public TaskRunner(Task task)
        {
            this.task=task;
        }
        @Override
        public void run() {
            task.todo();
        }   
    }
    /**
     * Interface every Task must implement.
     */
    public interface Task {

        /**
         * Delay in seconds to wait before todo() must be called.
         * @return
         */
        public long getDelay();

        public void todo();
    }
}