Форум программистов, компьютерный форум, киберфорум
Наши страницы
ManyGames
Войти
Регистрация
Восстановить пароль
Рейтинг: 5.00. Голосов: 1.

Немного про промышленное и спротивное программирование

Запись от ManyGames размещена 24.08.2018 в 12:46

Добрый день, форумчане!

Я совсем недавно зарегистрировался на форуме. На первый взгляд люди хорошие, добрые. Да, так и есть. Но не в отношении к олимпиадникам или людям, которые иногда ошибаются. Как вы уже, наверное, поняли, я являюсь олимпиадником, и, как и каждый человек, иногда совершаю ошибки. Но, к сожалению, а может и к счастью, воспринимаю только адекватную критику или указание на ошибки. И так, теперь о "постояльцах" форума (конечно не обо всех).
1)Все мы когда-то ошибались, ошибаемся и будет ошибаться. Людям надо указывать на ошибки, а не начинать их засерать из-за малейшего отклонения от нужно курса, имхо. То есть критика, повторюсь, должна быть адекватной, ведь не каждому человеку будет приятно, если за то что он где-то не написал "private", его начнут засерать со всех сторон.
2)Все привыкли, что нужно действовать так, как нужно заказчику. Но мало кто задумывался о быстродействии. Представьте ситуацию: вам сказали написать какой-то супер калькулятор, считывающий строку и возвращающий результат операций. Конечно, первое что приходит на ум - функция eval (её аналог из perl). Для небольших строк это действительно хороший вариант: писать много не придется (2-3 строки), для небольших (!) строк вычисления производятся быстро. А что, если у нас строка с выражением длиной 1030 символов? Через тот же eval вычисляться значение будет очень долго (к сожалению, примерных расценок среднего времени выполнения на разных ЯП я не знаю, но точно выполняться будет долго), и не факт, что верно. Олимпиадник сказал бы: "нужно реализовать свою функцию для вычисления результата". И это верно. Своя функция, в зависимости от реализации, будет работать быстро даже при такой длине выражения. Да, размер кода теперь может занять от 30 до 100 строк, но быстродействие гарантированно. Похожая ситуация: Допустим, у нас есть задача, которая звучит так: Имеется лифт с максимальной грузоподъемностью x и n человек, желающих подняться с первого на последний этаж. Пассажиры пронумерованы от 0 до n-1, вес i-го пассажира равен weight[i]. За какое минимальное количество поездок удастся перевезти всех на верхний этаж? (из книги Антти Лааксонена - "Олимпиадное программирование"). Такая задача может попасться и в промышленном программировании. Задачу легко решить за O(n!n), проверив все возможные перестановки n человек. Но можно добиться более эффективного решения за O(2nn) при помощи динамического программирования. Только представьте, сколько времени будет работать решение с перебором всех вариантов: при n=100 Солнце погаснет раньше, чем решение закончит работу (т.к. будет выполнено ~100!*100 операций). А вдруг заказчик замышляет как раз и тестировать на больших значениях?
Из-за подобных ситуаций я считаю, что каждый программист обязан знать хоть немного эффективных алгоритмов и структур данных, а так же определение "О большое". Примерами алгоритмов и структур данных могут служить: двоичный поиск (во многих языках встроен, но а вдруг вам нужен поиск не по массиву, а по последовательности 1..n, где n - достаточно большое число), сортировка слиянием (например, для подсчета кол-ва чисел в массиве, меньших (больших) i-го), sqrt-декомпозицию. Да вообще, каждому эффективному алгоритму можно найти своё применение и в промышленном программировании. Например, у крупных поисковых систем есть функция, благодаря которой вы, даже если ошибётесь при вводе текста в поисковик, найдёте то, что искали ("вероятно, вы искали.."). Эта функция основана на динамическом программировании. Или возьмём ту же GPS: поиск кратчайших маршрутов осуществляется при помощи алгоритма Дейкстры. Однако стоит отметить, что некоторые алгоритмы вовсе не нужны в промышленном программировании. Например, по моему мнению, вычисление расстояния Левенштейна (также известное как "редакционное расстояние") не нужно. Хотя, кто знает.
И так, мы немного отклонились от темы. Многие люди на форуме, с которыми я общался, "олимпиадные подходы" (примеры которых я описал выше), очень сильно критикуют, в то же время не понимая многих нюансов. Типичный случай: проверить, подходит ли слово под шаблон (причем шаблон может быть либо в первой, либо во второй строке). Чуть что, так начинают втирать регулярные выражения. Такое решение на Java выглядит так:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
 
