Форум программистов, компьютерный форум, киберфорум
Наши страницы
Java
Войти
Регистрация
Восстановить пароль
 
Hixon10
6 / 6 / 0
Регистрация: 17.10.2011
Сообщений: 153
#1

Покритикуйте код

26.03.2013, 17:31. Просмотров 483. Ответов 5
Метки нет (Все метки)

Добрый вечер.
Выполнял одно тестовое задание (уже получил отрицательный ответ), буду рад, если скажите все ошибки, а также, как их можно было бы исправить.
Задание:
Создать свою key-value структуру данных для хранения кэша. Структура данных может хранить только N пар значений, поэтому нужно реализовать удаление какой-нибудь пары при добавлении новой пары, если в структуре данных уже нет места. Один из возможных алгоритмов удаления пары - FIFO.

Как я понял, нужно создать нечто похожее на java.util.LinkedHashMap

Сам пока нашёл лишь одну ошибку (но очень крутую): операции get и put O(N), а не O(1).

Буду рад любым мнениям.

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
package ru.hixon.cache;
 
import java.util.*;
 
public class FixedSizeCache<K,V> implements Map<K,V> {
 
    private ArrayList<K> keys;
    private ArrayList<V> values;
    private int maxCapacity;
 
    public FixedSizeCache() {
        keys = new ArrayList<>();
        values = new ArrayList<>();
        maxCapacity = -1;
    }
    
    public FixedSizeCache(int capacity) {
        this();
        if (capacity > 0) {
            maxCapacity = capacity;
        } else {
            maxCapacity = 0;
        }
    }
 
    /** Return the number of mappings in this Map. */
    @Override
    public int size() {
        return keys.size();
    }
 
    /** Return true if this map is empty. */
    @Override
    public boolean isEmpty() {
        return size() == 0;
    }
 
    /** Return true if key is contained as a Key in this Map. */
    @Override
    public boolean containsKey(Object key) {
        return keys.contains((K)key);
    }
 
    /** Return true if value is contained as a Value in this Map. */
    @Override
    public boolean containsValue(Object value) {
        return values.contains((V)value);
    }
 
    /** Get the V value corresponding to key k. */
    @Override
    public V get(Object k) {
      int i = keys.indexOf(k);
      if (i == -1) {
        return null;
      }
      return values.get(i);
    }
 
    /** Put the given pair (k, v) into this map, by maintaining "keys"
     * in sorted order.
     */
    @Override
    public V put(K k, V v) {
        if (k == null) {
             throw new NullPointerException();
        }
 
        if (maxCapacity == keys.size() && keys.size() > 0) {
            keys.remove(0);
            values.remove(0);
        }
 
        for (int i=0; i < keys.size(); i++) {
            K old = keys.get(i);
 
            /* Does the key already exist? */
            if (((Comparable)k).compareTo(keys.get(i)) == 0) {
                values.set(i, v);
                return get(old);
            }
        }
 
        // Else it goes at the end.
        int where = keys.size();
        keys.add(where, k);
        values.add(where, v);
        return null;
    }
 
    /** Put all the pairs from oldMap into this map */
    @Override
    public void putAll(Map<? extends K, ? extends V> oldMap) {
        Iterator<? extends K> keysIter = oldMap.keySet().iterator();
        while (keysIter.hasNext()) {
            K k = (K)keysIter.next();
            V v = oldMap.get(k);
            put(k, v);
        }
    }
 
    @Override
    public V remove(Object k) {
        int i = keys.indexOf(k);
        if (i == -1) {
            return null;
        }
        V old = values.get(i);
        keys.remove(i);
        values.remove(i);
        return old;
    }
 
    @Override
    public void clear() {
        keys.clear();
        values.clear();
    }
 
    @Override
    public java.util.Set<K> keySet() {
        return new TreeSet<>(keys);
    }
 
    @Override
    public java.util.Collection<V> values() {
        return values;
    }
 
    /** The Map.Entry objects contained in the Set returned by entrySet().
     */
    private class MyMapEntry<K,V> implements Map.Entry<K,V>, Comparable {
        private K key;
        private V value;
        MyMapEntry(K k, V v) {
            key = k;
            value = v;
        }
        
        @Override
        public K getKey() { 
            return key; 
        }
        
        @Override
        public V getValue() { 
            return value; 
        }
        
        @Override
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
 
        @Override
        public int compareTo(Object o2) {
            if (!(o2 instanceof MyMapEntry)) {
                throw new IllegalArgumentException("Not a MapEntry");
            }
            Object otherKey = ((MyMapEntry<K,V>)o2).getKey();
            return ((Comparable)key).compareTo((Comparable)otherKey);
        }
    }
 
    /** The set of Map.Entry objects returned from entrySet(). */
    private class MyMapSet<MyMapEntry> extends AbstractSet<MyMapEntry> {
        List<MyMapEntry> list;
        MyMapSet(ArrayList<MyMapEntry> al) {
          list = al;
        }
        
        @Override
        public Iterator iterator() {
          return list.iterator();
        }
        
        @Override
        public int size() {
          return list.size();
        }
    }
 
    /** Returns a set view of the mappings contained in this Map.
    * Each element in the returned set is a Map.Entry.
    */
    @Override
    public java.util.Set entrySet() {
        if (keys.size() != values.size()) {
            throw new IllegalStateException("InternalError: keys and values out of sync");
        }
        ArrayList<MyMapEntry<K,V>> al = new ArrayList<>();
        for (int i=0; i<keys.size(); i++) {
            al.add(new MyMapEntry<>(keys.get(i), values.get(i)));
        }
        return new MyMapSet(al);
    }
    
