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

вот такой вариант

на 35% медленнее для массива на 10^7 элементов

Eсли просто так добавлять, то когда у ArrayList кончается капасити, он выделяет х1.5 больше.

 

Итого это если мержить массивы размером N то сперва выделится 1.5N а затем 2.25N;

Это 2 лишние операции копирования O(1.5N) и O(2N);

Плюс они ещё память могут выжрать. В момент когда в ней находится [1.5n] и [2.25n] массивы.

 

Хотя мой вариант тоже памятезатратный за счет доп листа.

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

не должны, в managed языке нули ничего не значат и тебе никогда не даст массив с абстрактно нулями, особенно в шарпе из-за наличия не ссылочных типов. даже с++ вектор так не делает, а вызывает конструкторы

 

я специально тестил с datetime массивом, потому что этот тип 1) значимый 2) дефолт значение в памяти (скорее всего) не нули

и как и ожидалось new DateTime[5] заполнил массив default(DateTime)

 

если коллекция формата List<T> (ArrayList<T> в жаве) не имеет способа открыть индексы без add-ов когда инстанция уже создана то ему нет смысла инициализировать память при аллок/реаллок-е

правда тут всё зависит от того написаны ли эти куски имплементации листов на самом managed языке или всё-таки на чём-то более низкоуровневом

Eсли просто так добавлять, то когда у ArrayList кончается капасити, он выделяет х1.5 больше.

wrong

специально для этого делается ensurecapacity чтоб он сразу выделил сколько надо

 

никто так и не понял зачем она нужна блядь

Я тоже в его коде мало что понял.

 

    void merge(ArrayList first, ArrayList second) {
        if (first.size() != second.size()) throw new IllegalArgumentException("Not same size");

        ArrayList result = new ArrayList(first.size() * 2);
        ListIterator itFirst = first.listIterator();
        ListIterator itSecond = second.listIterator();
        while (itFirst.hasNext() && itSecond.hasNext()) { //O(2n) итерация 
            result.add(itFirst.next()); //O(1) 
            result.add(itSecond.next()); //O(1) 
        }
        first.clear(); //O(n)
        first.addAll(result); //O(2n) 
    }

Мой вариант к слову, его схавали.

 

итого 2n+n+2n

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

оверхед в 2n+n

специально для этого делается ensurecapacity чтоб он сразу выделил сколько надо

Я про add(Object);    

 

Собственно 

Приращение капасити при переполнении при еденичном добавлении.

Изменено 7 декабря 2017 пользователем Index

 

специально для этого делается ensurecapacity чтоб он сразу выделил сколько надо

Я про add(Object); 

 

объясни

 

у него все адд-ы идут исключительно после ensureCapacity

там не будет ни одного перевыделения в процессе итераций

дефолт для дейттайма в шарпе это ноль, тк дейттайм это просто один единственный ulong внутри

 

  private ulong dateData;

 

всё остальное константы и методы по превращению этого улонга в то, что хочет юзер

 

для ссылочных типов, у которых null, всё равно всё забивается нулями, тк null не существует в реальности, а оставлять мусор нельзя

 

и как там написано, в стандарте шарпа это явно указано

https://stackoverflow.com/questions/15300073/what-is-the-default-value-of-a-member-in-an-array

всё просто побитово зануляется и ниибет

 

 

у него все адд-ы идут исключительно после ensureCapacity
там не будет ни одного перевыделения в процессе итераций

 

Я про его второй код.

private T[] _items;

 

тоесть у list-а managed имплементация

всё тогда с ним ясно

 

хотя всё-равно есть шанс что сетов не будет делать если менеджер памяти знает куски памяти уже с нулями, насколько я понимаю GC после сборки может тоже обнулять память

мы ща опустимся в такие дебри реализации коллекций шарпа и джавы, что их влияние на сам мердж стремится к нулю

 

а если они нам мешают, то настала пора переписать всё на сях

Я про его второй код.

лол, он там не написал ensureCapacity

там оно тоже по идее должно быть если что, нет ни одной причины этого не делать

 

 

там оно тоже по идее должно быть если что, нет ни одной причины этого не делать

Так я и говорю, оно есть но 2 раза в полтора раза. Блять.    

мы ща опустимся в такие дебри реализации коллекций шарпа и джавы, что их влияние на сам мердж стремится к нулю

 

а если они нам мешают, то настала пора переписать всё на сях

глянул arraylist у джавы, там то же самое

тогда рли один хуй, но так или иначе хуярить адд-ы быстрее чем любой другой вариант кроме как Array.Resize() но в оригинале стояла задача именно на ArrayList<T>

 

там оно тоже по идее должно быть если что, нет ни одной причины этого не делать

Так я и говорю, оно есть но 2 раза в полтора раза. Блять. 

 

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

бля, я ща глянул в реализациюю смены капасити у листа 

[__DynamicallyInvokable]
    public int Capacity
    {
      [__DynamicallyInvokable] get
      {
        return this._items.Length;
      }
      [__DynamicallyInvokable] set
      {
        if (value < this._size)
          ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
        if (value == this._items.Length)
          return;
        if (value > 0)
        {
          T[] objArray = new T[value];
          if (this._size > 0)
            Array.Copy((Array) this._items, 0, (Array) objArray, 0, this._size);
          this._items = objArray;
        }
        else
          this._items = List<T>._emptyArray;
      }
    }

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

     public void ensureCapacity(int minCapacity) {
         modCount++;
         int oldCapacity = elementData.length;
         if (minCapacity > oldCapacity) {
             Object oldData[] = elementData;
             int newCapacity = (oldCapacity * 3)/2 + 1;
             if (newCapacity < minCapacity)
                 newCapacity = minCapacity;
             // minCapacity is usually close to size, so this is a win:
             elementData = Arrays.copyOf(elementData, newCapacity);
         }
     }

походу та же хуйня

 

 

 

никаких даже попыток делать ресайз

В жаве так же?

 

А что не так то? Выделили новую память, а потом 256битными AVX регистрам хуяк хуяк в пару тактов и в продакшн.

Как ты будешь ресайзить блок памяти зажатый между занятых блоков памяти? Даже если там суперпиздатый аллокатор внутренний в JVM то все равно проще выделить новый блок.

Не хочешь выделений блоков памяти, можно юзать LinkedList например.

ну у реаллока есть шанс удлинить массив, у создания нового массива его нет по определению

но поцоны просто не заморачивались и всегда создают новый массив

Не хочешь выделений блоков памяти, можно юзать LinkedList например.

и иметь дикую фрагментацию чтоб потом полдня итерировать по списку с кучей промахов?

 

 

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

 

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

ну у реаллока есть шанс удлинить массив, у создания нового массива его нет по определению

но поцоны просто не заморачивались и всегда создают новый массив

это

при чём это создаёт фрагментацию там где её не должно быть если ты выделил всё что надо раньше и тупо список ресайзишь

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

 

 

<T> List<T> merge2(ArrayList<T> a, ArrayList<T> b) {
    ArrayList<T> res = new ArrayList<>(a.size()*2);
    for (int i = 0; i < b.size(); i++) {
        res.add(a.get(i));
        res.add(b.get(i));
    }
    return res;
}

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

 

и я уже сам не могу понять почему мой огород выигрывает бенчмарк

 

<T> void merge1(ArrayList<T> a, ArrayList<T> b) {
    a.ensureCapacity(a.size()*2);
    boolean even = a.size() % 2 == 0;
    int idxMid = a.size() / 2;
    int idx = idxMid;


    if (even) {
        while (idx < b.size()) {
            a.add(a.get(idx));
            a.add(b.get(idx));
            idx++;
        }
    } else {
        boolean first = true;
        while (idx < b.size()) {
            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) {
        a.set(idx*2, a.get(idx));
        a.set(idx*2 + 1, b.get(idx));
        idx--;
    }
}

 

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

Если у Вас есть хорошие ресурсы/статьи/что-то по Node.js - скиньте, плиз