2015-12-23 10 views
3

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

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

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

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

спасибо.


EDIT:

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

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

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

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

+0

Вы можете попробовать Guava 'TreeMultiset', который поддерживает' headMultiset (element) .size() 'в O (log n), а не O (n). Однако это не то же самое, что и «TreeSet». Но 'headMultiset (element) .elementSet(). Size()' также будет O (log n). –

+0

Зачем вам нужно дерево? Вы часто обновляете структуру данных? Если вы не обновляете структуру данных, просто сохраните количество элементов меньше X в хэш-карте! Если вы обновляете его не часто, сохраните отсортированный список номеров. В insert/remove добавьте/удалите из списка в O (1) и обновите hashmap (O (n)). –

+0

Спасибо за ваш комментарий @Masood_mj. Проблема в том, что X не является конкретным значением, оно изменяется каждый раз, когда я вызываю функцию cardinality(). Поэтому, если я хочу использовать hashmap, тогда я должен обновлять все элементы с помощью ключа> Y каждый раз, когда я добавляю или удаляю Y в хэш-карту (+1 или -1 все). Я что-то упускаю? – mnmp

ответ

1

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

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

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

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

-1
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); 

    } 

} 
+0

Прочитайте вопрос, прежде чем отвечать. – EJP

+0

Возможно, это ответ на другой вопрос? – KarlM

+0

Это не ответ на любой вопрос. Искаженный массив полон нулей. Поэтому счетчик для любого конкретного значения известен заранее: поиск не требуется. @KarlM – EJP

2

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

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()

+0

Спасибо! У меня есть сто тысяч элементов! Я не знал о count(), я думал, что использование subSet - проблема. – mnmp

+0

Как вы утверждаете, что метод subview 'count()', или, вернее, я предполагаю, что вы имеете в виду метод size(), выполняет итерацию всей исходной коллекции? – EJP

+0

Спасибо за вопрос. Я видел ответы вроде http://stackoverflow.com/questions/15703120/unexpected-complexity-of-common-methods-size-in-java-collections-framework и http://stackoverflow.com/questions/14290751/time -complexity-of-treemap-operations-subap-headmap-tailmap Но когда я исследовал, я не смог обосновать эти претензии на основе исходного кода - версии могут быть изменены и т. д. Фактически, запись моих собственных тестов size() doesn ' t, похоже, сильно различаются, даже когда N изменяется на x100. Я буду смотреть дальше - может снять ответ - @mnmp вы нашли какие-то улучшения? – KarlM

0

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