List<List<String>>诉String[][]

Question

我希望在Java中创建一个2D字符串“矩阵”对象。我的两个目标是提高效率和简化代码。

我听说使用ArrayList比字符串要高效得多。首先，我想知道这是否属实，如果是的话，效率有多高？

另一件事是，我必须有能力向“矩阵”中添加列和行。我开发了一些有效的算法来将行和列添加到字符串中。我很想知道，用这种方式开发算法来操作2D列表是否值得--性能会有显著的提高吗？

谢谢你的帮忙!

Answer 1

首先，简单的回答是:直接数组操作将更快，因为您避免了通用类的开销。通过利用不安全实例(非公共API)进行直接数组访问，您甚至可以获得更高的性能。

对于意见部分:如果性能如此重要，我宁愿看看如何在不同的系统中并发执行或分发。在这种情况下，我倾向于避免直接使用数组，因为这将很难维护。当然，这一切都取决于您的特定用例。

因此，与所有与性能相关的问题一样，为您的特定用例做一些度量，并自行决定什么对您最合适。

正如我在评论中所说的，我摆弄了自己的矩阵实现，它们有两个专门的Map实现(CompactArrayMap和DirectArrayMap)，它们都是键自然顺序上的键映射的int，非常类似于数组，但具有映射功能。

Answer 2

List是一个接口。给定此接口，您可以使用不同的实现，如ArrayList、LinkedList、CopyOnWriteArrayList等。

所以你的问题应该改为

ArrayList<ArrayList<String>> vs String[][]

ArrayList是使用数组实现的列表。它有让您在特定位置处理元素的方法：

void add(int index, E element);
E    get(int index);

我以前认为ArrayList几乎和数组一样快，但我认为实际的使用将决定实际的性能差异。下面，我添加了一个轶事实验的一些结果，表明数组比ArrayList更快，特别是在二维矩阵的填充过程中。两人的访问时间似乎是相等的。

ArrayList给了您一些优势，比如您不必事先知道大小。话虽如此，但是，如果我确信我需要的是数组，而不是泛型列表(例如，正如您所说的，用于矩阵计算)，那么我可以使用数组来实现更简洁的语法。

String s1 = array[i][j];
array[i][j] = s1;

对比

String s2 = list.get(j).get(i);
list.get(j).add(i, s2);

有关将接口与其实现区分开来的更多信息，请参阅Oracle/Sun编写的本教程：

https://docs.oracle.com/javase/tutorial/collections/implementations/list.html

轶事实验

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class ArrayListVsString {

    private static final int NUM_TESTS = 5;

    public static void main(String[] args) {
        List<List<String>>  list;
        String[][]          array; 
        int height  = 500;
        int width   = 1000;
        String __ = "    "; // indent
        for (int n=0; n<NUM_TESTS; n++) {
            System.out.format("Testing 2D matrix of %dx%d: Test %d%n"
                    , height, width, n);
            /*
             * Time to populate the matrices
             */
            long startTime = System.nanoTime();
            // array
            String subTestArray = "2-D array";
            array = new String[width][height];
            for (int i=0; i<width; i++) {
                for (int j=0; j<height; j++) {
                    array[i][j] = getRandomString();
                }
            }
            startTime 
                = logElapsedTime(startTime
                                , __ + "creating matrix as " 
                                     + subTestArray);
            // array-list
            String subTestList = "2-D array-list";
            list = new ArrayList<>(height);
            for (int j=0; j<height; j++) {
                List<String> row = new ArrayList<>(width);
                list.add(j, row);
                for (int i=0; i<width; i++) {
                    String element = getRandomString();
                    list.get(j).add(i, element);
                }
            }
            startTime 
                = logElapsedTime(startTime
                            , __ + "creating matrix as " 
                                 + subTestList);

            int hash = 0;
            /*
             * Time to do a full walk through all the elements
             */
            // array
            for (int i=0; i<width; i++) {
                for (int j=0; j<height; j++) {
                    hash += (array[i][j]).hashCode();
                }
            }
            startTime 
                = logElapsedTime(startTime
                                , __ + "full walk of matrix as" 
                                     + subTestArray);

            // array-list
            for (int j=0; j<height; j++) {
                for (int i=0; i<width; i++) {
                    hash += list.get(j).get(i).hashCode();
                }
            }
            startTime 
                = logElapsedTime(startTime
                                , __ + "full walk of matrix as "
                                     + subTestList);
            list = null;

        }

    }

    private static Random random = new Random();

    private static String getRandomString() {
        return String.valueOf(random.nextInt());
    }

    private static long logElapsedTime(long startTimeNano
            , String action) {
        long elapsedTimeNano = System.nanoTime() - startTimeNano;
        System.out.format("%s took %,d ms%n"
                    , action, elapsedTimeNano/1000000);

        return System.nanoTime();
    }
}

结果

Testing 2D matrix of 500x1000: Test 0
    creating matrix as 2-D array took 117 ms
    creating matrix as 2-D array-list took 232 ms
    full walk of matrix as2-D array took 25 ms
    full walk of matrix as 2-D array-list took 31 ms
Testing 2D matrix of 500x1000: Test 1
    creating matrix as 2-D array took 65 ms
    creating matrix as 2-D array-list took 186 ms
    full walk of matrix as2-D array took 20 ms
    full walk of matrix as 2-D array-list took 30 ms
Testing 2D matrix of 500x1000: Test 2
    creating matrix as 2-D array took 61 ms
    creating matrix as 2-D array-list took 60 ms
    full walk of matrix as2-D array took 14 ms
    full walk of matrix as 2-D array-list took 15 ms
Testing 2D matrix of 500x1000: Test 3
    creating matrix as 2-D array took 66 ms
    creating matrix as 2-D array-list took 358 ms
    full walk of matrix as2-D array took 16 ms
    full walk of matrix as 2-D array-list took 15 ms
Testing 2D matrix of 500x1000: Test 4
    creating matrix as 2-D array took 45 ms
    creating matrix as 2-D array-list took 55 ms
    full walk of matrix as2-D array took 14 ms
    full walk of matrix as 2-D array-list took 15 ms