Считайте случаи объектов в ArrayList

Как уже говорили другие респонденты, если вы твердо намерены хранить свои элементы в неупорядоченном списке ArrayList, то подсчет элементов займет O (n) времени, где n - количество элементов в списке. Здесь, в SO, мы даем советы, но не творим волшебства!

Как я только что намекнул, если в списке ищут больше, чем изменяют, может иметь смысл сохранить его отсортированным. Если ваш список отсортирован, вы можете найти свой элемент за время O (log n), что намного быстрее; и если у вас есть реализация хэш-кода , которая хорошо сочетается с вашим равным , все идентичные элементы будут рядом друг с другом.

Другой возможностью было бы создать и поддерживать две структуры данных параллельно. Вы можете использовать HashMap , содержащий ваши элементы в качестве ключей и их количество в качестве значений. Вы должны будете обновить эту вторую структуру каждый раз, когда ваш список изменится, но поиск по количеству элементов будет o (1).

Я могу ошибаться, но мне кажется, что структура данных, которая вам действительно нужна, может быть Multiset (из google-collections / guava ), а не List . В отличие от Set , он позволяет использовать кратные, но на самом деле не заботится о порядке. Учитывая это, у него есть метод int count (Object element) , который делает именно то, что вы хотите. А поскольку это не список, а реализации, поддерживаемые HashMap , подсчет значительно эффективнее.

Вы можете использовать Collections класс:

public static int frequency(Collection<?> c, Object o)

Возвращает количество элементов в указанной коллекции, равное указанному объекту. Более формально возвращает количество элементов e в коллекции, такое что (o == null? E == null: o.equals (e)).

Если вам нужно много раз подсчитывать вхождения в длинном списке, я предлагаю вам использовать HashMap для хранения счетчиков и обновления их при добавлении новых элементов в список. Это позволит избежать вычисления каких-либо счетчиков ... но, конечно, у вас не будет индексов.

HashMap<Item, Integer> counters = new HashMap<Item, Integer>(5000);
ArrayList<Item> items = new ArrayList<Item>(5000);

void insert(Item newEl)
{
   if (counters.contains(newEl))
     counters.put(newEl, counters.get(newEl)+1);
   else
     counters.put(newEl, 1);

   items.add(newEl);
 }

Последний совет: вы можете использовать другую структуру коллекций (например, Apache Collections ) и использовать структуру данных Bag , которая описывается как

Определяет коллекцию, которая подсчитывает количество раз объект появляется в коллекции.

Итак, именно то, что вам нужно ..

Это легко сделать вручную.

public int countNumberEqual(ArrayList<Item> itemList, Item itemToCheck) {
    int count = 0;
    for (Item i : itemList) {
        if (i.equals(itemToCheck)) {
          count++;
        }
    }
    return count;
}

Имейте в виду, что если вы не переопределите равным в своем классе Item , этот метод будет использовать идентификатор объекта (поскольку это реализация Object.equals () ).

Изменить : Что касается вашего второго вопроса (пожалуйста, попробуйте ограничить количество сообщений одним вопросом за штуку), вы также можете сделать это вручную.

public List<Integer> indices(ArrayList<Item> items, Item itemToCheck) {
    ArrayList<Integer> ret = new ArrayList<Integer>();
    for (int i = 0; i < items.size(); i++) {
        if (items.get(i).equals(itemToCheck)) {
            ret.add(i);
        }
    }
    return ret;
}

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

void insert(Item newEl) 
{ 
   if (counters.contains(newEl)) 
     counters.put(newEl, counters.get(newEl)+1); 
   else 
     counters.put(newEl, 1); 

   items.add(newEl); 
 } 

Спасибо Джеку. Хорошая публикация.

Спасибо,

Бинод Суман

http://binodsuman.blogspot.com