Сравнение двух JSONArray массивов

225

14 января 2018, 04:52

Добрый день.

Есть приложение, которое получает 2 массива JSONArray с объектами, в которых находится по 3 поля. У каждого объекта есть поле_id int с каким-то значением. Размеры каждого массива всегда разные. Один массив может быть равен 300, другой 3000. Необходимо их сравнить и найти объекты, значения полей поле_id одинаковые.

Подскажите как правильно это реализовать?

Первое, что приходит в голову, это сделать 2 цикла, в которых объекты каждого массива помещаются в 2 разных ArrayList<JSONObject>, а потом в цикле каждое значение большего списка сравнивать со всеми значениями меньшего списка, но что-то мне подсказывает, что это неправильное решение, которое займёт очень много времени.

Может есть какие-то более правильные решения?

Answer 1

Один массив кладёте в Map-у, с ключами id.

А второй просто в цикле прогоняете, беря из Map-ы объект с ключом из второго массива. Зная что по Map-е поиск идёт за константное время, сложность алгоритма получается в O(N).

Никаких собственных сложных алгоритмов реализовывать не придётся, просто цикл.

Код примерно такой:

JSONArray one = ...
JSONArray two = ...
Map<Integer, JSONObject> idsToOneElements = new HashMap<>();
for (int i = 0; i < one.length; ++i) {
    JSONObject object = one.getJSONObject(i);
    idsToOneElements.put(object.getInt("id"), object);
}
List<JSONObject> commonElements = new ArrayList<>();
for (int i = 0; i < two.length; ++i) {
    JSONObject object = two.getJSONObject(i);
    if (idsToOneElements.containsKey(object.getInt("id"))) {
        commonElements.add(object);
    }
}

(Используются классы JSONArray, JSONObject, HashMap, ArrayList и методы JSONArray.length, JSONArray.getJSONObject, JSONObject.getInt, HashMap.put, HashMap.containsKey. Вместо HashMap<Integer, JSONObject> можно был в принципе и HashSet<Integer> использовать)

Answer 2

Идея такова: отсортировать quick sort-ом массив по этим самым id, а затем для каждого такого массива выполнить бинарный поиск. Это самые быстрые алгоритмы, которые избавят вас от необходимости перебирать каждый элемент и сравнивать со всеми другими. В Java уже есть метод для быстрой сортировки, а бинарный поиск или уже есть, или вы можете написать сами.