java内核中文字操作和整数操作之间的性能问题

Question

我有一个PowerSet Util类，它计算set的所有可能的子集:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
/**
 * Created by ngrigoriev on 5/19/14.
 */
public class PowerSet {
    /**
     * Returns the power set from the given set by using a binary counter ordered by size Example: S = {a,b,c} P(S) = {[], [c], [b], [b, c], [a],
     * [a, c], [a, b], [a, b, c]}
     * @param superSet - Typed Set {@see Set}
     * @return LinkedHashSet @{see LinkedHashSet} with all possible Sub sets of @param superSet
     */
    public static <E> List<Set<E>> getAllCombinationsOfSubsets(final Set<E> superSet) {
        final List<E> listSet = new ArrayList<>(superSet);
        // create the empty power set
        final List<Set<E>> power = new LinkedList<>();
        // get the number of elements in the set
        final int elements = listSet.size();
        // the number of members of a power set is 2^n
        final int powerElements = (int) Math.pow(2, elements +1) - 1;
        // run a binary counter for the number of power elements
        for (int i = 0; i <= powerElements; i++) {
            // create a new set
            final Set<E> innerSet = new HashSet<>();
            // convert each digit in the current binary number to the
            // corresponding element
            // in the given set
            int tmp = i;
            for (int j = 0; j < elements; j++) {
                if (tmp % 2 == 1) {
                    innerSet.add(listSet.get(j));
                }
                tmp = tmp >> 1;
                if (tmp <= 0) {
                    break;
                }
            }
            // add the new set to the power set
            power.add(innerSet);
        }
        return power;
    }
    public static <E> List<Set<E>> powerset(final Set<E> superSet) {
        final List<E> listSet = new ArrayList<>(superSet);
        // create the empty power set
        final List<Set<E>> power = new LinkedList<>();
        // get the number of elements in the set
        final int elements = listSet.size();
        // the number of members of a power set is 2^n
        final int powerElements = (int) Math.pow(2, elements);
        // run a binary counter for the number of power elements
        for (int i = 0; i < powerElements; i++) {
            // convert the binary number to a String containing n digits
            final String binary = intToBinary(i, elements);
            // create a new set
            final LinkedHashSet<E> innerSet = new LinkedHashSet<>();
            // convert each digit in the current binary number to the
            // corresponding element
            // in the given set
            for (int j = 0; j < binary.length(); j++) {
                if (binary.charAt(j) == '1') {
                    innerSet.add(listSet.get(j));
                }
            }
            // add the new set to the power set
            power.add(innerSet);
        }
        return power;
    }

    /**
     * Converts the given integer to a String representing a binary number with
     * the specified number of digits For example when using 4 digits the binary
     * 1 is 0001
     *
     * @param binary
     * int
     * @param digits
     * int
     * @return String
     */
    private static String intToBinary(final int binary, final int digits) {
        final String temp = Integer.toBinaryString(binary);
        final int foundDigits = temp.length();
        String returner = temp;
        for (int i = foundDigits; i < digits; i++) {
            returner = "0" + returner;
        }
        return returner;
    }
}

这里是UnitTest

import java.util.HashSet;
import java.util.Set;
import junitparams.JUnitParamsRunner;
import org.junit.Test;
import org.junit.runner.RunWith;
/**
 * Created by ngrigoriev on 5/19/14.
 */
@RunWith(JUnitParamsRunner.class)
public class TestPowerSet {
    public static final int CONST = 1000;
    @Test
    public void testOnInteger() {
        final Set<Integer> set = new HashSet<>();
        for (int i = 0; i < 10; i++) {
            set.add(i);
        }
        final long time = System.currentTimeMillis();
        for (int lll = 1; lll < CONST; lll++) {
            PowerSet.getAllCombinationsOfSubsets(set);
        }
        System.out.println("Time: " + (System.currentTimeMillis() - time));
        System.out.println("total  " + Runtime.getRuntime().totalMemory() / 1024);
        final long time2 = System.currentTimeMillis();
        for (int lll = 1; lll < CONST; lll++) {
            PowerSet.powerset(set);
        }
        System.out.println("Time: " + (System.currentTimeMillis() - time2));
        System.out.println("total  " + Runtime.getRuntime().totalMemory() / 1024);
    }
}

为什么powerset方法工作得更快?有时占用更少的内存??我已经试着看了byteCode，但我没有发现很大的差异。也许有人能告诉我发生了什么事。

Answer 1

原因很简单:较慢的方法是错误的。它返回的列表包含的元素数量是快的列表的两倍。

运行，例如

public class TestPowerSet2
{
    public static void main(String[] args)
    {
        Set<Integer> set = new LinkedHashSet<Integer>(Arrays.asList(0,1,2));
        List<Set<Integer>> resultA = PowerSet.getAllCombinationsOfSubsets(set);
        System.out.println("Result A:");
        for (Set<Integer> s : resultA)
        {
            System.out.println("    "+s);
        }
        List<Set<Integer>> resultB = PowerSet.powerset(set);
        System.out.println("Result B:");
        for (Set<Integer> s : resultB)
        {
            System.out.println("    "+s);
        }
    }
}

getAllCombinationsOfSubsets中元素数的计算和循环应与powerset方法相同，即

// the number of members of a power set is 2^n
final int powerElements = (int) Math.pow(2, elements);
// run a binary counter for the number of power elements
for (int i = 0; i < powerElements; i++) {

那么，第一种方法更快(如预期的那样)。

顺便说一下:2的幂也可以通过位移位来计算:

final int powerElements = 1 << elements;