Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Java [игнор отключен] [закрыт для гостей] / Оптимальные раелизации Set и Map по памяти / 25 сообщений из 55, страница 1 из 3
  1  все
25.03.2014, 17:18
    #38596088
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
Подскажите, если знает кто.

λf.(λx.f (x x)) (λx.f (x x))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 17:20
    #38596093
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
з.ы. количество элементов мало. от одного до десятка.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 17:22
    #38596098
Blazkowicz
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
Что-нибудь на базе массивов
http://javadoc.google-api-java-client.googlecode.com/hg/1.0.10-alpha/com/google/api/client/util/ArrayMap.html
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 20:33
    #38596317
Atum1
Atum1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
Map - из родной java - по умолчанию - 16 корзинок , достаточно компактен !?

Если нужно меньше то возьми и реализуй свою хеш таблицу на основе Открытой адресации ?!

или реализовать свой Ассоциативный массив на базе java.util Class Dictionary<K,V>?!

Если количество элементов заранее известно и из значения - создать enum ( enumset)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 20:42
    #38596322
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
ZyK_BotaN, загони в строку

Код: java
1.
String ZyK_BotaN_map="key1=value1;key2=value2.........";



и будет тебе оптимальность по memory. Чо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 20:45
    #38596325
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
maytonZyK_BotaN, загони в строку

Код: java
1.
String ZyK_BotaN_map="key1=value1;key2=value2.........";




и будет тебе оптимальность по memory. Чо.
Ну про производительность, тоже желательно не забывать.
Таких мапов - несколько миллионов. И это не для хранения, или отправки, а для "живой работы".
Т.е. нужно что-бы оперативы поменьше жрало, при том что в каждой мапе\сете элементов не много.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 21:16
    #38596346
Blazkowicz
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
ZyK_BotaNНу про производительность, тоже желательно не забывать.

До 10ти элементов же! Какая нафиг производительность, даже на полном переборе ничего не просядет. А если сортировать и искать двоичным поиском, то вообще залетает.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 21:19
    #38596349
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
BlazkowiczДо 10ти элементов же! Какая нафиг производительность, даже на полном переборе ничего не просядет.
Обращений миллионы.
Вставки, удаления, чтение.
Поэтому производительность должна быть хотя-бы вменяемая(максимальное быстродействие не обязательно).
А вот по памяти - больший приоритет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 21:20
    #38596350
Usman
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
ZyK_BotaN,

Посмотрите в сторону:
- EnumMap - internally implemented as an array
- IdentityHashMap - never invokes the equals

работают (вроде) быстрее остальных реализаций.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 21:21
    #38596351
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
Usmanбыстрее остальных реализаций.
меня больше память сейчас волнует.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 21:31
    #38596354
Atum1
Atum1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
ZyK_BotaN,

Обращений миллионы?

а что с потокобезопасностью?

так все таки нужен set или map ?

опишите конкретно что у вас за задача?

чем вас не устраивает HashMap , IdentityHashMap , ConcurrentHashMap?

Дайте свои оценки по скорости , и по ограничению памяти !
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 21:37
    #38596361
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
Atum1а что с потокобезопасностью?
в одном потоке
Atum1Обращений миллионы?
да

Atum1так все таки нужен set или map ?
и первое, и второе

Atum1опишите конкретно что у вас за задача?
миллионы сетов и мапов - с малым кол-ом элементов.
скорость - в пределах разумного
паять - в первую очередь
Atum1чем вас не устраивает HashMap
просто вопрос возник, есть ли более легковесные решения, так как процентов 35 занимает "Shallow Size" мап и сетов(не полезная нагрузка, т.е. с вычитом занимаемой памяти самими элементами).

мне надо уменьшить расходы памяти приложения, не в разы, но процентов на 10-20.
Вот у меня и возник вопрос, нет ли более легковесных решений, пускай даже с накладными рассходами на производительность.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 21:40
    #38596366
cdtyjv
cdtyjv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
ZyK_BotaN ,
Проблема заключается в том, что с точки зрения производвительности вы сейчас ведете абсолютно беспредметный и неконструктивный диалог. "Надо, что б памяти мало ело", "надо, что б быстро было" - так вопросы по перфомансу не ставят. Насколько мало? Насколько быстро? Где те цифры, достигнув которых, вы скажете "ок, вот теперь хватит"?
Вот берем HashMap. Приближенно можем считать, что у нее оверхед 40 байт на одну энтри. В каждой мапе 10 энтри, всего миллион мапов. Получаем: 40 * 10 * 1000000 = 400,000,000b = 380Mb.
Теперь давайте посчитаем теоретический предел. Одна энтри это референс ключа + референс значения. 16 байт. 16 * 10 * 1000000 = 150Mb. Итого, вы сейчас боретесь за 230 мегабайт дополнительного оверхеда.
Это критично для вашего приложения? А это какая часть вашего хипа? А сколько у вас хипа всего? А сколько у вас сейчас длятся GC паузы? А на какие максимальные GC паузы вы готовы? А сколько времени вы готовы потратить на тюнинг хипа? А насколько вам критична скорость работы приложения, какой запас есть? Вот замените вы HashMap на ArrayMap, сэкономите метров 100, а работать все станет медленнее - переживете?

Я думаю, вы уловили идею
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 21:42
    #38596369
cdtyjv
cdtyjv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
ZyK_BotaNмне надо уменьшить расходы памяти приложения, не в разы, но процентов на 10-20.А зачем? Хипа не хватает? GC паузы душат? На все должна быть причина.
ZyK_BotaNВот у меня и возник вопрос, нет ли более легковесных решений, пускай даже с накладными рассходами на производительность.Вам же уже дали ответ - ArrayMap. Что-то проще врядли можно придумать.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 21:46
    #38596371
Atum1
Atum1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
ZyK_BotaN,

тогда книга вам в помощь :
тут примеры и решения , смотрите главы по хеш таблицам и 2-3-4 деревьям .
http://algs4.cs.princeton.edu/code/

создайте свою реализацию на основе java.util Class Dictionary<K,V> - берите реализацию HashMap и выбрасывайте все ненужно или вкуривайте главы из книги - там есть пример как раз по вашей задачки .


PS
Миллионы маленьких сетов и мапов в памяти ?! Хм вы что игры делаете ? это для каждого пользователя?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 21:55
    #38596373
Atum1
Atum1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
обычный hasmap - гарантирует что при количестве корзин по умолчанию 16 - положив в него 8 элементов при дефолтовом коэффициенте заполнения у вас будет чуть более 50% коллизий , т.е. с 50% вероятность два элемента попадут в одну корзинку.

Если вам этого мало - делайте мапу на открытой адресации - зная что у вас будет не более 10 элементов.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 22:26
    #38596408
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
ZyK_BotaNmaytonZyK_BotaN, загони в строку

Код: java
1.
String ZyK_BotaN_map="key1=value1;key2=value2.........";




и будет тебе оптимальность по memory. Чо.
Ну про производительность, тоже желательно не забывать.
Таких мапов - несколько миллионов. И это не для хранения, или отправки, а для "живой работы".
Т.е. нужно что-бы оперативы поменьше жрало, при том что в каждой мапе\сете элементов не много.
Ну ты и жуууук... Хочешь и рыбку сьесть и в Раде сесть?

Огласи критерии.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 22:43
    #38596419
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
cdtyjvА зачем? Хипа не хватает? GC паузы душат? На все должна быть причина.
хипа не хватает.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 22:45
    #38596421
cdtyjv
cdtyjv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
ZyK_BotaN ,
А сколько миллионов Map у вас?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 22:46
    #38596422
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
cdtyjvИтого, вы сейчас боретесь за 230 мегабайт дополнительного оверхеда.
да.


cdtyjvА насколько вам критична скорость работы приложения, какой запас есть?
если уменьшить расход памяти процентов на 20-ть, то можно хоть в два три раза что-бы медленнее работало.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 22:47
    #38596423
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
cdtyjvВот замените вы HashMap на ArrayMap, сэкономите метров 100, а работать все станет медленнее - переживете?
Заменил. Медленнее не стало. Но и меньше есть не стало. Ровно столько же.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 22:51
    #38596426
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
cdtyjv ZyK_BotaN ,
А сколько миллионов Map у вас?
Сейчас не вспомню, но несколько.

з.ы при этом размер сетов может быть ограничен в пределах от "4-20", а размеры мапов - не ограничены, но редко превышают пару десятков.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 23:00
    #38596430
cdtyjv
cdtyjv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
ZyK_BotaNcdtyjvВот замените вы HashMap на ArrayMap, сэкономите метров 100, а работать все станет медленнее - переживете?
Заменил. Медленнее не стало. Но и меньше есть не стало. Ровно столько же.Значит вы не туда смотрите, так как ArrayMap - это теоретический миеимум того, что можно выжать по памяти.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 23:12
    #38596436
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
cdtyjvZyK_BotaNпропущено...

Заменил. Медленнее не стало. Но и меньше есть не стало. Ровно столько же.Значит вы не туда смотрите, так как ArrayMap - это теоретический миеимум того, что можно выжать по памяти.
Возможно. Но профайлер показывает, что 35% занимает "не полезная" нагрузка мапов с сетами, т.е. без учета веса самих элементов.
остальное занимают строки.
А по поводу строк, есть что сказать?
Есть более оптимальные реализации?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.03.2014, 23:22
    #38596441
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оптимальные раелизации Set и Map по памяти
Жук. Экономия оперативки никогда к особому успеху не приводила. Может
не будешь нас троллить структурами данных а расколешся на реальную
постановку. Ато были у нас тут всякие стебельки с мясом... Бывалы-ча дескыть
бывалы-ча...

А мы тебе просто dbms присоветуем. Хорошую. С малой латентностью
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Java [игнор отключен] [закрыт для гостей] / Оптимальные раелизации Set и Map по памяти / 25 сообщений из 55, страница 1 из 3
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 442ms
Закрыть
start [/forum/topic.php?fid=59&mobile=1&tid=2127432]:
 0ms
get settings:
 6ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 174ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 39ms
get tp. blocked users:
 1ms
others: 191ms
total:  442ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]