Создание списка элементов из существующего списка - PullRequest
Новая
       20

Создание списка элементов из существующего списка

1 голос
/ 22 марта 2019

Я создаю генетический алгоритм для решения какой-то конкретной проблемы.Поскольку проблему трудно описать, я написал крошечный пример, который показывает, что я делаю.

У меня есть список Элементов, который должен развиваться со временем.

Каждый Элемент имеет пригодностьзначение, которое определяет, насколько это хорошо.Вот класс, который представляет элемент: 

class Element implements Comparable<Element>{
    private int fitness;
    Element( int _fitness){
        this.fitness=_fitness;
    }

    public int getFitness() {
        return fitness;
    }

    @Override
    public int compareTo( Element o ) {
        return this.fitness-o.getFitness();
    }

    @Override
    public String toString() {
        return this.fitness+"";
    }
}

Лучший элемент - это элемент, который имеет максимальное значение пригодности.

Пример: 

list_Iteration_One | list_Iteration_Two| list_Iteration_Three
Element(5)         | Element(9)        | Element(14) 

Element(4)         |Element(5)         | Element(9) 

Element(3)         |Element(5)         | Element(9) 

Element(2)         |Element(4)         | Element(5) 

Element(1)         |Element(3)         | Element(5)

Как мыможно увидеть, что программа должна взять как элемент списка Элемент и развить эти Элементы для создания нового Списка.

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

Для выбранного элемента они должны иметь максимальное значение пригодности.

В моем примере выше я взял Element(5) + Element(4), чтобы создать Element(9), и я Element(3) + Element(2), чтобы создать Element(5) и что осталось, я взял Element(5), Element(4), Element(3).

Для итерации 3 я делаю то же самое и так далее.

Вот что я сделал для одной итерации:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class BestDataStructure {

    public static void main( String[] args ) {
        List<Element> list = Stream.of(new Element(5),
                new Element(4),
                new Element(3),
                new Element(2),
                new Element(1)).collect(Collectors.toCollection(ArrayList::new));
        List<Element> theNewList = getTheNewList(list);
        System.out.println(theNewList);
    }

    private static List<Element> getTheNewList( List<Element> list ) {
        List<Element> theNewList = new ArrayList<>();

        int numberOfTimes = list.size()/2;
        Element bestElement=null;
        Element secondBestElement=null;
        for (int i =0; i<numberOfTimes; i++){
            bestElement= Collections.max(list);
            list.remove(bestElement);

            secondBestElement= Collections.max(list);
            list.remove(secondBestElement);

            Element child = new Element(bestElement.getFitness()+secondBestElement.getFitness());
            theNewList.add(child);

            theNewList.add(bestElement);
            theNewList.add(secondBestElement);
        }
        return theNewList;
    }


}

class Element implements Comparable<Element>{
    private int fitness;
    Element( int _fitness){
        this.fitness=_fitness;
    }

    public int getFitness() {
        return fitness;
    }

    @Override
    public int compareTo( Element o ) {
        return this.fitness-o.getFitness();
    }

    @Override
    public String toString() {
        return this.fitness+"";
    }
}

Поскольку я должен обработать List размера (между 2000 и 50000 Элементами), мне нужно знать лучшую структуру данных, чтобы справиться с такой обработкой.

Я ищуМаксимальный Элемент каждый раз в ArryList, и это очень плохая идея.

TПолученный список после каждой итерации должен иметь тот же размер, что и первый список, и, к сожалению, это не то, что я получаю в моем getTheNewList методе.

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

Ответы [ 2 ]

1 голос
/ 24 марта 2019

Вы можете использовать потоки Java: используйте IntStream, чтобы сгенерировать первую половину элементов и добавить первую половину исходного списка. Следующий метод ожидает отсортированный список и возвращает новый отсортированный список элементов: 

private static List<Element> getTheNewList(List<Element> elements) {
    int halfElements = elements.size() / 2;
    return Stream.concat(
            IntStream.range(0, halfElements)
                    .mapToObj(index -> new Element(elements.get(index * 2).getFitness() + elements.get(index * 2 + 1).getFitness())),
            elements.stream().limit(halfElements + 1)
    )
            .sorted(Comparator.reverseOrder())
            .collect(Collectors.toList());
}

Если вы используете его следующим образом: 

List<Element> iteration1 = Arrays.asList(
        new Element(5),
        new Element(4),
        new Element(3),
        new Element(2),
        new Element(1)
);
System.out.println(iteration1);
List<Element> iteration2 = getTheNewList(iteration1);
System.out.println(iteration2);
List<Element> iteration3 = getTheNewList(iteration2);
System.out.println(iteration3);

Будет напечатано: 

[5, 4, 3, 2, 1]
[9, 5, 5, 4, 3]
[14, 9, 9, 5, 5]
0 голосов
/ 22 марта 2019

Я бы посоветовал убедиться, что ваш список отсортирован по пригодности, прежде чем передавать его в какой-либо метод, например getTheNewList, и вместо того, чтобы этот метод возвращал новый список, просто включите его в тот же список.Например, если ваш список отсортирован в порядке убывания, вы можете просто удалить последние два элемента, поскольку size of list/2 равно 2 в этом случае.Затем объедините элементы в группы по 2, начиная с первого элемента в списке, и вставьте этот список в другой список.Затем просмотрите этот список комбинированных элементов и выясните, где этот новый элемент должен быть вставлен в список, чтобы сохранить порядок.Вот как это будет выглядеть: 

private void getTheNewList( List<Element> list ) {
    List<Element> theNewList = new ArrayList<>();
    int numberOfTimes = list.size()/2;
    Element bestElement=null;
    Element secondBestElement=null;
    for (int i = 0 ; i < numberOfTimes; i++) {
        //remove last element of the list
        list.remove(list.size() - 1);
        bestElement= list.get(numberOfTimes * 2 - 2);

        secondBestElement= Collections.max(numberOfTimes * 2 - 1);

        Element child = new Element(bestElement.getFitness()+secondBestElement.getFitness());
        theNewList.add(child);
    }
    //insert combined elements into original list
    for (int i = 0; i < numberOfTimes; i++) {
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j) <= theNewList.get(i)) {
                list.insert(j, theNewList.get(i));
                break;
            }
            list.insert(j, theNewList.get(i));
        }
    }
}
...