Способ экономии памяти на adjacencylist - PullRequest
Новая
       31

Способ экономии памяти на adjacencylist

0 голосов
/ 26 октября 2018

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

Я читаю файл слов, добавляю их в свой граф и добавляю соседей графа 

static public void createEdges(){
    for(String string : words){  //words is the list of all the ~4 000 words that have been read
        ArrayList<String> wordlist = new ArrayList<String>();
       // ........................................................
       //(irrelevant part where I create a new String "word" from "string")
       // .........................................................
                    if (Contains(word) != null){  //Contains checks if the new String "word" is a part of the file I read. 
                        wordlist.add(word);
                    }
        list.put(string, wordlist); //list is of type: Hashtable<String, ArrayList<String>>; and represents the wordgraph where "string" is the node and "wordlist" is the neighbors of the node
    }}

В одну сторонуЯ думаю, что сэкономит память, не создавая новый цикл ArrayList evere, поскольку он будет повторяться ~ 4000 раз ... Но тогда я не могу придумать какой-либо хороший способ хранения соседних узлов.Использование этой структуры данных обречено для моей цели или есть какие-нибудь более разумные способы реализовать это?

1 Ответ

0 голосов
/ 26 октября 2018

Я думаю, что если это правильно, ваш подход не должен использовать слишком много дополнительной памяти.Возможно, вы могли бы сэкономить память, убедившись, что вы инициализируете ArrayList с тем, сколько элементов вы собираетесь добавить.Это может или не может работать для вашего алгоритма.

Возможно, вам придется создать новый ArrayList после определения всех значений, а затем скопировать в него свои результаты.Это уменьшит избыточную емкость, выделенную списком.Когда список массивов достигает своей внутренней емкости, он должен выделить больше памяти.

Это сэкономит вам только несколько байтов на ArrayList, поэтому будет стоить только, если у вас будет МНОГО записей на карте.

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

Еще один аспект, который следует учитывать, - это то, сколько места занимает объект String.Кажется, вы ссылаетесь на файл и список слов.Если файл может оставаться в памяти в виде большой строки (максимальный размер ~ 2 ГБ), тогда все вызовы .substring будут просто «окнами» в этот файл.Если вы создаете новые объекты String, это будет более требовательным к памяти.

Почему добавление "" в String сохраняет память?

...