LINUX.ORG.RU

Java datastructures

 , ,


1

0

Интересно, почему в java нет такой очевидной и часто нужной структуры данных как упорядоченная коллекция ключ-значение с поддержкой дубликатов ключей.

Или оно все же есть в стандартной библиотеке, а я ее не заметил?

★★★★

class Pair<A, B> {
    public final A first;
    public final B second;

    public Pair(A first, B second){
        this.first = first;
        this.second = second;
    }
}

//List<Pair> ...

Тебе вот это надо или что?

Не очень понимаю для чего такая структура нужна, но попробуй поковырять апач коммон, там у них чего только нет, может и такой изврат найдётся.

ya-betmen ★★★★★
()
Последнее исправление: ya-betmen (всего исправлений: 1)
Ответ на: комментарий от ya-betmen

и где тут упорядоченная коллекция key-value с поддержкой дубликатов ключей?

А нужна много для чего. Например, для анализа данных.

unt1tled ★★★★
() автор топика
Последнее исправление: unt1tled (всего исправлений: 2)
Ответ на: комментарий от unt1tled

Тут пока только key-value.

class Pair<A, B> implements Comparable<Pair> {
    public final A first;
    public final B second;

    public Pair(A first, B second){
        this.first = first;
        this.second = second;
    }

    int compareTo(Pair o){
        //...
    }

}

Вот так будет упорядоченная.

PriorityQueue q

Вот так будет упорядоченная коллекция.

У самого рук что ль нету?

ya-betmen ★★★★★
()

Я вкурсе, что в сторонних библиотеках есть, поэтому и выделил болдом (запилите нормальный болд!) стандартную.

unt1tled ★★★★
() автор топика
Ответ на: комментарий от sad_but_true1

В чем смысл дубликатов ключей?

Например, есть у тебя пары имя-возраст и надо считать и отсортировать по возрасту. Логично сделать key возраст. И фишка в том, что людям бывает одинаково лет.

Обычный датамайнинг, а жаба так нелепо сливает.

unt1tled ★★★★
() автор топика

Еще прикол: чтобы отсортировать мапу (или даже LinkedHashMap), надо создавать отдельную мапу, тоесть дублировать память. Адъ. Про in place сортировку они не слышали?

unt1tled ★★★★
() автор топика
Ответ на: комментарий от unt1tled

И как это не укладывается в мапу в духе Map<int, Collection<String>>?
Делаешь ключом возраст, а по этому ключу в коллекцию суешь имена.

sad_but_true1
()
Ответ на: комментарий от sad_but_true1

слово «упорядоченная» понятно?

Да и свой класс я и сам могу написать. Но какого хрена такого нет в стандартной либе.

unt1tled ★★★★
() автор топика
Последнее исправление: unt1tled (всего исправлений: 1)
Ответ на: комментарий от unt1tled

Тогда std::multimap

multimap containers are generally slower than unordered_multimap containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.

motto
()
Ответ на: комментарий от motto

У PriorityQueue поиск/удаление линейные, у multimap — логарифмические.

это не говоря о том, что PriorityQueue нифига не мапа

unt1tled ★★★★
() автор топика
Ответ на: комментарий от unt1tled

Это вторая половина вопроса, которую решает что-нибудь, реализующее интерфейс SortedMap, например TreeMap. В итоге твою задачу можно уложить в Map<Integer, Collection<String>> = new TreeMap<Integer, Collection<String>>().

sad_but_true1
()
Ответ на: комментарий от sad_but_true1
Map<Integer, Collection<String>> hm = new TreeMap<Integer, Collection<String>>();
hm.put(1, "raz");
hm.put(1, "dva");
hm.put(1, "tri");

Угадай, что будет?

Еще раз: свое поделие я сам могу запилить, возмущает отсутствие такой структуры в стандартной либе.

unt1tled ★★★★
() автор топика
Последнее исправление: unt1tled (всего исправлений: 1)
Ответ на: комментарий от unt1tled

пары имя-возраст

map

И фишка в том, что людям бывает одинаково лет.

Логично сделать key возраст.

Не пойму логики.

Deleted
()
Ответ на: комментарий от unt1tled

Инициализацию коллекций забыл + пытаешься на место коллекции всунуть строку. Попробуй тоньше.

И чем тут не стандартная библиотека? Никакого написания своей реализации, просто комбинирование стандартных контейнеров.

sad_but_true1
()
Последнее исправление: sad_but_true1 (всего исправлений: 1)
Ответ на: комментарий от sad_but_true1

Инициализацию коллекций забыл + пытаешься на место коллекции всунуть строку.

там все равно что будет, тримапа не поддерживает дубликаты ключей и запишет последнюю коллекцию в 1

unt1tled ★★★★
() автор топика
Ответ на: комментарий от unt1tled

Перестань упарываться, вот правильно использовать:

Map<Integer, Collection<String>> hm = new TreeMap<Integer, Collection<String>>();
        if (!hm.containsKey(2))
        {
            hm.put(2, new PriorityQueue<String>());
        }
        hm.get(2).add("raz");
        hm.get(2).add("dva");
        hm.get(2).add("tri");
        if (!hm.containsKey(1))
        {
            hm.put(1, new PriorityQueue<String>());
        }
        hm.get(1).add("raz");
        hm.get(1).add("dva");
        hm.get(1).add("tri");

        for (Map.Entry<Integer, Collection<String>> entry : hm.entrySet())
        {
            System.out.println(entry.getKey());
            for (String string : entry.getValue())
            {
                System.out.println(string);
            }
        }

