问题

以下是您提供的代码的翻译：

import java.io.*;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;

public class JobQueue {
    private int numWorkers;
    private int[] jobs;
    private int[] assignedWorker;
    private long[] startTime;

    private FastScanner in;
    private PrintWriter out;

    public static void main(String[] args) throws IOException {
        new JobQueue().solve();
    }

    private void readData() throws IOException {
        numWorkers = in.nextInt();
        int m = in.nextInt();
        jobs = new int[m];
        for (int i = 0; i < m; ++i) {
            jobs[i] = in.nextInt(); 
        }
    }

    private void writeResponse() {
        for (int i = 0; i < jobs.length; ++i) {
            out.println(assignedWorker[i] + " " + startTime[i]);
        }
    }

    private void assignJobs() {
        // TODO: 用更快的算法替换这部分代码。
        assignedWorker = new int[jobs.length];
        startTime = new long[jobs.length];
        PriorityQueue<Integer> nextTimesQueue = new PriorityQueue<Integer>();
        HashMap<Integer, Set<Integer>> workersReadyAtTimeT = new HashMap<Integer, Set<Integer>>();
        long[] nextFreeTime = new long[numWorkers];
        int duration = 0;
        int bestWorker = 0;
        for (int i = 0; i < jobs.length; i++) {
            duration = jobs[i];
            if(i < numWorkers) {
                bestWorker = i;
                nextTimesQueue.add(duration);
                addToSet(workersReadyAtTimeT, duration, i, 0);
            } else {
                int currentTime = nextTimesQueue.poll();
                Set<Integer> workersReady = workersReadyAtTimeT.get(currentTime);
                if (workersReady.size() > 1) { 
                    bestWorker = workersReady.iterator().next();
                    workersReady.remove(bestWorker);
                    workersReadyAtTimeT.remove(currentTime);
                    workersReadyAtTimeT.put(currentTime, workersReady);
                    nextTimesQueue.add(currentTime);
                } else {
                    bestWorker = workersReady.iterator().next();
                    workersReadyAtTimeT.remove(currentTime);
                    nextTimesQueue.add(currentTime + duration);
                    addToSet(workersReadyAtTimeT, duration, bestWorker, currentTime);
                }
            }

            assignedWorker[i] = bestWorker;
            startTime[i] = nextFreeTime[bestWorker];
            nextFreeTime[bestWorker] += duration;
        }
    }
    
    private void addToSet(HashMap<Integer, Set<Integer>> workersReadyAtTimeT, int duration, int worker, int current) {
        if(workersReadyAtTimeT.get(current + duration) == null) {
            HashSet<Integer> s = new HashSet<Integer>();
            s.add(worker);
            workersReadyAtTimeT.put(current + duration, s);
        } else {
            Set<Integer> s = workersReadyAtTimeT.get(current + duration);
            s.add(worker);
            workersReadyAtTimeT.put(current + duration, s);
        }
    }

    public void solve() throws IOException {
        in = new FastScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        readData();
        assignJobs();
        writeResponse();
        out.close();
    }

    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public FastScanner() {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
        }