public class Test{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String s[] = {in.next(), in.next()};
        in.close();
        //обращаем внимание, что шаблон может быть как и в первой строке, так и во второй
        for(int i = 0; i<2; i++) {
            s[i] = s[i].replaceAll("\\*", "\\.*");
            s[i] = s[i].replaceAll("\\?", "\\.");
        }
        System.out.println((s[0].matches(s[1]) || s[1].matches(s[0]))?"YES":"NO");
    }
}
Сразу стоит отметить, что с регулярными выражениями данная задача уже при 200+ символов (и в шаблоне, и в слове) будет выполняться долго. А вдруг, у нас в шаблоне и слове - 255 различных символов? Например, входные данные такие:
Кликните здесь для просмотра всего текста

*W*?*D*J*?*N*H*?*Q*O*?*H*A*?*B*G*?*H*U*?*L*X*?*W*T*?*U*S*?*B*F*?*V*C*?*F*Y*?*A*D*?*C*J*?*W*V*?*B*C*?*S*S*?*T*Y*?*Q*E*?*N *W*?*A*J*?*N*K*?*H*I*?*A*W*?*F*Y*?*C*L*?*E*V*?*G*U*?*O*W*?*H*K*?*N*D*?*E*R*?*E*M*?*L*T*?*Q*F*?*U*T*?*T*O*?*B*E*?*S*N*?*X *X*?*D*B*?*J*J*

XAHOYHUUPJFVKUJGNFDRHHUCSKWDJSANFFGMYYSIRHGHUOUXHDWYMULKQHKJDRJWCBGONPUTMVAXIRSYQKDFCWDRIEYVXSWEESYNDLBBKPCHPCQEABCMXYYC GNFIBPGPVXSPMUJKXAFQNYVALFFUNXRLCOSWXHYHUOROCMXFOLMVKRJPOCIJMDAJCRWGXVUFADNFUUSIFHRHHEVNILHVQHCYCLMNGCRLAUTPJOEYTRFVKBMJ COCJQAIHLRFEIICY

Тут первое слово - шаблон, второе - слово, это понятно. Попробуйте протестировать программу при таких входных данных. Она у Вас вообще завершилась? А такая ситуация вполне реальна. Предлагаю другой вариант: применить метод динамического программирования. Он заключается в том, что задача разбивается на подзадачи, и, зная ответ к прошлой подзадаче, вычисляется значение текущей подзадачи. Таким образом может быть решена вся задача. Моё решение не самое красивое, но оно точно скажет ответ к данному тесту:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import java.io.*;
import java.util.*;
 
public class Test{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        char []pattern, str;
        String str1 = in.next(), str2 = in.next();
        in.close();
 
        if(str1.indexOf("*")>=0||str1.indexOf("?")>=0){
            str = str2.toCharArray();
            pattern = str1.toCharArray();
        }
        else{
            str = str1.toCharArray();
            pattern = str2.toCharArray();
        }
 
        int len1 = pattern.length, len2 = str.length;
        int dp[][] = new int[len1][len2], sum, min = 0;
        boolean check;
 
        for(int i = 0; i<len1; i++){
            if(pattern[i]=='?' || (pattern[i]!='*' && pattern[i]!='?')) min++;
            check = false;
            sum=0;
            for(int j = 0; j<len2; j++){
                if(pattern[i]=='*'){
                    if(i==0) dp[i][j]=j+1;
                    else if(i>0){
                        if(dp[i-1][len2-1]==len2){
                            dp[i][j] = j+1;
                        }
                        if(pattern[i-1]=='*' || (i==len1-1 && dp[len1-2][len2-1]==len2)){
                            dp[i][j] = dp[i-1][j];
                        }
                        else {
                            if (j > 0 && dp[i - 1][j - 1] > 0) {
                                check = true;
                                dp[i][j] = j + 1;
                            } else if (check) {
                                dp[i][j] = j + 1;
                            }
                        }
                    }
                }
                else if(pattern[i]=='?'){
                    if(i==0){
                        dp[0][0] = 1;
                        sum+=dp[i][j];
                        break;
                    }
                    if(i>0){
                        if(pattern[i-1]=='*'){
                            dp[i][j] = dp[i-1][j];
                        }
                        else {
                            if (j > 0 && dp[i - 1][j - 1] > 0) {
                                dp[i][j] = j + 1;
                                sum+=dp[i][j];
                            }
                        }
                    }
                }
                else{
                    if(i==0){
                        if(pattern[0]==str[0]){
                            dp[0][0] = 1;
                            sum+=dp[i][j];
                            break;
                        }
                        else{
                            System.out.println("NO");
                            return;
                        }
                    }
                    if(i>0){
                        if(pattern[i-1]=='*' && pattern[i]==str[j]){
                            dp[i][j] = dp[i-1][j];
                        }
                        else if(pattern[i]==str[j] && j>0 && dp[i-1][j-1]!=0){
                            dp[i][j] = j+1;
                        }
                    }
                }
                sum+=dp[i][j];
            }
            if(sum==0){
                System.out.println("NO");
                return;
            }
        }
        System.out.println(dp[len1-1][len2-1]==len2 && len2>=min?"YES":"NO");
    }
}
Я засекал время выполнения моего решения на приведённом здесь тесте, в среднем оно колеблется от 50 до 170 мс, в то время как решение при помощи регулярных выражений вообще не останавливается (именно на этом тесте). При этом у меня доволно слабенький процессор: intel Pentium inside. Как можно заметить, чем меньше длины строк, тем более быстро работают оба решения. При достаточно небольших длинах обеих строк оба решения работают практически одинаково.


