Автор Тема: ещё про цикл дейкстры  (Прочитано 28145 раз)

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: ещё про цикл дейкстры
« Ответ #15 : Июль 20, 2012, 12:43:47 pm »
Может быть... не спорю. Но у меня в голове никаких ЦД не было. Когда я прочитал ваше условие у меня в голове мгновенно возник этот код. И я все не мог понять почему у вас так громоздко выглядит решение. Я даже несколько раз перечитывал условие задачи... а вдруг что упустил  :)

Это ведь классика. Расчет итогов по группировкам.
Можно группировок сделать сколько угодно. И столько же будет IF'ов с ELSE'ами.

Например есть таблица
Склад | Номенклатура | Сумма
отсортированная по первым двум полям.

Две переменные: Склад, Номенклатура
Форыч, два IF'а (для текущего склада и номенклатуры)

Пока текущий элемент равен предыдущему накапливаем итог, в противном случае скидываем результаты в таблицу итогов и обнуляем счетчики.

Любой прикладник напишет это с закрытыми глазами, не отвлекаясь от WoW   ;)

info21

  • Newbie
  • *
  • Сообщений: 43
    • Просмотр профиля
    • Информатика-21
Re: ещё про цикл дейкстры
« Ответ #16 : Июль 20, 2012, 12:47:24 pm »
Там просто идеалогия важнее истины :-)
Точнее, там истина важнее эго недоучек.
Ничто так не воспитывает отвращение к "ИТ-профессионалам", как их навязчивые понты при невладении элементарной алгоритмикой.

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: ещё про цикл дейкстры
« Ответ #17 : Июль 20, 2012, 01:08:12 pm »
Там просто идеалогия важнее истины :-)
Точнее, там истина важнее эго недоучек.
хм... истина посередине..  8)
Идеология > Истина > Недоучки

vlad

  • Hero Member
  • *****
  • Сообщений: 1388
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #18 : Июль 20, 2012, 02:29:42 pm »
Я написал цикл буквально за минуту-другую, не отрывая ручки от бумаги...

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

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #19 : Июль 20, 2012, 02:31:47 pm »
Я, "распробовав" ЦД, теперь воспринимаю его как общую, наиболее регулярную форму цикла, с которой удобно работать при построении - и по которой потом можно выполнить любые целесообразные "свёртки".
С ЦД стоит начинать построение, если задача требует вложенных циклов или цикла с вложенным IF, где внутри IF идёт манипулирование переменными цикла.

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 481
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #20 : Июль 20, 2012, 02:34:27 pm »
Какими ошибками? При вводе с листка на экран очевидная опечатка не поменялось бы на c i на j?
Ну Вам эта ошибка очевидна, мне, например, нет. Я сильно не рассамтривал Ваш алгоритм, не анализировал его, но всё же с первого взгляда его суть я не понял...
А уж как я-то не понял второй хаскельный вариант - это что-то  :)
Понял только что вся эта байда фантастически неэффективна.
Здесь эффективность нафиг не нужна, но смотреть на это тошно.

vlad

  • Hero Member
  • *****
  • Сообщений: 1388
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #21 : Июль 20, 2012, 02:44:55 pm »
А уж как я-то не понял второй хаскельный вариант - это что-то  :)

Да, надо признать, что хаскельный вариант не очень. Самый нормальный оказался на SQL (не верю, что я говорю это, но это так).

vlad

  • Hero Member
  • *****
  • Сообщений: 1388
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #22 : Июль 20, 2012, 02:48:11 pm »
Я, "распробовав" ЦД, теперь воспринимаю его как общую, наиболее регулярную форму цикла, с которой удобно работать при построении - и по которой потом можно выполнить любые целесообразные "свёртки".
С ЦД стоит начинать построение, если задача требует вложенных циклов или цикла с вложенным IF, где внутри IF идёт манипулирование переменными цикла.

Не представляю, как имея на руках это месиво (ЦД с манипулированием переменными и кучей условий) можно получить нормальный свернутый вариант (простой цикл + функция). Проще сразу нормально написать. Или ты про какие-то другие "свертки" говорил?

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #23 : Июль 20, 2012, 02:57:18 pm »
Проще сразу нормально написать. Или ты про какие-то другие "свертки" говорил?

Да, я говорил про варианты без функции.

Вариант с функцией - конечно, можно, но не для такого же алгоритма? Кроме (ладно уж) понижения эффективности, ещё и есть момент дробления совсем маленького алгоритма, как бы :)
Я сразу отбросил вариант с функцией, потому что нужно придумывать интерфейс, через какие параметры две части алгоритма взаимодействуют... Морока тоже, короче.
« Последнее редактирование: Июль 20, 2012, 02:59:08 pm от Илья Ермаков »

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 481
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #24 : Июль 20, 2012, 03:03:51 pm »
Самый нормальный оказался на SQL (не верю, что я говорю это, но это так).
Тут опять каждый стал решать свою задачу, ибо строго не оговорено, что дано и что требуется получить. Во всяком случае, данный SQL-ный вариант не скажет, что ровно 5 задач решило 0 человек.

vlad

  • Hero Member
  • *****
  • Сообщений: 1388
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #25 : Июль 20, 2012, 04:17:31 pm »
Вариант с функцией - конечно, можно, но не для такого же алгоритма?

Гхм. А почему нет? Алгоритм не укладывается в тривиальный цикл. Запутаем читателя еще больше с помощью ЦД?

Кроме (ладно уж) понижения эффективности, ещё и есть момент дробления совсем маленького алгоритма, как бы :)

Ой, не надо про эффективность. Каждый раз когда речь заходила про эффективность ЦД оказывался где-то в конце. Про оптимизирующие компиляторы тоже все в курсе. И вообще, есть люди, для которых функция на 1000 строк не самая большая ;)

Я сразу отбросил вариант с функцией, потому что нужно придумывать интерфейс, через какие параметры две части алгоритма взаимодействуют... Морока тоже, короче.

Какая морока? Если в обероне завести тиривиальную функцию "морока" - то тем хуже для его читателей, которые будут продираться через ЦД :) Интерфейс очевиден из описания - принять индекс, вернуть следующий индекс (указатель/итератор). Какие еще варианты?

DIzer

  • Гость
Re: ещё про цикл дейкстры
« Ответ #26 : Июль 20, 2012, 09:19:53 pm »
Там просто идеалогия важнее истины :-)
Точнее, там истина важнее эго недоучек.
  :):D :D

DIzer

  • Гость
Re: ещё про цикл дейкстры
« Ответ #27 : Июль 20, 2012, 09:25:59 pm »

хм... истина посередине..  8)
Идеология > Истина > Недоучки
  ;D

DIzer

  • Гость
Re: ещё про цикл дейкстры
« Ответ #28 : Июль 20, 2012, 09:29:48 pm »
А так:

:) А так, боюсь что не совсем это верно - запросы с группировкой подразумевают соответствующее упорядочение данных (не хватает соответствующих секций ORDER BY)

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1953
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #29 : Июль 20, 2012, 09:43:09 pm »
Ладно, приз зрительских симпатий отдаю участнику ilovb за его решение на 1С -- когда я прочитал его алгоритм, я наконец понял что они там делали в императивных языках.
Да, конкретно эта задачка не очень красиво ложится на чистый ФП-язык с иммутабельными переменными, и по производительности тоже не очень получилось.
Ну да ладно, задача решена, а если бы возникли реальные проблемы из-за тормозов программы -- можно было бы переделать )))
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…