Блог пользователя fullaccepted

ArrayList vs LinkedList vs HandList
Автор fullaccepted, 13 лет назад, По-русски
Всем привет!
Я продолжаю изучать Яву, и это дается не очень легко. Новая проблема встала при написании задач на теорию графов.

Если на Си++ я использовал вектора, то тут работа с Vector несколько иная, а LinkedList и ArrayList довольно медленны и занимают очень много памяти.

Что вы предпочитаете? Или при ограничениях до 2000^2 ребер и 64 Мб памяти надо всегда писать все руками?
  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
С ArrayList<Integer>[] проблем никогда не возникало.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

Извиняюсь, но вопрос какой-то нетолковый. Что значит "довольно медленны" и что значит "очень много". Что значит 64Мб - хипа или всего?

Они конечно медленнее чем простой массив в Си, но не настолько медленнее, как можно было бы опасаться. Вообще говоря довольно шустрые. %)

Что значит "писать руками" - в смысле массив руками написать вместо ArrayList или что?

ArrayList и LinkedList кроме того очень разные структуры - в первом доступ к центральным элементам за O(1), во втором за O(N) - с другой стороны при операциях стека/очереди первый будет работать несколько медленнее. Так что их надо правильно выбирать.

Вообще потребность в ArrayList в спортивных задачах обычно невелика т.к. почти всегда вместо него простой массив можно забацать.

В некоторых случаях удобно использовать вместо массива HashMap с ключом по индексу.

UPD: И поясните, что вы с 4млн рёбер своими делать собрались? Если вам нужен 1 проход по ним, то тут даже "довольно медленные" ArrayList/LinkedList справятся. Но в какой задаче нужен 1 проход по всем рёбрам, и чтобы их при этом ещё хранить было зачем-то нужно...

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Извините, что сразу не сформулировал все правильно, буду исправляться.

    "Довольно медленны" - медленнее, чем в массивы в Си++. Уже не раз было(у меня) на контестах, что на Си++ вектора не проходили по времени, из-за динамического выделения памяти. Думал, здесь есть подобные проблемы.

    Писать руками - это написать список на массиве, то есть с массивом указателей на начало цепочек(head), и много вершин с информацией(номер вершины) и указатель на следующий элемент в цепочку(next).

    Задача, на которой я споткнулся - тимус 1198.
    Мое решение (асимптотически правильное, как я думаю), получает ML на 49 тесте, при ограничениях в 64 метра.
    Естественно, я понимаю, что это может быть проблема кривых рук.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А почему не использовать в задачах без ограничения  на общее количество ребер матрицу смежности? Минимум памяти, максимум скорости.
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну руки не сильно кривые (хотя у вас там массивы генеричных классов, ненужный импорт какой-то и т.п. - но это всё мелочи) - т.к. вашу идею вы в общем реализовали. Здесь действительно типичный случай когда из-за количества элементов вам нужно пользоваться простыми массивами интов (можно для них обёртку написать, но внутри это должен быть тупо массив int[]).

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

      Но на тимусе точно есть задачи в которых java-решение нереально или почти нереально затолкнуть по времени/памяти - из тех что натыкался, помню, была 1100... Или путаю...
      → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    > при операциях стека/очереди первый будет работать несколько медленнее

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

    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Кстати... Прав!!! Но заметим - только если "верхушка" стека в конце. Если в начале, то ой-ой... ;-)

      UPD:

      Я имею в виду, если делать:

      list.add(0, elem);

      elem = list.remove(0);

      То быстрее LinkedList (в десятки раз, если сначала заполнить потом вытряхивать)

      А если наоборот:

      list.add(elem);

      elem = list.remove(list.size() - 1);

      То быстрее ArrayList (раза в 2-3)

      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ну вообще-то Vector раз в 5-10, наверное, медленнее, чем ArrayList. И проблем с массивом ArrayList-ов действительно никогда не возникает.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ну в твоем случае ты имеешь около 4 млн рёбер, если каждое ребро будет по 16 байт, то ML тебе почти гарантирован. динамическая память штука такая, если ты выделяешь 1 байт с помощью оператора new даже в C++, реально ты выделишь 16 байт (может даже 32, наверное от платформы зависит)

можешь проверить мою гипотезу о 16 байтах посабмитив A+B, выделя память с помошью new.

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    т.е. если ты напишешь даже свои списки на плюсах, каждая операция new выделит минимум 16 байт, а операций таких будет 4 млн, и ты получишь ML почти гарантировано (из-за доп расходов на стек и остальное)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да не, тут же интов-то разных всего 2000 тыщи а не 4 млн. Можно даже принудительно заставить все указатели в обоих Vector-ах указывать на одни и те же инты - впрочем, я попробовал, вместо 49-го теста на 50-м стало вываливаться. Массив векторов просто сам по себе здоровый (указатели-то не сишные, а до фига "умные" и т.п.)
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Кто сказал что всего 2000 ? у нас есть 2000 списков, в каждом из которых может быть до 2000 элементов. Вот вам и 4 млн. 
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А, понял о чем ты. Я не про new для Integer говорю, я вообще не думал что такой тип юзается, а не просто int. В моем комменте выше я говорю о самописных списках на плюсах. Также я считаю что умный указатель на жаве по размеру равен обычному указателю, другое дело что у каждого созданного объекта, есть еще счетчик ссылок 4-8 байт, в зависимости от разрядности.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            До чего приятно с более умным собеседником (чем я)! Я именно это имел в виду, но вчера сервер перестал работать и сообщение кануло в лету :-)

            Вот так я закэшировал интежеры, чтобы 49-й тест прошёл (но обломился 50-й).

            Насчёт размера указателей вроде бы он тупо равен 32 байтам для 32-разрядных JVM, (но в принципе это на усмотрение авторов машины) но всё равно Vector явно не является просто массивом указателей, например, 4-разрядных, а содержит ещё O(size()) какой-то ерунды, т.к. если вручную попробовать на массив интов int[] заменить, всё проходит, как я выше написал в ответ топикстартеру... %)
            → Ответить