@azazelija

Разработать алгоритм для уменьшения количества итераций с большими числами?

Добрый день. Имеет задача: найти через сколько дней числа на двух табло будут равны заданному коэффиценту. Но табло показывает только двузначные числа, если число больше 100 то она будет возвращать 99. Если какое-то из чисел до конца цикла обернется в ноль возвращается -1.
Проблема заключается в больших числах, так как при тестировании 100.000 пар чисел программа обрабатывает один запрос раз в полторы секунды.

Мой алгоритм (я возвращаю флоат так как стоит проблема с точностью при делении. Например 99 делить на 49 будет 2 :))
public static int countRelations(long x, long y, int k) {

        int days = 0;
        while (countDaysOnScoreboard(x)/countDaysOnScoreboard(y) != k
                && countDaysOnScoreboard(y)/countDaysOnScoreboard(x) != k) {
            days += 1;
            x--;
            y--;
            if (x == 0 || y == 0) {
                days = -1;
                break;
            }
        }
        return days;
    }

public static float countDaysOnScoreboard(long num) {
        if (num >= 100)
            return 99;
        return num;
    }


Код для тестирования:
@Test
    void countRelationsTest() throws IOException {
        assertEquals(0, Main.countRelations(2,1,2));
        assertEquals(98, Main.countRelations(100,99,2));
        assertEquals(-1, Main.countRelations(17,13,10));
        assertEquals(0, Main.countRelations(3,3,1));
        assertEquals(-1, Main.countRelations(1,1,2));

        BufferedReader reader = new BufferedReader(new FileReader("src/ДИТ КИБ (Остроумов)/02"));
        BufferedReader readerAnsw = new BufferedReader(new FileReader("src/ДИТ КИБ (Остроумов)/02.a"));
        String s;
        String sAnsw;
        int i = 0;
        while ((s = reader.readLine()) != null) {
            sAnsw = readerAnsw.readLine();
            String[] strArr = s.split(" ");
            assertEquals(Integer.parseInt(sAnsw), Main.countRelations(Integer.parseInt(strArr[0]),Integer.parseInt(strArr[1]),Integer.parseInt(strArr[2])));
            System.out.println("Test passed " + i++);
        }

    }


Также прилагаю два файла. Один с заданными парами и коэффицентом. Другой с ответами.
Пары
Ответы
  • Вопрос задан
  • 134 просмотра
Пригласить эксперта
Ответы на вопрос 1
Bavashi
@Bavashi
azazelija, ads83, смотрите, что какую фигню придумал: если убрать во внимание работу с файлами, то в самом алгоритме много времени вызывает метод countDaysOnScoreboard(), который вызывается каждый проход цикла 4 раза для двух аргументов. Чтобы уйти от этого метода, можно "покрыть" метод countRelations() условиями для "отсекания" не нужных итераций в цикле. Например, для таких входных тестовых пар как (300, 400, 3), (800, 940, 2) и так далее. То есть вместо метода countDaysOnScoreboard() у нас будет 8 if'ов, что по идее должно дать буст в скорости выполнения. При этом на каждое условие будут свои методы - немного измененные countRelations(). Всего их три: countRelationsWithDays(x,y,k,c), countRelationsWithoutY(x,y,k), countRelationsWithoutX(x,y,k). Но, что главное, вызываться один из них будет только один раз и без метода countDaysOnScoreboard() вообще. Вопрос будет в том, на сколько if'ы будут быстрее и будут ли.

Код для теста

import java.util.*;
import java.lang.*;

class SomeClass
{  
    public static void main(String args[])
    {
        
        System.out.println("countRelations(2,1,2) = " + countRelations(2,1,2)); // 0
        System.out.println("countRelations(100,99,2) = " + countRelations(100,99,2)); // 98
        System.out.println("countRelations(17,13,10) = " + countRelations(17,13,10)); // -1
        System.out.println("countRelations(3,3,1) = " + countRelations(3,3,1)); // 0
        System.out.println("countRelations(1,1,2) = " + countRelations(1,1,2)); // -1
        
        System.out.println();
        
        System.out.println("countRelations(1,2,2) = " + countRelations(1,2,2)); // 0
        System.out.println("countRelations(99,100,2) = " + countRelations(99,100,2)); // 98
        System.out.println("countRelations(170,130,10) = " + countRelations(170,130,10)); // -1
        System.out.println("countRelations(400,379,2) = " + countRelations(400,379,2)); // 358
        System.out.println("countRelations(900,883,2) = " + countRelations(900,883,2)); // 866
        
    }
    
    public static long countRelations(long x, long y,  int k) {
        
        if (x >= 200 && y < 100) {
            x = 99;
            countRelationsWithoutX(x,y,k);
        }
        
        if (x < 100 && y >= 200) {
            y = 99;
            countRelationsWithoutY(x,y,k);
        }
        
        if (x >= 100 && x < 200 && y < 100) {
            long c = x - 99;
            x = 99;
            y = y - c;
            return countRelationsWithDays(x,y,k,c);
        }
        
        if (y >= 100 && y < 200 && x < 100) {
            long c = y - 99;
            y = 99;
            x = x - c;
            return countRelationsWithDays(x,y,k,c);
        }
        
        if (x > 200 && x < 1000 && y > 200 && y < 1000) {
            if (k != 1) {
                if (x > y) {
                    long c = ((y/100)*100);
                    x = x - c;
                    y = y - c;
                    return countRelationsWithDays(x,y,k,c);
                }
                else if (x < y) {
                    long c = ((x/100)*100);
                    x = x - c;
                    y = y - c;
                    return countRelationsWithDays(x,y,k,c);
                }
            } else {
                return 0;
            }
        } else {
            long c = 0;
            return countRelationsWithDays(x,y,k,c);
        }
        
        int days = 0;
        return days;
    }

    public static int countRelationsWithoutX(long x, long y,  int k) {
        
        int days = 0;
        while (x/y != k && y/x != k) {
            days += 1;
            //x--;
            y--;
            if (x == 0 || y == 0) {
                days = -1;
                break;
            }
        }
        return days;
    }
    
    public static int countRelationsWithoutY(long x, long y,  int k) {
        
        int days = 0;
        while (x/y != k && y/x != k) {
            days += 1;
            x--;
            //y--;
            if (x == 0 || y == 0) {
                days = -1;
                break;
            }
        }
        return days;
    }
    
    public static long countRelationsWithDays(long x, long y,  int k, long c) {
        
        long days = c;
        while (x/y != k && y/x != k) {
            days += 1;
            x--;
            y--;
            if (x == 0 || y == 0) {
                days = -1;
                break;
            }
        }
        return days;
    }
}


Чую, что где-то накосячил в коде и нужно проверить его на входных тестовых данных из файла.

P.S. В лучшем случае, если это и даст увеличение скорости выполнения, то если оставлять чтение из файлов и проверку через ассерты (их вызов тоже может влиять на скорость при большом количестве тестовых данных) - прирост будет не очень большой. Надо тестить. При этом исходил из того, что в метод countRelations() будут передаваться числа не более 1000. Если в тестовом файле есть числа (x, y) > 1000, то нужно будет переделать код.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы