搜索 200 k 数组的整数数组？？ java

Question

我有一个包含 200 000 行整数的数组（包含更小的整数数组）。每行包含 1 - 20 个成员。整数的值为 0-200。看起来像这样：

...

[42, 66, 54, 145, 183, 198, 104, 24, 22, 125, 127]
[71, 149, 59, 147, 115, 36, 124]  // <--lets say i am searching for this line
[27, 141, 19, 75, 101, 149, 36, 7, 12, 108, 69, 149, 1, 39, 55, 87, 178, 76, 133]
[94, 170, 185, 17, 121, 42, 51, 70, 176, 187, 31, 181, 167, 200, 144, 126, 123, 120, 91, 40]
[112, 162, 173, 145, 0, 165, 106, 137]
[141, 198, 32]
...

如何在其中搜索特定行？请指导我正确的方向，如果可能 link 我举个例子。

我的意思是搜索 - 当我输入 71、149、59 时，我会得到我的行（如果有几行类似的行，我会接近它）。
花几天时间阅读仍然不确定如何进行。请帮忙。（我的列表是升序排列的）

哪种方法更好，哈希？二分查找？任何好的关键字或 link 感谢（我第一次搜索）

Answer 1

我怀疑您试图过早地优化您的搜索。除非您打算每秒执行多次，否则详尽搜索应该没问题。我假设 'close to it' 你的意图是找到所有以你传入的值开头的数组。

这是使用 Java 8:

的详尽搜索

List<int[]> searchForArrays(int[][] data, int[] value) {
    return Arrays.stream(data).parallel()
        .filter(line -> {
            for (int i = 0; i < value.length; i++)
                if (i >= line.length || value[i] != line[i])
                    return false;
            return true;
        });
        .collect(Collectors.toList());
}

这会找到与您的搜索词匹配的所有数组。如果您只需要找到一个匹配的数组并且您的数组已排序，那么您可以使用二进制搜索来加快速度：

int[] binarySearch(int[][] data, int from, int to, int[] value) {
    int trial = (from + to) / 2;
    if (from >= to)
        return new int[]{};
    int compare = compareTo(data[trial], value);
    if (compare < 0)
        return binarySearch(data, from, trial, value);
    else if (compare > 0)
        return binarySearch(data, trial, to, value);
    else 
        return data[trial];
}

如果您真的需要优化，那么您最好将数据重新组织成一棵树，其中包含从值到节点的映射。然后搜索将是一件微不足道的事情，只需按照树的节点查找要搜索的值。这可能看起来像：

class Node {
    private final Map<Integer, Node> children;
    private boolean terminal;
}

Answer 2

像下面这样的怎么样，以后觉得合适我再充实一下：

package area51;

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

public class Junk {
    Node root;
    static void main(String[] args) {

    }

    public Node initialize() {
        root = new Node(0);
        int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 } };
        for (int[] row : matrix) {
            Node parent = root;
            for (int childValue : row) {
                parent = parent.addChild(childValue);
            }
        }
        return root;
    }

    public List<int[]> find(int[] key, int limit){
        //use some recursion
        List<int[]> list = new ArrayList<int[]>();
        Node node = root;
        for (Node child: node.children){
            ....
        }
        return list;
    }


    class Node {
        int value;
        List<Node> children;

        Node(int value) {
            super();
            this.value = value;
        }

        Node addChild(int childValue) {
            if (children == null) {
                children = new ArrayList<Node>();
            }
            Node child = new Node(childValue);
            children.add(child);
            return child;
        }
    }
}

搜索 200 k 数组的整数数组？？ java

search 200 k array of arrays of integers?? java

java

arrays

sorting

search