Я конечно не уверен что смотрю верные данные и правильно понимаю таблицу,
но если посмотреть число убитых гражданских НЕ от криминала и НЕ от самодельных взрыв устройств:
Category NOT EQUAL TO 'IED Explosion' AND Type NOT EQUAL TO 'Criminal Event'; aggregate SUM(Civilian kia)
то получается 12,779
как и «IED EXPLOSION» — что есть самодельное взрывное устройство.
Как трактовать Murder, я не знаю, но по этим двум пунктам самое большое количество гражданских.
В общем, карту очень хорошо использовать в агит целях, если не смотреть на причины смертей.
В общем случае — да, утечка.
В некоторых частных случаях — формально тоже утечка, но с которой можно мериться (малое время до следующей перезаписи — объекты не успеют попасть в old gen, малые объекты/малое количество объектов)
Конкретное решение очень зависит от задачи. В случае задачи на тех интервью — достаточно указать на данную особенность коллекции и сказать для финального решения по выбору (или не выбору данной структуры) не достаточно информации о том как коллекция будет использоваться.
Причем тут завалить?
У каждого решения есть слабые и сильные стороны, и если человек не видит слабых сторон, велик риск использовать решение не эффективно. (и далее можно перейти на тему работы с памятью, дабы выяснить — он просто не заметил эту проблему или есть провал в знаниях)
Спасибо! Ваш вопрос заставил меня задуматься глубже :)
array = new Object[initSize]
компилируется в команду jvm «anewarray» c указанием размера. инициализация массива null'ами — тоже внутри этой операции.
И, честно говоря, я не знаю как оценить данный вызов.
Буду премного благодарен, если кто-нить подскажет куда посмотреть дабы узнать что реально делает эта команда.
Ок, ваш подход понятен.
Я придерживаюсь немного другой точки зрения:
в 95% случаев — средняя оценка реально отражает суть процессов. оставшиеся 5% — отдельный случай (и данные случаи часто хорошо видны) — тут надо анализировать отдельно. Иначе нам грозит оверинжениринг.
Если мы подходим со строго формальной точки зрения — да O всегда описывает худший вариант.
Однако в реальной жизни нас более интересует не худшее время, а среднее. Кормен указывал что его больше интересуют худшие случаи — скорее для строгости дальнейшего повествования — худший случай нам даёт гарантию времени работы алгоритма.
В 90% случаев достаточно оперировать средним случаем, и большинство оценок делается именно для этого среднего случая.
Однако, если нам супер важно теоретически обосновать сложность алгоритма, или область работы такова, что худшие случаи часты — вы правы, HashMap это O(n) а quicksort это O(n^2) :)
Добавление в любом случае это O(1).
а для получения n элементов в бакете — это же нужно целенаправленно стрелять себе в ногу :)
Именно в общем случае будет всё ок, в худшем — да, грубо говоря O(N) — но на то это и худший случай.
Поправьте меня если я где-то ошибся:
Добавление — берём бакет по хэшкоду, добавление в список — везде константа
Поиск — берём бакет по хэшкоду, поиск в бакете фиксированного размера (в общем, не зависит от N) — опять O(1)
Удаление — аналогично поиску
Накидал грубый тест: pastebin.com/zKYxyiSG
Результат:
Map<String, MutableInteger> быстрее ~ на 51%
Работа через массив (выгодно если у нас малое/фиксированное колличество ключей) ~ на 48% быстрее.
В тривиальной имплементации (Map<String, Integer>) проседание по перфомансу естественно есть, видимо из-за боксинга, GC работает моментально.
Имплементация c Mutable работает быстрее всего, но совсем немного опережает имплементацию через массив (грубый пример можно посмотреть в тесте)
lany, с вами согласен — в данном конктертом случае mutableInteger более быстр и вполне себе гуд решение, однако с ним надо аккуратно
я бы остановился на решении с массивом, но это уже для каждой задачи своё.
+ все эти временные Integer будут довольно быстро появляться и умирать в эдене.
У вас есть какие-нить замеры перфоманса на тему Integer vs MutableInteger?
но если посмотреть число убитых гражданских НЕ от криминала и НЕ от самодельных взрыв устройств:
Category NOT EQUAL TO 'IED Explosion' AND Type NOT EQUAL TO 'Criminal Event'; aggregate SUM(Civilian kia)
то получается 12,779
Как трактовать Murder, я не знаю, но по этим двум пунктам самое большое количество гражданских.
В общем, карту очень хорошо использовать в агит целях, если не смотреть на причины смертей.
В некоторых частных случаях — формально тоже утечка, но с которой можно мериться (малое время до следующей перезаписи — объекты не успеют попасть в old gen, малые объекты/малое количество объектов)
Конкретное решение очень зависит от задачи. В случае задачи на тех интервью — достаточно указать на данную особенность коллекции и сказать для финального решения по выбору (или не выбору данной структуры) не достаточно информации о том как коллекция будет использоваться.
У каждого решения есть слабые и сильные стороны, и если человек не видит слабых сторон, велик риск использовать решение не эффективно. (и далее можно перейти на тему работы с памятью, дабы выяснить — он просто не заметил эту проблему или есть провал в знаниях)
компилируется в команду jvm «anewarray» c указанием размера. инициализация массива null'ами — тоже внутри этой операции.
И, честно говоря, я не знаю как оценить данный вызов.
Буду премного благодарен, если кто-нить подскажет куда посмотреть дабы узнать что реально делает эта команда.
Я придерживаюсь немного другой точки зрения:
в 95% случаев — средняя оценка реально отражает суть процессов. оставшиеся 5% — отдельный случай (и данные случаи часто хорошо видны) — тут надо анализировать отдельно. Иначе нам грозит оверинжениринг.
в отличии от способа со счетчиками, мы не держим референсы на «удалённые» объекты.
Однако в реальной жизни нас более интересует не худшее время, а среднее. Кормен указывал что его больше интересуют худшие случаи — скорее для строгости дальнейшего повествования — худший случай нам даёт гарантию времени работы алгоритма.
В 90% случаев достаточно оперировать средним случаем, и большинство оценок делается именно для этого среднего случая.
Однако, если нам супер важно теоретически обосновать сложность алгоритма, или область работы такова, что худшие случаи часты — вы правы, HashMap это O(n) а quicksort это O(n^2) :)
а для получения n элементов в бакете — это же нужно целенаправленно стрелять себе в ногу :)
Именно в общем случае будет всё ок, в худшем — да, грубо говоря O(N) — но на то это и худший случай.
Добавление — берём бакет по хэшкоду, добавление в список — везде константа
Поиск — берём бакет по хэшкоду, поиск в бакете фиксированного размера (в общем, не зависит от N) — опять O(1)
Удаление — аналогично поиску
советую почитать: kjellkod.wordpress.com/2012/08/08/java-galore-linkedlist-vs-arraylist-vs-dynamicintarray/
Целью было не получить точные цифры, а увидеть общую картинку.
«Copyright © Luxoft» — посыпаю голову пеплом, что не почистил файл перед копированием… или вы на что-то намекаете
pastebin.com/zKYxyiSG
Результат:
Map<String, MutableInteger> быстрее ~ на 51%
Работа через массив (выгодно если у нас малое/фиксированное колличество ключей) ~ на 48% быстрее.
В тривиальной имплементации (Map<String, Integer>) проседание по перфомансу естественно есть, видимо из-за боксинга, GC работает моментально.
Имплементация c Mutable работает быстрее всего, но совсем немного опережает имплементацию через массив (грубый пример можно посмотреть в тесте)
lany, с вами согласен — в данном конктертом случае mutableInteger более быстр и вполне себе гуд решение, однако с ним надо аккуратно
я бы остановился на решении с массивом, но это уже для каждой задачи своё.
У вас есть какие-нить замеры перфоманса на тему Integer vs MutableInteger?