Задание для опытных или начинающих: слияние сигналов

 
 
 
Сообщения:9995
Кто из начинающих хочет попробовать боевую задачу либо кто из опытных хочет потренировать мозги - вот вам задача. Требование к решению:
* Нужно выложить на гитхаб
* Должно быть покрыто модульными тестами
* Должно быть читабельным если хотите чтоб кто-то на него взглянул
* Должно работать с примитивами, никаких оберточных типов

Прежде чем браться советую изучить и попробовать реализовать следующее:
* Структура данных Куча (Heap)
* Сортировка слиянием (Merge sort)
* Как расширять массивы если уже не влазим (можно подсмотреть в ArrayList)
* Ну и научиться писать модульные тесты если до этого не делали этого

Итого, вот наброски, в них же - что нужно сделать и как (мне кажется) нужно делать:
class SignalMerger {
    /**
     * Combines signals together (all of them often have the same {@code x} but not always):
     * <p>
     *     <li>If 2 or more signals have same {@code x} coordinates - their {@code y} are summed</li>
     *     <li>If signals have different {@code x} coordinates - both of their {@code x} and {@code y} values appear in the merged signal</li>
     * </p>
     * 
     * @param signals signals to merge together
     * @return a sum of all the input signals, its length could stay the same as input signals or it could be 
     * larger if there are distinct values in input signals 
     */
    Signal merge(Signal... signals){
        int n = signals.length;
        // what's the appropriate length? It could stay the same if all signals have the same x's
        // but it could also be bigger because signals may have different x's. 
        float[] resultX = new float[signals[0].size()];
        float[] resultY = new float[resultX.length];
        // since all signals are sorted by x coordinate we need to find next min(x) and put it into the resulting 
        // array, then we increment currentIndex for that signal, check if there are other values like that in the 
        // array and sum them. Then repeat. 
        int[] currentIndex = new int[n];
        // mm.. should probably be a Heap in order to quickly find the minimum values, but at the same time it should
        // point to the signal each of the values originates from. So maybe a Point{int signalIdx; float value} 
        // should be used instead?
        float[] cut = new float[n];
        // initial fill (do we need it?)
        for (int i = 0; i < n; i++) 
            cut[i] = signals[i].x(currentIndex[i]);
        // the main part of the algorithm
        
        return new Signal(resultX, resultY);
    }
}

public class Signal {
    private final float[] x, y;

    public Signal(float[] x, float[] y) {
        this.x=x;
        this.y=y;
    }

    public float x(int idx) { return x[idx]; }
    public float y(int idx) { return y[idx]; }
    public int size() { return x.length; }
}

А вот небольшой (и никак не полный) набор тестов:
import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

public class SignalTest {

    @Test public void signalDomainWithRepeatingValuesBecomesDistinctAfterMerge() {
        Signal signal = new Signal(new float[]{.1f, .1f, .2f, .2f, .3f}, repeat(1, 5));
        Assert.assertArrayEquals(new float[]{.1f, .2f, .3f}, merge(signal).x(), 0);

        Signal one = new Signal(new float[]{.1f, .1f, .2f}, repeat(1, 3));
        Signal two = new Signal(new float[]{.1f, .2f, .2f}, repeat(1, 3));
        Assert.assertArrayEquals(new float[]{.1f, .2f,}, merge(one, two).x(), 0);
    }

    @Test public void intensityValuesOfRepeatingDomainValuesAreSummed() {
        Signal signal = new Signal(new float[]{.1f, .1f, .2f, .2f, .3f}, repeat(1, 5));
        Assert.assertArrayEquals(new float[]{2f, 2f, 1f}, merge(signal).y(), 0);

        Signal one = new Signal(new float[]{.1f, .1f, .2f}, repeat(1, 3));
        Signal two = new Signal(new float[]{.1f, .2f, .2f}, repeat(1, 3));
        Assert.assertArrayEquals(new float[]{3f, 3f}, merge(one, two).y(), 0);
    }

    @Test public void domainValuesAreCombinedFromAllSignals() {
        Signal one = new Signal(new float[]{.1f, .2f}, repeat(1, 2));
        Signal two = new Signal(new float[]{.2f, .3f}, repeat(1, 2));
        Signal three = new Signal(new float[]{.4f, .5f}, repeat(1, 2));
        Assert.assertArrayEquals(new float[]{.1f, .2f, .3f, .4f, .5f}, merge(one, two, three).x(), 0);
    }

    @Test public void domainValuesAreSortedInNaturalOrderAfterMerge() {
        Signal signal = new Signal(new float[]{.2f, .3f, .1f}, new float[]{2f, 3f, 1f});
        Signal merged = merge(signal);
        Assert.assertArrayEquals(new float[]{.1f, .2f, .3f}, merged.x(), 0);
        Assert.assertArrayEquals(new float[]{1f, 2f, 3f}, merged.y(), 0);
    }

    @Test public void canMergeSignalsOfDifferentSize() {
        Signal one = new Signal(new float[]{.4f}, repeat(1, 1));
        Signal two = new Signal(new float[]{.1f, .2f, .3f}, repeat(1, 3));
        Assert.assertEquals(4, merge(one, two).x().length);
        Assert.assertEquals(4, merge(one, two).y().length);
    }

    static float[] repeat(float v, int n) {
        float[] data = new float[n];
        Arrays.fill(data, v);
        return data;
    }
    private static Signal merge(Signal ... signals){
        return new SignalMerger().merge(signals);
    }
}
Изменен:21 июл 2020 17:43
 
Модераторы:Нет
Сейчас эту тему просматривают:Нет