И так, выводы: "олимпиадные подходы" решения задач - всегда хорошо. Круг решения задач этим подходом неограничен, в то время как "обычное программисты" делают хорошие решения в зависимости от количества данных, которые подаются программе.
Надеюсь, что после появления данной статьи, на форуме уменьшится количество людей, которые презирают нестандартные подходы к решению задач. Если заметили ошибку или знаете более эффективное решение - комментируйте адекватно. если не умеете адекватно комментировать, то идите лесом не стоит лезть. Также не стоит делать поспешных выводов, причиной которых могут послужить возраст человека или "выдуманные" ошибки.
Хороший форумчанин - вежливый форумчанин!

(источник: моё мнение)

Upd:
vcrop предложил свой вариант решения задачи с шаблоном и словом, с использованием регулярных выражений:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.io.*;
import java.util.*;
import java.util.regex.*;
  
public class Main {
  
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
  
        String[] input = new String[]{"!" + in.next() + "!", "!" + in.next() + "!"};
        Arrays.sort(input, Comparator.comparing((String n) -> n.matches(".*[*?].*")));
  
        out.println(
                Arrays.stream(input[1].split("\\*+"))
                        .map(s -> s.replaceAll("\\?", "."))
                        .map(c -> Pattern.compile(c).matcher(input[0]))
                        .allMatch(Matcher::find) ? "YES" : "NO");
  
        out.flush();
    }
}
Это решение по времени мало чем отличается от предложенного мною. Значит, и мне нужно что-то подучить. Но это не меняет тот факт, что быстродействие часто играет большую роль.
Размещено в Без категории
Просмотров 713 Комментарии 10
Всего комментариев 10
Комментарии
  1. Старый комментарий
    Аватар для Agregat
    Да. Вежливость - это хорошо.

    Что же касается оптимизации - в промышленном программировании ее целесообразно делать не всегда, а только в тех случаях, когда скорость выполнения программы не устраивает пользователя.
    Запись от Agregat размещена 24.08.2018 в 14:17 Agregat вне форума
  2. Старый комментарий
    Аватар для Avazart
    Цитата:
    Сразу стоит отметить, что с регулярными выражениями данная задача уже при 200+ символов (и в шаблоне, и в слове) будет выполняться долго. А вдруг, у нас в шаблоне и слове - 255 различных символов?
    А если не "вдруг" ? Если ложить сколько она будет выполнятся?

    P.S.: Разве приложения на Java не выполняются одинаково медленно?
    Запись от Avazart размещена 24.08.2018 в 16:03 Avazart вне форума
    Обновил(-а) Avazart 24.08.2018 в 16:07
  3. Старый комментарий
    А зачем делать полный перебор? В подобных случаях делается "случайный" перебор. То есть неполный с использованием случайных чисел и далее оценивается время ... Ведь по сути нужна оценка, а не точное значение.
    Запись от нтч размещена 24.08.2018 в 16:23 нтч вне форума
  4. Старый комментарий
    Хочу добавить, что в играх (например шахматах) с использование искусственного интеллекта программа на первых двух-трёх шагах использует полный перебор. И на его основе выбирает две - три позиции, которые прорабатывает отдельно на большую глубину. Кстати так играет и человек ...
    Запись от нтч размещена 24.08.2018 в 16:29 нтч вне форума
  5. Старый комментарий
    Цитата:
    Сообщение от нтч Просмотреть комментарий
    А зачем делать полный перебор? В подобных случаях делается "случайный" перебор. То есть неполный с использованием случайных чисел и далее оценивается время ... Ведь по сути нужна оценка, а не точное значение.
    В приведённом примере динамическое программирование - самый эффективный вариант. Но опять же, всё зависит от того, насколько большие будут данные. Если данные достаточно большие, то ДП - лучший вариант.
    Запись от ManyGames размещена 24.08.2018 в 17:19 ManyGames вне форума
  6. Старый комментарий
    Вроде бы, это - один из самых вежливых форумов. Невежливость и слова не по теме тут попросту удалят в итоге, да и все.
    Просто надо иметь в виду, что невежливость на программистских ! (впрочем, и не на программистских - тоже, отчасти) форумах - это неслучайно. Это результат целенаправленного стремления нескольких известных персонажей разобщить людей, воспитать в них озлобленность, отчужденность, враждебность и т.п. Т.н. "тролли" возникли неслучайно. Точно так же, как в 90-е годы "вдруг" повозникали разные бандитские группировки. Были, конечно, и те, кто сами по себе, но, таких, вроде бы, немного. Их-то как раз и уничтожили. По очевидным причинам.
    Если мне, к примеру, человек вместо ответа на вопрос начинает всякую ахинею нести - лично я попросту покидаю его (а не тему), да и все.

    Что же касается алгоритмов, так Вы тут немного о разных вещах. Программист, это, как правило - кодер. Создающий программу ПО ГОТОВОМУ алгоритму. А разработчик алгоритмов, с их оценкой сложности - это несколько другой специалист. Хотя, нередки совмещения.
    Чтобы найти именно оптимальный алгоритм - для этого, иной раз, приходится полностью отвлечься от этих #include, посвятив себя математическим аспектам. Не всем образование позволяет это сделать, ведь немало программистов - самоучки, не имеющие за плечами толком даже матанализа, не говоря уже о чем-то большем. Немало тех, кто учился, пренебрегая дисциплинами математического цикла (в жизни, мол, "не пригодится"), акцентируясь лишь на дисциплинах программистской направленности - вот и результат.
    Поэтому, естественно, многим проще предложить самый простой, дубовый, но рабочий алгоритм. Собственно, это так - даже и в научной среде. Когда исследователь применяет известный ЕМУ алгоритм, а не тот, который эффективнее.
    Запись от Htext размещена 25.08.2018 в 14:51 Htext вне форума
  7. Старый комментарий
    Htext
    в реальной жизни часто и не нужен самый эффективный алгоритм. Нужно получить
    просто ответ. А сколько будет считать программа? ... одну секунду или час? ... да какая
    разница!! Главное ответ получен! А поиск эффективного алгоритма может затянуться на
    очень длительное время...
    Запись от нтч размещена 26.08.2018 в 08:30 нтч вне форума
  8. Старый комментарий
    Аватар для Rius
    Цитата:
    А поиск эффективного алгоритма может затянуться на
    очень длительное время...
    ... за которое твои конкуренты выпустят тот же самый сервис, хоть и на неэффективном алгоритме, захватят мир, а к твоему появлению с эффективным алгоритмом они уже многократно свой оптимизируют под реальность и ты останешься с носом.
    Запись от Rius размещена 26.08.2018 в 09:00 Rius вне форума
  9. Старый комментарий
    Уважаемый Rius,
    в чём-то вы правы НО. Не надо при написании каждой программы делать самоцелью её максимальную эффективность. Есть программы "одноразового" использования. То есть такая программа должна что-то сделать (сосчитать) и более она не нужна. Поиск эффективного алгоритма может занять столько времени, что проще "на пальцах сосчитать", чем этим заниматься. Вот и есть алгоритмы, которые просты в написании ... они решают задачу за приемлемое время и ... эффективность от них не требуется. Результат полученный быстро и с малыми затратами оправдывает всё. Ведь второй раз программа не нужна. А более эффективная программа может оказаться более сложной, потребует время для ее написания, проверки и много чего другого...
    И ради чего?
    В общем программа не должна быть самоцелью. ...
    Запись от нтч размещена 26.08.2018 в 09:33 нтч вне форума
  10. Старый комментарий
    Аватар для Rius
    нтч, это вы автору-олимпиаднику рассказывайте, я-то согласен.
    Запись от Rius размещена 26.08.2018 в 09:38 Rius вне форума
    Обновил(-а) Rius 26.08.2018 в 09:39
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru