Весь ArrayList обновляется, когда я пытаюсь обновить один элемент Java 21
В свободное время я занимался алгоритмами и столкнулся со странной проблемой. Я не могу понять, почему это происходит. У меня есть два списка, и в обоих я обновляю элементы одинаково, но в «ленивом» списке при обновлении элемента обновляются все элементы.
Это важная часть кода:
public class SegmentTree {
public static void main(String[] args) {
List<Integer> a = List.of(1, 2, 3, 4, 5, 6, 7, 8);
SegmentTreeObject segmentTreeObject = new SegmentTreeObject(a);
segmentTreeObject.build(a);
segmentTreeObject.list.forEach(s -> System.out.println(s.leftPosition + " " + s.rightPosition + " " + s.value));
segmentTreeObject.updateLazy(new Point(0, 7), 5);
segmentTreeObject.lazy.forEach(s -> System.out.println(s.leftPosition + " " + s.rightPosition + " " + s.value));
}
}
class SegmentTreeObject {
List<Node> list;
List<Integer> original;
//Lazy tree
List<Node> lazy;
int size;
SegmentTreeObject(List<Integer> obj) {
this.list = new ArrayList<>(Collections.nCopies(4 * obj.size(), new Node(100, 100, 0)));
this.lazy = new ArrayList<>(Collections.nCopies(4 * obj.size(), new Node(0, 0, 0)));
this.original = new ArrayList<>(obj);
this.size = obj.size();
}
void updateLazyTree(int start, int end, int left, int right, int node, int newValue) {
if (left > end || right < start) {
return;
}
if (start >= left && end <= right) {
this.list.get(node).updateNode(this.list.get(node).value + (end-start+1) * newValue);
this.lazy.get(2 * node + 1).updateNode(this.lazy.get(2*node+1).value + newValue);
this.lazy.get(2 * node + 2).updateNode(this.lazy.get(2*node+2).value + newValue);
return;
}
int mid = start + (end-start) / 2;
updateLazyTree(start, mid, left, right, 2 * node + 1, newValue);
updateLazyTree(mid + 1, end, left, right, 2 * node + 2, newValue);
}
void updateLazy(Point range, int value) {
updateLazyTree(0, this.size - 1, range.x, range.y, 0, value);
}
}
class Node {
int leftPosition;
int rightPosition;
int value;
// All-args constructor omitted for brevity
public void updateNode(int value){
this.value = value;
}
}
и вывод ленивых выглядит так:
0 0 10
0 0 10
0 0 10
0 0 10
0 0 10
0 0 10
0 0 10
Я также проверил с помощью отладчика, и да, «ленивый» список обновляет объект после одного вызова «updateNode».
Спасибо за ваше время!
Пожалуйста, дайте мне знать, если у вас есть идеи; Возможно, я ошибаюсь, создавая «ленивый» список.
Ответы 1
Посчитайте new. Именно столько у вас объектов. Таким образом, в:
this.list = new ArrayList<>(Collections.nCopies(4*obj.size(),new Node(100,100,0)));
Я считаю.. 1 new.
Итак, у вас есть список с множеством записей, но только один объект Node. Как это может быть? Как у вас может быть массив, чьи .size() отчеты в этом примере составляют 32 (obj — это 8, и вы умножаете его на 4) — но только один Node объект?
Ну представьте себе такую ситуацию:
Я строю один-единственный дом.
Затем я покупаю адресную книгу в магазине. В нем 32 страницы. На каждой странице я пишу один и тот же адрес. Адрес того дома, который я построил.
ТАДА! 32 дома!
Не совсем. Конечно, у меня 32 адреса. И они все одинаковы. 1 дом, 32 страницы.
Здесь происходит та же самая ситуация. У вас есть один объект узла и список массивов с 32 ссылками, все на этот один объект узла. Измените одну, и вы измените их все, по той же причине, по которой вы возьмете адресную книгу с ее 32 страницами, выберете случайную страницу, подойдете к дому, бросите кирпич в окно, а затем: независимо от того, какую страницу вы откроете. ваша адресная книга, если вы подойдете к адресу, который найдете там, угадайте, что? Окно разбито.
Вам нужно 32 объекта узла.
this.list = new ArrayList<>();
for (int i = 0; i < 4 * obj.size(); i++) this.list.add(new Node(100, 100, 0));
Если я подсчитаю, сколько раз new выполняется сейчас, в итоге я получу 32. Действительно, этот код подойдет (вам, конечно, также придется исправить this.lazy).
Если вы чувствуете, что это каким-то образом портит чистоту, то этот метод МОЖЕТ существовать в j.u.Collections:
public static <T> nTimes(int n, Supplier<T> supplier) {
if (n < 0) throw new IllegalArgumentException("" + n);
var list = new ArrayList<T>(n);
for (int i = 0; i < n; i++) list.add(supplier.get());
return list;
}
Тогда вы можете вызвать:
Collections.nTimes(4 * obj.size() () -> new Node(100, 100, 0));
Но такого метода просто не существует. Возможно, никогда: по большей части nCopies вообще существует потому, что обеспечивает весьма впечатляющую оптимизацию: он может представлять миллион записей практически без памяти, он просто запоминает одну ссылку, а также число «один миллион». nCopies похож на волшебную адресную книгу, в которой всего две страницы, поэтому она очень маленькая: одна страница с одним номером, а вторая страница с одним адресом. Для всех целей эта адресная книга действует так, как будто она большая (столько же страниц, сколько и первое число), с одним и тем же адресом на каждой из этих страниц. Это не очень-то полезная адресная книга, и действительно, nCopies используется редко. Но оно для этого и предназначено. Если вам нужна эта странная «адресная книга с МНОГО одинаковых записей», nCopies с ней очень хорошо справляется.
Хотя здесь совсем не то, что вам нужно. Итак, просто напишите цикл.
Другой вариант создания экземпляров объектов может быть чем-то вроде Arrays.asList(IntStream.range(0, obj.size()*4) .mapToObj(() -> new Node(100,100,0)) .toArray(Node[]::new)); похожим на ответы, найденные здесь.
@ Al3x4ndru1 Al3x4ndru1 Java в этом смысле очень-очень проста. Метод nCopies не может захватить new Node(100, 100, 0) и запустить его более одного раза. Нет; это выражение вычисляется тут же, прежде чем nCopies даже вызывается, и передается результат вычисления этого выражения. nCopies не могу повторно запустить выражение. В лучшем случае он может попытаться клонировать то, что получает (но практически ничто в основных библиотеках этого не делает, и nCopies тоже). () -> new Node(100, 100, 0) — это «лямбда» — он отражает «идею сделать это» и может вызываться так часто, как вам нравится.
@CalvinP кажется мне «злоупотреблением лямбдой». Цикл for не больше (если только вы не припишете «все блоки должны быть заключены в скобки», но тогда... почему тогда ваши вызовы mapToObj и co. не заключены в скобки? Если вы применяете непоследовательный стиль, проблема в вашем руководстве по стилю! ) и является должным образом прозрачным (проверенный ex, локальная изменяемая переменная и поток управления), тогда как лямбда-нет. Здесь это ничего не добавляет. Теперь, в примере nTimes, он добавляет кое-что полезное.
Спасибо вам, ребята. В следующий раз я буду осторожнее.
Спасибо большое за Ваш комментарий! Я учил, что «this.list = new ArrayList<>(Collections.nCopies(4*obj.size(),new Node(100,100,0)));» каждый раз будет создавать новый объект, как вы упомянули, 32 новых дома. Я учил этому, потому что использовал ту же логику для: «List<Node> list;» и это работает, как вы можете видеть в следующем примере: «0 7 76 0 3 10 4 7 26 0 1 3 2 3 7 4 5 11 6 7 15 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 100 100 0 100 100 0 100 100 0...» до 32. Теперь я немного не понимаю, почему это работает в «списке», а теперь в основном в «lasy». .