TreeSet: количество элементов меньше эффективного значения

Question

Мне нужен способ вычисления числа элементов меньше X в TreeSet целых чисел очень быстро.

я могу использовать

• подмножество()
• ШЛЕМОФОНА()
• постав хвоста()

методу, но они очень медленно (я просто нужно количество, а не номера самих). Есть ли способ?

спасибо.

---

EDIT:

Я нашел обходной путь, который делает вещи намного быстрее! Я использую BitSet и его метод cardinality(). Сначала я создаю BitSet, и для каждого элемента, добавленного в TreeSet, я устанавливаю соответствующий индекс в BitSet. Теперь, чтобы подсчитать количество элементов меньше, чем использование XI:

bitset.get (0, X + 1) .cardinality()

Это намного быстрее по сравнению с treeset.subSet (0, правда, X , true) .size().

Кто-нибудь знает почему? Я предполагаю, что BitSet.cardinality() не использует линейный поиск.

Answer 1

Если вы не обновляете структуру данных, просто сохраните количество элементов меньше X в хэш-карте!

Если вы обновите его не часто, сохраните отсортированный список номеров. В insert/remove добавьте/удалите из списка в O (1) и обновите hashmap (O (n)).

Вы можете получить O (Log (n)) get и O (Log (n)), используя (отсортированное) двоичное дерево. В каждом элементе дерева также сохраняйте число его потомков. Теперь, чтобы получить # items <, чем y, вы найдете его в двоичном дереве, но также суммируете количество элементов, когда вы идете прямо, а не слева. При обновлении вам также необходимо обновить предки нового элемента.

Кстати, если вы готовы принять приблизительные ответы, могут быть и более быстрые способы.

Answer 2

package ArrayListTrial; 

import java.util.Scanner; 

public class countArray { 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 

     int[] array = new int[100]; 
     Scanner scan = new Scanner(System.in); 
     System.out.println("input the number you want to compare:"); 
     int in = scan.nextInt(); 
     int count = 0; 
     System.out.println("The following is array elements:"); 
     for(int k=0 ; k<array.length ; k++) 
     { 
      array[k] = k+1; 
      System.out.print(array[k] + " "); 
      if(array[k] > in) 
      { 
       count++; 
      } 
     } 
     System.out.printf("\nThere are %d numbers in the array bigger than %d.\n" , count , in); 

    } 

} 

Answer 3

Как быстро «действительно быстро» должно быть? Примерно, сколько у вас элементов?

subSet()/headSet()/tailSet() являются O (1), потому что они возвращают вид оригинального TreeSet, но если вы size() ваш subSet() вы все еще перебирает все оригинальные элементы, следовательно, O (N).

Вы используете Java 8? Это будет примерно одинаково, но вы можете сравнить затраты.

Set<Integer> set = new TreeSet<>(); 
// .. add things to set 

long count = set.parallelstream().filter(e -> e < x).count(); 

---

NB EDIT

С дальнейшей разведки и тестирования я не могу обосновать утверждение «если вы size() ваш subSet() вы все еще перебирает все оригинальные элементы». Я был неправ. parallelstream().count() на этом 4-ядерном компьютере было ~ 30% медленнее, чем subSet().size()

Answer 4

Поскольку все ответы до сих пор указывают на структуры данных, отличные от Java TreeSet, я бы предложил дерево Fenwick, которое имеет O (log (N)) для обновлений и запросов; см. link для реализации Java.