List<List<String>> 与 String[][]

Question

我想在 Java 中创建一个二维字符串 'matrix' 对象。我的两个目标是提高效率和简化代码。

我听说使用 ArrayList 比使用 String[][] 更有效。首先，我想知道这是否属实，如果属实，效率会提高多少？

另一件事是我必须能够向 'matrix' 添加列和行。我能够开发一些有效的算法来向 String[][] 添加行和列。我很想知道以这种方式开发算法来操作 2D 列表是否值得 - 性能会有显着提高吗？

感谢您的帮助！

Answer 1

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

Answer 2

首先是简单的回答：直接数组操作会更快，因为您避免了通用目的的开销类。您甚至可以通过利用 Unsafe 实例（非 public API）进行直接数组访问来获得更高的性能。

对于意见部分：如果性能很重要，我宁愿研究如何在不同系统之间并发执行或分布事物。在那种情况下，我宁愿避免直接使用数组，因为这很难维护。但当然这完全取决于您的具体用例。

因此，就像所有与性能相关的问题一样，针对您的特定用例进行一些测量，然后自行决定最适合您的方法。

就像我在评论中所说的那样，我已经摆弄了自己的Matrix implementation which have two specialised Map implementations (CompactArrayMap and DirectArrayMap)，它们都是键自然顺序上的键映射，非常像数组但具有映射功能。

List<List<String>> 与 String[][]

List<List<String>> vs. String[][]

java

performance

math

matrix

processing-efficiency