为java矩阵编制索引

Question

我想知道是否有可能对矩阵的多列进行索引，以加快排序速度。在MySQL中，您可以在多个列上建立索引，这使得在表中查找元素的速度更快，但我不知道这在标准java矩阵中是否可行。例如，我的数据是一个由3列组成的矩阵，它有一个id、名字和姓氏，然后是这个表上的许多条目。现在，我可以说类似于mat5，并获得id为5的个人的条目，但我还希望能够按姓氏列搜索条目。在Java中如何才能最有效地完成这项工作？

Answer 1

如果是Java，您总是可以设置一个哈希表，将姓氏与矩阵行索引的数组相关联，以便这些行上的人员具有该姓氏。

或者你可以有一个多级哈希表，这样你就可以做m[index.get(lastName).get(firstName)]了。

此外，如果您希望按字典顺序遍历名称，则可以用TreeMap替换哈希表。

示例：

import java.util.*;
class Test{
    public static void main(String[]args){

        Object[][] m = new Object[][]{
            {1, "Smith", "John"},
            {2, "Stone", "Jack"},
            {3, "Stein", "Robert"},
            {4, "Stone", "Bob"}
        };

        //index.get(lastName) will return a map between
        //first names and matrix row indices. 
        //index.get(lastName).get(firstName) returns the index
        //in the matrix of the row pertaining to person (lastName, firstName)
        TreeMap<String, TreeMap<String, Integer>> index = 
            new TreeMap<String, TreeMap<String, Integer>>();

        //create index
        for(int i=0;i<m.length;i++){
            Object[]o = m[i];
            String last = o[1].toString();
            String first = o[2].toString();
            TreeMap<String,Integer> index2 = index.get(last);
            if (index2==null){
                index2=new TreeMap<String,Integer>();
                index.put(last, index2);
            }
            index2.put(first, i);
        }

        System.out.print("Smith, John -> ");
        System.out.println(Arrays.toString(m[index.get("Smith").get("John")]));

        System.out.print("Stone -> ");
        System.out.println(index.get("Stone"));

        System.out.print("Full index: ");
        System.out.println(index); 
    }
}

输出：

Smith, John -> [1, Smith, John]
Stone -> {Bob=3, Jack=1}
Full index: {Smith={John=0}, Stein={Robert=2}, Stone={Bob=3, Jack=1}}

在我给出的示例中，仅将姓氏映射到行索引是不够的，因为您可能会有两个姓氏相同的人。然而，我确实做了一个假设，你不会有两个名字完全相同的人。否则，您将需要像TreeMap<String, TreeMap<String, ArrayList<Integer>>>这样的东西，以便能够找到具有给定(姓，名)的每个人。如果想要按ID进行搜索，只需要创建第二个索引，将ID映射到行索引，它可以是一个HashMap<Integer, Integer>。

对于这个小示例，使用索引没有太多好处，因为它们可能比矩阵本身占用更多的空间，但如果您的记录很大，它可能会得到回报。

Answer 2

通常，如果您想通过多种方式访问Java数据结构，则必须创建额外的“并行”结构。

例如，您可以让您的“主表”--无论它是一个数组、一个列表还是其他什么--按名称排序或键控。然后，您将创建第二个表，该表按客户编号排序，该表中的每个条目都可以保存到第一个表的索引，或者对象句柄的另一个副本。然后，您可以有第三个按出生日期排序的表，其条目也指向第一个表，依此类推。

例如：

class Customer
{
  public String name;
  public int customerNumber;
  public int shoeSize;
  ... whatever ...
}
class byName implements Comparator<Customer>
{
  public int compareTo(Customer c1, Customer c2)
  {
    return c1.name.compareTo(c2.name);
  }
}
class byShoeSize implements Comparator<Customer>
{
  public int compareTo(Customer c1, Customer c2)
  {
    return c1.shoeSize-c2.shoeSize;
  }
}

... elsewhere ...
Customer[] nameOrder=new Customer[100];
nameOrder[0]=new Customer("Fred Smith", 10001, 9);
nameOrder[1]=new Customer("Mary Jones", 10002, 7);
... etc, however we get the list initialized ...
Arrays.sort(nameOrder, byName);

Customer[] shoeSizeOrder=new Customer[100];
for (int n=0;n<customerList.length;++n)
  byNumber[n]=customerList[n];
Arrays.sort(shoeSizeOrder, byShoeSize);

(通常的免责声明:未经测试的代码从我的头顶。请原谅任何语法错误。省略了错误检查和其他过度简化，从而给出了想法。等)

在此之后，您将拥有一个按姓名排序的列表和另一个按鞋码排序的列表。然后，您可以按顺序扫描每个列表，对分搜索以查找特定值，等等。

当然，并没有说明所有的列表都必须是数组。它们可以是哈希表、数组列表或任何其他有序的或具有键/值映射的结构。

请注意，这不是同一数据的两个副本。只有一组对象。每个对象只有两个句柄，每个列表中有一个句柄。