    public static void main(String[] argv) {
        Map<String,String> map = new FixedSizeCache<String,String>(100);
 
        for (int i = 0; i<200; i++) {
            map.put(String.valueOf(i), String.valueOf(i));
        }
 
        for (String key : map.keySet()) {
            System.out.println("Key " + key + "; Value " + (String) map.get(key));
        }
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2013, 17:31
Ответы с готовыми решениями:

Покритикуйте пожалуйста резюме Junior Java Developer
Пожалуйста скажите что стоит поправить. Если кому не сложно скиньте свои резюме...

Покритикуйте код
Всем привет. У меня есть обычный POJO-класс с полями и класс для работы с...

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

Покритикуйте новичка
Доброго всем времени суток! Самоучкой пытаюсь освоить Java, общение с опытными...

Алгоритм: Трамвайные билеты. Покритикуйте
Привет, решение данной задачи на Java. Покритикуйте. package...

5
AckiyBolt
649 / 398 / 35
Регистрация: 19.02.2013
Сообщений: 1,072
Записей в блоге: 2
26.03.2013, 19:13 #2
посмотрите реализацию HashMap. там структура веселее двух списков и при разборе принципов по которым оно работает вы поймете свои ошибки сами.
из ошибок меня больше всего улыбнуло такое:

Java
1
2
3
4
    @Override
    public boolean containsKey(Object key) {
        return keys.contains((K)key);
    }
у вас же используются дженерики, почему бы не написать так:

Java
1
2
3
4
    @Override
    public boolean containsKey(K key) {
        return keys.contains(key);
    }
1
Hixon10
6 / 6 / 0
Регистрация: 17.10.2011
Сообщений: 153
26.03.2013, 20:56  [ТС] #3
AckiyBolt, спасибо за мнение.
1) Да, я изучал классы HashMap и LinkedHashMap. Проблема в том, что для вытеснения старой пары ключ-значение я использовал FIFO. Следовательно, мне нужно было сделать так, чтобы добавляемые пары значений были отсортированы по дате добавления (в HashMap это не реализовано, в LinkedHashMap это реализовано). Можно, конечно, было скопировать весь механизм хранения значений с класса LinkedHashMap, но тогда бы получилось, что я скопировал большую часть класса LinkedHashMap в свой.

2) К сожалению, для реализации интерфейса требуется в реализующем классе использовать такие же сигнатуры методов, что в интерфейсе.
В Map методы выглядят так:
C#
1
2
boolean containsKey(Object key);
boolean containsValue(Object value);
Добавлено через 51 минуту
mutagen, спасибо за ответ. А как бы вы решили главную проблему (get, put не за О(1)). Делали бы тоже самое, что и в LinkedHashMap?
0
mutagen
2565 / 2238 / 257
Регистрация: 14.09.2011
Сообщений: 5,185
Записей в блоге: 18
26.03.2013, 20:58 #4
Цитата Сообщение от AckiyBolt Посмотреть сообщение
посмотрите реализацию HashMap. там структура веселее двух списков и при разборе принципов по которым оно работает вы поймете свои ошибки сами.
из ошибок меня больше всего улыбнуло такое:

Java
1
2
3
4
    @Override
    public boolean containsKey(Object key) {
        return keys.contains((K)key);
    }
у вас же используются дженерики, почему бы не написать так:

Java
1
2
3
4
    @Override
    public boolean containsKey(K key) {
        return keys.contains(key);
    }
тут проблема глубже, надо для начала проверить класс K и класс key на соответствие и если нет то сразу вернуть false иначе так можно нарваться на каст эксепшен
0
AckiyBolt
649 / 398 / 35
Регистрация: 19.02.2013
Сообщений: 1,072
Записей в блоге: 2
26.03.2013, 21:30 #5
Цитата Сообщение от Hixon10 Посмотреть сообщение
2) К сожалению, для реализации интерфейса требуется в реализующем классе использовать такие же сигнатуры методов, что в интерфейсе.
В Map методы выглядят так:
C#
1
2
boolean containsKey(Object key);
boolean containsValue(Object value);
да. тут я феерически затупил. извиняюсь

Цитата Сообщение от Hixon10 Посмотреть сообщение
1) Да, я изучал классы HashMap и LinkedHashMap. Проблема в том, что для вытеснения старой пары ключ-значение я использовал FIFO. Следовательно, мне нужно было сделать так, чтобы добавляемые пары значений были отсортированы по дате добавления (в HashMap это не реализовано, в LinkedHashMap это реализовано). Можно, конечно, было скопировать весь механизм хранения значений с класса LinkedHashMap, но тогда бы получилось, что я скопировал большую часть класса LinkedHashMap в свой.
я имел ввиду сам принцип хранения данных, точнее тот самый загадочный 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
Hixon10
6 / 6 / 0
Регистрация: 17.10.2011
Сообщений: 153
26.03.2013, 21:34  [ТС] #6
AckiyBolt, спасибо за отличный ответ!
0
26.03.2013, 21:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.03.2013, 21:34

Задачи на числа. Решение. Покритикуйте. (часть №1)
Привет, решение данных заданий на Java - ниже. Покритикуйте. package...

Задачи на строки и числа. Решение. Покритикуйте
Задачи: Привет, решение данных заданий на Java - см. ссылку ниже....

Покритикуйте код
Код использует Direct2D и WIC, и преобразует изображение (поворот,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru