我想我可以做得更好(对不起,有点长):
import java.io.File;
import java.io.FileInputStream;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class LZ78 {
public static double kComplexity(String s) {
Set dictionary = new HashSet();
StringBuilder w = new StringBuilder();
double comp = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (dictionary.contains(w.toString() + c)) {
w.append(c);
} else {
comp++;
dictionary.add(w.toString() + c);
w = new StringBuilder();
}
}
if (w.length() != 0) {
comp++;
}
return comp;
}
private static boolean equal(Object o1, Object o2) {
return o1 == o2 || (o1 != null && o1.equals(o2));
}
public static final class FList {
public final FList head;
public final T tail;
private final int hashCodeValue;
public FList(FList head, T tail) {
this.head = head;
this.tail = tail;
int v = head != null ? head.hashCodeValue : 0;
hashCodeValue = v * 31 + (tail != null ? tail.hashCode() : 0);
}
@Override
public boolean equals(Object obj) {
if (obj instanceof FList>) {
FList> that = (FList>) obj;
return equal(this.head, that.head)
&& equal(this.tail, that.tail);
}
return false;
}
@Override
public int hashCode() {
return hashCodeValue;
}
@Override
public String toString() {
return head + ", " + tail;
}
}
public static final class FListChar {
public final FListChar head;
public final char tail;
private final int hashCodeValue;
public FListChar(FListChar head, char tail) {
this.head = head;
this.tail = tail;
int v = head != null ? head.hashCodeValue : 0;
hashCodeValue = v * 31 + tail;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof FListChar) {
FListChar that = (FListChar) obj;
return equal(this.head, that.head) && this.tail == that.tail;
}
return false;
}
@Override
public int hashCode() {
return hashCodeValue;
}
@Override
public String toString() {
return head + ", " + tail;
}
}
public static double kComplexity2(String s) {
Map, FList> dictionary =
new HashMap, FList>();
FList w = null;
double comp = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
FList w1 = new FList(w, c);
FList ex = dictionary.get(w1);
if (ex != null) {
w = ex;
} else {
comp++;
dictionary.put(w1, w1);
w = null;
}
}
if (w != null) {
comp++;
}
return comp;
}
public static double kComplexity3(String s) {
Map dictionary =
new HashMap(1024);
FListChar w = null;
double comp = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
FListChar w1 = new FListChar(w, c);
FListChar ex = dictionary.get(w1);
if (ex != null) {
w = ex;
} else {
comp++;
dictionary.put(w1, w1);
w = null;
}
}
if (w != null) {
comp++;
}
return comp;
}
public static void main(String[] args) throws Exception {
File f = new File("methods.txt");
byte[] data = new byte[(int) f.length()];
FileInputStream fin = new FileInputStream(f);
int len = fin.read(data);
fin.close();
final String test = new String(data, 0, len);
final int n = 100;
ExecutorService exec = Executors.newFixedThreadPool(1);
exec.submit(new Runnable() {
@Override
public void run() {
long t = System.nanoTime();
double value = 0;
for (int i = 0; i < n; i++) {
value += kComplexity(test);
}
System.out.printf("kComplexity: %.3f; Time: %d ms%n",
value / n, (System.nanoTime() - t) / 1000000);
}
});
exec.submit(new Runnable() {
@Override
public void run() {
long t = System.nanoTime();
double value = 0;
for (int i = 0; i < n; i++) {
value += kComplexity2(test);
}
System.out.printf("kComplexity2: %.3f; Time: %d ms%n", value
/ n, (System.nanoTime() - t) / 1000000);
}
});
exec.submit(new Runnable() {
@Override
public void run() {
long t = System.nanoTime();
double value = 0;
for (int i = 0; i < n; i++) {
value += kComplexity3(test);
}
System.out.printf("kComplexity3: %.3f; Time: %d ms%n", value
/ n, (System.nanoTime() - t) / 1000000);
}
});
exec.shutdown();
}
}
结果:
kComplexity: 41546,000; Time: 17028 ms
kComplexity2: 41546,000; Time: 6555 ms
kComplexity3: 41546,000; Time: 5971 ms
编辑
同龄人压力:如何工作?
弗兰基,不知道,这似乎是一个加速事情的好方法。我也得想清楚,我们开始吧。
但是,可以观察到原始代码产生了许多字符串附加,将其替换为
LinkedList
因为在哈希表中查找集合的压力是恒定的,所以不会有任何帮助——每次使用hashcode()和equals()时,都需要遍历整个列表。
但我如何确保代码不执行这种不必要的操作呢?答案:不可变-如果类是不可变的,那么至少哈希代码是常量,因此,可以预先计算。相等性检查也可以缩短,但在最坏的情况下,它仍将遍历整个集合。
这很好,但是如何“修改”不可变类。不,你不需要,每次需要不同的内容时都会创建一个新的。但是,当您仔细查看字典的内容时,您会发现它包含冗余信息:
[]a
,
[abc]d
,
[abc]e
,
[abcd]f
. 那么,为什么不将头部存储为指向以前看到的模式的指针,并为当前角色设置尾部呢?
确切地。使用不可变和反向引用可以节省空间和时间,甚至垃圾收集器也会爱你。我的解决方案的一个特点是,在f_和haskell中,列表使用head:[尾]签名-head是元素类型,tail是指向下一个集合的指针。在这个问题中,当列表在尾部增长时,需要相反的结果。
从这里开始,它只是一些进一步的优化——例如,使用一个具体的
char
作为尾部类型,避免了常量字符自动氧化的通用版本。
我的解决方案的一个缺点是,它在计算列表的各个方面时使用递归。对于相对较小的列表来说,这是可以的,但是较长的列表可能需要增加运行计算的线程堆栈大小。理论上,用Java 7的尾部调用优化,可以以允许JIT执行优化的方式重写我的代码(或者它已经是这样)了吗?很难说清楚。