Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Java: Общие вопросы > Выбор коллекции для 300000 тысяч строк!


Автор: freshAngel 9.12.2009, 18:04
Привет.
Какую коллекцию лучше выбрать, что - бы хранить 300000 строк!?
Сейчас:
Код

Vector<ArrayList> hash = new Vector<ArrayList>(0);


Собственно будет храниться 300000 ArrayList'ов в векторе.
Сейчас все это тормозит ужасно!!!
-Xms1024m -Xmx1024m не помогает...

Автор: Kircul 9.12.2009, 18:12
ИМХО, в таком случае проще использовать БД

Автор: LSD 9.12.2009, 18:12
Цитата(freshAngel @  9.12.2009,  18:04 Найти цитируемый пост)
Какую коллекцию лучше выбрать, что - бы хранить 300000 строк!?

Лучше всего массивы.


Цитата(freshAngel @  9.12.2009,  18:04 Найти цитируемый пост)
Сейчас все это тормозит ужасно!!!

Что именно тормозит. Объекты лежат в листе, их никто не трогает и все тормозит?

Автор: freshAngel 9.12.2009, 18:14
Цитата(Kircul @ 9.12.2009,  18:12)
ИМХО, в таком случае проще использовать БД

При использовании БД тормозит еще хуже...
Поэтому перешел на хэш.
Беру кусок из БД и записываю его в хэш, а дальше прогоняю циклами, if'ми...

Добавлено @ 18:15
Цитата(LSD @ 9.12.2009,  18:12)
Цитата(freshAngel @  9.12.2009,  18:04 Найти цитируемый пост)
Какую коллекцию лучше выбрать, что - бы хранить 300000 строк!?

Лучше всего массивы.


Цитата(freshAngel @  9.12.2009,  18:04 Найти цитируемый пост)
Сейчас все это тормозит ужасно!!!

Что именно тормозит. Объекты лежат в листе, их никто не трогает и все тормозит?

Нажимаю кнопку "Найти" в этот момент заполняются вектора и происходит их обработка, далее жду минут сорок, пока не вывалится ексепшн: memory heap size...

Автор: Kircul 9.12.2009, 18:18
Ну попробуй LinkedList использовать, если заранее не известен размер коллекции, в противном случае в конструкторе укажи кол-во элементов.

Автор: freshAngel 9.12.2009, 18:28
Можно попробовать, только вот добавление в конец  быстрей в ArrayList и рандомный поиск элементов быстрей в ArrayList вместе с сортировкой.
А LinkedList быстрей только при добавлении в начало...
Есть еще варианты!?

Автор: LSD 9.12.2009, 18:28
Цитата(freshAngel @  9.12.2009,  18:14 Найти цитируемый пост)
Нажимаю кнопку "Найти" в этот момент заполняются вектора и происходит их обработка, далее жду минут сорок, пока не вывалится ексепшн: memory heap size...

Что означает, что памяти все таки нехватает и дело не в том, какая коллекция используется. По сравнению с размером данных, накладные расходы на саму коллекцию пренебрежимо малы. Надо или увеличить объем памяти, или как-то оптимизировать объемы данных.

Добавлено через 1 минуту и 44 секунды
На больших объемах LinkedList будет тратить больше памяти на один элемент.

Автор: freshAngel 9.12.2009, 18:32
Цитата(LSD @ 9.12.2009,  18:28)
Цитата(freshAngel @  9.12.2009,  18:14 Найти цитируемый пост)
Нажимаю кнопку "Найти" в этот момент заполняются вектора и происходит их обработка, далее жду минут сорок, пока не вывалится ексепшн: memory heap size...

Что означает, что памяти все таки нехватает и дело не в том, какая коллекция используется. По сравнению с размером данных, накладные расходы на саму коллекцию пренебрежимо малы. Надо или увеличить объем памяти, или как-то оптимизировать объемы данных.

Добавлено @ 18:30
На больших объемах LinkedList будет тратить больше памяти на один элемент.

Как можно оптимизировать!?
Что можно сделать со строкой!?  smile 
У меня в коде очень много сверок в условиях с equals и регулярными выражениями, вот пример кода:
Код

if (cdr_Hash.get(i).get(3).equals("a") &&
    cdr_Hash.get(i).get(7).equals("Hashl") &&
    in_array(cdr_Hash.get(i).get(4), "open", "open") &&
    cdr_Hash.get(i).get(6).toString().matches("^Local/.*$") &&
    cdr_Hash.get(i).get(8).toString().matches("^Local/.*$") &&
    cdr_Hash.get(i).get(5).toString().matches("^Transfered/.*$")
    )

Автор: Kircul 9.12.2009, 18:36
Цитата(LSD @  9.12.2009,  17:28 Найти цитируемый пост)
На больших объемах LinkedList будет тратить больше памяти на один элемент. 

На сколько я знаю ArrayList это только обертка на массив и при превышении размера созданного массива происходит создание нового с большим размером и копирование в него всех елементов. А при использование LinkedList каждый раз выделяется место только для одного элемента и он линкуется к уже созданной коллекции.

