Объединение одинаковых элементов в списке - PullRequest
Новая
       15

Объединение одинаковых элементов в списке

1 голос
/ 26 августа 2011

Я видел более раннюю запись , которая пытается сделать что-то подобное в Python.

Вот пример того, что я хочу.Допустим, у меня есть Список. 

public class MyObject {
    private String purchase;
    private Double price;
}

Допустим, что типичный List<MyObject> будет содержать: 

Bike 95.00
Clothes 24.99
Clothes 10.76
Food 6.35
Food 91.46

Я хочу, чтобы все предметы с одинаковой стоимостью покупки были объединеныв один предмет с ценой, суммируемой за этот предмет.Например, одежда - это один предмет с ценой 35,75 (если я правильно сделал сложение).

Я думал о том, как сделать это:

  1. Collections.sortсписок при покупке за O (n log n)
  2. Пройдите по отсортированному списку (это ArrayList, который я использую), поскольку одни и те же элементы будут последовательно и выполнять слияние по 2 элементам одновременно O (n)

Общее время выполнения O (n log n).

Теперь это звучит разумно для меня, однако есть ли библиотека, которая по крайней мере бьет штаны?из моих констант?Я всегда поддерживаю переход на упрощенную версию, если она существует.Так есть ли какие-либо существующие реализации, о которых мне следует подумать об использовании или улучшении моего алгоритма?

РЕДАКТИРОВАТЬ

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

public class MyObject {
   Map bucketOfStuff;
}

На самом деле bucketOfStuff действительно Map<String, Object>, где иногда значением является String, а иногда значением Double (иногда это также может быть Integer, но эй, я могу относиться кэто как двойной).Для всех объектов типа String они будут использоваться для формирования ключа в этой задаче.Итак, если бы у меня было

  • color => Red
  • size => Small
  • texture => Smooth

Тогда я мог бы закодироватьвсе в одну строку, такую ​​как Red,Small,Smooth, потому что я знаю, что запятая не будет символом, присутствующим в любом из значений, поэтому я могу использовать его в качестве разделителя.

Для значения для нашей гипотетической новой карты этобыло бы List, потому что я должен выполнить (математическое) сложение вектора для всех значений bucketOfStuff, которые являются двойными.Таким образом, предлагаемая новая карта будет либо Map<List<String>, List<Double>>, либо просто Map<String, List<Double>>, если я воспользуюсь разделителем, как указано выше.

Еще одна вещь, которая испортила мой мыслительный процесс, заключается в том, что в конце концов коллекция должна быть спискомпройти, чтобы я был в узком смысле, думая, список все время.Таким образом, я должен быть в состоянии восстановить оригинальный объект, который немного вовлечен, но не невозможен.Спасибо всем за помощь и хороший улов.

РЕДАКТИРОВАТЬ

Я должен немного изменить свое описание, потому что я только что напомнил, что я должен сохранить первоначальный порядок List<MyObject>, поэтому мое первоначальное решение было бы неверным в любом случае, так как я делал это.По этой причине я буду продолжать следовать предложенной помощи и использовать LinkedHashMap<String, List<Double>>.Исходя из Java 6 API"Этот связанный список определяет порядок итераций, который обычно является порядком, в котором ключи были вставлены в карту (порядок вставки)".

Ответы [ 3 ]

5 голосов
/ 26 августа 2011

Вопрос, который вы связали, кажется, больше интересует нечеткое сопоставление (две строки, которые «достаточно близки») друг к другу, но из вашего вопроса кажется, что вы просто заинтересованы в объединении одинаковых терминов.

Если это так, вы можете сделать это за O (n) время, используя стандарт HashMap.В частности, ваш алгоритм может работать так:

  1. Построить HashMap от String до Double.
  2. Для каждого элемента в списке:
    1. Если именованный объект не существует в HashMap, вставьте его со значением, равным цене.
    2. Если именованный объект существует в HashMap, обновите значение, добавив взначение, связанное с текущим объектом.
  3. Итерация по HashMap и для каждого элемента создайте новый MyObject из пары ключ / значение.

Шаг 1 занимает O (1) время.Шаг 2 занимает O (n) времени, так как вы выполняете только постоянную работу для каждого элемента.Наконец, шаг 3 снова занимает O (n), потому что вы должны посетить каждый элемент в HashMap ровно один раз.В целом это O (n), которое асимптотически быстрее вашего решения на основе сортировки O (n log n).Я также думаю, что это намного проще для кодирования, так как вам не нужно определять Comparator для вашего типа и вы можете просто использовать стандартные готовые компоненты Java.

Надеюсь, это поможет!

0 голосов
/ 05 января 2017

просьба попытаться сделать это таким образом 

public static ArrayList<EntryData> CompineEntries(EntryData... Entries) {
    ArrayList<EntryData> Compined = new ArrayList();
    for (int i = 0; i < Entries.length; i++) {
        boolean found = false;
        for (int j = 0; j < Compined.size(); j++) {
            if (Entries[i].SubAccountID == Compined.get(j).SubAccountID) {
                Compined.get(j).Value += Entries[i].Value;
                found = true;
            }
        }
        if (!found) {
            Compined.add(Entries[i]);
        }
    }
    return Compined;
}
0 голосов
/ 26 августа 2011

Вы можете легко сделать это в O (n), создав форму карты от String до Double (или double) и пройдя по списку, добавляя к двойному, если purchase уже является ключомили вставка новой записи, если это не так.

...