Пиковое значение числа явлений в массиве целых чисел

Question

В Java мне нужен алгоритм для поиска max. количество вхождений в наборе целых чисел. Например, если мой набор равен [2,4,3,2,2,1,4,2,2], алгоритм должен выводить 5, потому что 2 является главным образом встречающимся целым числом и появляется 5 раз. Подумайте, как найти пик гистограммы набора целых чисел.

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

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

Answer 1

Я бы цикл по коллекции вставки в картах с структурой данные следующей логикой:

• Если число еще не было включено в карту, а затем вставить ключ = целое число, значение = 1.
• Если ключ существует, увеличьте значение.

Есть две карты в Java можно использовать - HashMap и TreeMap - это сравниваются ниже:

HashMap против TreeMap

Вы можете пропустить подробное объяснение прыжок прямо к просмотр если желаете.

HashMap - это карта, в которой хранятся пары ключ-значение в массиве.Индекс, используемый для ключа к является:

• h.hashCode()% map.size()

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

Поскольку HashMap получает больше записей, вероятность этих столкновений возрастает, а эффективность структуры уменьшается. Чтобы решить эту проблему, когда число записей достигает критической точки (определяемый loadFactor аргумента в конструктор), структура изменяется:

• Новый массив выделяется примерно в два раза текущего размера
• A цикл выполняется по всем существующим ключей
  • расположение ключа пересчитывается для нового массива
  • пара ключ-значение вставляется в новую структуру

Как вы можете видеть, это может стать относительно дорогостоящим, если есть много размеров.

Эта проблема может быть решена, если вы можете предварительно выделить HashMap в соответствующем размере до начала, например map = new HashMap (input.size() * 1.5). Для больших наборов данных это может значительно уменьшить износ памяти.

Поскольку ключи по существу беспорядочно расположены в HashMap, итератор ключа будет перебирать их в случайном порядке. Java предоставляет ссылку LinkedHashMap, которая будет итератором в том порядке, в котором были вставлены ключи.

Performance для HashMap:

• Учитывая правильный размер и хорошее распределение хэш, поиск является постоянная временем.
• С плохим распределением производительность падает до (в худшем случае) линейного поиска - O (n).
• С плохой начальной калибровкой производительность становится переделкой. Я не могу тривиально вычислить это, но это не хорошо.

OTOH TreeMap хранит записи в сбалансированном дереве - добавляется динамическая структура, которая постепенно увеличивается, поскольку пары ключ-значение добавляются. Вставка зависит от глубины дерева (log (tree.size()), но предсказуема - в отличие от HashMap, нет перерывов и нет краевых условий, при которых производительность падает.

Каждая вставка и поиск дороже с учетом хорошо распределенной HashMap.

Кроме того, чтобы вставить ключ в дерево, каждый ключ должен быть сопоставим с любым другим ключом, требующим метода k.compare (другого) из интерфейса Comparable. вопрос о целых числах, это не проблема.

Производительность на TreeMap:

• Вставка из п элементов О (п § п)
• просмотра является O (журнал N)

Резюме

Первый мысли: Размер данных:

• Если маленький (даже в 1000-х и 10 000-х годах) действительно не имеет значения на каком-либо современном оборудовании
• Если большой, чтобы привести к тому, что машина исчерпала память, тогда TreeMap может быть единственным вариантом
• в противном случае, размер, вероятно, не является определяющим фактором

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

• Если мало, то общее время будет доминировать поиска ключей в небольшого набора, поэтому оптимизация не имеет никакого значения (вы можете остановиться здесь).
• Если большой, то общее время будет доминировать вставки, и решение лежит на нескольких факторов:
  • Dataset является известного размера?
    • Если да: HashMap может быть предварительно выделен, и поэтому отбраковка памяти будет устранена. Это особенно важно, если метод хэш-код() дорого (не в нашем случае)
    • Если нет: A TreeMap обеспечивает более предсказуемую производительность и может быть лучшим выбором
  • предсказуема производительность без больших киосков требуется , например, в системах реального времени или в потоке событий графического интерфейса?
    • Если да: A TreeMap обеспечивает гораздо лучшую предсказуемость без каких-либо киосков
    • Если нет: HashMap лучше, вероятно, обеспечивает лучшую производительность для всего вычисления

Один последний момент, если не является ошеломляющей точкой сверху:

• Является ли отсортированный список ключей?
  • Если да (например, для печати гистограмму): A TreeMap уже отсортирован ключи, и поэтому удобно

Однако, если производительность важна, единственный способ решить бы чтобы реализовать интерфейс карты, затем профиль и HashMap и TreeMap, чтобы увидеть, что на самом деле лучше в вашей ситуации. Premature optimization - корень большого зла :)

