Что означает термин аллокация (новый объект, память)?
Я набрал в Google запрос «java аллокация» и получил целую кучу русскоязычных статей, из которых легко понять значение этого термина.
6 авг 2018 в 13:21
Сразу видно, что не кодил в сях, там то уж сразу видишь функцию alloc() и сразу понимаешь о чем идет речь 🙂
6 авг 2018 в 19:48
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Означает выделение блока памяти, чаще всего в куче.
Отслеживать
ответ дан 6 авг 2018 в 12:47
Sergey Gornostaev Sergey Gornostaev
66.5k 6 6 золотых знаков 53 53 серебряных знака 112 112 бронзовых знаков
Калька с английского allocation — распределение. Смысл дословный. Управлять памятью, распределять ее и т.п.
Отслеживать
ответ дан 6 авг 2018 в 12:38
Serhii Dikobrazko Serhii Dikobrazko
1,762 1 1 золотой знак 9 9 серебряных знаков 15 15 бронзовых знаков
- java
- терминология
-
Важное на Мете
Похожие
Подписаться на ленту
Лента вопроса
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
Дизайн сайта / логотип © 2024 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2024.1.3.2953
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Время аллокации.
Никогда не задумывался над этим вопросом. Вроде считается, что это что-то такое, непредсказуемое.
Классическая реализация со связным списком свободных участков — в чистом виде есть отстой, ибо делает перебор в поисках свободного блока нужного размера, давая O(N). Впрочем, для объектов одного размера она всегда может спокойно выдавать первый же блок без проблем. Также для случая, когда объекты создаются в обратном порядке, чем создаются, число блоков всегда будет равно 1, и тут тоже эта реализация не даёт переголовы.
Но нетрудно же придумать, как вместо O(N) сделать O(logN) (при условии, что свободный блок существует и аллокатору не придётся просить дополнительную память у оси)
Вот мне интересно — стандартный аллокатор, реализованный в известных средах — он насколько оптимизирован именно в алгоритмическом смысле? Гарантия логарифма есть (при условии что память не закончилась)?
- Guppy the Cat
- Постоялец
#1
18:41, 4 дек 2014
- 1 frag / 2 deaths
- Участник
#2
18:42, 4 дек 2014
Guppy the Cat
На русском есть?
#3
18:46, 4 дек 2014
Guppy the Cat
на украинском есть?
#4
22:31, 4 дек 2014
Guppy the Cat
Без смс и регистрации есть?
#5
22:36, 4 дек 2014
Guppy the Cat
Аудиокнига есть?
- 1 frag / 2 deaths
- Участник
#6
22:38, 4 дек 2014
да задрали ржать
чё, никто не знает?
от инглиша у меня мозг закипит после первого же абзаца, при этом я даже не смогу врубиться в написанное
- return []()<>;
- Участник
#7
22:54, 4 дек 2014
TarasB
Это печально
#8
23:19, 4 дек 2014
Там по-моему вообще не о том статья. Она о тестировании алгоритмов выделения когда у нас несколько процессоров и много потоков. И говорится что асимптотика в худшем случае (для разных алгоритмов по разному, типа если чередуем большие и мелкие куски и т.д.) O(NA), где NA — число аллокаций. Т.е. каждую аллокацию они считают за О(1).
Это все на пятой странице, остальное не читал.
- 1 frag / 2 deaths
- Участник
#9
23:41, 4 дек 2014
kipar
> Т.е. каждую аллокацию они считают за О(1).
фига как вышло?
и если это амортизированная то это немного не то
#10
0:28, 5 дек 2014
TarasB
хм. вообще видимо получается что O(NA) — это для одной аллокации.
Ну т.е. в вольном переводе,
для первого алгоритма:
Для Хоарда, выделение кусков меньше 256 байт выполняется константное время, т.к. оно берет память из «кеша потока», организованного как массив. Если в кеше потока недостаточно памяти, выполняется последовательный поиск в массиве групп пустоты в локальной куче. Если запрос все еще не удалось выполнить — проводится еще один поиск в глобальной куче, которая тоже организована как массив групп пустоты. Поиск в «группе пустот» (emptiness group) занимает константное время, т.к. размер массива фиксирован. Таким образом, теоретическое время исполнения Хоарда — O(NA)
Для второго алгоритма:
Jemalloc разделяет аллокации на три класса (small, large, huge), которые обрабатываются по-разному. Маленькие (4 bytes to 4 kilobytes) выполняются с помощью кеша потока, за константное время. Время исполнения больших (4 kilobytes to 4 megabytes) связано с красно-черными деревьями, высота которых зависит от числа деаллокаций. В худшем случае будет NA деаллокаций а высота дерева пропорционально log (NA). Если все запросы аллокаций большие, время исполнения O(log NA), но если число маленьких запросов аллокаций больше числа больших, время будет O(NA). Таким образом, время исполнения Jemalloc’s — O(NA)
В третьем какие-то квадлисты, и в итоге тоже приходят к O(NA).
В четвертом —
Ptmallocv2 содержит два массива — Fast Bin and Normal Bin. Первый используется для запросов меньше 64 байт, которые всегда занимают константное время. Процедура для больших аллокаций(через Normal Bin) похожа на процедуру для маленьких. Худший случай — последовательный поиск который выполняется либо в несортированном списке (первый элемент Normal Bin) либо в сортированных списках Normal Bin (с 65 до 123 (байт?)). Т.к. в худшем случае получаем O(NA), то и для всего алгоритма получаем O(NA).
Особенности про многопоточность я опустил.
—
а, там еще два алгоритма. Но они тоже сводят к худшему случаю и там получается O(NA).
- 1 frag / 2 deaths
- Участник
#11
12:02, 5 дек 2014
kipar
> хм. вообще видимо получается что O(NA) — это для одной аллокации.
Тогда дерьмище. Буду пейсать свой логарифмический лолокатор.
#12
13:45, 5 дек 2014
TarasB
Юзай хештаблицы с О(1)
Бхабха
- 1 frag / 2 deaths
- Участник
#13
13:47, 5 дек 2014
laMer007
аллокатор через хеш-таблицы?
расскажи
- return []()<>;
- Участник
Как работает аллокация памяти?
Разрешено выделить память под некоторое количество переменных, которое не зависит от длины строки. Это вычурный способ запретить вам сделать копию строки, перевернуть ее и сравнить с оригиналом.
Ответ написан более года назад
Нравится 1 8 комментариев
Tylen @Tylen Автор вопроса
Ой спасибо большое, а не подскажете, что можно почитать или может вы объясните,какие действия аллоцируют одну единицу памяти, и что значит одна единица памяти? Один кластер?
Tylen, да просто одна переменная
Один кластер?
что такое, в вашем понимании, кластер?
Tylen @Tylen Автор вопроса
Jacen11, А где можно поподробнее почитать про это, допустим создание функции,тоже аллоцирует одну единицу памяти, хотелось бы узнать как внутри это работает. Не могу найти правильного источника
Tylen, тут задача не про выделение памяти, а про то что бы решить задачу без создания второй палиндромной строки
действия аллоцируют одну единицу памяти
объявление переменной
допустим создание функции,тоже аллоцирует одну единицу памяти
хотелось бы узнать как внутри это работает
конкретно выделение памяти под метод, сложно для вас работает. Это не требуется для джуна. Тут просто имелось ввиду использовать одну переменную
У вас какой то спгс. Все намного проще.
И обычно на собесах просят определить временную сложность, или сложность в определенных алгоритмах. Это можно просто вызубрить https://habr.com/ru/post/188010/ или понять, https://bimlibik.github.io/posts/complexity-of-alg. , или на любом другом сайте https://yandex.ru/search/?text=%D0%92%D1%80%D0%B5%.
Tylen @Tylen Автор вопроса
Jacen11, Спасибо большое за объяснение) Про спгс возможно)
Tylen @Tylen Автор вопроса
Jacen11, Привет, хотел спросить это же получается подходит под условия задачи
a="" if a.lower().replace("!","").replace(" ","").replace(",","") == a.lower().replace("!","").replace(" ","").replace(",","")[::-1]: print("it is palindrom!!") else: print("It is not palindrom")
Армянское Радио @gbg Куратор тега Программирование
Tylen, нет, потому что это как раз то, что вам делать запрещено (копировать строку, а потом переворачивать копию) + дополнительные ненужные действия в виде удаления восклицательный знаков, пробелов и запятых.
Аллокация с помощью make в Go
В языке программирования Go существует встроенная функция make(T, args) . По своему назначению она отличается от функции new(T) и создает лишь срезы, каналы и карты, возвращая инициализированное значение типа T(не *T).
Дело в том, что вышеперечисленные три типа представляют под капотом линки на структуры данных, которые необходимо инициализировать перед применением. К примеру, срез (slice) — это не что иное, как дескриптор из 3-х элементов, который содержит указатель на данные, длину и емкость, а пока эти элементы не станут инициализированными, срез будет равняться nil. При этом для срезов, каналов и карт make инициализирует внутреннюю структуру данных, подготавливая значение для использования.
Функция в вышеприведенном примере аллоцирует массив из 100 int’ов, после чего создает структуру среза длиной 10/вместимостью 100, указывающую на первые десять элементов массива (следует понимать, что при создании среза емкость можно опустить). Тогда как new([] int) , напротив, возвращает указатель на вновь выделенную обнуленную структуру среза, то есть возвращает указатель на значение nil-фрагмента.
Для окончательного понимания разницы между функциями new и make, рассмотрим еще один пример:
Остается отметить, что функция make применяется лишь к картам, каналам и срезам, то есть она не возвращает указатель. Таким образом, если вы хотите получить явный указатель, следует воспользоваться функцией new либо выбрать адрес переменной явно.