著名压缩算法（LZ78）的java慢速实现

# 1 楼答案

由于您总是检查prefix+c，我认为一个好的数据结构可以是一个树，其中每个子节点都有其父节点作为前缀：

           root
        /       |
       a        b
      /  |     /  | 
     an  ap   ba bo
         |         
         ape

另一种可能更简单的方法是使用排序列表，然后使用二进制搜索来查找正在查看的字符串。但我仍然认为树方法会更快

# 2 楼答案

ArrayList将具有O（N）搜索复杂性。使用数据结构，如哈希表或字典

# 3 楼答案

您可以尝试的另一个微观优化是用这些fastutil实现http://fastutil.dsi.unimi.it/替换collections对象，这基本上是免费的加速

# 4 楼答案

在我看来，{}并不是保存只包含和添加内容的词典的最佳数据结构

编辑

尝试使用HashSet，将其元素存储在哈希表中，这是Set interface的最佳实现；然而，它不保证迭代的顺序

# 5 楼答案

我想我可以做得更好（抱歉，时间有点长）：

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 {
    /**
     * Uses the LZ78 compression algorithm to approximate the Kolmogorov
     * complexity of a String
     * 
     * @param s
     * @return the approximate Kolmogorov complexity
     */
    public static double kComplexity(String s) {
        Set<String> dictionary = new HashSet<String>();
        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<T> {
        public final FList<T> head;
        public final T tail;
        private final int hashCodeValue;

        public FList(FList<T> 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<Character>, FList<Character>> dictionary = 
            new HashMap<FList<Character>, FList<Character>>();
        FList<Character> w = null;
        double comp = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            FList<Character> w1 = new FList<Character>(w, c);
            FList<Character> 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<FListChar, FListChar> dictionary = 
            new HashMap<FListChar, FListChar>(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<String>替换它不会有帮助，因为在哈希表中查找集合的压力是恒定的——每次使用hashCode（）和equals（）时，它都需要遍历整个列表

但是如何确保代码不会执行这些不必要的操作呢？答案是：不变性——如果你的类是不可变的，那么至少hashCode是常量，因此可以预先计算。等式检查也可以简化，但在最坏的情况下，它仍将遍历整个集合

这很好，但是如何“修改”一个不可变的类呢。不，你不需要，每次需要不同的内容时，你都会创建一个新的内容。然而，当你仔细查看字典的内容时，你会发现它包含冗余信息：[]a，[abc]d，[abc]e，[abcd]f。那么，为什么不将头部存储为指向之前看到的模式的指针，并为当前角色设置一个尾部呢

没错。使用不变性和反向引用可以节省空间和时间，甚至垃圾收集器也会喜欢你。我的解决方案的一个特点是，在F#和Haskell中，列表使用head:[tail]签名——head是元素类型，tail是指向下一个集合的指针。在这个问题上，随着列表在尾部的增长，需要相反的结果

从这里开始，它只是一些进一步的优化——例如，使用一个具体的char作为尾部类型，以避免泛型版本的常量字符自动装箱

我的解决方案的一个缺点是，它在计算列表的各个方面时使用递归。对于相对较小的列表，这是可以的，但较长的列表可能需要增加运行计算的线程堆栈大小。从理论上讲，通过Java7的尾部调用优化，我的代码可以被重写为允许JIT执行优化的方式（或者已经这么做了？很难说）

Python中文网

有 Java 编程相关的问题?