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

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

Моя проблема в том, что после добавления элементов и последующего их удаления программа 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: это ограничения памяти

https://imgur.com/nQuDfUF

Спасибо.

Java пожнет память, когда захочет; не раньше. Как вы определяете, сколько памяти используется? Кроме того, как определяется «тест на правильность»?

zero298 02.07.2018 18:59

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

Fox Alex 02.07.2018 19:01

Вы можете показать свою реализацию removeFirst()? Мне также интересно, как реализован этот тестовый пример.

zero298 02.07.2018 19:04

@FoxAlex Java, вероятно, не освободит память ОС до завершения программы. Однако эта память будет доступна для будущего выделения с помощью оператора new. Это особенность производительности. Java может (или должна иметь возможность) получать память для запроса new быстрее, чем ОС.

Mike Housky 02.07.2018 19:05

@Mike Housky Есть другие, которые проходят 100% и все тесты проходят, я, должно быть, делаю что-то не так.

Fox Alex 02.07.2018 19:07

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

zero298 02.07.2018 19:10

Странный. Вы сказали в вопросе «односвязный список», но имя класса - Deque. Если это двусвязно, тогда вам нужно будет установить предыдущие указатели на null, когда вы удалите первую запись; и установите указатель хвоста двухсторонней очереди в нуль, когда вы удалите эту самую последнюю запись.

Mike Housky 02.07.2018 19:13

@MikeHousky - это Deque, реализованный с использованием односвязного списка

Fox Alex 02.07.2018 19:14

@FoxAlex Deque обычно представляет собой двойную очередь (по крайней мере, в Java)

Peter Lawrey 02.07.2018 19:15

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

Fox Alex 02.07.2018 19:17

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

Haroldo_OK 02.07.2018 19:21

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

Fox Alex 02.07.2018 19:25

См. stackoverflow.com/questions/1582209/… и stackoverflow.com/questions/30458195/…. (Возможно, это дубликат? Я не думаю, что мы можем больше строить догадки по этому поводу, чем те обложки с вопросами и ответами.)

Radiodef 02.07.2018 19:25

Как вы думаете, пройдет ли этот тест использование списка с двойной связью?

Fox Alex 02.07.2018 20:23
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
4
14
118
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Из моего тестирования кажется, что память все еще выделена, но ожидает сборки мусора. Класс 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 как для имени поля, так и для имени универсального типа.

Спасибо за ответ, я не понимаю, как другие проходят этот тест с помощью единого связанного списка ...

Fox Alex 02.07.2018 20:17

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

Mike Housky 02.07.2018 20:46

вся информация, которая у меня есть о тесте, есть в сообщении на Edit, больше я не знаю.

Fox Alex 02.07.2018 20:51

Другие вопросы по теме