Я где-то заблуждаюсь?

Т.е. до срабатывания сборщика мусора мы имеем кучу засоренной памяти. Вероятно это так же как и при конкатенации строк при помощи + или StringBuffer

Автор: LSD 9.12.2009, 19:06
Цитата(freshAngel @  9.12.2009,  18:32 Найти цитируемый пост)
Как можно оптимизировать!?

Скорее всего общих советов, будет недостаточно, надо разбираться с конкретным случаем отдельно.

Если много дупликатов строк, можно их интернировать. Можно загрузить часть строк, обработать, записать промежуточные результаты в базу/файл, загрузить следующую партию и т.д. Вообщем надо смотреть на конкретный код.





Цитата(Kircul @  9.12.2009,  18:36 Найти цитируемый пост)
На сколько я знаю ArrayList это только обертка на массив и при превышении размера созданного массива происходит создание нового с большим размером и копирование в него всех елементов. А при использование LinkedList каждый раз выделяется место только для одного элемента и он линкуется к уже созданной коллекции.

Я где-то заблуждаюсь?

Все так, но давай посчитаем (для 32-х битной JVM):
  • ArrayList и LinkedList это объекты - 8 байт на заголовок объекта плюс 4 байта на каждое поле этого объекта, т.к. полей немного, то по сравнению с общим объемом данных, этим можно просто пренебречь
  • ArrayList хранит данные в массиве массив тратит на хранение каждой ссылки 4 байта плюс 8 байт на заголовок объекта (отнесем эти 8 байт к предыдущему пункту)
  • LinkedList хранит данные в объекте Entry размер которого: 3*4 байта полей (данные, предыдущий, следующий) плюс 8 байт на заголовок объекта
Вот и получается, что на больших объемах ArrayList тратит от 4 байт на элемент (если размер массива, точно соответвует количеству данных), до 8 байт (если массив в 2 раза больше). К тому же у ArrayList есть trimToSize().
LinkedList же на больших объемах, тратит на каждый элемент 20 байт.





Цитата(Kircul @  9.12.2009,  18:36 Найти цитируемый пост)
Т.е. до срабатывания сборщика мусора мы имеем кучу засоренной памяти. Вероятно это так же как и при конкатенации строк при помощи + или StringBuffer

Перед тем как будет выкинут OutOfMemoryError, всегда вызывается сборщик мусора. Так, что в данном случае не это вызывает проблему.

Автор: v2v 9.12.2009, 19:14
Цитата(freshAngel @  9.12.2009,  18:32 Найти цитируемый пост)

У меня в коде очень много сверок в условиях с equals и регулярными выражениями, вот пример кода:

Код

if (cdr_Hash.get(i).get(3).equals("a") &&
    cdr_Hash.get(i).get(7).equals("Hashl") &&
    in_array(cdr_Hash.get(i).get(4), "open", "open") &&
    cdr_Hash.get(i).get(6).toString().matches("^Local/.*$") &&
    cdr_Hash.get(i).get(8).toString().matches("^Local/.*$") &&
    cdr_Hash.get(i).get(5).toString().matches("^Transfered/.*$")
    )


а else есть ? нет? зачем выбирать из базы записи если вы их потом отфильтровываете?
возможно стоит пересмотреть условия по которому запись заноситься в коллекцию и уже на этом этапе выбрасывать не нужные записи?

Автор: Kircul 9.12.2009, 19:19
Цитата(LSD @  9.12.2009,  18:06 Найти цитируемый пост)
Перед тем как будет выкинут OutOfMemoryError, всегда вызывается сборщик мусора. Так, что в данном случае не это вызывает проблему. 

Так-то оно так, но если взять такой код
Код

        List<String> stringList = new ArrayList<String>();
        for (int i = 0; i < INITIAL_CAPACITY; i++) {
            stringList.add("WWWWWWWWWWWWWWWWWWWWWWWWWW");
        }

То на моей машине (параметры запуска дефолтные) при INITIAL_CAPACITY = 15000000 валится OutOfMemoryError (где-то на кол-ве в 7600000), но если поставить INITIAL_CAPACITY в аргументы конструктора то все работает нормально, при INITIAL_CAPACITY = 16000000 валится в обоих случаях. Т.е. при указании правильного кол-ва в аргументы конструктора мы выигрываем в 2 раза больше памяти.

При использовании LinkedList падает ошибка и на 7600000. Есть информация к размышлению... 

Автор: ivanovpv 9.12.2009, 21:25
Цитата(freshAngel @  9.12.2009,  18:04 Найти цитируемый пост)
Привет.
Какую коллекцию лучше выбрать, что - бы хранить 300000 строк!?
Сейчас:


Конечно же надо ставить все это безобразие на БД, индексировать строки и обращаться через нормальные select'ы... - типа:
Код

select mystring from strings where mystring like '%Hash1%'


Ну решите вы сейчас на 300 тыс. строк, а если будет 300 миллионов строк? Никакого хипа не хватит и никаких коллекций

