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

прочитал код ддамагера и понял что он сделал тупо всё о чём я написал

только код в начале малость лишний потому что a.len = b.len

вот именно что нельзя выделить индексное пространство

даже после ensureCapacity ты можешь работать только с индексами i < size, а size увеличивается на 1 после каждой операции add

угу, я так и ожидал в принципе

в списках обычно не должно быть пустых индексов

там нет лишнего кода

правильно, это я не так понял что там было написано

и да бтв, это скорее вопрос личных предпочтений

но
 

        while (idx < b.size()) {
            a.add(a.get(idx));
            a.add(b.get(idx));
            idx++;
        }

я предпочитаю писать как

        for ( ; idx < b.size(); idx++) {
            a.add(a.get(idx));
            a.add(b.get(idx));
        }

ненавижу итерации по массивам/списках в while циклах

^

тебе лишь бы попиздеть

 

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

ох блять, вот такие потом решальщики задач код и пишут

 

private static List<T> Merge<T>(List<T> a, List<T> b)
    {
      if (a.Count != b.Count)
        throw new ArgumentException();

      a.Capacity = a.Capacity * 2;
      a.InsertRange(a.Count, Enumerable.Repeat(default(T), a.Count));

      for (int i = a.Count - 1; i > 0; i--)
      {
        if (i % 2 == 0)
        {
          a[i] = a[i / 2];
        }
        else
        {
          a[i] = b[(i - 1) / 2];
        }
      }
      return a;
    }

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

private static T[] Merge<T>(T[] a, T[] b)
{
  if (a.Length != b.Length)
	throw new ArgumentException();

  Array.Resize(ref a, a.Length * 2);
  for (int i = a.Length - 1; i > 0; i--)
  {
	if (i % 2 == 0)
	{
	  a[i] = a[i / 2];
	}
	else
	{
	  a[i] = b[(i - 1) / 2];
	}
  }
  return a;
}

а у тебя же на кой-то хуй 3 цикла вместо 2, при этом я почти уверен, что в джаве есть аналог InsertRange, который вставит быстрее из-за отсутствия промежуточных проверок

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

логика блять замысловатая

 

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

забивать нулями массив чтобы открыть индексы и потом еще раз сетить что-то в эти индексы не будет быстрее чем сетить 1 раз

так что ты идешь нахуй

 

п.с. прогнал бенчмарки на джаве

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

 

<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++) {
        a.add(null);
    }

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

 

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

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

 

a.InsertRange(a.Count, Enumerable.Repeat(default(T), a.Count));

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

 

это прикол такой? это именно то чего надо избежать если нужна производительность

ты какого-то хуя

1) генерируешь N массив через Enumerable.Repeat

2) вставляешьего в предыдущий делая N set-ов

3) перезаписываешь потом каждый встравленый элемент

 

первые 2 пункта нахуй не нужны

особенно первый который поглощает дополнительные O(N) памяти

 

в его варианте он делает N add, N-1 set

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

 

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

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

всё у него правильно сделано

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

А Suez всегда такой злой?

п.с. прогнал бенчмарки на джаве

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

твой вариант не создает левого массива на O(N) памяти в процессе в отличии от решения канта

ебать нихуя себе в топике программирования программисты собрались кодом меряются

 

суез ну ка на улицу выйди и отпишись о впечатлениях

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

даже этот вариант по идее медлеенее в managed языке или как минимум не быстрее

 

Array.Resize<T> Method (T[], Int32)

 

 

If newSize is greater than the Length of the old array, a new array is allocated and all the elements are copied from the old array to the new one. If newSize is less than the Length of the old array, a new array is allocated and elements are copied from the old array to the new one until the new one is filled; the rest of the elements in the old array are ignored. If newSize is equal to the Length of the old array, this method does nothing.

This method is an O(n) operation, where n is newSize.

 

при ресайзе он по-любому должен set-ить внутренности чем-то типа default(T) или как оно там правильно называется

типа как это

 

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

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

 

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

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

кек, отбой

даже std::vector<T> в С++ не делает ресайзы без сетов

    vector<int> vec = vector<int>(4);

    cout << "at 0: " << vec[0] << endl;

    vec.resize(6);

    cout << "at 5: " << vec[5] << endl;

    return 0;

вот это работает и выводит 0 и 0

 

но когда я заменяю int на тип без конструктора который не берёт аргументов, то всё, хуй

/usr/lib/gcc/x86_64-pc-cygwin/6.4.0/include/c++/bits/stl_construct.h:75:7: error: no matching function for call to 'LinearAlgebra_Basic::Matrix::Matrix()'
     { ::new(static_cast<void*>(__p)) _T1(std::forward<_Args>(__args)...); }

при чём валится ещё на конструкторе, а не на ресайзе

так что по идее любой вариант который не создаёт ёбаного O(n) массива через Enumerable.Repeat() будет одинаково быстр и тут уже будет зависеть от имплементации того или иного метода

 

к слову тут есть шанс что ensureCapacity() в arraylist-e не инициализирует память когда её перевыделяет (не считая старых элементов) тоесть 0 сет-ов и тогда расширение индексного пространства через add-ы имеет нулевой оверхед потому что память уже инициализируется тем что ты ему в этот add кормишь

 

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

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

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

 

так что по идее любой вариант который не создаёт ёбаного O(n) массива через Enumerable.Repeat() будет одинаково быстр

 

если мы открываем индексы то мы сетим дефолтные значения (либо нули) 2 раза, один раз когда увеличиваем размер массива и второй раз когда открываем индексы

 

это отрабатывает медленнее на больших массивах, чем если не открывать индексы

сори, не знаю, что там с аналогами в джаве для Enumerable.Repeat, но в шарпе там никаких массивов не создается вообще

 public static IEnumerable<TResult> Repeat<TResult>(TResult element, int count) {
            if (count < 0) throw Error.ArgumentOutOfRange("count");
            return RepeatIterator<TResult>(element, count);
        }

        static IEnumerable<TResult> RepeatIterator<TResult>(TResult element, int count) {
            for (int i = 0; i < count; i++) yield return element;
        }

если джава так не умеет, ну ладно, вставьте туда просто сам же массив

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

 

 

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

надо делать вот так

for (int i = a.Count / 2 - 1; i >= 0; i--)
{
	a[i * 2] = a[i];
	a[i * 2 + 1] = b[i];
}

так конвеер не сбрасывается на каждой итерации , плюс нет делений, так что  работать должно раза в 2-3 быстрее.

 

 

 

ну и в третьих, если делать всё правильно, надо сразу сказать интервьюеру, что он долбоеб

и раз он хочет заниматься такими оптимизациями, то пусть делает их правильно

и узнает, что realloc ВНЕЗАПНО не меняет размер массива по указателю, а возвращает указатель на новую область памяти нужного размера

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

 

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

private static List<T> Merge<T>(List<T> a, List<T> b)
{
  if (a.Count != b.Count)
	throw new ArgumentException();

  var c = new List<T>(a.Count * 2);
  for (int i = 0; i < a.Count; i++)
  {
	c.Add(a[i]);
	c.Add(b[i]);
  }
  return c;
}

если мы открываем индексы то мы сетим дефолтные значения (либо нули) 2 раза, один раз когда увеличиваем размер массива и второй раз когда открываем индексы

 

это отрабатывает медленнее на больших массивах, чем если не открывать индексы

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

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

 

но бенчмарк с установкой нулей независимо от поведения ensurecapacity будет медленнее

я это писал к тому что возможно Array.Resize() может быть быстрее, но скорее всего это не так

думаю через Add-ы в сшарпе всё-равно будет быстрее чем Array.Resize()

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

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

 

    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) 
    }

Мой вариант к слову, его схавали.
Изменено 7 декабря 2017 пользователем Index

сори, не знаю, что там с аналогами в джаве для Enumerable.Repeat, но в шарпе там никаких массивов не создается вообще

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

 

 

 

 

ну и в третьих, если делать всё правильно, надо сразу сказать интервьюеру, что он долбоеб

и раз он хочет заниматься такими оптимизациями, то пусть делает их правильно

и узнает, что realloc ВНЕЗАПНО не меняет размер массива по указателю, а возвращает указатель на новую область памяти нужного размера

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

 

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

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

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

да и в любом случае писать в массив №1 если он не нужен дальше это самый быстрый вариант так или иначе т.к. если стандартная либа джавы правильно имплементировала ensureCapacity то ей не надо будет собирать эту память после реаллока

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

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

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

но в любом работающем приложении, а не тесте, тебе джава поверх твоего массива в куче сразу пару тонн мелких объектов насоздает из-за того, что приложение то работает

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

 

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

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