Реализация внутреннего соединения с использованием простого вложенного цикла в Java

Question

В одном из интервью меня спросили, как реализовать Inner Join с использованием вложенного цикла for в Java.Я нашел в интернете информацию о Hash Join здесь https://rosettacode.org/wiki/Hash_join, но не смог найти в интернете ничего, объясняющего простую реализацию внутреннего объединения с помощью вложенного цикла.Я пытался реализовать код, но застрял в нескольких местах, как указано в комментарии к коду.

/**
 * 
 * @param R
 * @param index1 Join column for table R.
 * @param S
 * @param index2 Join column for table S.
 * @return
 */
public String[][] innerJoin(String[][] R, int index1, String[][] S, int index2) {
    // How to define the result array. What should be it's size?? Is the below code correct.
    String[][] result = new String[R.length + S.length][R[0].length + S[0].length];

    // loop through both the tables to find out when the join column have common values.
    // output those common values.
    for (int i = 0; i < R.length; i++) {
        for (int j = 0; j < S.length; j++) {
            if (R[i][index1] == S[j][index2]) {
                // How to combine both tables here ???
            }
        }
    }

    return result;
}

)

Answer 1

Вы правильно определили 3 важных вопроса в коде вопроса:

• как рассчитать размер таблицы результатов?
• как вы находите совпадения?
• когда вы находите совпадение, как добавить его в таблицу результатов?

Простой способ подсчитать результатэто хранить совпадения где-то еще, а затем посчитать, сколько вы нашли, прежде чем вернуть их.В этом смысле было бы лучше использовать ArrayList<String[]> вместо String[][], потому что вы можете добавить к ArrayLists, но не можете изменить размер массивов.

Поиск совпадений с двойным циклом действительноочень неэффективный O(nm), но, эй, если это то, чего они хотят, это, безусловно, можно сделать.Было бы намного проще сначала отсортировать индексы, а затем работать с ними (O(n log n + m log m + n log m), с O (n + m) дополнительной памятью);или создайте хеш-таблицы и используйте их (O(n + m + n) = O(n + m)).

Выбор того, что возвращать, зависит от того, что представляют столбцы, и если есть какие-либо дубликаты.Например, вы можете выбрать следующий формат:

• в качестве 1-го столбца, содержимое index1
• всех столбцов (кроме index1 один) из 1-й таблицы
• все столбцы (кроме index2) из второй таблицы.

Обратите внимание, что выбор формата несколько произвольный;Вы могли бы оставить index1 на его месте, а затем просто опустить его из столбцов таблицы 2. В любом случае, с предыдущими ответами, вы получите:

public String[][] innerJoin(String[][] R, int index1, String[][] S, int index2) {
    // temporary storage for matches
    ArrayList<String[]> matches = new ArrayList<>();

    // loop through both the tables to find out when the join column have common values.
    // output those common values.
    for (int i = 0; i < R.length; i++) {
        for (int j = 0; j < S.length; j++) {
            if (R[i][index1] == S[j][index2]) {
                matches.add(combine(R[i], S[j], index1, index2));
            }
        }
    }

    // convert matches to expected output array
    return matches.toArray(new String[matches.size()][]);
}

private String[] combine(String[] one, String[] two, int index1, int index2) {
    String[] r = new String[one.length + two.length - 1];
    int pos = 0;
    r[pos ++] = one[index1];
    for (int i=0; i<one.length; i++) if (i != index1) r[pos ++] = one[i];
    for (int i=0; i<two.length; i++) if (i != index2) r[pos ++] = two[i];
    return r;
}

Answer 2

Я попытаюсь дать вам несколько подсказок:

• Длина массива результатов не является суммой длины таблиц R и S.В зависимости от содержимого таблиц, оно может быть до R.length * S.length.

• Количество «столбцов» в массиве результатов действительно R[0].length + S[0].length (при условии, что массивыявляются «настоящими» таблицами и не имеют переменного числа «столбцов» на «строку»).

• В вашем цикле (в блоке if) вы должны
  • В текущей «выходной» строке массива результатов (начиная с 0) сначала установите R[0].length столбцы (0..rl - 1) на содержимое R[i][0] ... R[i][rl - 1] столбцов
  • Затем установитеrl ... R[0].length + S[0].length - 1 столбцы (rl ... rl + sl - 1) к содержимому S[j][0] ... S[j][sl - 1] столбцов
  • Инкремент счетчика для текущей "выходной" строки в массиве результатов

В конце концов, это просто некоторая арифметика смещения массива; -)