import java.util.*;

public class Main {

    public static void main(String[] args) {

        runTest(100000);
        runTest(500000);
        runTest(1000000);

    }

    static void runTest(int size) {

        System.out.println("\nКоличество = " + size);
        measureTime(new TestArray(size));
        measureTime(new TestMap(size));

    }

    static <T extends Tester> void measureTime(T tester) {

        Tester collectionTester = null;

        if (tester instanceof TestArray) {
            collectionTester = (TestArray) tester;
        } else if (tester instanceof TestMap) {
            collectionTester = (TestMap) tester;
        }

        String nameClass = collectionTester.getClass().getName();

        loggedTime(collectionTester::insert, nameClass, "заполнение коллекции");
        loggedTime(collectionTester::search, nameClass, "поиск в коллекции");
        loggedTime(collectionTester::delete, nameClass, "удаление из коллекции");

    }

    static void loggedTime(Procedure procedure, String nameClass, String nameMethod) {

        long startTime = System.currentTimeMillis();

        procedure.exec();

        long endTime = System.currentTimeMillis();

        double timeSec = (double) (endTime - startTime) / 1000L;

        System.out.println(nameClass + ": " + nameMethod + " - " + timeSec + " сек.");
    }

}

interface Procedure {
    void exec();
}

abstract class Tester {

    List<Integer> inArray;
    List<Integer> randArray;
    List<Integer> outArray;

    public Tester() {
       this(1000);
    }

    public Tester(int elements) {

        inArray = new ArrayList<>();
        randArray = new ArrayList<>();
        outArray = new ArrayList<>();

        for (Integer i=1; i<=elements; i++) {
            inArray.add(i);
        }

        int size = inArray.size();

        Random random = new Random();

        // В случайные элементы добавляем 10% выборки
        int added = size / 10;
        do {
            Integer x = random.nextInt(size);
            if (!randArray.contains(x)) {
                randArray.add(x);
                added--;
            }
        } while (added > 0);
    }

    abstract void insert();
    abstract void search();
    abstract void delete();

}

class TestArray extends Tester {

    List<Integer> arrayList;

    public TestArray() {
        super();
    }

    public TestArray(int i) {
        super(i);
    }

    @Override
    void insert() {

        arrayList = new ArrayList<>();
        arrayList.addAll(inArray);

    }

    @Override
    void search() {

        List<Integer> outArray = new ArrayList<>();

        for (Integer x : randArray) {

            int i = arrayList.indexOf(x);
            if (i > -1) {
                super.outArray.add(arrayList.get(i));
            }

        }

    }

    @Override
    void delete() {
        arrayList.removeAll(super.randArray);
    }
}



class TestMap extends Tester {

    Map<Integer, Integer> hashMap;

    public TestMap() {
        super();
    }

    public TestMap(int i) {
        super(i);
    }

    @Override
    void insert() {

        hashMap = new HashMap<>();

        for (Integer x : super.inArray) {
            hashMap.put(x, x);
        }
    }

    @Override
    void search() {

        for (Integer x : super.randArray) {
            Integer y = hashMap.get(x);
            if (!(y ==null)) {
                super.outArray.add(y);
            }

        }

    }

    @Override
    void delete() {
        for (Integer x : super.randArray) {
            hashMap.remove(x);
        }
    }

}