Блог

Я хотел знать, возможно ли проиндексировать несколько столбцов матрицы для ускорения сортировки. В MySQL вы можете иметь индексы по нескольким столбцам, что ускоряет поиск элементов в таблице, но я не знаю, возможно ли это в стандартной матрице Java. Например, мои данные представляют собой матрицу из 3 столбцов, которая содержит идентификатор, имя и фамилию, а затем множество записей в этой таблице. Прямо сейчас я могу произнести что-то вроде mat[5] и получить запись для пользователя с идентификатором 5, но я также хочу иметь возможность искать записи по столбцу фамилии. Как я могу сделать это наиболее эффективно на Java?

Если это 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> .

В этом небольшом примере от наличия индексов мало что выиграет, поскольку они, вероятно, занимают больше места, чем сама матрица, но это, вероятно, окупается, если ваши записи большие.

В общем, если вам требуется более одного способа доступа к структуре данных 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);
  

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

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

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

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