Список форумов Roses Roses
Форум сообщества Roses
 
 FAQFAQ   ПоискПоиск   ПользователиПользователи   ГруппыГруппы   РегистрацияРегистрация 
 ПрофильПрофиль   Войти и проверить личные сообщенияВойти и проверить личные сообщения   ВходВход 


Visual Basic
На страницу Пред.  1, 2, 3  След.
 
Начать новую тему   Ответить на тему    Список форумов Roses -> Общий раздел -> Общий
Предыдущая тема :: Следующая тема  
Автор Сообщение
Doredel
Royal Rose
Royal Rose


Возраст: 109
Зарегистрирован: 23.02.2006
Сообщения: 11222


СообщениеДобавлено: 06 Февраль, 2011 01:55    Заголовок сообщения: Ответить с цитатой

Я не против циклов. Я против вложенных циклов. Они увеличивают время работы программы экспоненциально.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Narsil
Grammar nazi
Grammar nazi


Возраст: 35
Зарегистрирован: 09.03.2007
Сообщения: 5516
Откуда: Волшебная страна

СообщениеДобавлено: 06 Февраль, 2011 14:23    Заголовок сообщения: Ответить с цитатой

Doredel писал(а):
Я не против циклов. Я против вложенных циклов. Они увеличивают время работы программы экспоненциально.

Doredel писал(а):
Вложенные циклы зло, их не должно быть и их почти всегда можно избежать. В абапе кстати проще, там не нужны итераторы, луп по таблице меняет заголовочную строчку и обращаться к определенному элементу по индексу не нужно

Я надеюсь, ты понимаешь, что луп по таблице тоже самое, что и цикл. И в любом случае, используешь ты 2 вложенных цикла или 1 цикл в котором какая-то конструкция типа луп - время будет всё равно O(N^2).

В любом случае, фраза "в большинстве случаев их можно избежать" в корне неверна. Если алгоритм работает за O(N^2), хоть ты убейся, но у тебя будут 2 вложенных цикла. Возможно, они будут неявными, но они будут.
_________________
На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Doredel
Royal Rose
Royal Rose


Возраст: 109
Зарегистрирован: 23.02.2006
Сообщения: 11222


СообщениеДобавлено: 06 Февраль, 2011 23:16    Заголовок сообщения: Ответить с цитатой

Narsil, не знаю что это за сложные формулы. Есть оператор сортировки, есть оператор if, есть цикл. Сортировка + цикл работают быстрее чем два вложенных цикла.
Вдобавок ко всему всегда есть возможность два вложенных цикла расписать последовательно.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Narsil
Grammar nazi
Grammar nazi


Возраст: 35
Зарегистрирован: 09.03.2007
Сообщения: 5516
Откуда: Волшебная страна

СообщениеДобавлено: 07 Февраль, 2011 00:34    Заголовок сообщения: Ответить с цитатой

Doredel писал(а):
Вдобавок ко всему всегда есть возможность два вложенных цикла расписать последовательно.

Нет.
Doredel писал(а):
Сортировка + цикл работают быстрее чем два вложенных цикла.

Нет.

Если хочешь, могу объяснить почему подробнее в аську или ЛС.
_________________
На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Doredel
Royal Rose
Royal Rose


Возраст: 109
Зарегистрирован: 23.02.2006
Сообщения: 11222


СообщениеДобавлено: 07 Февраль, 2011 01:32    Заголовок сообщения: Ответить с цитатой

Я все написал верно, но неточно.
На первую цитату надо добавить "почти".
На вторую цитату надо добавить "Если мы работаем с БД".
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Narsil
Grammar nazi
Grammar nazi


Возраст: 35
Зарегистрирован: 09.03.2007
Сообщения: 5516
Откуда: Волшебная страна

СообщениеДобавлено: 07 Февраль, 2011 13:33    Заголовок сообщения: Ответить с цитатой

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 последовательных цикла). Я именно это имел ввиду.
_________________
На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Doredel
Royal Rose
Royal Rose


Возраст: 109
Зарегистрирован: 23.02.2006
Сообщения: 11222


СообщениеДобавлено: 07 Февраль, 2011 14:01    Заголовок сообщения: Ответить с цитатой

Narsil писал(а):
Я тут немного не понял тебя. Сортировка + цикл в каком плане? Сортировка внутри цикла? Типа есть N массивов и надо их всех отсортировать? В таком случае, сортировка и цикл будет работать медленнее, чем 2 цикла.


Есть выборка из БД. Ее можно отсортировать сразу же. И это произойдет быстрее, чем ты будешь все то же самое выполнять в программе.

Narsil писал(а):
На практике такие сортировки не применяются

Воистину. В абапе свои сортировки писать не нужно, поскольку есть оператор sort, который работает очень быстро.

Приведенный тобой пример вложенных циклов на деле один линейный цикл, и расписан на два только для читаемости. Тут он оправдан. Представь себе ситуацию когда у тебя две таблички, которые нужно смерджить в программе.

Если не отсортировать их, у тебя будут вложенные циклы. Если отсортировать, циклы будут работать параллельно. То есть на новый идентификатор первой таблички будет выбираться следующий элемент таблички 2.

Естественно это не касается ситуаций, когда можно объединить их еще во время выборки.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Narsil
Grammar nazi
Grammar nazi


Возраст: 35
Зарегистрирован: 09.03.2007
Сообщения: 5516
Откуда: Волшебная страна

СообщениеДобавлено: 07 Февраль, 2011 15:46    Заголовок сообщения: Ответить с цитатой

Doredel писал(а):
Приведенный тобой пример вложенных циклов на деле один линейный цикл, и расписан на два только для читаемости. Тут он оправдан.

Он на деле не один линейный. Он на деле один квадратичный.
ЗЫЖ Читабельность кода - это тоже показатель достаточно важный.

Doredel писал(а):
Представь себе ситуацию когда у тебя две таблички, которые нужно смерджить в программе.

Если не отсортировать их, у тебя будут вложенные циклы. Если отсортировать, циклы будут работать параллельно. То есть на новый идентификатор первой таблички будет выбираться следующий элемент таблички 2.

2 цикла - квадратичное время, сортировка + слияние - время N*log(N). Второе офк быстрее. Только это не совсем относится к теме обсуждения. Ты утверждал, что
Doredel писал(а):
Вдобавок ко всему всегда есть возможность два вложенных цикла расписать последовательно.
, что неверно. даже учитывая твоё "почти". Вот тебе пример:

Есть массив из N точек, есть некая функция distance, которая возвращает расстояние между точками. Найти минимальное расстояние между точками (естественно, различными точками).

Реши её двумя последовательными циклами. (Ну, я имею ввиду за линейное время, 2 последовательных цикла - это линейное время)
_________________
На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
spec
Elysium
Elysium



Зарегистрирован: 01.02.2006
Сообщения: 600
Откуда: питер

СообщениеДобавлено: 07 Февраль, 2011 16:10    Заголовок сообщения: Ответить с цитатой

Я знаю людей которые против глобальных переменных, например, или против "плохих" названий переменных... Но чтобы человек был против вложенных циклов...

Ну вот есть у тебя таблица N на N и тебе что-то нужно с каждой из ячеек сделать, ты хоть тресни но всё равно программа будет вложенные циклы делать (как бы при этом код ни выглядел). Более того вложенные циклы вообще не добавляют никаких избыточных действий и они не могут "экспоненциально увеличивать время работы программы".

Что до сортировки, то складывается впечатление будто ты веришь, что если вся сортировка заключается в вызове какой-то встроенной функции, то от этого она начинает работать мгновенно. Хотя на самом деле быстрее N*log(N) её не сделать теоретически даже, что легко доказуемо.

Добавлено спустя 2 минуты 27 секунд:

Doredel писал(а):

Есть выборка из БД. Ее можно отсортировать сразу же. И это произойдет быстрее, чем ты будешь все то же самое выполнять в программе.


Разве что потому что эта сортировка будет происходить на сервере БД, где возможно более сильный комп Smile

upd: Исключение только если в БД что-то уже для сортировки по этому параметру уже сделано, но тогда и задачи отсортировать как таковой не стоит уже.
_________________
--
Elysium
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Narsil
Grammar nazi
Grammar nazi


Возраст: 35
Зарегистрирован: 09.03.2007
Сообщения: 5516
Откуда: Волшебная страна

СообщениеДобавлено: 07 Февраль, 2011 16:23    Заголовок сообщения: Ответить с цитатой

spec писал(а):
Хотя на самом деле быстрее 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 писал(а):
Они увеличивают время работы программы экспоненциально.

Вот. Да. Важное замечание. не экспоненциально, а полиномиально.
_________________
На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Doredel
Royal Rose
Royal Rose


Возраст: 109
Зарегистрирован: 23.02.2006
Сообщения: 11222


СообщениеДобавлено: 07 Февраль, 2011 17:20    Заголовок сообщения: Ответить с цитатой

Narsil писал(а):
Есть массив из N точек, есть некая функция distance, которая возвращает расстояние между точками. Найти минимальное расстояние между точками (естественно, различными точками).


Такая не решается без вложенных циклов. Хотя задача на оптимизацию довольно интересная. Ты видимо неправильно понял что я имел в виду. Не всегда вложенные циклы можно обойти. Но часто можно превратить два вложенных цикла в один линейный, либо два параллельных. Я выше приводил пример. Кагбэ да, можно привести сотню примеров, которые не будут работать без вложенных циклов.

Narsil писал(а):
Только это не совсем относится к теме обсуждения.

Ну на самом деле я об этом и говорил с самого начала. Smile

spec писал(а):
Но чтобы человек был против вложенных циклов...

Внезапно оказывается есть такие, кому небезразлична скорость работы программ, не так ли? Smile

spec писал(а):
Ну вот есть у тебя таблица N на N и тебе что-то нужно с каждой из ячеек сделать, ты хоть тресни но всё равно программа будет вложенные циклы делать

Спасибо, капитан.

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

Нет, просто БД оптимизированы под выполнение такой работы. Я не пишу исходники серверов БД, поэтому не возьмусь объяснять почему. Сила машины тоже добавляет скорости, несомненно.

Также ты забываешь, что разные методы сортировки пригодны для разного количества записей. Если ты работаешь с табличкой в 10 строк ее можно сортировать как угодно. Если в ней 10 миллионов строк, я думаю надо задуматься, прежде чем делать по ней два вложенных цикла. Все же сортировка позволит вовремя цикл оборвать и не лезть в дебри заведомо ненужных строк.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Gabol
Grammar nazi
Grammar nazi


Возраст: 35
Зарегистрирован: 30.01.2006
Сообщения: 3132


СообщениеДобавлено: 08 Февраль, 2011 02:05    Заголовок сообщения: Ответить с цитатой

Narsil писал(а):
Вот. Да. Важное замечание. не экспоненциально, а полиномиально.
Как раз-таки экспоненциально=)
1 цикл = О(N), 2 = О(N^2).... x = O(N^x), где N - параметр, х - переменная. Время экспоненциально зависит от количества циклов.
Если бы было полиномиально, то было бы х = О(N^c1*х^c2), что бред.

Doredel, почитай что-нибудь про теорию сложности вычислений, все сразу станет понятно.
_________________
grammar nazi,
scientific whore.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Narsil
Grammar nazi
Grammar nazi


Возраст: 35
Зарегистрирован: 09.03.2007
Сообщения: 5516
Откуда: Волшебная страна

СообщениеДобавлено: 08 Февраль, 2011 11:44    Заголовок сообщения: Ответить с цитатой

Gabol, каюсь, дурак. Это я с прямым углом перепутал.
_________________
На опушке маленький мальчик плакал от страха и кричал: "Волк, волк!", а волк, стоя за кустом, с тоской думал, что главная беда с маленькими мальчиками - их совершенное неумение расставаться.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Lord GAD
Roses Gardener
Roses Gardener


Возраст: 23
Зарегистрирован: 04.02.2006
Сообщения: 1817


СообщениеДобавлено: 08 Февраль, 2011 12:45    Заголовок сообщения: Ответить с цитатой

Gabol писал(а):
Как раз-таки экспоненциально=)

полиномиально звучит умней и внушительней. я вникать в суть не вникаю, но аргумент на меня впечатление произвел Smile
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Gabol
Grammar nazi
Grammar nazi


Возраст: 35
Зарегистрирован: 30.01.2006
Сообщения: 3132


СообщениеДобавлено: 08 Февраль, 2011 20:19    Заголовок сообщения: Ответить с цитатой

Lord GAD, я просто тоже это "экспоненциально" увидел, возмутился, подумал.. И понял, что правда экспоненциально=)
И все-таки нет, не знаю, как насчет умней, но экспонента гораздо внушительнее полинома. Причем, полинома любой степени Very Happy
_________________
grammar nazi,
scientific whore.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Показать сообщения:   
Начать новую тему   Ответить на тему    Список форумов Roses -> Общий раздел -> Общий Часовой пояс: GMT + 4
На страницу Пред.  1, 2, 3  След.
Страница 2 из 3

 
Перейти:  
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах


Powered by phpBB © 2001, 2005 phpBB Group
Русская поддержка phpBB

Яндекс.Метрика

Anti Bot Question MOD - phpBB MOD against Spam Bots
Заблокировано регистраций: 18215