Statystyki dotyczące dużego strumienia liczb całkowitych w java

Question

Czytam ogromną liczbę liczb całkowitych z pliku, a na koniec chcę uzyskać podstawowe statystyki z tych liczb całkowitych (mediana, średnia, 25-ty centyl, 75-ty percentyl, itd.). Mogę obliczyć niektóre z tych statystyk w ruchu, ale wydaje mi się, że obliczenie 25./75 centyla byłoby skomplikowane. Najprostszym podejściem, jak sądzę, byłoby umieszczenie liczb całkowitych na liście i wykonanie statystyk z tej listy. Jednak, ponieważ lista jest tak duża, może spowolnić program używania tak dużej ilości pamięci. Czy macie jakieś sugestie? Jest to rodzaj jak ja zdobyć dane i obie opcje myślałem:

Scanner input = new Scanner(new File("name")); 
ArrayList<Integer> lits= new ArrayList<Integer>(); 
while(input.hasNextLine()){ 
    list.add(Integer.parseInt(input.nextLine())); 
} 
doStatistics(list); 

LUB

Scanner input = new Scanner(new File("name")); 
while(input.hasNextLine()){ 
    //I dont know how I would acomplish this for the percentile stats 
    acqquireStats(Integer.parseInt(input.nextLine())); 
} 

Answer 1

Biorąc pod uwagę, że liczba wartości jest znacznie mniejsza niż liczba próbek, bardziej sensowne jest przechowywanie liczby na wartość niż r everse.

Long[] samples = new Long[101]; 

while(input.hasNextLine()){ 
    try{ 
     samples[Math.max(0, Math.min(100, Integer.parseInt(input.nextLine())))]; 
    } catch (ParseException e){/*not a number*/} 
} 

To pozostawia ogromny zestaw danych reprezentowany przez niewielką tablicę.

Answer 2

Ten artykuł i John D. Cooka są najlepsze zakłady:

http://www.codeproject.com/Articles/33781/Calculate-Percentiles-in-O-1-space-and-O-n-time