Нахождение режима с уменьшением точности

Question

Я чувствую, что должна быть доступная библиотека для более простого выполнения двух вещей: A) Найти режим для массива, в случае удвоений и B) изящно снизить точность, пока вы не достигнете определенной частоты.

Итак, представьте массив, подобный следующему:

double[] a = {1.12, 1.15, 1.13, 2.0, 3.4, 3.44, 4.1, 4.2, 4.3, 4.4};

Если бы я искал частоту 3, то она бы изменилась с 2 десятичных разрядов на 1 десятичную и, наконец, вернула 1.1 в качестве моего режима.Если бы у меня было требование к частоте 4, в качестве режима я бы вернул 4.

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

public static double findMode(double[] r, int frequencyReq)
{
    double mode = 0d;
    int frequency = 0;
    int iterations = 4;

    HashMap<Double, BigDecimal> counter = new HashMap<Double, BigDecimal>();

    while(frequency < frequencyReq && iterations > 0){
        String roundFormatString = "#.";
        for(int j=0; j<iterations; j++){
            roundFormatString += "#";
        }
        DecimalFormat roundFormat = new DecimalFormat(roundFormatString);
        for(int i=0; i<r.length; i++){

            double element = Double.valueOf(roundFormat.format(r[i]));

            if(!counter.containsKey(element))
                counter.put(element, new BigDecimal(0));

            counter.put(element,counter.get(element).add(new BigDecimal(1)));
        }

        for(Double key : counter.keySet()){

            if(counter.get(key).compareTo(new BigDecimal(frequency))>0){
                mode = key;
                frequency = counter.get(key).intValue();
                log.debug("key: " + key + " Count: " + counter.get(key));
            }
        }
        iterations--;
    }

    return mode;
}

Edit

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

Answer 1

Вот решение переформулированного вопроса:

Цель состоит в том, чтобы найти число, где в окрестности находится не менее frequency элементов массива, а радиус окрестности должен быть как можно меньше.

(я взял свободу переключения порядка 1.15 и 1.13 во входном массиве.)

Основная идея такова: входные данные уже отсортированы (т. Е. Соседние элементы являются последовательными), и мы знаем, сколько элементов мы хотим получить в нашем районе. Таким образом, мы зациклились один раз над этим массивом, измерив расстояние между левым элементом и элементом frequency больше справа. Между ними находятся frequency элементов, поэтому это образует соседство. Тогда мы просто берем минимальную такую ​​дистанцию. (У моего метода есть сложный способ вернуть результаты, вы можете сделать это лучше.)

Это не полностью эквивалентно вашему первоначальному вопросу (не работает с фиксированными шагами цифр), но, возможно, это больше, чем вы действительно хотите: -)

Однако вам придется найти лучший способ форматирования результатов.

package de.fencing_game.paul.examples;

import java.util.Arrays;

/**
 * searching of dense points in a distribution.
 *
 * Inspired by /5382879/nahozhdenie-rezhima-s-umensheniem-tochnosti.
 */
public class InpreciseMode {

    /** our input data, should be sorted ascending. */
    private double[] data;

    public InpreciseMode(double ... data) {
        this.data = data;
    }


    /**
     * searchs the smallest neighbourhood (by diameter) which
     * contains at least minSize elements.
     *
     * @return an array of two arrays:
     *     {   { the middle point of the neighborhood,
     *           the diameter of the neighborhood  },
     *        all the elements of the neigborhood }
     *
     * TODO: better return an object of a class encapsuling these.
     */
    public double[][] findSmallNeighbourhood(int minSize) {
        int currentLeft = -1;
        int currentRight = -1;
        double currentMinDiameter = Double.POSITIVE_INFINITY;

        for(int i = 0; i + minSize-1 < data.length; i++) {
            double diameter = data[i+minSize-1] - data[i];
            if(diameter < currentMinDiameter) {
                currentMinDiameter = diameter;
                currentLeft = i;
                currentRight = i + minSize-1;
            }
        }
        return
            new double[][] {
            { 
                (data[currentRight] + data[currentLeft])/2.0,
                currentMinDiameter
            },
            Arrays.copyOfRange(data, currentLeft, currentRight+1)
        };
    }

    public void printSmallNeighbourhoods() {
        for(int frequency = 2; frequency <= data.length; frequency++) {
            double[][] found = findSmallNeighbourhood(frequency);

            System.out.printf("There are %d elements in %f radius "+
                              "around %f:%n     %s.%n",
                              frequency, found[0][1]/2, found[0][0],
                              Arrays.toString(found[1]));
        }
    }


    public static void main(String[] params) {
        InpreciseMode m =
            new InpreciseMode(1.12, 1.13, 1.15, 2.0, 3.4, 3.44, 4.1,
                              4.2, 4.3, 4.4);
        m.printSmallNeighbourhoods();
    }

}

Выход

There are 2 elements in 0,005000 radius around 1,125000:
     [1.12, 1.13].
There are 3 elements in 0,015000 radius around 1,135000:
     [1.12, 1.13, 1.15].
There are 4 elements in 0,150000 radius around 4,250000:
     [4.1, 4.2, 4.3, 4.4].
There are 5 elements in 0,450000 radius around 3,850000:
     [3.4, 3.44, 4.1, 4.2, 4.3].
There are 6 elements in 0,500000 radius around 3,900000:
     [3.4, 3.44, 4.1, 4.2, 4.3, 4.4].
There are 7 elements in 1,200000 radius around 3,200000:
     [2.0, 3.4, 3.44, 4.1, 4.2, 4.3, 4.4].
There are 8 elements in 1,540000 radius around 2,660000:
     [1.12, 1.13, 1.15, 2.0, 3.4, 3.44, 4.1, 4.2].
There are 9 elements in 1,590000 radius around 2,710000:
     [1.12, 1.13, 1.15, 2.0, 3.4, 3.44, 4.1, 4.2, 4.3].
There are 10 elements in 1,640000 radius around 2,760000:
     [1.12, 1.13, 1.15, 2.0, 3.4, 3.44, 4.1, 4.2, 4.3, 4.4].

Answer 2

Я думаю, в вашем коде нет ничего плохого, и я сомневаюсь, что вы найдете библиотеку, которая делает что-то настолько специфическое. Но если все же вы хотите, чтобы идея подошла к этой проблеме, используя более ООП-подход, в котором повторно используются Java-коллекции, вот вам и другой подход:

• Создать класс для представления чисел с разным количеством десятичных знаков. Было бы что-то вроде VariableDecimal(double d,int ndecimals) в качестве конструктора.
• В этом классе переопределяют методы объекта equals и hashCode. Ваша реализация equals проверит, являются ли два экземпляра VariableDecimal одинаковыми, принимая во внимание значение d и количество десятичных знаков. hashCode может просто вернуть d*exp(10,ndecimals) приведенное к целому числу.

В вашей логике используйте HashMaps, чтобы они повторно использовали ваш объект:

HashMap<VariableDecimal, AtomicInteger> counters = new HashMap<VariableDecimal, AtomicInteger>();
for (double d : a) {
     VariableDecimal vd = new VariableDecimal(d,ndecimals);
     if (counters.get(vd)!=null)
         counters.set(vd,new AtomicInteger(0));
     counters.get(vd).incrementAndGet();

}
/* at the end of this loop counters should hold a map with frequencies of 
   each double for the selected precision so that you can simply traverse and 
   get the max */

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