Суть задачи такова. Необходимо написать метод, который принимает в качестве аргументов две коллекции ArrayList одинакового размера, например, одна a = [a1, a2, a3, ....], а вторая b = [b1, b2, b3 ...]. Метод должен превратить коллекцию а в следующий вид: a = [a1, b1, a2, b2, a3, b3....]. При этом решение должно быть экономным к ресурсам и процессорному времени.
Первый вариант, который может быть придуман фактически в лоб и этот вариант я тоже видел на форуме:
static void merge4(ArrayList a, ArrayList b) {
int size = a.size();
int count = 0;
for (int i = 0; i<size*2; i++){
if (i % 2 != 0) {
a.add(i, b.get(count));
count++;
}
}
}
Когда тестировал метод, который принимает две коллекции с количеством элементов 1 000 000, то еле дождался результата. Получил 76 867 мс, печально, хотя вполне ожидаемо, когда каждая вставка методом add, сопровождается копированием массива, что находится правее… При миллионе элементов это, увы, очень плохой вариант.
Потом второй вариант, который можно придумать, тоже скорее всего в лоб, это использование промежуточной коллекции, типа:
static void merge3(ArrayList a, ArrayList b) {
ArrayList c = new ArrayList(a.size()*2);
for (int i=0; i<a.size();i++){
c.add(a.get(i));
c.add(b.get(i));
}
a = c;
}
Это заняло около 6 мс. Однако вполне очевидно, что данный способ не вполне экономен в части Memory.
Потом конечно хочется исключить промежуточную коллекцию. Именно этот вариант я предложил на собеседовании, и увы, провалил задание, хотя утешило, что на форуме предлагали и похуже вариант ребята, которые уже не парятся на тему «надо найти стартовую площадку для начала». Вот собственно говоря код:
static void merge2(ArrayList a, ArrayList b) {
int size = b.size();
for (int i = 0; i < size; i++) {
a.add(null);
}
for (int i = b.size(); i > 0; i--) {
a.set((i << 1) - 1, b.get(i - 1));
a.set((i << 1) - 2, a.get(i - 1));
}
}
Время выполнения составило 16 мс. Время ухудшилось, причем значительно. Но плюс естественно есть — это отсутствие промежуточной коллекции. Причем здесь решил «выпендриться», показав, что я знаю как побитовыми операциями я могу сделать умножение на 2. По факту, вряд ли я получил тут экономию процессорного времени, но даже если и получил, то она едва заметна в данном случае.
Последний вариант, я думал оптимизировал за счет того, что использую метод a.ensureCapacity(size * 2) с мыслями, что как минимум я избавлюсь от одного лишнего копирования массива, потому что при превышении текущего размера Array коллекция увеличивает число нового массива в 1,5 больше от текущего, а так как нам нужна в итоге коллекция с удвоенным числом элементов, то это потом приведет еще к одному увеличению размера массива, которое нам по факту не нужно (т.е. чуточку экономит ресурсы Memory), т.е. по факту выглядело бы это так:
static void merge1(ArrayList a, ArrayList b) {
int size = b.size();
a.ensureCapacity(size * 2);
for (int i = 0; i < size; i++) {
a.add(null);
}
for (int i = b.size(); i > 0; i--) {
a.set((i << 1) - 1, b.get(i - 1));
a.set((i << 1) - 2, a.get(i - 1));
}
}
Выгода по времени не существенна, но вроде 1мс есть. Но плюс все-таки есть. Пусть в каждой из коллекций, передаваемых в метод было size элементов, то при вызове метода merge1 там будет size*2 элементов. Для метода merge1 в принципе при вызове a.size() покажет такой же результат, но в основе этой коллекции до вызова метода trimToSize() будет массив с количеством элементов 1,5*1,5*size, т.е. мы сэкономили уток ресурсов.
Вообщем, ближе к самому оптимальному варианту решения задачи с учетом условия задачи, которое как минимум я нашел:
static void merge0(ArrayList a, ArrayList b) {
a.addAll(b);
for (int i = b.size(); i > 0; i--) {
a.set((i << 1) - 1, b.get(i - 1));
a.set((i << 1) - 2, a.get(i - 1));
}
}
Итог 5 мс, и, как мне кажется, перерасхода ресурсов тоже нету.
Задача оказалась достаточно интересной, для ее решения мне дали 30 минут.
Однако, сама постановка задачи вроде и имеет цель оценить знания внутренней реализации коллекции, но в то же время все-таки изменять один из передаваемых параметров в методе является дурным тоном, поэтому стоило бы ее переформулировать немного ее в другом контексте.
Комментарии (25)
blanabrother
13.07.2016 16:56Сам не джавист, но 5-минутные поиски (в том числ на хабре: Структуры данных в картинках. ArrayList) привели к System.arraycopy(), который умеет в слияние двух массивов начиная с индекса, нативный неджававский, т.е. видимо во внутренностях рантайм умеет быстро выделить память нужного куска и туда скопировать, потом вернуть.
kefirfromperm
13.07.2016 16:59+4Вы не экономите память после 2го варианта. Расширение коллекции неизменно приводит к выделению нового массива.
APXEOLOG
13.07.2016 17:14Комментарий по последнему методу: Если открыть реализацию функции addAll у ArrayList'a, то можно увидеть, что он вызывает toArray() у входящей коллекции. В случае ArrayList'a эта функция возвращает копию исходного массива заданного размера. То есть при вызове a.addAll(b) сначала создается полная копия массива b, затем создается новый массив в который сначала записывается a (это то что делает ensureCapacity), затем дописывается массив b.
То что выделение памяти спрятано внутри не означает, что его нет, по памяти этот метод не выигрывает у остальных (даже проигрывает, если учитывать что toArray() создает дополнительный массив которого можно избежать). А выигрыш по скорости идет за счет использования System.arraycopy. А на собеседовании я бы сказал что у каждого инструмента своя область применения, если так нужна скорость/память зачем вообще использовать ArrayList, может стоит использовать обычные массивыAPXEOLOG
13.07.2016 18:40Вот мой вариант, по тестам выходит немного быстрее. Дополнительная память выделяется однократно в размере a.size() + b.size()
Ускорение в том что мы срезаем все дополнительные проверки и работаем напрямую с массивами + избегаем дополнительного копирования памяти
public void reflectionBasedMerge() throws Exception { // Access private Object[] field Field dataField = ArrayList.class.getDeclaredField("elementData"); dataField.setAccessible(true); Object[] arrayA = (Object[]) dataField.get(a); Object[] arrayB = (Object[]) dataField.get(b); // Create resulting array Object[] result = new Object[a.size() + b.size()]; int c = 0; for (int i = 0; i < arrayA.length; i++) { result[c++] = arrayA[i]; result[c++] = arrayB[i]; } }
Результат тестов:
Benchmark Mode Cnt Score Error Units
MyBenchmark.method1 thrpt 5 0,010 ± 0,001 ops/us
MyBenchmark.method2 thrpt 5 0,129 ± 0,003 ops/us
MyBenchmark.method3 thrpt 5 0,169 ± 0,040 ops/us
MyBenchmark.method4 thrpt 5 0,377 ± 0,010 ops/us
MyBenchmark.method5 thrpt 5 0,425 ± 0,037 ops/us
chibitko
13.07.2016 17:26ensureCapacity(minCapacity) реализовано как (oldCapacity * 3) / 2 + 1 (https://habrahabr.ru/post/128269/)
думаю нужно правильно подобрать minCapacity, чтобы размер внутреннего массива был оптимален
kez
13.07.2016 17:26+3В порядке бреда:
Написать итератор, который на it.next() возвращает поочередно элементы то из одной коллекции, то из другой.blanabrother
13.07.2016 17:39Часть алгоритма сортировки слиянием. Круто.
Но у вас же исходный массив нельзя перезаписывать, поэтому автор с конца пишет, чтобы не затереть элементы исходного массива.
И в Java нет структур (в отличие от .NET например), только классы. Соответственно, Вам нужно +2 аллокации в памяти для такого итерирования. Это небольшая, но нагрузка на GC на пустом месте. Если два массива по 1кк элементов, то эти затраты несущественны (если конечно такое слияние не вызывается тоже 1кк раз). Если два массива по 100 элементов, то сборка мусора становится сопоставимой. Хотя Ваша задумка значительно нагляднее, чем цикл у автора.
izzholtik
13.07.2016 17:26Возможно ли избавиться от накладных расходов по памяти? ArrayList, насколько я знаю, захватывает новый массив при превышении объёма и копирует туда старое содержимое, т.е. в любом случае хотя бы на некоторое время будет захвачен удвоенный объём памяти (a со старым содержимым, «новый» а, b).
Valle
13.07.2016 18:07+3Вообще оригинальная задача звучала как «interleave array of 2n elements a1 a2 aN b1 b2 bN». Все нормальные решения этой задачи происходят без выделения памяти. А два слияние двух списков на яве в подавляющем большинстве случаев конечно проще и лучше всего сделать в третьем списке.
VoidEx
13.07.2016 18:48Либо я не понимаю до конца условия, либо что значит «без выделения памяти». Есть два массива размера 10, один из них должен стать 20, как обойтись без выделения?
mird
13.07.2016 19:35Использовать итератор. На выходе будет не массив, а ленивая последовательность элементов, которая при запросе дай следующий элемент возьмет элемент из одного или из другого списка.
Ну либо, можно реализовать класс с индексером, который будет вычислять по входящему индексу в какой массив и по какому внутреннему индексу обратится за элементом.VoidEx
13.07.2016 19:54Ну да, в этом варианте она эквивалентна задаче вывести элементы двух массивов в таком порядке. Понятно, что лишняя память тут не нужна.
Меня просто сбила с толку фраза «оригинальная задача». Между ней и той, что в посте, есть весьма существенная разница, почему их приравняли, это какая-то каноническая задача что ли?
Antelle
13.07.2016 21:08+1Каноническая. Вопрос даже не в языке и не в реализации через итератор, а в том, как замёржить два списка, не используя дополнительной памяти, равной их размеру. Пример: оперативки 8gb, в ней записано два массива, каждый по 4gb. На выходе надо сделать так, чтобы 8gb были "отсортированы" таким вот образом. Есть несколько мегабайт для работы алгоритма, плюс стек, больше никаких ресурсов.
http://cs.stackexchange.com/questions/332/in-place-algorithm-for-interleaving-an-array
manusovich
13.07.2016 19:45class JoinedList extends ArrayList { List<Integer> l1, l2; public JoinedList(List l1, List l2) { if (l1 == null || l2 == null || l1.size() != l2.size()) { throw new IllegalArgumentException(); } this.l1 = l1; this.l2 = l2; } @Override public Iterator iterator() { return new Iterator() { int p = 0; @Override public boolean hasNext() { return l1 != null && l2 != null && l1.size() > 0 && p < l1.size() * 2; } @Override public Object next() { Integer res; if (p % 2 == 0) { res = l1.get(p / 2); } else { res = l2.get(p / 2); } p++; return res; } }; } @Override public int size() { return l1.size() + l2.size(); } }
И пример использования
List<Integer> l1 = new ArrayList<>(); l1.add(1); l1.add(2); l1.add(3); List<Integer> l2 = new ArrayList<>(); l2.add(11); l2.add(22); l2.add(33); l1 = join(l1, l2); for (Integer i : l1) { System.out.println("r = " + i); }
michael_vostrikov
13.07.2016 20:04-1Именно этот вариант я предложил на собеседовании, и увы, провалил задание
int size = b.size(); for (int i = 0; i < size; i++) { a.add(null); } for (int i = b.size(); i > 0; i--) { a.set((i << 1) - 1, b.get(i - 1)); a.set((i << 1) - 2, a.get(i - 1)); }
Я бы тоже вас не взял с таким кодом. Во-первых, у вас размер массива уже хранится в переменнойsize. Во-вторых, битовая операция не к месту. В-третьих, от-1можно было избавиться (и если бы там было умножение, то это было бы более заметно). Сложность алгоритма это хорошо, но и о понятности кода забывать не стоит.
for (int i = size - 1; i >= 0; i--) { a.set((i * 2) + 1, b.get(i)); a.set((i * 2) + 0, a.get(i)); }
x893
13.07.2016 21:54Для полной красоты
for (int i = size — 1; i >= 0; i--) {
int j = i * 2;
a.set(j++, a.get(i));
a.set(j, b.get(i));
}
brain_leo
13.07.2016 22:05Пардон, но не дай бог попасть на интервью к такому как Вы. Только потому что мы все не роботы и есть стрессовые ситуации и все такое. А вот с пальца фактически высосать про "-1", так это вообще убиться и не встать.
GreyCat
Откуда вы все это берете? На дворе 2016 год, компиляторы прекрасно умеют делать такие «оптимизации» сами уже лет 15, а то и 20 как.
А еще сейчас придет кто-нибудь и скажет, что ArrayList, а не ArrayList — это плохо.
brain_leo
:) где-то нагуглил, это точно не мои личные домыслы. И между прочим я не писал нигде что умножать на 2 это плохо!
myxo
Дело в том, что так писали на заре программирования С, сегодня так писать вредно, на собеседовании такой код только в минус.
brain_leo
Может не совсем в той плоскости, но вредно ли писать i = i + 1 или i++?
brain_leo
Я лишь ошибся в одном — в том что в применении этой операции я ожидал определенного эффекта, но чисто теоретически тот кто собседует не должен делать таких предположений. В любом случае плохой опыт — это тоже опыт.