Answer 2

Что случилось с сортировкой? Это O (n log n), что неплохо. Любое лучшее решение потребует больше информации о наборах ввода (возможно, верхняя граница на числах) или включает Map<Integer, Integer> или что-то подобное.

Answer 3

1. Основным методом является сортировка коллекции, а затем просто пробежка сортированной коллекции. (Это будет сделано в O (nLog (n) + n), которое является O (nLog (n))).

2. Если числа ограничены (например, -10000,10000), а коллекция содержит много целых чисел, вы можете использовать таблицу поиска и подсчитывать каждый элемент. Это займет O (n + l) (O (n) для count, O (l), чтобы найти элемент max), где l - длина диапазона (в этом случае 20001). Как вы можете видеть, если n >> l, тогда это станет O (n), которое лучше 1, но если n < < l, то это O (l), который является постоянным, но достаточно большим, чтобы сделать это непригодным.

3. Другой вариант предыдущего - использовать HashTable вместо таблицы поиска. Это улучшило бы сложность до O (n), но не гарантировалось бы быстрее, чем 2 при n >> l. Хорошей новостью является то, что значения не обязательно должны быть ограничены.

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

Answer 4

Вот пример реализации вашей программы. Он возвращает значение no с большей частотой, и если два nos найдены с максимальными вхождениями, то возвращается больше no. Если u хочет вернуть частоту, то измените последнюю строку кода на «return mf».

{public int mode(int[]a,int n) 
    {int i,j,f,mf=0,mv=a[0]; 
    for(i=0;i<n;i++) 
     {f=0; 
     for(j=0;j<n;j++) 
      {if(a[i]==a[j]) 
       {f++; 
       } 
      } 
     if(f>mf||f==mf && a[i]>mv) 
      {mf=f; 
      mv=a[i]; 
      } 
     } 
    return mv;   
    } 

}

Answer 5

Этот маленький щенок работает (отредактирован, чтобы вернуть частоту вместо числа):

public static int mostFrequent(int[] numbers) { 
    Map<Integer, AtomicInteger> map = new HashMap<Integer, AtomicInteger>() { 
     public AtomicInteger get(Object key) { 
      AtomicInteger value = super.get(key); 
      if (value == null) { 
       value = new AtomicInteger(); 
       super.put((Integer) key, value); 
      } 
      return value; 
     } 

    }; 

    for (int number : numbers) 
     map.get(number).incrementAndGet(); 

    List<Entry<Integer, AtomicInteger>> entries = new ArrayList<Map.Entry<Integer, AtomicInteger>>(map.entrySet()); 
    Collections.sort(entries, new Comparator<Entry<Integer, AtomicInteger>>() { 
     @Override 
     public int compare(Entry<Integer, AtomicInteger> o1, Entry<Integer, AtomicInteger> o2) { 
      return o2.getValue().get() - o1.getValue().get(); 
     } 
    }); 

    return entries.get(0).getValue().get(); // return the largest *frequency* 

    // Use this next line instead to return the most frequent *number* 
    // return entries.get(0).getKey(); 
} 

AtomicInteger был выбран, чтобы избежать создания новых объектов с каждым приращением, а код читает немного чище.

анонимный класс карта была использована для централизации «если нуль» код

Вот тест:

public static void main(String[] args) { 
    System.out.println(mostFrequent(new int[] { 2, 4, 3, 2, 2, 1, 4, 2, 2 })); 
} 

Выход:

5 

Answer 6

Поскольку это набор целых чисел, один могут использоваться либо

1. для сортировки коллекции, которая принимает O (nb), где b - количество битов, используемых для представления целых чисел (32 или 64, если вы используете примитивные целочисленные типы данных java) или
2. сравнение на основе сортировки (quicksort, сортировка слияния и т. д.) и принимает O (n log n).

Примечания:

• Чем больше ваш п, тем более вероятно, что-то радикс будет быстрее, чем всякие сравнения на основе. Для меньшего n вы, вероятно, лучше со сравнительной сортировкой.
• Если вы знаете привязку к значениям в коллекции, b будет даже меньше 32 (или 64), что делает сортировку radix более желательной.