Jux*_*hin 9 java algorithm text
我已经使用SO用户建议的更新代码更新了问题,并将澄清之前存在的任何模糊文本.
我只能访问相关应用程序生成的日志文件.因此,我被限制在日志文件的内容中工作,并且没有超出该范围的解决方案.我会稍微修改一下样本数据.我想指出以下关键变量.
Thread ID - 范围从0..19 - 线程被多次使用.因此ScriptExecThread(2)可以在日志中多次出现.
Script - 每个线程都将在特定文件上运行脚本.同样的脚本可能会在同一个线程上运行,但不会在同一个线程AND文件上运行.
File- 每个人都Thread ID跑Script一个File.如果Thread(10)在运行myscript.script上myfile.file,然后,准确的线不会被再次执行.使用上述示例的成功示例将是这样的.
- - - 开始 - - -
线程(10)在myfile.file上启动myscript.script
线程(10)在myfile.file上完成了myscript.script
- - - 结束 - - - -
使用上面示例的不成功示例将是:
- - - 开始 - - -
线程(10)在myfile.file上启动myscript.script
- - - 结束 - - -
在解决我的查询之前,我将简要介绍所使用的代码和所需的行为.
我正在解析大型日志文件(平均需要100k到600k行),并且我试图按特定顺序检索某些信息.我已经根据我的要求制定了布尔代数,它似乎在纸上起作用但在代码上却没有那么多(我肯定错过了一些显而易见的东西).我想提前告知代码没有任何形状或形式优化,现在我只想让它工作.
在此日志文件中,您可以看到某些线程在它们启动时挂起但从未完成.可能的线程ID范围的数量.这是一些伪代码:
REGEX = "ScriptExecThread(\\([0-9]+\\)).*?(finished|starting)" //in java
Set started, finished
for (int i=log.size()-1; i >=0; i--) {
if(group(2).contains("starting")
started.add(log.get(i))
else if(group(2).contains("finished")
finished.add(log.get(i)
}
started.removeAll(finished);
Set<String> started = new HashSet<String>(), finished = new HashSet<String>();
for(int i = JAnalyzer.csvlog.size()-1; i >= 0; i--) {
if(JAnalyzer.csvlog.get(i).contains("ScriptExecThread"))
JUtility.hasThreadHung(JAnalyzer.csvlog.get(i), started, finished);
}
started.removeAll(finished);
commonTextArea.append("Number of threads hung: " + noThreadsHung + "\n");
for(String s : started) {
JLogger.appendLineToConsole(s);
commonTextArea.append(s+"\n");
}
public static boolean hasThreadHung(final String str, Set<String> started, Set<String> finished) {
Pattern r = Pattern.compile("ScriptExecThread(\\([0-9]+\\)).*?(finished|starting)");
Matcher m = r.matcher(str);
boolean hasHung = m.find();
if(m.group(2).contains("starting"))
started.add(str);
else if (m.group(2).contains("finished"))
finished.add(str);
System.out.println("Started size: " + started.size());
System.out.println("Finished size: " + finished.size());
return hasHung;
}
ScriptExecThread(1)在afile.xyz上启动
ScriptExecThread(2)在bfile.abc上启动
ScriptExecThread(3)在cfile.zyx上启动
ScriptExecThread(4)在dfile.zxy上启动
ScriptExecThread(5)在efile.yzx上启动
ScriptExecThread(1)在afile.xyz上完成
ScriptExecThread(2)在bfile.abc上完成
ScriptExecThread(3)在cfile.zyx上完成
ScriptExecThread(4)在dfile.zxy上完成
ScriptExecThread(5)在efile.yzy上完成
ScriptExecThread(1)在bfile.abc上启动
ScriptExecThread(2)在dfile.zxy上启动
ScriptExecThread(3)在afile.xyz上启动
ScriptExecThread(1)在bfile.abc上完成
记录结束
如果您举例说明,您会注意到第2和第3个线程已经启动但未能完成(原因不是必需的,我只需要获取该行).
09.08 15:06.53,ScriptExecThread(7),Info,###########出发
09.08 15:06.54,ScriptExecThread(18),Info,######################出发
09.08 15:06.54,ScriptExecThread(13),Info,########在#########中完成
09.08 15:06.54,ScriptExecThread(13),Info,##########出发
09.08 15:06.55,ScriptExecThread(9),Info,#####在########中完成
09.08 15:06.55,ScriptExecThread(0),Info,####在###########中完成
09.08 15:06.55,ScriptExecThread(19),Info,####在########中完成
09.08 15:06.55,ScriptExecThread(8),Info,######在2777完成#########
09.08 15:06.55,ScriptExecThread(19),Info,##########出发
09.08 15:06.55,ScriptExecThread(8),Info,#######开始
09.08 15:06.55,ScriptExecThread(0),Info,##########出发
09.08 15:06.55,ScriptExecThread(19),Info,Post ######在#####中完成
09.08 15:06.55,ScriptExecThread(0),Info,######在#########中完成
09.08 15:06.55,ScriptExecThread(19),Info,##########出发
09.08 15:06.55,ScriptExecThread(0),Info,###########出发
09.08 15:06.55,ScriptExecThread(9),Info,########## starting
09.08 15:06.56,ScriptExecThread(1),Info,#######在########中完成
09.08 15:06.56,ScriptExecThread(17),Info,######在#######中完成
09.08 15:06.56,ScriptExecThread(17),Info,######################出发
09.08 15:06.56,ScriptExecThread(1),Info,##########出发
目前,代码只显示整个日志文件,其中的行以"starting"开头.当我查看代码时,这有点有意义.
我删除了任何我不想显示的冗余信息.如果有什么我可能遗漏的请随时告诉我,我会添加它.
如果我理解正确,你有大文件,并试图找到X的所有数值的形式"X开始(但没有提到X完成)"的模式.
如果我这样做,我会使用这个伪代码:
Pattern p = Pattern.compile(
"ScriptExecThread\\(([0-9]+).*?(finished|started)");
Set<Integer> started, finished;
Search for p; for each match m,
int n = Integer.parseInt(m.group(1));
if (m.group(2).equals("started")) started.add(n);
else finished.add(n);
started.removeAll(finished); // found 'em: contains started-but-not-finished
这需要在每个文件上进行单个正则表达式传递,并且需要O(完成大小)设置减法; 它应该比您当前的方法快20倍.正则表达式将使用optional(|)匹配来同时查找两个备选项,从而减少传递次数.
编辑:显式正则表达式.编译正则表达式而不是每行一次应该可以减少一些额外的运行时间.
编辑2:实现伪代码,适合我
编辑3:替换实现以显示文件和行.减少内存需求(不将整个文件加载到内存中); 但是打印该行确实需要存储所有"开始"行.
public class T {
public static Collection<String> findHung(Iterable<String> data) {
Pattern p = Pattern.compile(
"ScriptExecThread\\(([0-9]+).*?(finished|starting)");
HashMap<Integer, String> started = new HashMap<Integer, String>();
Set<Integer> finished = new HashSet<Integer>();
for (String d : data) {
Matcher m = p.matcher(d);
if (m.find()) {
int n = Integer.parseInt(m.group(1));
if (m.group(2).equals("starting")) started.put(n, d);
else finished.add(n);
}
}
for (int f : finished) {
started.remove(f);
}
return started.values();
}
static Iterable<String> readFile(String path, String encoding) throws IOException {
final Scanner sc = new Scanner(new File(path), encoding).useDelimiter("\n");
return new Iterable<String>() {
public Iterator<String> iterator() { return sc; }
};
}
public static void main(String[] args) throws Exception {
for (String fileName : args) {
for (String s : findHung(readFile(fileName, "UTF-8"))) {
System.out.println(fileName + ": '" + s + "' unfinished");
}
}
}
}
输入:上面的示例数据,作为第一个参数,称为"data.txt".另一个名为"data2.txt"的文件中的相同数据作为第二个参数(javac T.java && java T data.txt data2.txt).输出:
data.txt: ' 09.08 15:06.54, ScriptExecThread(18),Info,###################### starting' unfinished
data.txt: ' 09.08 15:06.53, ScriptExecThread(7),Info,########### starting' unfinished
data2.txt: ' 09.08 15:06.54, ScriptExecThread(18),Info,###################### starting' unfinished
data2.txt: ' 09.08 15:06.53, ScriptExecThread(7),Info,########### starting' unfinished
保留两组独立的started和finished线程（如@tucuxi 所描述）是行不通的。如果 ID 为 5 的线程启动、运行并结束，则 5 将finished永远出现在集合中。如果 ID 为 5 的另一个线程启动并挂起，则不会报告该情况。
不过，暂时假设线程 ID 没有被重用。每个创建的线程都会收到一个新的 ID。通过保持分离started和finished集合，当您完成时，您将在每个元素中拥有数十万个元素。这些数据结构的性能与操作时它们所包含的内容成正比。性能不太可能对您的用例产生影响，但如果您执行更昂贵的操作，或者运行 100 倍大的数据，则可能会产生影响。
序言不碍事，这里是 @tucuxi 代码的工作版本：
import java.util.*;
import java.io.*;
import java.util.regex.*;
public class T {
public static Collection<String> findHung(Iterable<String> data) {
Pattern p = Pattern.compile(
"ScriptExecThread\\(([0-9]+).*?(finished|starting)");
HashMap<Integer, String> running = new HashMap<Integer, String>();
for (String d : data) {
Matcher m = p.matcher(d);
if (m.find()) {
int n = Integer.parseInt(m.group(1));
if (m.group(2).equals("starting"))
running.put(n, d);
else
running.remove(n);
}
}
return running.values();
}
static Iterable<String> readFile(String path, String encoding) throws IOException {
final Scanner sc = new Scanner(new File(path), encoding).useDelimiter("\n");
return new Iterable<String>() {
public Iterator<String> iterator() { return sc; }
};
}
public static void main(String[] args) throws Exception {
for (String fileName : args) {
for (String s : findHung(readFile(fileName, "UTF-8"))) {
System.out.println(fileName + ": '" + s + "' unfinished");
}
}
}
}
请注意，我已经删除了该finished集合，HashMap现在称为running。当新线程开始时，它们进入，当线程结束时，它被拉出。这意味着HashMap始终是当前正在运行的线程数的大小，该大小始终小于（或等于）曾经运行的线程总数。所以对它的操作会更快。（一个令人愉快的副作用是，您现在可以逐条日志行跟踪正在运行的线程数量，这可能有助于确定线程挂起的原因。）
这是我用来生成大量测试用例的 Python 程序：
#!/usr/bin/python
from random import random, choice
from datetime import datetime
import tempfile
all_threads = set([])
running = []
hung = []
filenames = { }
target_thread_count = 16
hang_chance = 0.001
def log(id, msg):
now = datetime.now().strftime("%m:%d %H:%M:%S")
print "%s, ScriptExecThread(%i),Info,%s" % (now, id, msg)
def new_thread():
if len(all_threads)>0:
for t in range(0, 2+max(all_threads)):
if t not in all_threads:
all_threads.add(t)
return t
else:
all_threads.add(0)
return 0
for i in range(0, 100000):
if len(running) > target_thread_count:
new_thread_chance = 0.25
else:
new_thread_chance = 0.75
pass
if random() < new_thread_chance:
t = new_thread()
name = next(tempfile._get_candidate_names())+".txt"
filenames[t] = name
log(t, "%s starting" % (name,))
if random() < hang_chance:
hung.append(t)
else:
running.append(t)
elif len(running)>0:
victim = choice(running)
all_threads.remove(victim)
running.remove(victim)
log(t, "%s finished" % (filenames[victim],))