6 / 6 / 0
Регистрация: 17.10.2011
Сообщений: 153
|
||||||
1 | ||||||
Покритикуйте код26.03.2013, 17:31. Показов 751. Ответов 5
Метки нет (Все метки)
Добрый вечер.
Выполнял одно тестовое задание (уже получил отрицательный ответ), буду рад, если скажите все ошибки, а также, как их можно было бы исправить. Задание: Создать свою key-value структуру данных для хранения кэша. Структура данных может хранить только N пар значений, поэтому нужно реализовать удаление какой-нибудь пары при добавлении новой пары, если в структуре данных уже нет места. Один из возможных алгоритмов удаления пары - FIFO. Как я понял, нужно создать нечто похожее на java.util.LinkedHashMap Сам пока нашёл лишь одну ошибку (но очень крутую): операции get и put O(N), а не O(1). Буду рад любым мнениям.
0
|
26.03.2013, 17:31 | |
Ответы с готовыми решениями:
5
Покритикуйте пожалуйста резюме Junior Java Developer Покритикуйте код Покритикуйте код моего сокет сервера для игрового чата Покритикуйте новичка |
26.03.2013, 19:13 | 2 | ||||||||||
посмотрите реализацию HashMap. там структура веселее двух списков и при разборе принципов по которым оно работает вы поймете свои ошибки сами.
из ошибок меня больше всего улыбнуло такое:
1
|
6 / 6 / 0
Регистрация: 17.10.2011
Сообщений: 153
|
||||||
26.03.2013, 20:56 [ТС] | 3 | |||||
AckiyBolt, спасибо за мнение.
1) Да, я изучал классы HashMap и LinkedHashMap. Проблема в том, что для вытеснения старой пары ключ-значение я использовал FIFO. Следовательно, мне нужно было сделать так, чтобы добавляемые пары значений были отсортированы по дате добавления (в HashMap это не реализовано, в LinkedHashMap это реализовано). Можно, конечно, было скопировать весь механизм хранения значений с класса LinkedHashMap, но тогда бы получилось, что я скопировал большую часть класса LinkedHashMap в свой. 2) К сожалению, для реализации интерфейса требуется в реализующем классе использовать такие же сигнатуры методов, что в интерфейсе. В Map методы выглядят так:
mutagen, спасибо за ответ. А как бы вы решили главную проблему (get, put не за О(1)). Делали бы тоже самое, что и в LinkedHashMap?
0
|
26.03.2013, 21:30 | 5 |
да. тут я феерически затупил. извиняюсь
я имел ввиду сам принцип хранения данных, точнее тот самый загадочный Entry. см. entrySet() ок. начнем FixedSizeCache(int capacity) если вы используете ArrayList в качестве хранилища, то в конструкторе принимающем capacity было бы неплохо инициализировать эти листы размером в это самое capacity (возможно даже размером capacity+1, почему - ниже в put) т.к. ArrayList это динамический массив который пересоздается при достижении его лимита (при инициализации по умолчанию он кажется 10) V put(K k, V v) проверку на переполнение лучше сделать после вставки нового элемента (к вопросу о capacity+1). если вы добавите элемент с ключом как в самом первом - вы не получите старое значение entrySet() создавать только лишь для этого метода дефолтную логику мапы - м... скажем так: это странно. было бы логично использовать повсеместно. да, отчасти копирование логики родной джавовской коллекции, но тем не менее оно предельно логично, вам только нужно переписать логику для реализации "конечности" буфера все методы принимающие что-то на вход отсутствие null check (почти везде) и instanceof (мутаген опять опередил) операция get и put O(N), а не O(1) для O(1) вам таки придется слегка передрать реализацию хэш мапы. иначе у вас максимум выйдет O(log(...)) с применением три сета в качестве хранилища ключей
1
|
6 / 6 / 0
Регистрация: 17.10.2011
Сообщений: 153
|
|
26.03.2013, 21:34 [ТС] | 6 |
AckiyBolt, спасибо за отличный ответ!
0
|
26.03.2013, 21:34 | |
26.03.2013, 21:34 | |
Помогаю со студенческими работами здесь
6
Алгоритм: Трамвайные билеты. Покритикуйте Задачи на числа. Решение. Покритикуйте. (часть №1) Задачи на строки и числа. Решение. Покритикуйте Задачи на Servlets и JSPs. Решение. Покритикуйте Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |