Какую структуру данных я могу использовать для сортировки/сравнения объектов по нескольким критериям?

У нас есть коллекция объектов, каждый объект имеет целочисленный идентификатор и отметку времени. Мы хотим иметь возможность искать дубликаты и обновлять коллекцию на основе идентификатора.

Но мы также хотим иметь возможность взять «кусок» коллекции, например, найти каждый объект с отметкой времени после заданного времени. Итак, мы также хотим отсортировать по отметке времени.

Мы используем TreeMap, который на первый взгляд дал нам то, что мы хотели. Но поскольку TreeMap (и все, что происходит от SortedSet) использует только compareTo() и игнорирует метод equals(), мы обнаруживаем, что поиск дубликатов на основе идентификатора не работает. Наш метод compareTo() пытается учесть оба условия (поиск по идентификатору ИЛИ временной метке), но в конечном итоге он большой и уродливый и на самом деле не работает. :)

Эта коллекция может стать очень большой, поэтому, конечно, мы хотим максимально быстрого поиска/сортировки/вставки.


java collections
person Phillip Atkinson    schedule 07.09.2011    source источник
comment
Является ли дубликат объектом, который имеет тот же идентификатор и временную метку, что и другой объект?   -  person Liviu T.    schedule 07.09.2011
comment
Извините, нужно было указать - Объект является дубликатом, если он имеет тот же идентификатор.   -  person Phillip Atkinson    schedule 07.09.2011

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете использовать два TreeMaps, один из которых сопоставляет ID с объектами, а другой сопоставляет временные метки с объектами.

Затем вы можете легко найти объект по его идентификатору или по временной метке. Вы также можете получить набор объектов с отметкой времени в определенном диапазоне (как вы уже знаете).

Недостаток, очевидно, заключается в том, что вы должны удалить объекты из обеих коллекций. Это, однако, не должно быть так уж плохо, поскольку каждый объект знает и свой идентификатор, и свою отметку времени, поэтому, если вы хотите удалить по отметке времени, вы получаете идентификатор бесплатно, и вы просто вынуждены выполнять еще одну операцию журнала.

Оберните их в свою собственную коллекцию, если хотите.

person aioobe    schedule 07.09.2011
comment
Спасибо за предложение! Сейчас мы пытаемся использовать эту идею, но у нас возникли проблемы с настройкой TreeMap, которая использует метку времени в качестве ключа, поскольку уникальность меток времени не гарантируется. Пытался использовать TreeMap, например TreeMap‹Date, List‹Object››, но это очень быстро становится очень уродливым, и мы все еще боремся, чтобы заставить его работать. - person Phillip Atkinson; 07.09.2011
comment
О да. Это может быть проблемой. Если бы я был на вашем месте, я бы уже начал смотреть на общие ресурсы Guava или Apache, если бы я был на вашем месте. Должен быть какой-то TreeMultiMap, который должен соответствовать вашим потребностям. - person aioobe; 07.09.2011
comment
Спасибо, мы собираемся сделать это, используя Apache TreeMultiMap. Мы старались держаться подальше от слишком большого количества сторонних библиотек, но в данном случае это лучше, чем изобретать велосипед. - person Phillip Atkinson; 13.09.2011
comment
@Phillip, держаться подальше от беспорядка сторонних зависимостей - это хороший способ, IMO, Apache Commons или Guava довольно стандартны, однако и, в свою очередь, не требуют ничего, о чем я знаю, поэтому я думаю, что вы делаете правильно здесь . - person aioobe; 13.09.2011