Программирование, т. 7

<T> void merge2(ArrayList<T> a, ArrayList<T> b) {

    if ((long) a.size() + b.size() > Integer.MAX_VALUE - 8) { //max value taken from arraylist source code

        throw new IllegalArgumentException("cannot merge arraylists because they don't fit into single array");

    }

    int initSize = a.size();

    for (int i = 0; i < initSize; i++) { //O(n);

        a.add(null); //за время работы происходит 2 перевыделения памяти с копированием, итого + O(1.5n) + O(2n)

    }


    for (int i = a.size() - 1; i > 0; i--) //O(2n);

    {

        if (i % 2 == 0)

        {

            a.set(i, a.get(i/2));

        }

        else

        {

            a.set(i, b.get((i-1)/2));

        }

    }

}

 

против 2n-1 у варианта ддамагера

Алсо, где там у него 2n-1 ?

 

<T> void merge(ArrayList<T> a, ArrayList<T> b) {
    if ((long) a.size() + b.size() > Integer.MAX_VALUE - 8) { //max value taken from arraylist source code
        throw new IllegalArgumentException("cannot merge arraylists because they don't fit into single array");
    }

    a.ensureCapacity(a.size() + b.size());
    boolean even = a.size() % 2 == 0;
    int idxMid = a.size() / 2;
    int idx = idxMid;

    if (even) {
        while (idx < b.size()) { // [  O(n)  ]
            a.add(a.get(idx));
            a.add(b.get(idx));
            idx++;
        }
    } else {
        boolean first = true;
        while (idx < b.size()) { // [  O(n)  ] взаимоисключающий с предыдущим
            if (!first) {
                a.add(a.get(idx));
            } else {
                first = false;
            }
            a.add(b.get(idx));
            idx++;
        }
        a.set(b.size() - 1, a.get(idxMid));
    }
    idx = idxMid - 1;
    while (idx >= 0) { // [  O(n)  ]
        a.set(idx*2, a.get(idx));
        a.set(idx*2 + 1, b.get(idx));
        idx--;
    }
}

 

<T> void merge2(ArrayList<T> a, ArrayList<T> b) {
    if ((long) a.size() + b.size() > Integer.MAX_VALUE - 8) { //max value taken from arraylist source code
        throw new IllegalArgumentException("cannot merge arraylists because they don't fit into single array");
    }
    int initSize = a.size();
    for (int i = 0; i < initSize; i++) { //O(n);
        a.add(null); //за время работы происходит 2 перевыделения памяти с копированием, итого + O(1.5n) + O(2n)
    }

    for (int i = a.size() - 1; i > 0; i--) //O(2n);
    {
        if (i % 2 == 0)
        {
            a.set(i, a.get(i/2));
        }
        else
        {
            a.set(i, b.get((i-1)/2));
        }
    }
}

Итого O(n+1.5n+2n+2n)

 

я ориентировался на первый

выглядит наиболее адекватно и его стоит писать и на собесе

я ориентировался на первый

 

выглядит наиболее адекватно и его стоит писать и на собесе

Земля тебе пухом братишка, просят void метод, а ты с возвратом сделаешь

нужно пояснить что давайте сделаем с возвратом, а если надо записать в 'a' то сделаем a = merge(a,b)

я уже не выкупаю почему merge1 отрабатывает быстрее на ~30 ms для массивов 10^7 * 2

да уж, стоит признать что решение

 

выглядит наиболее адекватно и его стоит писать и на собесе

твой код настолько хорошой, насколько хорош самый хуёвый его компонент

и когда этот компонент это managed язык который ебал в рот скорость то ты не выиграешь этот бой как бы ты этого ни хотел

 

а сколько тотал рантайм?

~200 ms для нового листа и ~170 для огорода

 

выглядит наиболее адекватно и его стоит писать и на собесе

Земля тебе пухом братишка, просят void метод, а ты с возвратом сделаешь.

я ориентировался на первый

a.ensureCapacity(a.size() + b.size()); O(n) операция считается

 

 

а сколько тотал рантайм?

 

~200 ms для нового листа и ~170 для огорода

 

а если надо записать в 'a' то сделаем a = merge(a,b)

 

а если надо записать в 'a' то сделаем a = merge(a,b)

Сломав тем самым какие-нибудь weak листы, синхронизации и тп которые хронят в себе ссылку на изначальный массив?

ну ок если это обязательное условие менять непосредственно 'a', то мой огород остается лучшим решением

ох уже эти микро-оптимизации 

всё-равно быстрее, просто оверхед стаёт 2n вместо 3n

Я вот это

        while (itFirst.hasNext() && itSecond.hasNext()) { //O(2n) итерация 
            result.add(itFirst.next()); //O(1) 
            result.add(itSecond.next()); //O(1) 
        }

Он же 
    while (idx >= 0) { // [  O(n)  ]
        a.set(idx*2, a.get(idx));
        a.set(idx*2 + 1, b.get(idx));
        idx--;
    }

 

всё-равно быстрее, просто оверхед стаёт 2n вместо 3n

Я скажу так, тут смотря как считать.

 

Я вот это

        while (itFirst.hasNext() && itSecond.hasNext()) { //O(2n) итерация 
            result.add(itFirst.next()); //O(1) 
            result.add(itSecond.next()); //O(1) 
        }

За o(2n) посчитал, хотя число циклов N, так как внутри 2 вставки по o(1);

 

Он же 
    while (idx >= 0) { // [  O(n)  ]
        a.set(idx*2, a.get(idx));
        a.set(idx*2 + 1, b.get(idx));
        idx--;
    }

Считает за O(n) когда тут по той же логике O(2n)

 

n/2*2 = n

Там оверхед только в 1 n;

Бтв есть ещё такое решение

    static void merge(ArrayList first, ArrayList second) {
        if (first.size() != second.size()) throw new IllegalArgumentException("Not same size");
        int n = first.size();
        first.addAll(first);
        ListIterator itFirst = first.listIterator();
        ListIterator itMiddle = first.listIterator(n);
        ListIterator itSecond = second.listIterator();
        int i = 0;
        itFirst.next();
        Integer vm = (Integer)itMiddle.next();
        Integer vs = (Integer)itSecond.next();
        while (true) {
            if (i % 2 == 0) {
                itFirst.set(vm);
                if (itMiddle.hasNext())
                    vm = (Integer)itMiddle.next();
            } else {
                itFirst.set(vs);
                if (itSecond.hasNext())
                    vs = (Integer)itSecond.next();
            }
            i++;
            if (!itFirst.hasNext())
                break;
            itFirst.next();
        }
 
    }

Там оверхед только в 1 n;

тут кол-во итераций n/2 а не n

n/2*2 = n

То что там идет итерация по половине удвоенного сохраняет число итераций равное n изначального размера.

мы просто как дауны все юзаем О() нотацию тогда как что бы мы не делали сложность всё-равно линейная

надо смотреть коеффициент у n где n это кол-во копирований, т.е. надо в лоб считать кол-во копирований

его коеффициент это 3n, твой 5n

3n =

n - ensurecapacity

n - idx < b.size(), любой из двух

n - у него "while (idx >= 0)" где "idx = idxMid - 1;" где "idxMid = a.size() / 2;" из чего следует "while a.size() / 2 >= 0" что есть n/2 итераций где внутри 2х копирования => n

5n =

2n - while (itFirst.hasNext() && itSecond.hasNext()) что есть n+n

n - first.clear(); n set-ов на нули, что не совсем копирование но недалеко от этого, могу сойтись на 0.5n если тебя устроит

2n - first.addAll(result); тупо 2n копирований

итого 2n или 1.5n (сам выбирай)

edit: я тут заметил что idx < b.size() это тоже n/2*2 но это всё-равно нихуя не меняет

[offtop][/offtop]import com.google.common.collect.ImmutableList;
import org.junit.Test;

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.ListIterator;

import static org.junit.Assert.*;

public class TestTest {

    @org.junit.Test
    public void test() throws NoSuchFieldException, IllegalAccessException {
        ArrayList a = new ArrayList(11);
        ArrayList b = new ArrayList(11);
        a.addAll(ImmutableList.of(1, 3, 5, 7, 9, 11));
        b.addAll(ImmutableList.of(2, 4, 6, 8, 10, 12));
        merge(a, b);
        System.out.println(Arrays.toString(a.toArray()));

        a = new ArrayList(11);
        b = new ArrayList(11);
        a.addAll(ImmutableList.of(1, 3, 5, 7, 9, 11));
        b.addAll(ImmutableList.of(2, 4, 6, 8, 10, 12));
        merge2(a, b);
        System.out.println(Arrays.toString(a.toArray()));
    }

    <T> void merge(ArrayList<T> a, ArrayList<T> b) {
        System.out.println("DDamager");
        if ((long) a.size() + b.size() > Integer.MAX_VALUE - 8) { //max value taken from arraylist source code
            throw new IllegalArgumentException("cannot merge arraylists because they don't fit into single array");
        }
        int counter = 0;
        a.ensureCapacity(a.size() + b.size());
        counter += b.size();
        System.out.println("N:" + b.size());
        boolean even = a.size() % 2 == 0;
        int idxMid = a.size() / 2;
        int idx = idxMid;

        if (even) {
            while (idx < b.size()) { // [  O(n)  ]
                a.add(a.get(idx));
                a.add(b.get(idx));
                counter += 2;
                idx++;
            }
        }
        idx = idxMid - 1;
        while (idx >= 0) { // [  O(n)  ]
            a.set(idx * 2, a.get(idx));
            a.set(idx * 2 + 1, b.get(idx));
            idx--;
            counter += 2;
        }
        System.out.println("Number O(1):" + counter);
    }

    void merge2(ArrayList first, ArrayList second) {
        System.out.println("Index");
        if (first.size() != second.size()) throw new IllegalArgumentException("Not same size");
        int counter = 0;
        System.out.println("N:" + second.size());
        ArrayList result = new ArrayList(first.size() * 2);
        ListIterator itFirst = first.listIterator();
        ListIterator itSecond = second.listIterator();
        while (itFirst.hasNext() && itSecond.hasNext()) { //O(n) + O(n) итерация
            result.add(itFirst.next()); //O(1)
            result.add(itSecond.next()); //O(1)
            counter += 2;
        }
        first.clear(); //O(n)
        counter += second.size();
        first.ensureCapacity(first.size() * 2); //O(n)
        counter += second.size();
        first.addAll(result); //O(1) так как мы уже произвели копирование в first.ensureCapacity
        System.out.println("Number O(1):" + counter);
    }
}

Я собственно все и посчитал

 T E S T S
-------------------------------------------------------
Running TestTest
DDamager
N:6
Number O(1):18
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Index
N:6
Number O(1):24
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

 

        first.addAll(result); //O(1) так как мы уже произвели копирование в first.ensureCapacity

 

у тебя всё в порядке?