VPF::Выбор коллекции для 300000 тысяч строк!

freshAngel

Дата 9.12.2009, 18:04 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 248
Регистрация: 1.10.2008

Репутация: нет
Всего: нет

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

Код


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

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

Kircul

Дата 9.12.2009, 18:12 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 20.2.2007

Репутация: 6
Всего: 7

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

LSD

Дата 9.12.2009, 18:12 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538

Цитата(freshAngel @ 9.12.2009, 18:04

)

Какую коллекцию лучше выбрать, что - бы хранить 300000 строк!?

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

Цитата(freshAngel @ 9.12.2009, 18:04

)

Сейчас все это тормозит ужасно!!!

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

--------------------

Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.

freshAngel

Дата 9.12.2009, 18:14 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 248
Регистрация: 1.10.2008

Репутация: нет
Всего: нет

Цитата(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...

Это сообщение отредактировал(а) freshAngel - 9.12.2009, 18:16

Kircul

Дата 9.12.2009, 18:18 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 20.2.2007

Репутация: 6
Всего: 7

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

freshAngel

Дата 9.12.2009, 18:28 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 248
Регистрация: 1.10.2008

Репутация: нет
Всего: нет

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

LSD

Дата 9.12.2009, 18:28 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538

Цитата(freshAngel @ 9.12.2009, 18:14

)

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

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

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

--------------------

freshAngel

Дата 9.12.2009, 18:32 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 248
Регистрация: 1.10.2008

Репутация: нет
Всего: нет

Цитата(LSD @ 9.12.2009, 18:28)

Цитата(freshAngel @ 9.12.2009, 18:14

)

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

Добавлено @ 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/.*$")
    )

Это сообщение отредактировал(а) freshAngel - 9.12.2009, 18:34

Kircul

Дата 9.12.2009, 18:36 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 20.2.2007

Репутация: 6
Всего: 7

Цитата(LSD @ 9.12.2009, 17:28

)

На больших объемах LinkedList будет тратить больше памяти на один элемент.

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

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

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

Это сообщение отредактировал(а) Kircul - 9.12.2009, 18:38

LSD

Дата 9.12.2009, 19:06 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538

Цитата(freshAngel @ 9.12.2009, 18:32

)

Как можно оптимизировать!?

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

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

Цитата(Kircul @ 9.12.2009, 18:36

)

Все так, но давай посчитаем (для 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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1620
Регистрация: 20.9.2006
Где: Киев

Репутация: 8
Всего: 56

Цитата(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 есть ? нет? зачем выбирать из базы записи если вы их потом отфильтровываете?
возможно стоит пересмотреть условия по которому запись заноситься в коллекцию и уже на этом этапе выбрасывать не нужные записи?

--------------------

java блох

Kircul

Дата 9.12.2009, 19:19 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 20.2.2007

Репутация: 6
Всего: 7

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Варвар

Профиль
Группа: Участник
Сообщений: 639
Регистрация: 26.1.2005
Где: Москва

Репутация: 4
Всего: 28

Цитата(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 интерфейс и получать результаты за секунды.

Это сообщение отредактировал(а) ivanovpv - 9.12.2009, 21:29

--------------------

Aut viam inveniam aut faciam

serger

Дата 10.12.2009, 10:26 (ссылка)

(голосов:1)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 518
Регистрация: 19.6.2007
Где: Ижевск

Репутация: 1
Всего: 5

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

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

--------------------

упс!

LSD

Дата 10.12.2009, 14:34 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538

Цитата(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

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

--------------------

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »