индексирование Java-матрицы

Question

Я хотел знать, можно ли индексировать несколько столбцов матрицы для ускорения сортировки. В MySQL вы можете иметь индексы по нескольким столбцам, что ускоряет поиск элементов в таблице, но я не знаю, возможно ли это в стандартной Java-матрице. Например, мои данные представляют собой матрицу из 3 столбцов, в которой есть идентификатор, имя и фамилия, а затем много записей в этой таблице. Прямо сейчас я могу сказать что-то вроде mat [5] и получить запись для человека с идентификатором 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>>>, чтобы можно было найти всех с заданным именем (фамилия, имя).Если вы хотите осуществлять поиск по идентификатору, вам просто нужно создать второй индекс, сопоставляя идентификаторы с индексами строк, которые могут быть 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);

(Обычный отказ от ответственности: непроверенный код у меня в голове. Прошу прощения за любые синтаксические ошибки. Проверка ошибок пропущена и другие упрощения, чтобы дать идею. И т.д.

После этого у вас будет один список, отсортированный по имени, и другой список, отсортированный по размеру обуви. Затем вы можете сканировать каждый список по порядку, двоичный поиск, чтобы найти конкретные значения и т. Д.

Конечно, ничто не говорит о том, что все списки должны быть массивами. Это могут быть хеш-таблицы, списки массивов или любая другая структура, которая либо упорядочена, либо имеет сопоставление ключ / значение.

Обратите внимание, что это не две копии одних и тех же данных. Есть только один набор объектов. У нас есть только две РУЧКИ для каждого объекта, по одному в каждом списке.