Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум на Исходниках.RU > Java > Сортированный список пар значений |
Автор: Rulikkk 16.11.07, 15:33 |
Всем доброго времени суток. Мне нужно сделать сортированный список пар значений <integer, integer>. (сортированный по key. Значение - value) Необходимо, чтобы он был оптимален по времени по след. параметрам: - вставка элемента, а если он есть, то изменение значения. - изменение значения элемента - пробег по последовательным элементам, с доступом к их значениям Какой стандартный класс посоветуете? Предположим, я выбрал класс TreeMap. Вот так я реализовад вставку элемента. Если же такой элемент есть, то суммировал: <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> Integer v = map.put(n,q); if (v != null) { map.put(n,q+v); } Мне не нравится, что я использую два поиска. Как оптимальнее? Вот так я реализовал изменение значения (опять два посика) : <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> Integer v = map.put(nt,q); if (v != null) { map.put(nt,q+v); } как оптимальнее? И наконец так я сделал пробег по последовательным элементам с суммированием их значений. это оптимально? <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> SortedMap<Integer, Integer> sm = map.subMap(nf, nt); int s = 0; for (Map.Entry<Integer, Integer> e : sm.entrySet()) { s+=e.getValue(); } Есть что-то быстрее чем TreeMap? |
Автор: s-e-r-g-e 16.11.07, 20:42 |
про экономию на поиске 2м наеврно с интегером тяжело чего сделать, а вот если класс в котором есть поле интегер, то для случая присутсвующих значений можно его получить и изменить это поле, а если отсутсвует то просто вставить, обязательно использовать Integer? но это вроде не по жаве вопрос получится |
Автор: wind 17.11.07, 14:16 |
Rulikkk, если вашей целью не является увеличение производительности имеещегося решения, то ваши вопросы бессмысленны. Если же вы озадачены именно этим, тогда: Оптимальнее не использовать java.lang.Integer, потому как он immutable. Я бы сделал примерно так: <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> class IntegerHolder { int value; } ... IntegerHolder v = map.put(nt, q); if (v != null) { q.value += v.value; } Вроде нет, но следует учесть, что для небольших наборов данных HashMap по-идее должен работать шустрее. Тут уже вам решать, что важнее - сортировка или быстрая выборка/вставка. Я бы отставил сортировку на тот момент, когда она нужна. Кстати, есть очень интересное решение для вас - коллекции Trove for Java, а именно gnu.trove.TIntObjectHashMap. |
Автор: Rulikkk 17.11.07, 15:35 |
wind, спасибо большое. Цель - именно ускорение. Размер дерева -- примерно 50.000 элементов. Спасибо, было познавательно. |