Я не против циклов. Я против вложенных циклов. Они увеличивают время работы программы экспоненциально.
Doredel писал(а):
Вложенные циклы зло, их не должно быть и их почти всегда можно избежать. В абапе кстати проще, там не нужны итераторы, луп по таблице меняет заголовочную строчку и обращаться к определенному элементу по индексу не нужно
Я надеюсь, ты понимаешь, что луп по таблице тоже самое, что и цикл. И в любом случае, используешь ты 2 вложенных цикла или 1 цикл в котором какая-то конструкция типа луп - время будет всё равно O(N^2).
В любом случае, фраза "в большинстве случаев их можно избежать" в корне неверна. Если алгоритм работает за O(N^2), хоть ты убейся, но у тебя будут 2 вложенных цикла. Возможно, они будут неявными, но они будут. _________________ На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Narsil, не знаю что это за сложные формулы. Есть оператор сортировки, есть оператор if, есть цикл. Сортировка + цикл работают быстрее чем два вложенных цикла.
Вдобавок ко всему всегда есть возможность два вложенных цикла расписать последовательно.
Вдобавок ко всему всегда есть возможность два вложенных цикла расписать последовательно.
Нет.
Doredel писал(а):
Сортировка + цикл работают быстрее чем два вложенных цикла.
Нет.
Если хочешь, могу объяснить почему подробнее в аську или ЛС. _________________ На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Сортировка + цикл работают быстрее чем два вложенных цикла.
Я тут немного не понял тебя. Сортировка + цикл в каком плане? Сортировка внутри цикла? Типа есть N массивов и надо их всех отсортировать? В таком случае, сортировка и цикл будет работать медленнее, чем 2 цикла.
Если тебе надо найти минимум в массиве, а потом отсортировать (то есть цикл и сортировка идут последовательно) - тогда да, они офк быстрее, чем 2 вложенных цикла. Но я совсем не про это говорил.
Doredel писал(а):
На первую цитату надо добавить "почти".
Расскажу подробнее про то, что такое вычислительная трудоёмкость.
Предположим, есть некий алгоритм на входных данных длины N. Тогда, фраза "этот алгоритм работает за время O(F(N))" означает, что существует некая константа C, что время работы алгоритма меньше, чем С*F(N) для любого N на любом наборе входных данных. Например есть задача: найти минимальный элемент в массиве длины N. Этот алгоритм имеет вычислительную трудоёмкость O(N) - то есть линейное время работы. Это значит, что при достаточно больших N время поиска минимального элемента для N элементов будет в 2 раза меньше, чем для массива длины 2*N.
Или вот например, сортировка массива длины N пузырьком. Она работает за O(N^2). То есть сортировка массива длины N будет в 4 раза быстрее, чем сортировка массива длины 2*N. На практике такие сортировки не применяются, а используют более быстрые вещи, которые работают за время O(N*log(N)), например quicksort, или mergesort
Последний пример - поиск элемента в отсортированном массиве. Он работает за время O(log(N)). Поиск элемента в массиве длины N будет в 2 раза быстрее, чем поиск элемента в массиве длины N^2.
Итак. К чему я это всё. А это всё я ко вложенным циклам. Естественно, если есть 2 вложенных цикла от 0 до N-1, то они очевидным образом заменяются на 1 цикл от 0 до N^2 - 1:
Код:
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
doSomething(i, j);
Код:
for (int i = 0; i < N*N; i++)
doSomething(i / N, i % N)
/ - целочисленное деление, % - взятие остатка от деления
Только вот проблема в том, что это не убирает квадратичное время. Разницы между двумя этими подходами в скорости нету, но читабельность понижается.
Если алгоритм работает за квадратичное время (то есть в наиболее очевидной реализации двумя циклами) ты его не напишешь за линейное время (то есть как ты говоришь 2 последовательных цикла). Я именно это имел ввиду. _________________ На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Я тут немного не понял тебя. Сортировка + цикл в каком плане? Сортировка внутри цикла? Типа есть N массивов и надо их всех отсортировать? В таком случае, сортировка и цикл будет работать медленнее, чем 2 цикла.
Есть выборка из БД. Ее можно отсортировать сразу же. И это произойдет быстрее, чем ты будешь все то же самое выполнять в программе.
Narsil писал(а):
На практике такие сортировки не применяются
Воистину. В абапе свои сортировки писать не нужно, поскольку есть оператор sort, который работает очень быстро.
Приведенный тобой пример вложенных циклов на деле один линейный цикл, и расписан на два только для читаемости. Тут он оправдан. Представь себе ситуацию когда у тебя две таблички, которые нужно смерджить в программе.
Если не отсортировать их, у тебя будут вложенные циклы. Если отсортировать, циклы будут работать параллельно. То есть на новый идентификатор первой таблички будет выбираться следующий элемент таблички 2.
Естественно это не касается ситуаций, когда можно объединить их еще во время выборки.
Приведенный тобой пример вложенных циклов на деле один линейный цикл, и расписан на два только для читаемости. Тут он оправдан.
Он на деле не один линейный. Он на деле один квадратичный.
ЗЫЖ Читабельность кода - это тоже показатель достаточно важный.
Doredel писал(а):
Представь себе ситуацию когда у тебя две таблички, которые нужно смерджить в программе.
Если не отсортировать их, у тебя будут вложенные циклы. Если отсортировать, циклы будут работать параллельно. То есть на новый идентификатор первой таблички будет выбираться следующий элемент таблички 2.
2 цикла - квадратичное время, сортировка + слияние - время N*log(N). Второе офк быстрее. Только это не совсем относится к теме обсуждения. Ты утверждал, что
Doredel писал(а):
Вдобавок ко всему всегда есть возможность два вложенных цикла расписать последовательно.
, что неверно. даже учитывая твоё "почти". Вот тебе пример:
Есть массив из N точек, есть некая функция distance, которая возвращает расстояние между точками. Найти минимальное расстояние между точками (естественно, различными точками).
Реши её двумя последовательными циклами. (Ну, я имею ввиду за линейное время, 2 последовательных цикла - это линейное время) _________________ На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Я знаю людей которые против глобальных переменных, например, или против "плохих" названий переменных... Но чтобы человек был против вложенных циклов...
Ну вот есть у тебя таблица N на N и тебе что-то нужно с каждой из ячеек сделать, ты хоть тресни но всё равно программа будет вложенные циклы делать (как бы при этом код ни выглядел). Более того вложенные циклы вообще не добавляют никаких избыточных действий и они не могут "экспоненциально увеличивать время работы программы".
Что до сортировки, то складывается впечатление будто ты веришь, что если вся сортировка заключается в вызове какой-то встроенной функции, то от этого она начинает работать мгновенно. Хотя на самом деле быстрее N*log(N) её не сделать теоретически даже, что легко доказуемо.
Добавлено спустя 2 минуты 27 секунд:
Doredel писал(а):
Есть выборка из БД. Ее можно отсортировать сразу же. И это произойдет быстрее, чем ты будешь все то же самое выполнять в программе.
Разве что потому что эта сортировка будет происходить на сервере БД, где возможно более сильный комп
upd: Исключение только если в БД что-то уже для сортировки по этому параметру уже сделано, но тогда и задачи отсортировать как таковой не стоит уже. _________________ --
Elysium
Хотя на самом деле быстрее N*log(N) её не сделать теоретически даже, что легко доказуемо.
Это не совсем верно. Точнее так, это верно только если мы хотим сделать общий алгоритм сортировки без привязки к типу сортируемых значений.
Существуют разные ухищрения. Например, radixsort работает за O(N*K) и требует затрат памяти O(K), где K - максимальное кол-во разрядов в числах. Понятно дело, она не всегда применима.
Есть ещё бешеная сортировка Хана, которая работает за O(N * log(log(N)) * log(log(log(N)))) тоже с какими-то допущениями, но я её не смотрел детально. Если интересно, вот линк http://www.csee.umkc.edu/~hanyij/research/isortls.ps.
Добавлено спустя 16 минут 1 секунду:
Doredel писал(а):
Они увеличивают время работы программы экспоненциально.
Вот. Да. Важное замечание. не экспоненциально, а полиномиально. _________________ На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Есть массив из N точек, есть некая функция distance, которая возвращает расстояние между точками. Найти минимальное расстояние между точками (естественно, различными точками).
Такая не решается без вложенных циклов. Хотя задача на оптимизацию довольно интересная. Ты видимо неправильно понял что я имел в виду. Не всегда вложенные циклы можно обойти. Но часто можно превратить два вложенных цикла в один линейный, либо два параллельных. Я выше приводил пример. Кагбэ да, можно привести сотню примеров, которые не будут работать без вложенных циклов.
Narsil писал(а):
Только это не совсем относится к теме обсуждения.
Ну на самом деле я об этом и говорил с самого начала.
spec писал(а):
Но чтобы человек был против вложенных циклов...
Внезапно оказывается есть такие, кому небезразлична скорость работы программ, не так ли?
spec писал(а):
Ну вот есть у тебя таблица N на N и тебе что-то нужно с каждой из ячеек сделать, ты хоть тресни но всё равно программа будет вложенные циклы делать
Спасибо, капитан.
spec писал(а):
если вся сортировка заключается в вызове какой-то встроенной функции, то от этого она начинает работать мгновенно
Нет, просто БД оптимизированы под выполнение такой работы. Я не пишу исходники серверов БД, поэтому не возьмусь объяснять почему. Сила машины тоже добавляет скорости, несомненно.
Также ты забываешь, что разные методы сортировки пригодны для разного количества записей. Если ты работаешь с табличкой в 10 строк ее можно сортировать как угодно. Если в ней 10 миллионов строк, я думаю надо задуматься, прежде чем делать по ней два вложенных цикла. Все же сортировка позволит вовремя цикл оборвать и не лезть в дебри заведомо ненужных строк.
Вот. Да. Важное замечание. не экспоненциально, а полиномиально.
Как раз-таки экспоненциально=)
1 цикл = О(N), 2 = О(N^2).... x = O(N^x), где N - параметр, х - переменная. Время экспоненциально зависит от количества циклов.
Если бы было полиномиально, то было бы х = О(N^c1*х^c2), что бред.
Doredel, почитай что-нибудь про теорию сложности вычислений, все сразу станет понятно. _________________ grammar nazi,
scientific whore.
Gabol, каюсь, дурак. Это я с прямым углом перепутал. _________________ На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Lord GAD, я просто тоже это "экспоненциально" увидел, возмутился, подумал.. И понял, что правда экспоненциально=)
И все-таки нет, не знаю, как насчет умней, но экспонента гораздо внушительнее полинома. Причем, полинома любой степени _________________ grammar nazi,
scientific whore.
Часовой пояс: GMT + 4 На страницу Пред.1, 2, 3След.
Страница 2 из 3
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете голосовать в опросах