Для задания нас попросили реализовать структуру данных с использованием единого связанного списка.
Моя проблема в том, что после добавления элементов и последующего их удаления программа java по-прежнему использует ту же память, что и раньше.
Вот простой пример
Deque<Integer> deck = new Deque<>();
for( int i =0; i < 500000;i++) {
deck.addFirst(i);
}
for( int i =0; i < 500000;i++) {
deck.removeFirst();
}
System.out.println("end"); //Debugger here
Добавление полумиллиона элементов занимает 27 МБ памяти. После их удаления осталось еще 27мб. Прыгая с отладчиком в конце, переменная колода имеет поля first = null и count = 0;
Почему это так? колода пуста и в ней нет элементов, но память по-прежнему используется.
Код проходит все тесты на корректность, но не проходит тесты памяти.
Я также посмотрел с пошаговым отладчиком и сделал то, что должен был делать.
Может быть, в removeFirst () я ничего не устанавливаю на null и просто назначаю first first.next?
Обновлено: вот результат теста памяти
Test 10: Total memory usage after inserting 4096 items, then successively
deleting items, seeking values of n where memory usage is maximized
as a function of n
n bytes
---------------------------------------------------
=> passed 3200 65592
=> passed 1600 65592
=> FAILED 800 65592 (1.7x)
=> FAILED 400 65592 (3.4x)
=> FAILED 200 65592 (6.7x)
=> FAILED 100 65592 (13.1x)
=> FAILED 50 65592 (25.3x)
==> 2/7 tests passed
Как видите, при 50 элементах по-прежнему используется 65592
Edit2:
// remove and return the item from the front
public Item removeFirst() {
if (this.isEmpty()) throw new java.util.NoSuchElementException();
Item current = first.Item;
first = first.Next;
count--;
return current;
}
Это removeFirst ()
Edit3:
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.concurrent.TimeUnit;
/**
* Created by Alex on 6/30/2018.
*/
public class Deque<Item> implements Iterable<Item> {
private Node first;
private int count;
private class Node {
private Node Next;
private Item Item;
}
// construct an empty deque
public Deque() {
first = null;
count = 0;
}
// is the deque empty?
public boolean isEmpty() {
if (count == 0) {
return true;
}
return false;
}
// return the number of items on the deque
public int size() {
return count;
}
// add the item to the front
public void addFirst(Item item) {
if (item == null) throw new IllegalArgumentException();
Node temp = new Node();
temp.Item = item;
temp.Next = first;
first = temp;
count++;
}
// add the item to the end
public void addLast(Item item) {
if (item == null) throw new IllegalArgumentException();
if (isEmpty()) {
addFirst(item);
} else {
Node last = first;
while (last.Next != null) {
last = last.Next;
}
Node newLast = new Node();
newLast.Item = item;
newLast.Next = null;
last.Next = newLast;
count++;
}
}
// remove and return the item from the front
public Item removeFirst() {
if (this.isEmpty()) throw new java.util.NoSuchElementException();
Item current = first.Item;
first = first.Next;
count--;
return current;
}
// remove and return the item from the end
public Item removeLast() {
if (isEmpty()) throw new java.util.NoSuchElementException();
if (size() == 1) {
return removeFirst();
}else {
Node newLast = first;
Node oldLast = first;
while (oldLast.Next != null) {
newLast = oldLast;
oldLast = oldLast.Next;
}
newLast.Next = null;
count--;
// Item lastItem = ;
return oldLast.Item;
}
}
// return an iterator over items in order from front to end
public Iterator<Item> iterator() {
return new DequeIterator();
}
private void debug() {
Iterator<Item> deckIter = iterator();
while(deckIter.hasNext()) {
System.out.println(deckIter.next());
}
System.out.println(isEmpty());
System.out.println("Size:" + size());
}
// an iterator, doesn't implement remove() since it's optional
private class DequeIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.Item;
current = current.Next;
return item;
}
}
// unit testing (optional)
public static void main(String[] args) throws InterruptedException {
Deque<Integer> deck = new Deque<>();
for( int i =0; i < 500000;i++) {
deck.addFirst(i);
}
for( int i =0; i < 500000;i++) {
deck.removeFirst();
}
System.out.println("end");
TimeUnit.MINUTES.sleep(5);
}
}
Edit4: это ограничения памяти
Спасибо.
Смотрю в диспетчере задач на винде. Обновлено: тесты на правильность проверяют только вывод программы, я добавлю вывод для проверки памяти
Вы можете показать свою реализацию removeFirst()
? Мне также интересно, как реализован этот тестовый пример.
@FoxAlex Java, вероятно, не освободит память ОС до завершения программы. Однако эта память будет доступна для будущего выделения с помощью оператора new
. Это особенность производительности. Java может (или должна иметь возможность) получать память для запроса new
быстрее, чем ОС.
@Mike Housky Есть другие, которые проходят 100% и все тесты проходят, я, должно быть, делаю что-то не так.
Если ваша программа связанного списка не такая уж и длинная, опубликуйте весь класс.
Странный. Вы сказали в вопросе «односвязный список», но имя класса - Deque
. Если это двусвязно, тогда вам нужно будет установить предыдущие указатели на null
, когда вы удалите первую запись; и установите указатель хвоста двухсторонней очереди в нуль, когда вы удалите эту самую последнюю запись.
@MikeHousky - это Deque, реализованный с использованием односвязного списка
@FoxAlex Deque обычно представляет собой двойную очередь (по крайней мере, в Java)
Учитель показал нам только один связанный список и массив изменения размера. Мы должны были выбирать между ними в зависимости от использования памяти.
Что касается использования памяти, правильно оптимизированный массив изменения размера почти всегда будет использовать меньше памяти, чем связанный список.
Да, я реализовал другую структуру данных, используя массив изменения размера, и этот массив проходит все тесты, поэтому остается единственный связанный список, который будет использоваться для этого назначения.
См. stackoverflow.com/questions/1582209/… и stackoverflow.com/questions/30458195/…. (Возможно, это дубликат? Я не думаю, что мы можем больше строить догадки по этому поводу, чем те обложки с вопросами и ответами.)
Как вы думаете, пройдет ли этот тест использование списка с двойной связью?
Из моего тестирования кажется, что память все еще выделена, но ожидает сборки мусора. Класс java.lang.Runtime имеет несколько методов для информирования вас об использовании памяти и статический метод gc (), предлагающий запустить сборщик мусора. Вот дополнительный метод и модификация вашего класса main()
, которые могут вам помочь:
private final static long MB = 1024*1024;
static void memStats(String when)
{
Runtime rt = Runtime.getRuntime();
long max = rt.maxMemory();
long tot = rt.totalMemory();
long free = rt.freeMemory();
System.out.printf(
"mem(mb): %5d tot, %5d free %5d used %5d max %s\n",
tot/MB, free/MB, (tot-free)/MB, max/MB, when);
}
// unit testing (optional)
public static void main(String[] args) {
Deque<Integer> deck = new Deque<>();
memStats("startup");
for( int i =0; i < 500000;i++) {
deck.addFirst(i);
}
memStats("after alloc");
for( int i =0; i < 500000;i++) {
deck.removeFirst();
}
memStats("after removal");
Runtime.getRuntime().gc();
memStats("after gc");
System.out.println("end");
try {
TimeUnit.MINUTES.sleep(5);
} catch (InterruptedException ex)
{
}
}
Поместите их вместо main () в свой класс Deque и запустите его. Я получил:
mem(mb): 15 tot, 15 free 0 used 247 max startup
mem(mb): 29 tot, 10 free 19 used 247 max after alloc
mem(mb): 29 tot, 10 free 19 used 247 max after removal
mem(mb): 29 tot, 29 free 0 used 247 max after gc
end
Как видите, (1) память, выделенная для Java, начинается с общего объема выделенной памяти для объектов Java 15 МБ, при этом используется 0 МБ. (Не обращайте внимания на цифру max
. Это не говорит о том, что я думал.) Он уменьшается до 29 МБ, а после выделения используется 19.
Сразу после выпуска всех Node
в Deque
никаких изменений нет!
Однако после вызова gc () обратите внимание, что общая память, выделенная для кучи, не изменилась, но теперь вся память свободна для использования другими объектами Java. Эта сборка мусора в конечном итоге произойдет - обычно, когда в куче не хватает непрерывной памяти для удовлетворения запроса new
.
Как я сказал в комментариях, я не удивлен, что дополнительные 14 МБ или около того, добавленные в кучу, не были возвращены в ОС. Если вы используете диспетчер задач в Windows, эта память все равно будет считаться «используемой». Переход к ОС за памятью обходится дорого, поэтому обычно это делается только для расширения большими блоками (в данном случае, кажется, ~ 15 миллионов байт) и освобождается только в конце выполнения. Однако это поведение зависит от реализации и может отличаться на другой JVM.
Заметка о вашем коде. Я преобразовал класс Node в:
private static class Node<Item> {
Node<Item> next; // lowercase next
Item item; // You were using Item for both a type and field name!?
}
... и конвертировал практически все вхождения Node
в Node<Item>
. Так и должно быть, поскольку тип элемента узла является универсальным. Это уменьшило использование памяти с 19 МБ до 15 МБ в том же отчете. В нестатических внутренних классах каждый экземпляр внутреннего класса привязан к определенному экземпляру окружающего класса. Вам это не нужно, и это требует времени и памяти.
Это исправление может помочь вам пройти тесты.
О да, обратите внимание, что имя поля меняется с «Далее» на «следующий» и с элемента на элемент. Начните имена полей и методов со строчной буквы, если вы хотите вписаться в традиционные стили именования Java. Ни в коем случае нельзя использовать Item как для имени поля, так и для имени универсального типа.
Спасибо за ответ, я не понимаю, как другие проходят этот тест с помощью единого связанного списка ...
@FoxAlex Вы так и не объяснили, что это был за тест. Однако вам может потребоваться знать, что связанные списки занимают больше места, чем массивы, а также использование нестатического внутреннего класса для затрат на узел.
вся информация, которая у меня есть о тесте, есть в сообщении на Edit, больше я не знаю.
Java пожнет память, когда захочет; не раньше. Как вы определяете, сколько памяти используется? Кроме того, как определяется «тест на правильность»?