Как лучше использовать порядок одного ArrayList для заказа другого в Java?

Question

Для приложения Java, которое я сейчас разрабатываю, я использую систему идентификаторов, каждый из которых является уникальной строкой.У меня есть два списка массивов, один из которых представляет собой ArrayList<String>, который содержит только идентификаторы в правильном порядке, другой - список массивов объектов, у всех из которых есть поле .ID.Каков наилучший способ упорядочить список массивов объектов, чтобы их идентификаторы были в том же порядке, что и список массивов идентификаторов строк?

Answer 1

Я бы поместил все объекты в HashMap, используя их ID в качестве ключа, затем запустил второй список ID и создал новый список объектов, используя ID и карту.Должен иметь сложность около 2n -> n, но не как ресурс.

РЕДАКТИРОВАТЬ: чтобы прояснить, что я имею в виду

List<String> idList;
List<ObjectWithID> objectList;

Map<String, ObjectWithID> helperMap=new HashMap<>();

//first O(n)
for (ObjectWithID o:objectList) {
  helperMap.put(o.ID, o);
}

int i=0;
//second O(n)
for (String id:idList) {
  objectList.set(i,helperMap.get(id));
  i++;
}

Предполагая, что objectList и idList имеют одинаковый размер и одинаковые идентификаторы / object.IDs соответственно.

Answer 2

Отказ от ответственности: Вы не упоминаете, почему вам нужно упорядочить эти записи, но если это только для целей сопоставления идентификаторов, вам, вероятно, следует изменить дизайн своего приложения, чтобы оно использовало что-то вроде HashMap или TreeMap с самого начала .

Вот возможное решение с O(n) сложностью для подготовки и O(n * log(n)) сложностью для фактической сортировки:

class MyEntry {
   public String id;
}

ArrayList<String> idList = new ArrayList<String>();
ArrayList<MyEntry> entryList = new ArrayList<MyEntry>();

final HashMap<String, Integer> index = new HashMap<String, Integer>();

// Match each ID to its index
for (int i = 0; i < idList.size(); ++i) {
    index.put(idList.get(i), i);
}

Collections.sort(entryList, new Comparator<MyEntry>() {
    public int compare(MyEntry o1, MyEntry o2) {
        return index.get(o1.id) - index.get(o2.id);
    }
});

Отказ от ответственности II: я на самом деле не запускал этот код, но он должен работать ...

EDIT:

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

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

Answer 3

Выделите 3-й список.O (n ^ 2) решение состоит в том, чтобы перебрать список, который имеет упорядоченные идентификаторы.Внутри этого цикла есть еще один цикл для поиска объекта с его идентификатором == текущий идентификатор, найденный в первом цикле / списке.Извлеките этот предмет и добавьте его в третий список:

for (ID in List<ID>)
    for (Item item in List<Item>){
        if (item.ID == ID){
            list3.add(item);
        }
    }

Ужасный алгоритм.Я предлагаю вам разработать свои структуры данных.Используйте карту или компаратор.

Answer 4

Хранение в 2 списках не является хорошим дизайном.Если возможно, вы можете изменить его и сохранить на карте.В зависимости от ваших требований, вы можете решить, какая реализация Map вам нужна.Например: если вы хотите сохранить порядок вставки, вы можете перейти к LinkedHashMap.

Если невозможно выполнить рефакторинг / редизайн, вы можете использовать следующий пример, который я кодировал, чтобы проверить функциональность сортировки.Во-первых, я создал объект Person с переменными «id» и «name» следующим образом:

public class Person {
    private String id;
    private String name;

    /**
     * @return the id
     */
    public String getId() {
        return id;
    }

    /**
     * @param id the id to set
     */
    public void setId(String id) {
        this.id = id;
    }

    /**
     * @return the name
     */
    public String getName() {
        return name;
    }

    /**
     * @param name the name to set
     */
    public void setName(String name) {
        this.name = name;
    }

}

И ниже класс Main, в котором реализована сортировка:

public class TwoLists {
    public static void main(String[] args) {
        ArrayList<String> idList = new ArrayList<String>();
        ArrayList<Person> personList = new ArrayList<Person>();

        idList.add("1");
        idList.add("2");
        idList.add("3");
        idList.add("4");

        TwoLists twoLists = new TwoLists();

        personList.add(twoLists.createPerson("4", "Name4"));
        personList.add(twoLists.createPerson("2", "Name2"));
        personList.add(twoLists.createPerson("3", "Name3"));
        personList.add(twoLists.createPerson("1", "Name1"));

        System.out.println("Before Sorting:");
        for(Person person: personList) {
            System.out.println(person.getId());
        }

        Collections.sort(personList, twoLists.new TwoListsComparator(idList));

        System.out.println("After Sorting:");
        for(Person person: personList) {
            System.out.println(person.getId());
        }
    }

    private class TwoListsComparator implements Comparator<Person> {
        ArrayList<String> idList;

        private TwoListsComparator(ArrayList<String> idList) {
            this.idList = idList;
        }

        public int compare(Person person1, Person person2) {
            int index1 = idList.indexOf(person1.getId());
            int index2 = idList.indexOf(person2.getId());

            return Integer.valueOf(index1).compareTo(index2);
        }
    }

    private Person createPerson(String id, String name) {
        Person p = new Person();
        p.setId(id);
        p.setName(name);

        return p;
    }
}

В приведенном выше коде я создал 2 списка: один для строк идентификатора, а другой для объектов Person.Затем я сортирую список лиц, передавая idList компаратору и сравнивая индексы.

Answer 5

Просто общая идея (без компилятора)

public class MyListComparator implements Comparator<MyObject>{

    private ArrayList<String> ids;

    public MyListComparator(ArrayList<String> ids)
    {
        this.ids = ids;
    }

    @Override
    public int compare(MyObject o1, MyObject o2) {
        Integer i1 = ids.indexOf(o1.id);
        Integer i2 = ids.indexOf(o2.id);
        return i1.compareTo(i2);
    }
}

Answer 6

Почему бы не отсортировать оба списка отдельно по идентификатору.

Создайте один компаратор, который сортирует ваш список строк, а затем создайте другой компаратор, который сравнивает поле .ID на ваших объектах. Сортируйте оба списка по отдельности, при условии, что оба списка 1: 1, все должно быть в порядке.

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