        public String next() throws IOException {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}

请注意，这是您提供的代码的逐行翻译，没有任何额外的内容。

英文:

I am trying to do a multi threading simulation in Java and I have managed to do it with a queue but the execution time is high, any ideas on how I could optimize this? Can using recursion save time?

The input has to be like this:

2 5 It means that there are two threads(workers) for 5 jobs
1 2 3 4 5 This is the jobs that are an integer which means the time cost of processing that job so the output will be this:
0 0 The two threads try to simultaneously take jobs from the list, so thread with index 0 actually
1 0 takes the first job and starts working on it at the moment 0
0 1 After 1 second, thread 0 is done with the first job and takes the third job from the list, and starts processing it immediately at time 1.
1 2 One second later, thread 1 is done with the second job and takes the fourth job from the list, and starts processing it immediately at time 2
0 4 Finally, after 2 more seconds, thread 0 is done with the third job and takes the fifth job from the list, and starts processing it immediately at time 4

This is the code:

import java.io.*;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;
public class JobQueue {
private int numWorkers;
private int[] jobs;
private int[] assignedWorker;
private long[] startTime;
private FastScanner in;
private PrintWriter out;
public static void main(String[] args) throws IOException {
new JobQueue().solve();
}
private void readData() throws IOException {
numWorkers = in.nextInt();
int m = in.nextInt();
jobs = new int[m];
for (int i = 0; i &lt; m; ++i) {
jobs[i] = in.nextInt(); 
}
}
private void writeResponse() {
for (int i = 0; i &lt; jobs.length; ++i) {
out.println(assignedWorker[i] + &quot; &quot; + startTime[i]);
}
}
private void assignJobs() {
// TODO: replace this code with a faster algorithm.
assignedWorker = new int[jobs.length];
startTime = new long[jobs.length];
PriorityQueue&lt;Integer&gt; nextTimesQueue = new PriorityQueue&lt;Integer&gt;();
HashMap&lt;Integer, Set&lt;Integer&gt;&gt; workersReadyAtTimeT = new HashMap&lt;Integer,Set&lt;Integer&gt;&gt;();
long[] nextFreeTime = new long[numWorkers];
int duration = 0;
int bestWorker = 0;
for (int i = 0; i &lt; jobs.length; i++) {
duration = jobs[i];
if(i&lt;numWorkers) {
bestWorker = i;
nextTimesQueue.add(duration);
addToSet(workersReadyAtTimeT, duration, i,0);
}else {
int currentTime = nextTimesQueue.poll();
Set&lt;Integer&gt; workersReady = workersReadyAtTimeT.get(currentTime);
if (workersReady.size()&gt;1) { 
bestWorker = workersReady.iterator().next();
workersReady.remove(bestWorker);
workersReadyAtTimeT.remove(currentTime);
workersReadyAtTimeT.put(currentTime,workersReady);
nextTimesQueue.add(currentTime);
} else {
bestWorker = workersReady.iterator().next();
workersReadyAtTimeT.remove(currentTime);
nextTimesQueue.add(currentTime+duration);
addToSet(workersReadyAtTimeT, duration, bestWorker, currentTime);
}
}
assignedWorker[i] = bestWorker;
startTime[i] = nextFreeTime[bestWorker];
nextFreeTime[bestWorker] += duration;
}
}
private void addToSet(HashMap&lt;Integer, Set&lt;Integer&gt;&gt; workersReadyAtTimeT, int duration, int worker, int current) {
if(workersReadyAtTimeT.get(current+duration)==null) {
HashSet&lt;Integer&gt; s = new HashSet&lt;Integer&gt;();
s.add(worker);
workersReadyAtTimeT.put(current+duration, s);
}else {
Set&lt;Integer&gt; s = workersReadyAtTimeT.get(current+duration);
s.add(worker);
workersReadyAtTimeT.put(current+duration,s);
}
}
public void solve() throws IOException {
in = new FastScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
readData();
assignJobs();
writeResponse();
out.close();
}
static class FastScanner {
private BufferedReader reader;
private StringTokenizer tokenizer;
public FastScanner() {
reader = new BufferedReader(new InputStreamReader(System.in));
tokenizer = null;
}
public String next() throws IOException {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
}

答案1

得分: 1

似乎你的 `jobsList` 对象是完全多余的，它包含的所有内容也都在 `jobs` 数组中，当你取前面的元素时，你得到的是 `jobs[i]` 处的项。为了稍微提高速度，你可以将整数的构造函数从循环中取出，只需为它们分配新的数字。另一个优化是在前 `numWorkers` 个作业中不进行搜索，因为你知道在用尽池子之前你仍有空闲的工作者。一旦找到一个合适的工作者，你就不必继续寻找，所以你可以从 for 循环中使用 `continue`。

```java
public class JobQueue {
    private void assignJobs() {
        // ...（其他成员变量的定义和读取数据的部分）

        PriorityQueue<Integer> nextTimesQueue = new PriorityQueue<Integer>();
        HashMap<Integer, Set<Integer>> workersReadyAtTimeT = new HashMap<Integer, Set<Integer>>();
        long[] nextFreeTime = new long[numWorkers];
        int duration = 0;
        int bestWorker = 0;
        for (int i = 0; i < jobs.length; i++) {
            duration = jobs[i];
            if (i < numWorkers) {
                bestWorker = i;
                nextTimesQueue.add(duration);
                addToSet(workersReadyAtTimeT, duration, i, 0);
            } else {
                int currentTime = nextTimesQueue.poll();
                Set<Integer> workersReady = workersReadyAtTimeT.get(currentTime);
                if (workersReady.size() > 1) {
                    bestWorker = workersReady.iterator().next();
                    workersReady.remove(bestWorker);
                    workersReadyAtTimeT.remove(currentTime);
                    workersReadyAtTimeT.put(currentTime, workersReady);
                    nextTimesQueue.add(currentTime);
                } else {
                    bestWorker = workersReady.iterator().next();
                    workersReadyAtTimeT.remove(currentTime);
                    nextTimesQueue.add(currentTime + duration);
                    addToSet(workersReadyAtTimeT, duration, bestWorker, currentTime);
                }
            }
            assignedWorker[i] = bestWorker;
            startTime[i] = nextFreeTime[bestWorker];
            nextFreeTime[bestWorker] += duration;
        }
    }

    private void addToSet(HashMap<Integer, Set<Integer>> workersReadyAtTimeT, int duration, int worker, int current) {
        if (workersReadyAtTimeT.get(current + duration) == null) {
            HashSet<Integer> s = new HashSet<Integer>();
            s.add(worker);
            workersReadyAtTimeT.put(current + duration, s);
        } else {
            Set<Integer> s = workersReadyAtTimeT.get(current + duration);
            s.add(worker);
            workersReadyAtTimeT.put(current + duration, s);
        }
    }
}

不过，你的解决方案和这个稍微精简的解决方案运行时间都是 2 毫秒。我还尝试了使用 HashMap 来维护 NextWorker 标记，但在某个点上你会赶上它，最终每次都在寻找下一个，节省不了多少时间。

你可以尝试使用有序的 List/Queue，但这样你就会有昂贵的插入操作代替了昂贵的搜索操作，而且你还得跟踪时间片。但是一个类似这样的版本可能会是这样的：

private void assignJobs() {
    // ...（其他成员变量的定义和读取数据的部分）

    PriorityQueue<Integer> nextTimesQueue = new PriorityQueue<Integer>();
    HashMap<Integer, Set<Integer>> workersReadyAtTimeT = new HashMap<Integer, Set<Integer>>();
    long[] nextFreeTime = new long[numWorkers];
    int duration = 0;
    int bestWorker = 0;
    for (int i = 0; i < jobs.length; i++) {
        duration = jobs[i];
        if (i < numWorkers) {
            bestWorker = i;
            nextTimesQueue.add(duration);
            addToSet(workersReadyAtTimeT, duration, i, 0);
        } else {
            int currentTime = nextTimesQueue.poll();
            Set<Integer> workersReady = workersReadyAtTimeT.get(currentTime);
            if (workersReady.size() > 1) {
                bestWorker = workersReady.iterator().next();
                workersReady.remove(bestWorker);
                workersReadyAtTimeT.remove(currentTime);
                workersReadyAtTimeT.put(currentTime, workersReady);
                nextTimesQueue.add(currentTime);
            } else {
                bestWorker = workersReady.iterator().next();
                workersReadyAtTimeT.remove(currentTime);
                nextTimesQueue.add(currentTime + duration);
                addToSet(workersReadyAtTimeT, duration, bestWorker, currentTime);
            }
        }
        assignedWorker[i] = bestWorker;
        startTime[i] = nextFreeTime[bestWorker];
        nextFreeTime[bestWorker] += duration;
    }
}

private void addToSet(HashMap<Integer, Set<Integer>> workersReadyAtTimeT, int duration, int worker, int current) {
    if (workersReadyAtTimeT.get(current + duration) == null) {
        HashSet<Integer> s = new HashSet<Integer>();
        s.add(worker);
        workersReadyAtTimeT.put(current + duration, s);
    } else {
        Set<Integer> s = workersReadyAtTimeT.get(current + duration);
        s.add(worker);
        workersReadyAtTimeT.put(current + duration, s);
    }
}

英文:

It seems to me that your jobsList object is completely redundant, everything it contains is also in the jobs array and when you take the front element you get the item at jobs[i]. To speed up a little you could take the constructors of the ints out of the loop and just assign new numbers to them. Another optimization would be to not search during the first numWorkers jobs because you know you still have idle workers until you have exausted your pool. Once you have found one good worker you dont have to keep looking so you can continue out of your for-loop.

public class JobQueue {
private int numWorkers;
private int[] jobs;
private int[] assignedWorker;
private long[] startTime;
private void readData() throws IOException {
numWorkers = in.nextInt();
int m = in.nextInt();
jobs = new int[m];
for (int i = 0; i &lt; m; ++i) {
jobs[i] = in.nextInt();
}
}
private void assignJobs() {
assignedWorker = new int[jobs.length];
startTime = new long[jobs.length];
long[] nextFreeTime = new long[numWorkers];
int duration = 0;
int bestWorker = 0;
for (int i = 0; i &lt; jobs.length; i++) {
duration = jobs[i];
bestWorker = 0;
if (i&lt; numWorkers){
bestWorker= i;
} else{
for (int j = 0; j &lt; numWorkers; ++j) {
if (nextFreeTime[j] &lt; nextFreeTime[bestWorker])
bestWorker = j;
continue;
}
}
assignedWorker[i] = bestWorker;
startTime[i] = nextFreeTime[bestWorker];
nextFreeTime[bestWorker] += duration;
}
}

However, both your solution and this slightly trimmed down one take 2 milliseconds to run. I also looked at having HashMap to maintain a NextWorker marker but at some point you catch up with it and end up looking everytime for the next one and don't win much.

You could try having an ordered List/Queue, but then you have expensive inserts instead of expensive searches, and you have to kee track of the timeslice. But a version like that could look like this:

private void assignJobs() {
assignedWorker = new int[jobs.length];
startTime = new long[jobs.length];
PriorityQueue&lt;Integer&gt; nextTimesQueue = new PriorityQueue&lt;Integer&gt;();
HashMap&lt;Integer, Set&lt;Integer&gt;&gt; workersReadyAtTimeT = new HashMap&lt;Integer,Set&lt;Integer&gt;&gt;();
long[] nextFreeTime = new long[numWorkers];
int duration = 0;
int bestWorker = 0;
for (int i = 0; i &lt; jobs.length; i++) {
duration = jobs[i];
if(i&lt;numWorkers) {
bestWorker = i;
nextTimesQueue.add(duration);
addToSet(workersReadyAtTimeT, duration, i,0);
}else {
int currentTime = nextTimesQueue.poll();
Set&lt;Integer&gt; workersReady = workersReadyAtTimeT.get(currentTime);
if (workersReady.size()&gt;1) { 
bestWorker = workersReady.iterator().next();
workersReady.remove(bestWorker);
workersReadyAtTimeT.remove(currentTime);
workersReadyAtTimeT.put(currentTime,workersReady);
nextTimesQueue.add(currentTime);
} else {
bestWorker = workersReady.iterator().next();
workersReadyAtTimeT.remove(currentTime);
nextTimesQueue.add(currentTime+duration);
addToSet(workersReadyAtTimeT, duration, bestWorker, currentTime);
}
}
assignedWorker[i] = bestWorker;
startTime[i] = nextFreeTime[bestWorker];
nextFreeTime[bestWorker] += duration;
}
}
private void addToSet(HashMap&lt;Integer, Set&lt;Integer&gt;&gt; workersReadyAtTimeT, int duration, int worker, int current) {
if(workersReadyAtTimeT.get(current+duration)==null) {
HashSet&lt;Integer&gt; s = new HashSet&lt;Integer&gt;();
s.add(worker);
workersReadyAtTimeT.put(current+duration, s);
}else {
Set&lt;Integer&gt; s = workersReadyAtTimeT.get(current+duration);
s.add(worker);
workersReadyAtTimeT.put(current+duration,s);
}
}

通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。

如何优化这个Java中的模拟？

问题

答案1

从一个类传递到另一个类

为什么子类对象在Java中调用父类字段变量？

"Circular view path would dispatch back to the current handler URL." when using Spring Boot and Thymeleaf

如何创建一个PKCS12密钥库？

What's the correct way to type hint an empty list as a literal in python?

如何在Highcharts Gantt中更改本地化的星期名称

如何在同一个流中使用多个过滤器和映射函数？

如何使用Map/Set来将代码优化到O(n)？

.NET MAUI Android在GitHub Actions上构建失败，错误代码为1。

如何在Playwright视觉比较中屏蔽多个定位器？

在C++中，可以使用可变模板参数来检索类型的内部类型。

selenium.common.exceptions.StaleElementReferenceException: Message: stale element reference: stale element not found

Creating and opening a URL to log in to Website via Basic Auth with Robot Framework/Selenium (Python)

AG Grid 在上下文菜单中以大文本形式打开

发表评论