Операция equals() на String'е очень дорогая операция знаете ли... А любая нормальная СУБД справится с select'ом на 300 тыс. записей за доли секунды - отвечаю smile 

Так что подумайте что лучше сидеть перед монитором 40 минут в ожидании OutOfMemory или перенести все в БД и написать через JDBC интерфейс и получать результаты за секунды.

Автор: serger 10.12.2009, 10:26
Посмотри вариант Bercley DB
Специально для больших хэшей - сомневаюсь, что свой велосипед будет много лучше...

http://ru.wikipedia.org/wiki/Berkeley_DB
http://www.oracle.com/technology/products/berkeley-db/index.html

Автор: LSD 10.12.2009, 14:34
Цитата(Kircul @  9.12.2009,  19:19 Найти цитируемый пост)
Так-то оно так, но если взять такой код
...
То на моей машине (параметры запуска дефолтные) при INITIAL_CAPACITY = 15000000 валится OutOfMemoryError (где-то на кол-ве в 7600000), но если поставить INITIAL_CAPACITY в аргументы конструктора то все работает нормально, при INITIAL_CAPACITY = 16000000 валится в обоих случаях. Т.е. при указании правильного кол-ва в аргументы конструктора мы выигрываем в 2 раза больше памяти.

При использовании LinkedList падает ошибка и на 7600000. Есть информация к размышлению...  

Информация то конечно, есть. Но тут надо учитывать таку вещь как особенности работы Java со строками. В твоем случае, у тебя всего один екземпляр строки, с таким же успехом можно инициализировать коллекцию null-ами.

Вот более коплексный пример с одинаковыми, разными и вообще нулевыми строками:
Код

import org.apache.log4j.Logger;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class Test
{
  public static final Logger logger = Logger.getLogger("test");

  private static Random rnd = new Random();

  public static void main(String[] args)
  {
    logger.info("=== StaticStringGen ===");
    doTest("LinkedList", new LinkedList<String>(), StaticStringGen.INSTANCE);
    doTest("ArrayList default size", new ArrayList<String>(), StaticStringGen.INSTANCE);
    doTest("ArrayList predefined size", new ArrayList<String>(30900000), StaticStringGen.INSTANCE);
    logger.info("");

    logger.info("=== NullStringGen ===");
    doTest("LinkedList", new LinkedList<String>(), NullStringGen.INSTANCE);
    doTest("ArrayList default size", new ArrayList<String>(), NullStringGen.INSTANCE);
    doTest("ArrayList predefined size", new ArrayList<String>(30900000), NullStringGen.INSTANCE);
    logger.info("");

    logger.info("=== RandomStringGen ===");
    doTest("LinkedList", new LinkedList<String>(), RandomStringGen.INSTANCE);
    doTest("ArrayList default size", new ArrayList<String>(), RandomStringGen.INSTANCE);
    doTest("ArrayList predefined size", new ArrayList<String>(950000), RandomStringGen.INSTANCE);
  }

  public static void doTest(final String msg, final List<String> stringList, final StringGen gen)
  {
    System.gc();
    int i = 0;
    try
    {
      for(; i < Integer.MAX_VALUE; i++)
      {
        stringList.add(gen.generateString());
      }
    }
    catch(Throwable t)
    {
      logger.info(String.format("%s final size: %,d", msg, i));
    }
    System.gc();
  }

  public interface StringGen
  {
    public String generateString();
  }

  public static class NullStringGen implements StringGen
  {
    public static final NullStringGen INSTANCE = new NullStringGen();

    public String generateString()
    {
      return null;
    }
  }

  public static class StaticStringGen implements StringGen
  {
    public static final StaticStringGen INSTANCE = new StaticStringGen();
    private static final String STR = "12345678901234567890123456789012345678901234567890";

    public String generateString()
    {
      return STR;
    }
  }

  public static class RandomStringGen implements StringGen
  {
    public static final RandomStringGen INSTANCE = new RandomStringGen();
    public static final int LEN = StaticStringGen.STR.length();

    public String generateString()
    {
      final char[] chars = new char[LEN];
      for(int i = 0; i < chars.length; i++)
      {
        chars[i] = (char) ('A' + rnd.nextInt('Z' - 'A'));
      }
      return new String(chars);
    }
  }
}

Запускать с ключем: -Xmx128M -Xms128M
Результат:
Код

[INFO ] [test] === StaticStringGen ===
[INFO ] [test] LinkedList final size: 5 538 650
[INFO ] [test] ArrayList default size final size: 17 176 655
[INFO ] [test] ArrayList predefined size final size: 30 900 000
[INFO ] [test] 
[INFO ] [test] === NullStringGen ===
[INFO ] [test] LinkedList final size: 5 538 028
[INFO ] [test] ArrayList default size final size: 17 176 655
[INFO ] [test] ArrayList predefined size final size: 30 900 000
[INFO ] [test] 
[INFO ] [test] === RandomStringGen ===
[INFO ] [test] LinkedList final size: 830 705
[INFO ] [test] ArrayList default size final size: 947 731
[INFO ] [test] ArrayList predefined size final size: 949 358

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)