Такая хрень и по возрасту отсортирует, и по имени внутри возрастов.

sad_but_true1
()
Ответ на: комментарий от sad_but_true1

containsKey(2)

кулстори, бро =\

hm.get(2).add(

это и называется пилить свою реализацию и по хорошему это все придется заворачивать в свой класс

unt1tled ★★★★
() автор топика
Последнее исправление: unt1tled (всего исправлений: 1)
Ответ на: комментарий от unt1tled

кулстори, бро =\

В чем проблема? Инициализировать коллекцию как предлагаешь?) Если сразу делать put, как ты писал выше, то это вообще бред, потому что пытаешься положить String вместо Collection<String>, а не в неё.

это и называется пилить свою реализацию и по хорошему это все придется заворачивать в свой класс

Один простой метод на добавление это так сложно.

sad_but_true1
()
Последнее исправление: sad_but_true1 (всего исправлений: 2)
Ответ на: комментарий от sad_but_true1

Да забудь ты про синтаксис. То, что ты тут наваял просто так в код не вставишь. Придется запиливать реализацию.

unt1tled ★★★★
() автор топика
Ответ на: комментарий от unt1tled

Пример уровня /b, чего ты ожидал на ЛОРе? Пишешь коротенький метод, проверяющий есть ли ключ и складывающий по этому ключу значение, что не так? Из стандартных контейнеров можно смастерить практически любой велосипед. А ты хочешь чтоб реализации конкретных велосипедов была в стандартной библиотеке.

sad_but_true1
()
Ответ на: комментарий от TERRANZ

структура ключ-значение ну никак-никак не может быть использована для сортировки повторяющихся данных в которых есть ключ и значение?

unt1tled ★★★★
() автор топика
Ответ на: комментарий от sad_but_true1

в плюсах же есть и вообще это очень тривиально чтобы писать каждый раз самому, чай не сишка

unt1tled ★★★★
() автор топика
Ответ на: комментарий от unt1tled

товарищ, если вам не нравится джава, просто не пишите на ней. пишите например на плюсах. не вижу проблемы

rusich
()
Ответ на: комментарий от sad_but_true1

Один простой метод на добавление это так сложно.

в своей реализации, кстати, одним простым методом не отделаешься, придется делать генерик + прочая головная боль на обработку ошибок и иже с ним

unt1tled ★★★★
() автор топика
Ответ на: комментарий от unt1tled

как тебе уже выше написали, используй мапу ключ -> коллекция, иначе нарушается строгое соответствие значения ключу, либо тебе не нужна мапа, используй просто списки

TERRANZ ★★★★
()
Ответ на: комментарий от unt1tled

В плюсах много чего веселого есть.
Пиши в оракл, требуй включить свой конкретный велосипед под конкретную задачу в стандартную библиотеку.

Btw, multimap вообще не очень соответствует идее key-value структуры (один ключ == одно значение). Вариант того, что ты хочешь в рамках этой идеи есть в виде моего предложения и ссылки на SO.

sad_but_true1
()
Ответ на: комментарий от unt1tled

Например, есть у тебя пары имя-возраст и надо считать и отсортировать по возрасту. Логично сделать key возраст. И фишка в том, что людям бывает одинаково лет.

Обычный датамайнинг

Логично для этого использовать кучу (т.е. PriorityQueue) или вектор любых удобных контейнеров. multimap, допустим, тебе сделают через дерево, но при частых вырезках по ключам дерево может давать большой оверхед.

mashina ★★★★★
()
Ответ на: комментарий от Gorthauer

Такую хрень можно обернуть. Зато без написания своих реализаций и сторонних библиотек, как ТС и хотел.

sad_but_true1
()
Ответ на: комментарий от mashina

А в чем профит от кучи? Я что-то не пойму. И что такое «вырезка по ключам»?

cdshines ★★★★★
()
Ответ на: комментарий от unt1tled

Например, есть у тебя пары имя-возраст и надо считать и отсортировать по возрасту.
Логично сделать key возраст

Нет не логично. Делаешь компаратор по возрасту и Collections.sort. Откуда берётся желание сделать всё через зад?

ya-betmen ★★★★★
()
Ответ на: комментарий от ya-betmen

И так каждый раз? Вот почему и говорят, что джава тормозная. Алгоритмической сложностью тут явно не особо заморачиваются. Хотя бы set взяли в качестве хранилки значений.

Gorthauer ★★★★★
()
Ответ на: комментарий от unt1tled

Логично сделать key возраст

Не в обиду, но ни разу ничего логичного здесь нет.

bytecode ★★
()
Ответ на: комментарий от ya-betmen

Ключу соответствует несколько значений, они должны быть упорядочены, подозреваю, что вставка в этот массив должна быть за log n, а не за n log n.

Gorthauer ★★★★★
()
Ответ на: комментарий от unt1tled

Я вкурсе, что в сторонних библиотеках есть, поэтому и выделил болдом (запилите нормальный болд!) стандартную

А зачем всё должно быть в стандартных? Чтобы установщик разбух с 80Мб до 800Мб? Для этого?

Karapuz ★★★★★
()
Ответ на: комментарий от Deleted

почему в java нет 100500 структур данных на все наркоманские случаи?

Угу, вот-вот. А еще она не может java с утра заваривать и приносить в постель. А лучше бы умела. Стандартно

Karapuz ★★★★★
()
Ответ на: комментарий от cdshines

Ты что, новый анонімус? Файл уже оптимизировал? Скоро будешь круг рисовать!

Рождение нового мема?

Karapuz ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.