Какой эффективный алгоритм сделать один список равным другому?

Question

Допустим, у меня есть список A, который должен выглядеть точно так же, как список B. Все объекты, которые есть у B, но у A нет необходимости, должны быть добавлены к A. И все объекты, которые есть у A, но не B, должны быть удаленным из А.

Причина, по которой мне это нужно, заключается в том, что у меня есть ArrayList of Players, который я сохраняю в файл. Каждый раз, когда я обновляю атрибут Player, я сохраняю изменения в файле, вызывая метод, который просматривает ArrayList of Players и сохраняет его. Это работает, потому что ArrayList имеет ссылки на игроков.

Однако всякий раз, когда я ищу игрока в списке, я сначала обновляю список, читая файл, в котором он хранится. Это заменяет все ссылки совершенно новыми объектами. После того, как я сделаю это, если я внесу изменения в ранее загруженного пользователя и попытаюсь сохранить его. Новый экземпляр проигрывателя сохраняется вместо того, в котором я внес изменения.

Может ли придумать хороший алгоритм, чтобы сделать список равным другому решению? Или есть лучший способ обновить весь список, сохраняя ссылки там?

ОБНОВЛЕНИЕ: обновленное решение, выполняется за время O (nlogm). Перебирает каждый элемент в пункте назначения, ищет его в источнике. Если он найден, удален из источника. Если нет, удаляется из пункта назначения. Затем добавьте оставшиеся элементы в источнике к месту назначения. Конечно, список нужно отсортировать, но список, который я получаю из файла, будет уже отсортирован, потому что я сортирую по мере добавления.

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class CopyList {
    public static void copyList(List dest, List src) {
        copy(dest, src);

        // the remaining elements in src list will be those that were originally
        // in src but not in dest and so they need to be added
        dest.addAll(src);
    }

    public static void copyList(List dest, List src, Verify v) {
        copy(dest, src);

        // the remaining elements in src list will be those that were originally
        // in src but not in dest and so they need to be added
        addAll(dest, src, v);
    }

    public static void copyList(List dest, List src, Comparator c) {
        copy(dest, src, c);

        // the remaining elements in src list will be those that were originally
        // in src but not in dest and so they need to be added
        dest.addAll(src);
    }

    public static void copyList(List dest, List src, Comparator c, Verify v) {
        copy(dest, src, c);

        // the remaining elements in src list will be those that were originally
        // in src but not in dest and so they need to be added
        addAll(dest, src, v);
    }

    private static void copy(List dest, List src) {
        // go through dest list to search if every element is in the new list
        // travel backwards through dest because we will be removing elements from it
        for(int i = dest.size()-1; i >= 0 ; i--) {
            int src_i = Collections.binarySearch(src, dest.get(i));
            if(src_i >= 0)
                // if element is found in src list, remove it from src list
                src.remove(src_i);
            else
                // if element is NOT found in src list, remove it from dest list
                dest.remove(i);
        }
    }

    private static void copy(List dest, List src, Comparator c) {
        // go through dest list to search if every element is in the new list
        // travel backwards through dest because elements might be removed
        for(int i = dest.size()-1; i >= 0 ; i--) {
            int src_i = Collections.binarySearch(src, dest.get(i), c);
            if(src_i >= 0)
                // if element is found in src list, remove it from src list
                src.remove(src_i);
            else
                // if element is NOT found in src list, remove it from dest list
                dest.remove(i);
        }
    }

    private static void addAll(List dest, List src, Verify v) {
        // verify each element in src list before adding it to dest list
        for(Object o: src)
            if(v.verify(o))
                dest.add(o);
    }
}

Answer 1

Я бы отступил и подумал о дизайне вашей программы. Похоже, было бы разумнее иметь класс, который будет управлять всеми вашими игроками - сохранять их, обновлять их, раздавать ссылки на них. Тогда просто не храните ссылку на игрока где-либо еще, сохраняйте ссылку на свой PlayerManager (или как вы хотите его назвать) и запрашивайте его, чтобы получить игроков.

Это даст вам один канонический список, и вам не нужно будет беспокоиться об устаревших ссылках.

Answer 2

Не проще ли было бы создать копию списка B? Это будет включать только создание копии базового массива, что потребует гораздо меньше времени и усилий, чем сложный алгоритм (не говоря уже о том, что его легче обслуживать).

Answer 3

Ваша программа была бы быстрее, если бы вы использовали наборы вместо списков, т. Е. O (1) сложность времени при отсутствии коллизий хешей.

for(User u : new_users) {
    if (!users.contains(u)) {
        users.add(u);
    }
}
for(User u : users) {
    if (!new_users.contains(u)) {
        users.remove(u);
    }
}

Answer 4

Рассматривали ли вы использовать HashSet для своих списков? Таким образом, вы можете просто сделать addAll() и объединить эти списки. Используйте LinkedHashSet, если вы хотите сохранить оригинальный порядок. Было бы намного быстрее Вам просто нужно переопределить hashCode() в классе Player, чтобы вернуть хэш их имени.

Answer 5

Я согласен с другим представлением здесь, что это кажется ненужным для вашего приложения, но из интереса, если вы хотите, чтобы алгоритм, который выполняет то, что вы описываете, лучше, чем n ^ 2 раза, есть один (и он работает в n * войти n раз)

sort list users (n log n)
sort list new_users (n log n)
iterate through users and new_users in parallel, adding or removing items from users as necessary ( n )

Answer 6

Однако всякий раз, когда я ищу игрока в списке, я сначала обновляю список, читая файл, в котором он хранится.

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

О, и есть действительно простой способ заставить a содержать те же вещи, что и b:

a = b;