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

huangapple
go评论72阅读模式
英文:

How to optimize this simulation in Java?

问题

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

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

huangapple
  • 本文由 发表于 2020年7月23日 21:01:49
  • 转载请务必保留本文链接：https://go.coder-hub.com/63054938.html
  • algorithm
  • data-structures
  • java
  • multithreading
  • optimization
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定