Oberon space

General Category => Общий раздел => Тема начата: Geniepro от Июль 20, 2012, 05:23:07 am

Название: ещё про цикл дейкстры
Отправлено: Geniepro от Июль 20, 2012, 05:23:07 am
На вражеском форуме новая тема про ЦД: http://forum.oberoncore.ru/viewtopic.php?f=82&t=4027
Там у Ермакова получился запутанный и глючный ЦД, походу он его ни разу не тестировал.
А вот что вышло бы на хацкеле, идеально подходящем для подобных задач по обработке текстов:
calc_stat = map length . groupПолный пример:
module Main

import Data.List

pasports = [ "123", "123", "234", "345", "345", "345" ]

calc_stat :: (Eq a) => [a] -> [Int]
calc_stat = map length . group

main = do
    print $ calc_stat pasports
Main> :main
[2,1,3]

ЗЫ. WinHUGS не может понять тип функции calc_stat, для него пришлось указать. GHCi понимает без проблем.
Впрочем, для глобальных функций всё равно принято специфицировать типы...
Название: Re: ещё про цикл дейкстры
Отправлено: Peter Almazov от Июль 20, 2012, 06:06:49 am
Это решение другой, более удобной для решателя, задачи  :)
В решении Ильи ответом является массив, по которому можно дать ответ на вопрос: скока человек решили ровно 5 задач? Ответ: stat[5] = 0, т.е. 0 человек.

А ЦД там можно выкинуть в конце. Он использовался на этапе рассуждений.
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Июль 20, 2012, 06:45:51 am
Это решение другой, более удобной для решателя, задачи  :)
В решении Ильи ответом является массив, по которому можно дать ответ на вопрос: скока человек решили ровно 5 задач? Ответ: stat[5] = 0, т.е. 0 человек.
Ок, тогда сложнее:
module Main where
import Data.List
import qualified Data.Map as Map

pasports = [ "123", "123", "234", "345", "345", "345", "456", "567", "567"
           , "789", "789", "789", "789", "789", "789"
           ]

stats = pasports
     |> group
     |> map length
     |> sort
     |> group
     |> map (\xs@(x:_) -> (x, length xs))
     |> Map.fromList

get_stat :: Int -> Int
get_stat n =
    case Map.lookup n stats of
        Nothing -> 0
        Just m  -> m

-- Список, по которому можно дать ответ на вопрос:
--      Cкока человек решили ровно 5 задач?
--      Ответ: stat[5] = 0, т.е. 0 человек.
solveds = map get_stat [0..10]

main = do
    print $ solveds !! 1    -- Сколько народа решило 1 задачу?
    print $ solveds !! 3    -- Сколько народа решило 3 задачи?
    print $ solveds !! 5    -- Сколько народа решило 5 задач?

(|>) :: a -> (a -> b) -> b
x |> f = f x; infixl 0 |>
Main> :main
2
1
0
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 20, 2012, 07:54:31 am
Ну и что в итоге-то выигрываем, в последнем варианте? Достаточно хитрая комбинация трансформаций... Что думать над циклом, что думать над ней... Только уровень абстракции гораздо выше - вам нужно правильно применить достаточно сложные по поведению общие средства к решению частной задачи... По моему убеждению, легче (и надёжнее) собирать из простых частных элементов, нежели комбинировать и параметризовать сложные обобщённые.

Кстати, сколько минут писали последнюю программу?

Я написал цикл буквально за минуту-другую, не отрывая ручки от бумаги...
Название: Re: ещё про цикл дейкстры
Отправлено: ilovb от Июль 20, 2012, 08:16:56 am
А так:
SELECT
ExamCount,
SUM(ExamCount) AS StatCount
FROM
(SELECT
PasNum AS PasNum,
COUNT(PasNum) AS ExamCount
FROM
Tab.Passports
GROUP BY
PasNum)

GROUP BY
ExamCount
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 20, 2012, 08:27:34 am
Этот вариант был бы прекрасен, если бы структура БД была открытой и документированной. Всё, что мы имеем, - это CSV или XLS-экспорт.
Можно было, правда, как вариант, быстренько залить в какой-нить MySQL и поиметь это дело запросами...
С другой стороны, всё равно CSV надо сначала как-то машинно преобразовать в дамп для загрузки.
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Июль 20, 2012, 08:31:48 am
Ну и что в итоге-то выигрываем, в последнем варианте? Достаточно хитрая комбинация трансформаций...
Да ничего особо хитрого там нет. Просто пошаговые приближения от исходных данных к требуемому результату...

Кстати, сколько минут писали последнюю программу?

Я написал цикл буквально за минуту-другую, не отрывая ручки от бумаги...
Несколько минут с подготовкой тестовых данных и тестированием...
А Ваш цикл на бумаге кишел ошибками, и если одну указал бы компилятор, то другую пришлось бы отлаживать тестами.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 20, 2012, 08:42:52 am
Какими ошибками? При вводе с листка на экран очевидная опечатка не поменялось бы на c i на j?
Название: Re: ещё про цикл дейкстры
Отправлено: ilovb от Июль 20, 2012, 09:07:26 am
Этот вариант был бы прекрасен, если бы структура БД была открытой и документированной. Всё, что мы имеем, - это CSV или XLS-экспорт.
Можно было, правда, как вариант, быстренько залить в какой-нить MySQL и поиметь это дело запросами...
С другой стороны, всё равно CSV надо сначала как-то машинно преобразовать в дамп для загрузки.

Тык к CSV тоже запросы можно делать. ADODB умеет.

ps. Упс... У меня там вместо sum count должен быть
Название: Re: ещё про цикл дейкстры
Отправлено: ilovb от Июль 20, 2012, 09:22:00 am
Эта задача чисто SQL-ная.

И решаться такие задачи имхо должны по возможности только на SQL.
Запрос к тексту не проблема. Можно сделать даже в виде скрипта VBS или JS.

Этот вариант не подойдет только тогда, когда нужно выжать максимум скорости.
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Июль 20, 2012, 09:57:53 am
Какими ошибками? При вводе с листка на экран очевидная опечатка не поменялось бы на c i на j?
Ну Вам эта ошибка очевидна, мне, например, нет. Я сильно не рассамтривал Ваш алгоритм, не анализировал его, но всё же с первого взгляда его суть я не понял...
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Июль 20, 2012, 09:59:42 am
На вражеском форуме новая тема про ЦД: http://forum.oberoncore.ru/viewtopic.php?f=82&t=4027
Там у Ермакова получился запутанный и глючный ЦД, походу он его ни разу не тестировал.
Ну, во первых, то не вражеский форум а просто альтернативный с очень альтернативными порядками и модераторами. Там просто идеалогия важнее истины :-)

Во-вторых, в силу его альтернативности, там сообщения имеют тенденцию бегать по всему форуму, периодически оказываясь то в архиве, то в закрытых разделах, поэтому просьба - не просто давать ссылку на пост с инфой, но и все ценное/краткое содержание, вставлять в виде цитаты в своем сообщении, дабы не зависить от колеблющейся линии партии того форума.

В данном случае прошу озвучить условие решаемой задачи.
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Июль 20, 2012, 10:55:03 am
... просьба - не просто давать ссылку на пост с инфой, но и все ценное/краткое содержание, вставлять в виде цитаты в своем сообщении, дабы не зависить от колеблющейся линии партии того форума.

В данном случае прошу озвучить условие решаемой задачи.

Цитата: Илья Ермаков
При расчёте статистики по результатам ЕГЭ в регионе у нас в ОРЦОКО пришлось кое-что дописывать, т.к. федеральное ПО ужасное и не считает всё, что нужно.
Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена.
Программист сортирует экспортированные из системы результаты экзаменов в Excel по полю "номер паспорта" и дальше сохраняет в CSV одну только эту колонку. Т.е. имеется последовательность строк с номерами паспортов, где каждый номер повторяется (рядом) столько раз, сколько человек сдавал экзаменов.
Программист сейчас ваяет на ББ процедурку, которая посчитает статистику.
Я тоже тут накидал алгоритм. Не напрягая мозги, получился сразу цикл Дейкстры. Тестировать не тестировал, написал на бумажке.
Правда, программист не хочет его брать, говорит, что не понимает  Колдует уже час над вложенными циклами, пытаясь, к тому же, это сделать прямо над TextMappers.Scanner.

Привожу свой вариант:
stat[i] имеет смысл количества человек, сдававших i экзаменов
обнуление массива stat
i := 0; j := 1; (* Инвариант: [i, j) - интервал из одинаковых номеров паспортов *)
WHILE (j < len) & (pass[j] = pass[i]) DO
   INC(j)
ELSIF (j < len) & (pass[j] # pass[i]) DO
   INC(stat[j - i]); i := j; j := i + 1
END;
IF i < len THEN (* чтобы алгоритм был применим к пустой последовательности *)
   INC(stat[j - i])
END
Название: Re: ещё про цикл дейкстры
Отправлено: ilovb от Июль 20, 2012, 11:27:24 am
Посмотрел на том форуме.... чета слишком заумно для такой задачи.

Прикладники классически пишут так:

Список = Новый Массив;
   Список.Добавить("10");
   Список.Добавить("10");
   Список.Добавить("20");
   Список.Добавить("30");
   Список.Добавить("30");
   Список.Добавить("30");
   Список.Добавить("40");
   Список.Добавить("50");
   Список.Добавить("50");
   Список.Добавить("50");
   
   МаксимумЭкзаменов = 100;
   
   Статистика = Новый Массив(МаксимумЭкзаменов);
   
   ТекЭлемент = Неопределено;
   КоличествоЭкзаменов = 0;
   
   Для Каждого Элемент Из Список Цикл
      
      Если Элемент = ТекЭлемент Тогда // считаем
         КоличествоЭкзаменов = КоличествоЭкзаменов + 1;
      Иначе // обрабатываем результат и берем следующий элемент
         Статистика[КоличествоЭкзаменов] = Статистика[КоличествоЭкзаменов] + 1;
         КоличествоЭкзаменов = 1;
         ТекЭлемент = Элемент;
      КонецЕсли;
      
   КонецЦикла;
   
   Статистика[КоличествоЭкзаменов] = Статистика[КоличествоЭкзаменов] + 1;
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 20, 2012, 12:17:30 pm
Ваш цикл тоже, по структуре, оптимизированный ЦД (где условие "пока не конец последовательности" вынесено).
Название: Re: ещё про цикл дейкстры
Отправлено: ilovb от Июль 20, 2012, 12:43:47 pm
Может быть... не спорю. Но у меня в голове никаких ЦД не было. Когда я прочитал ваше условие у меня в голове мгновенно возник этот код. И я все не мог понять почему у вас так громоздко выглядит решение. Я даже несколько раз перечитывал условие задачи... а вдруг что упустил  :)

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

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

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

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

Любой прикладник напишет это с закрытыми глазами, не отвлекаясь от WoW   ;)
Название: Re: ещё про цикл дейкстры
Отправлено: info21 от Июль 20, 2012, 12:47:24 pm
Там просто идеалогия важнее истины :-)
Точнее, там истина важнее эго недоучек.
Название: Re: ещё про цикл дейкстры
Отправлено: ilovb от Июль 20, 2012, 01:08:12 pm
Там просто идеалогия важнее истины :-)
Точнее, там истина важнее эго недоучек.
хм... истина посередине..  8)
Идеология > Истина > Недоучки
Название: Re: ещё про цикл дейкстры
Отправлено: vlad от Июль 20, 2012, 02:29:42 pm
Я написал цикл буквально за минуту-другую, не отрывая ручки от бумаги...

Похоже, что все задачи, где якобы блещет ЦД (неправильные циклы) на деле оказываются задачами на правильную декомпозицию: простой цикл + функция.  В данном случае функция будет возвращать индекс следующего элемента отличного от текущего, а цикл тупо итерировать и считать статистику.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 20, 2012, 02:31:47 pm
Я, "распробовав" ЦД, теперь воспринимаю его как общую, наиболее регулярную форму цикла, с которой удобно работать при построении - и по которой потом можно выполнить любые целесообразные "свёртки".
С ЦД стоит начинать построение, если задача требует вложенных циклов или цикла с вложенным IF, где внутри IF идёт манипулирование переменными цикла.
Название: Re: ещё про цикл дейкстры
Отправлено: Peter Almazov от Июль 20, 2012, 02:34:27 pm
Какими ошибками? При вводе с листка на экран очевидная опечатка не поменялось бы на c i на j?
Ну Вам эта ошибка очевидна, мне, например, нет. Я сильно не рассамтривал Ваш алгоритм, не анализировал его, но всё же с первого взгляда его суть я не понял...
А уж как я-то не понял второй хаскельный вариант - это что-то  :)
Понял только что вся эта байда фантастически неэффективна.
Здесь эффективность нафиг не нужна, но смотреть на это тошно.
Название: Re: ещё про цикл дейкстры
Отправлено: vlad от Июль 20, 2012, 02:44:55 pm
А уж как я-то не понял второй хаскельный вариант - это что-то  :)

Да, надо признать, что хаскельный вариант не очень. Самый нормальный оказался на SQL (не верю, что я говорю это, но это так).
Название: Re: ещё про цикл дейкстры
Отправлено: vlad от Июль 20, 2012, 02:48:11 pm
Я, "распробовав" ЦД, теперь воспринимаю его как общую, наиболее регулярную форму цикла, с которой удобно работать при построении - и по которой потом можно выполнить любые целесообразные "свёртки".
С ЦД стоит начинать построение, если задача требует вложенных циклов или цикла с вложенным IF, где внутри IF идёт манипулирование переменными цикла.

Не представляю, как имея на руках это месиво (ЦД с манипулированием переменными и кучей условий) можно получить нормальный свернутый вариант (простой цикл + функция). Проще сразу нормально написать. Или ты про какие-то другие "свертки" говорил?
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 20, 2012, 02:57:18 pm
Проще сразу нормально написать. Или ты про какие-то другие "свертки" говорил?

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

Вариант с функцией - конечно, можно, но не для такого же алгоритма? Кроме (ладно уж) понижения эффективности, ещё и есть момент дробления совсем маленького алгоритма, как бы :)
Я сразу отбросил вариант с функцией, потому что нужно придумывать интерфейс, через какие параметры две части алгоритма взаимодействуют... Морока тоже, короче.
Название: Re: ещё про цикл дейкстры
Отправлено: Peter Almazov от Июль 20, 2012, 03:03:51 pm
Самый нормальный оказался на SQL (не верю, что я говорю это, но это так).
Тут опять каждый стал решать свою задачу, ибо строго не оговорено, что дано и что требуется получить. Во всяком случае, данный SQL-ный вариант не скажет, что ровно 5 задач решило 0 человек.
Название: Re: ещё про цикл дейкстры
Отправлено: vlad от Июль 20, 2012, 04:17:31 pm
Вариант с функцией - конечно, можно, но не для такого же алгоритма?

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

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

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

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

Какая морока? Если в обероне завести тиривиальную функцию "морока" - то тем хуже для его читателей, которые будут продираться через ЦД :) Интерфейс очевиден из описания - принять индекс, вернуть следующий индекс (указатель/итератор). Какие еще варианты?
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 20, 2012, 09:19:53 pm
Там просто идеалогия важнее истины :-)
Точнее, там истина важнее эго недоучек.
  :):D :D
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 20, 2012, 09:25:59 pm

хм... истина посередине..  8)
Идеология > Истина > Недоучки
  ;D
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 20, 2012, 09:29:48 pm
А так:

:) А так, боюсь что не совсем это верно - запросы с группировкой подразумевают соответствующее упорядочение данных (не хватает соответствующих секций ORDER BY)
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Июль 20, 2012, 09:43:09 pm
Ладно, приз зрительских симпатий отдаю участнику ilovb за его решение на 1С -- когда я прочитал его алгоритм, я наконец понял что они там делали в императивных языках.
Да, конкретно эта задачка не очень красиво ложится на чистый ФП-язык с иммутабельными переменными, и по производительности тоже не очень получилось.
Ну да ладно, задача решена, а если бы возникли реальные проблемы из-за тормозов программы -- можно было бы переделать )))
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 21, 2012, 08:10:15 am
Я, "распробовав" ЦД, теперь воспринимаю его как общую, наиболее регулярную форму цикла, с которой удобно работать при построении - и по которой потом можно выполнить любые целесообразные "свёртки".
С ЦД стоит начинать построение, если задача требует вложенных циклов или цикла с вложенным IF, где внутри IF идёт манипулирование переменными цикла.
Жуть какая то -вроде  классическая задача на применение сортировки подсчетом...- вместо того, что бы почитать нормальные книги (не Сиськина с Вертом) -очередные пляски вокруг идола (ЦД)...
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 22, 2012, 04:46:56 pm
Цитата: Илья Ермаков
При расчёте статистики по результатам ЕГЭ в регионе у нас в ОРЦОКО пришлось кое-что дописывать, т.к. федеральное ПО ужасное и не считает всё, что нужно.
Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена.
Программист сортирует экспортированные из системы результаты экзаменов в Excel по полю "номер паспорта" и дальше сохраняет в CSV одну только эту колонку. Т.е. имеется последовательность строк с номерами паспортов, где каждый номер повторяется (рядом) столько раз, сколько человек сдавал экзаменов.
Программист сейчас ваяет на ББ процедурку, которая посчитает статистику.
Я тоже тут накидал алгоритм. Не напрягая мозги, получился сразу цикл Дейкстры. Тестировать не тестировал, написал на бумажке.
Правда, программист не хочет его брать, говорит, что не понимает  Колдует уже час над вложенными циклами, пытаясь, к тому же, это сделать прямо над TextMappers.Scanner.
(жирным шрифтом выделено мной).
В который раз одно и то же на оберонкоре... задачу ставить/понимать не хотим, но сразу предлагаем решение "не напрягая мозги" и получаем... цикл Дейкстры... с ошибками и без тестирования...
"Всё это было бы смешно, когда бы не было, так грустно"...
1. И не смущает, что нет постановки задачи, просто декларируется: "Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена"... Кому это нужно?.. Для чего это нужно?.. Какая статистика вообще востребована?.. Ну, вот, Илье потребовалось "это", а кому-то "это" и ещё "вот это"... а кому-то... важен средний балл по математике... или биологии, или средний балл по всем предметам тех, кто сдавал математику и биологию.
2. И не смущает, что при такой постановке задачи "софт" получается "ужасным и не полным"... Он реально не может быть другим... потому что, придёт ещё один "илья" со своим видением и допишет ещё 20-40 строк с ужасным циклом Дейкстры, который в очередной раз никто не поймёт...
3. И не смущает, что писать этот самый цикл Дейкстры берутся... "не напрягая мозги"... А мозгам, вообще говоря, полезно, когда их напрягают... примерно также, как мышцам... Мышцы напрягают, когда работают физически, а мозг - когда умственно... Собственно, мозг - это некая "интеллектуальная мышца"... :) И вот если мозги напрячь, то... получим несколько простых, но полезных идей...i := 0;
while (i < cntItems) do begin
        cur_pass := pass[i];
        k := 0;
        while (i < cntItems) and (cur_pass = pass[i]) do begin
                inc(k);     // k - количество сданных экзаменов учащимся с данным паспортом
                inc(i);
        end;
        inc(stat[k]);    // stat[k] массив, где хранятся количества сдавших k-ое количество экзаменов (размерность от 0 до Количество экзаменов, размеры элементов массива (положительное целое) должны вмещать количество сдававших)
end;

А что реально смущает, так это то... что они ещё и учат...
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 22, 2012, 05:19:17 pm
Не знаю чему они учат...но минимальными знаниями по алгоритмике преподаватель владеть (ИМХО) ОБЯЗАН...
Что касается задачи....пусть данные о количестве экзаменов содержатся в массиве  exams[1..Max], пусть решение будет хранится
в массиве res[0..9]  инициализированном нулями  тогда алгоритм (Паскаль) сводится к
...
for i:=1 to Max do inc(res[exams[i]])

что  есть сортировка подсчетом в ЧИСТОМ виде....
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 22, 2012, 07:35:58 pm
Гхм. А почему нет? Алгоритм не укладывается в тривиальный цикл. Запутаем читателя еще больше с помощью ЦД?
Да я не против решения с процедурой. Как ты совершенно верно заметил, поборем нестандартность декомпозицией :) Но в арсенале полезно иметь и то, и то.
Всё больше убеждаюсь, что "вытаскивание" на один уровень всех условий, которые иначе были бы во вложенных IF-ах и циклах - очень полезный метод при построении алгоритма. Чисто структурная сложность алгоритма становится ниже - не думаем о последовательности проверок, циклов, о вложенности - а просто регулярно описываем все ситуации.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 22, 2012, 07:41:48 pm


Мы не разрабатываем ПО ЕГЭ. Вообще, львиная доля работы сейчас в той организации, куда меня пригласили на должность зам. директора, - внедрение и организация использования в масштабах региона таких систем, как, например, автоматизированная система школ.
Претензии к "ущербности" ПО статистики - к Федеральному центру тестирования.
Остальные рассуждения "а зачем нужна цифра" хороши, когда эту цифру от вас не требует в режиме "надо уже вчера", например, аппарат губернатора. А официальное ПО её дать не может.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 22, 2012, 07:47:55 pm
Не надо полагаться на то, что данные из внешнего источника будут представлены в нужной последовательности или группировке, или отфильтрованы так, как требуется для данной задачи (не ленитесь преобразовывать... но не сами данные, а текущее представление о данных).
Для задачи однократно посчитать и как можно быстрее самое правильное решение - это отсортировать CSV прямо в Excel... А программист занимается в период ЕГЭ вообще не программированием, а "любовью" с ЕГЭ-шной системой статистики.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 22, 2012, 07:52:00 pm
Что касается задачи....пусть данные о количестве экзаменов содержатся в массиве  exams[1..Max], пусть решение будет хранится
в массиве res[0..9]  инициализированном нулями  тогда алгоритм (Паскаль) сводится к

У нас нет "данных о количестве экзаменов".
У нас есть экспорт всех результатов всех участников по всем экзаменам. Т.е. определить количество экзаменов, сданных участником, можно, подсчитав, сколько строк в экспорте с его номером паспорта.
Так что Вы куда-то не в ту степь.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 22, 2012, 07:58:49 pm
У alexus-а опять диагностируем манию величия.
Сам он, имея богатый опыт и сильные идеи, так никого им и не научил.. И, видимо, не научит. Гораздо приятнее ходить по форумам и весям и намекать всем про то, что он эти идеи имеет и что никто вокруг ничего не понимает.
Хотя залезает он на такой уровень абстракций, что все его рассуждения просто не получается воспринимать как "одновариантные". Т.е. легко представляется другая картина мира, такая же красивая, как и его. Работу же на уровне обобщения пониже он презирает и поливает г-ном, это все уже знают :)
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 22, 2012, 08:02:07 pm

Так что Вы куда-то не в ту степь.
Вту степь..я вообще не знаю в каком виде у вас данные и поэтому наложил условие на них - чтобы удовлетворить ему
достаточно добавить еще один цикл...-который  определяется ВАШИМИ данными..
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Июль 22, 2012, 08:19:02 pm
Не надо полагаться на то, что данные из внешнего источника будут представлены в нужной последовательности или группировке, или отфильтрованы так, как требуется для данной задачи (не ленитесь преобразовывать... но не сами данные, а текущее представление о данных).
Для задачи однократно посчитать и как можно быстрее самое правильное решение - это отсортировать CSV прямо в Excel... А программист занимается в период ЕГЭ вообще не программированием, а "любовью" с ЕГЭ-шной системой статистики.
Кстати, да. Когда мне доводится обрабатывать массивы данных и строить по ним статистику, то частенько я не пишу специализированную прогу, и даже матлаб не задействую, а просто всю эту статистику считаю и визуализирую в excel'e. Подозреваю что и эту задачу в excel'e вполне можно решить.

А особо excel'e-продвинутые пишут прогу в оном excel'e, чтобы оно автоматом все считало, без ручных манипуляций.
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 22, 2012, 08:29:13 pm
 ;) И..в каком месте здесь цикл Дейкстры?
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Июль 22, 2012, 09:06:15 pm
;) И..в каком месте здесь цикл Дейкстры?
А фиг знает. В данной задаче использовать конструкции которые привносят тьюринг-полноту явно не оправдано (ибо черевато ошибками).
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 22, 2012, 09:23:33 pm
Не знаю чему они учат...но минимальными знаниями по алгоритмике преподаватель владеть (ИМХО) ОБЯЗАН...
Что касается задачи....пусть данные о количестве экзаменов содержатся в массиве  exams[1..Max], пусть решение будет хранится
в массиве res[0..9]  инициализированном нулями  тогда алгоритм (Паскаль) сводится к
...
for i:=1 to Max do inc(res[exams[i]])

что  есть сортировка подсчетом в ЧИСТОМ виде....
Всё хорошо... только это какая-то другая задача... В исходной "постановке" было сказано: "Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена"...
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 22, 2012, 09:32:57 pm


Мы не разрабатываем ПО ЕГЭ.
Это радует...

Вообще, львиная доля работы сейчас в той организации, куда меня пригласили на должность зам. директора, - внедрение и организация использования в масштабах региона таких систем, как, например, автоматизированная система школ.
Региону... мои сочувствия... При таком подходе к делу... не позавидуешь ему. (о подходе к делу сказано ниже)

Претензии к "ущербности" ПО статистики - к Федеральному центру тестирования.
Само собой...

Остальные рассуждения "а зачем нужна цифра" хороши, когда эту цифру от вас не требует в режиме "надо уже вчера", например, аппарат губернатора. А официальное ПО её дать не может.
Это я слышу каждый раз, когда разговариваю с работниками АСУ предприятий... От них всегда требуют чего-то такого... и всегда вчера... Мода такая видимо у руководителей... или... может быть это такой подход к делу у самих работников АСУ?.. Не имея представления о системе, как едином целом, они всё время натыкаются на частности, а частностей столько, что... вспоминается "проклятие размерности". Деминг однажды сказал правильную вещь... "почему мы, не найдя время сразу сделать правильно, потом находим гораздо больше времени на исправления"... (понимаю, что это всего лишь риторика, но...)
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 22, 2012, 09:45:31 pm
У alexus-а опять диагностируем манию величия
Ну, кого что заботит... Правда забавно, когда у других диагностируют "манию величия", говоря от своего имени... во множественном числе...
Лучше бы сказали, Ваша Скромность, задачка правильно решена аль нет?.. Нужен ли пресловутый цикл Дейкстры... или без него решение проще и нагляднее? (Только мозги напрягите...)

Сам он, имея богатый опыт и сильные идеи, так никого им и не научил..
Это видимо опять от скромности... если Ермакова не научил, значит никого... ну-ну...

И, видимо, не научит.
А зачем?.. Кто хочет, тот научится... Не педагог я, Ваша Скромность.

Гораздо приятнее ходить по форумам и весям и намекать всем про то, что он эти идеи имеет и что никто вокруг ничего не понимает.
А ссылку не выложите... про то где я намекаю?.. И вообще... эти высказывания имеют хоть какое-то отношение к тем решениям Вашей задачи, которые предоставили Вы и я?.. Или это от скромности пронесло?..

Хотя залезает он на такой уровень абстракций, что все его рассуждения просто не получается воспринимать как "одновариантные". Т.е. легко представляется другая картина мира, такая же красивая, как и его. Работу же на уровне обобщения пониже он презирает и поливает г-ном, это все уже знают :)
Работа на любом уровне обобщений мне интересна и приятна... А вот когда с умным видом подают чушь (это я про Ваш пример с циклом Дейкстры)... то это и поливать не надо... всё одно - не вырастет... зачахнет.
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 22, 2012, 10:44:58 pm

Всё хорошо... только это какая-то другая задача... В исходной "постановке" было сказано: "Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена"...
Хе хе, именно ЭТУ задачу я и решил...и СПЕЦИАЛЬНО привел решение в таком виде чтобы было видно что ЦД -здесь и не пахнет.... по СМЫСЛУ задачи у нас есть зависимость(в каком то виде):  ученик->кол.во сданных экзаменов, пусть они хранятся в массиве exams[], его размер (Max)=количеству учеников, i-тый элемент массива=количество экзаменов сданных i-тым учеником, это количество варьируется в диапазоне от 0..9, искомые величины накапливаются в массиве res[] (например,
в res[1] будет содержаться число учеников сдавших 1 экзамен) элементарным подсчетом...и делается это одной строчкой. Многоточие перед ЭТОЙ строчкой обозначает код заполняющий массив exams из исходных данных.
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 23, 2012, 04:44:46 am

Всё хорошо... только это какая-то другая задача... В исходной "постановке" было сказано: "Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена"...
Хе хе, именно ЭТУ задачу я и решил...и СПЕЦИАЛЬНО привел решение в таком виде чтобы было видно что ЦД -здесь и не пахнет.... по СМЫСЛУ задачи у нас есть зависимость(в каком то виде):  ученик->кол.во сданных экзаменов, пусть они хранятся в массиве exams[], его размер (Max)=количеству учеников, i-тый элемент массива=количество экзаменов сданных i-тым учеником, это количество варьируется в диапазоне от 0..9, искомые величины накапливаются в массиве res[] (например,
в res[1] будет содержаться число учеников сдавших 1 экзамен) элементарным подсчетом...и делается это одной строчкой. Многоточие перед ЭТОЙ строчкой обозначает код заполняющий массив exams из исходных данных.
Спасибо, понял... Трудность понимания данного решения была в том, что не приведено заполнение массива exams[], поэтому я предположил, что данные в exams[] - просто позиции ведомостей, где каждому выпускнику поставлена (положительная) оценка (так было в исходном примере).
А вообще обсуждать решение подобных задач - пустая трата времени. Я бы не стал в это влезать, если бы не очередная буффонада про "цикл Дейкстры"...
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 23, 2012, 05:04:18 am
Всё хорошо... только это какая-то другая задача... В исходной "постановке" было сказано: "Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена"...
Хе хе, именно ЭТУ задачу я и решил...и СПЕЦИАЛЬНО привел решение в таком виде чтобы было видно что ЦД -здесь и не пахнет.... по СМЫСЛУ задачи у нас есть зависимость(в каком то виде):  ученик->кол.во сданных экзаменов, пусть они хранятся в массиве exams[], его размер (Max)=количеству учеников, i-тый элемент массива=количество экзаменов сданных i-тым учеником, это количество варьируется в диапазоне от 0..9, искомые величины накапливаются в массиве res[] (например,
в res[1] будет содержаться число учеников сдавших 1 экзамен) элементарным подсчетом...и делается это одной строчкой. Многоточие перед ЭТОЙ строчкой обозначает код заполняющий массив exams из исходных данных.
В исходном варианте у Вас было сказано:
пусть данные о количестве экзаменов содержатся в массиве exams[1..Max]
Теперь Вы пишите, что "они хранятся в массиве exams[], его размер (Max)=количеству учеников". Путаница какая-то...
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 23, 2012, 05:20:36 am
Не надо полагаться на то, что данные из внешнего источника будут представлены в нужной последовательности или группировке, или отфильтрованы так, как требуется для данной задачи (не ленитесь преобразовывать... но не сами данные, а текущее представление о данных).
Для задачи однократно посчитать и как можно быстрее самое правильное решение - это отсортировать CSV прямо в Excel... А программист занимается в период ЕГЭ вообще не программированием, а "любовью" с ЕГЭ-шной системой статистики.
Кстати, да. Когда мне доводится обрабатывать массивы данных и строить по ним статистику, то частенько я не пишу специализированную прогу, и даже матлаб не задействую, а просто всю эту статистику считаю и визуализирую в excel'e. Подозреваю что и эту задачу в excel'e вполне можно решить.

А особо excel'e-продвинутые пишут прогу в оном excel'e, чтобы оно автоматом все считало, без ручных манипуляций.
Мысль не доведена до логического завершения... а жаль. В таком (недодуманном) варианте программисты так и останутся "мальчиками-на-побегушках"... Незавидно.
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 23, 2012, 06:28:34 am
Всё хорошо... только это какая-то другая задача... В исходной "постановке" было сказано: "Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена"...
Хе хе, именно ЭТУ задачу я и решил...и СПЕЦИАЛЬНО привел решение в таком виде чтобы было видно что ЦД -здесь и не пахнет.... по СМЫСЛУ задачи у нас есть зависимость(в каком то виде):  ученик->кол.во сданных экзаменов, пусть они хранятся в массиве exams[], его размер (Max)=количеству учеников, i-тый элемент массива=количество экзаменов сданных i-тым учеником, это количество варьируется в диапазоне от 0..9, искомые величины накапливаются в массиве res[] (например,
в res[1] будет содержаться число учеников сдавших 1 экзамен) элементарным подсчетом...и делается это одной строчкой. Многоточие перед ЭТОЙ строчкой обозначает код заполняющий массив exams из исходных данных.
В исходном варианте у Вас было сказано:
пусть данные о количестве экзаменов содержатся в массиве exams[1..Max]
Теперь Вы пишите, что "они хранятся в массиве exams[], его размер (Max)=количеству учеников". Путаница какая-то...
Да так оно и есть - количество экзаменов сданных учеником является элементом этого массива всего этих элементов
Max штук-это можно записать как exams[1..Max] и массив exams[] содержит "данные о количестве экзаменов" а еще он целочисленный (как и res[])....  а вообще тяжко писать на Experia Mini -полноценные пояснения к алгоритму на 1 строку (морально тяжело).
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 23, 2012, 06:50:12 am

А вообще обсуждать решение подобных задач - пустая трата времени. Я бы не стал в это влезать, если бы не очередная буффонада про "цикл Дейкстры"...
Насчет ЦД-предлагаю убогих не трогать без необходимости...как говорится -хорошая свинья при желании всегда грязь найдет,  к тому же, пока они водят вокруг нового идола хороводы в коровнике - вред от них локализован. Конечно противно, когда
преподаватель у которого "практики выше крыши", и является "управленец с 10 летним стажем"  опускается до низкопробной демагогии (в который уже раз) когда требуется проанализировать ситуацию,показать минимальную грамотность, аргументировать позицию... но... бог ему судья.
Название: Re: ещё про цикл дейкстры
Отправлено: info21 от Июль 23, 2012, 07:11:01 am
Забавно.
Была указана полезная простенькая тренажерная задачка из разряда "сделать нечто конкретным методом", коих в обучении нужно иметь множество, а по данной теме их дефицит, чем оригинальный пост и был мотивирован,
-- а какое полетело во все стороны от этого альтернативного вентилятора говно.

Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 23, 2012, 07:16:32 am
Забавно.
Была указана полезная простенькая тренажерная задачка из разряда "сделать нечто конкретным методом", коих в обучении нужно иметь множество, а по данной теме их дефицит, чем оригинальный пост и был мотивирован,
-- а какое полетело во все стороны от этого альтернативного вентилятора говно.
ну да, ну да.... :(
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 23, 2012, 07:44:53 am
Забавно.
Была указана полезная простенькая тренажерная задачка из разряда "сделать нечто конкретным методом", коих в обучении нужно иметь множество, а по данной теме их дефицит, чем оригинальный пост и был мотивирован,
-- а какое полетело во все стороны от этого альтернативного вентилятора говно.
Как всегда... всё с точностью, до наоборот... Из того, что написал Илья (http://oberspace.dyndns.org/index.php/topic,288.msg6900.html#msg6900) не следует,... ещё немного и здесь будет оберонкоре № 2... (грусть и тоска...)
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Июль 23, 2012, 07:51:55 am
Забавно.
Была указана полезная простенькая тренажерная задачка из разряда "сделать нечто конкретным методом", коих в обучении нужно иметь множество, а по данной теме их дефицит, чем оригинальный пост и был мотивирован,
-- а какое полетело во все стороны от этого альтернативного вентилятора говно.
Дык это ж вентилятор! Что на него набросишь, то и полетит. В данном случае на него набросили решение через ЦД элементарной задачки. :-)
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 23, 2012, 07:56:05 am
Забавно.
Была указана полезная простенькая тренажерная задачка из разряда "сделать нечто конкретным методом", коих в обучении нужно иметь множество, а по данной теме их дефицит, чем оригинальный пост и был мотивирован,
-- а какое полетело во все стороны от этого альтернативного вентилятора говно.
Дык это ж вентилятор! Что на него набросишь, то и полетит. В данном случае на него набросили решение через ЦД элементарной задачки. :-)
то есть говно?  ;)
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 23, 2012, 08:10:29 am

... ещё немного и здесь будет оберонкоре № 2... (грусть и тоска...)
  :D не каркайте! большинству участников этого форума в маразм впадать рановато. правила здесь либеральные
(что посеешь то и пожнешь - с гарантией!), а опыта маловато для оголтелой быдлодемагогии...
Название: Re: ещё про цикл дейкстры
Отправлено: albobin от Июль 23, 2012, 08:53:10 am
Забавно слушать ( в т.ч и себя) спор о абсолютной хорошести или нехорошести того или иного решения. Типа зачем ЦД, лучше вложенные циклы и т.п.  Другой посмотрит и скажет, да тут ваще можно обойтись утилитами cat,cat,sort и uniq (естественно в Линухе).

Речь ведь всё же наверное о том, что если в багаже есть удачные шаблоны, то грех ими не пользоваться , оставив мозгам задачи по "умнее". И "технику надо ставить" в том числе и на простых тупых задачках, несмотря на обилие вариантов ну уж самых "оптимальных", которые тоже конечно нужно знать.
Название: Re: ещё про цикл дейкстры
Отправлено: albobin от Июль 23, 2012, 08:57:21 am
В предыдущем  сообщении надо 'cat,cut,sort и uniq'
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 23, 2012, 09:40:18 am
Забавно слушать ( в т.ч и себя) спор о абсолютной хорошести или нехорошести того или иного решения. Типа зачем ЦД, лучше вложенные циклы и т.п.  Другой посмотрит и скажет, да тут ваще можно обойтись утилитами cat,cat,sort и uniq (естественно в Линухе).

:D  вон оно как, оказывается на самом деле!  ;D Alexus, а вы говорите второй коровник - не вижу ни каких оснований, нда, решительно не вижу....
Название: Re: ещё про цикл дейкстры
Отправлено: albobin от Июль 23, 2012, 09:57:39 am
:D  вон оно как, оказывается на самом деле!
И как?И что?
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 23, 2012, 10:18:46 am
:D  вон оно как, оказывается на самом деле!
И как?И что?
"Забавно слушать ( в т.ч и себя)" -вот так!, "спор о абсолютной хорошести или нехорошести того или иного решения."  -вот это ;)  ;D
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Июль 23, 2012, 10:31:50 am
Забавно слушать ( в т.ч и себя) спор о абсолютной хорошести или нехорошести того или иного решения. Типа зачем ЦД, лучше вложенные циклы и т.п.  Другой посмотрит и скажет, да тут ваще можно обойтись утилитами cat,cat,sort и uniq (естественно в Линухе).

Речь ведь всё же наверное о том, что если в багаже есть удачные шаблоны, то грех ими не пользоваться , оставив мозгам задачи по "умнее". И "технику надо ставить" в том числе и на простых тупых задачках, несмотря на обилие вариантов ну уж самых "оптимальных", которые тоже конечно нужно знать.
Кстати, да. В том смысле, что ЦД возможно хорош для тех случаев когда мы пишем write-only код, когда нам надо написать что-то минимально включая мозг (и при этом чтобы оно работало корректно) и нас не волнует сопровождаемость этого кода. То есть это типичное скриптовое применение языка. Я бы сравнил это с написанием кода на перле с активным использованием регулярных варажений. Получается правильно, пишется быстро, мозг задействуется минимально, код получается абсолютно не поддерживаемый (если что-то нужно изменить - проще выбросить и написать с нуля).

Но обучать только такому подходу конечно же нельзя. Всегда нужно показывать, что задача имеет множество вариантов решения и что для вот такое решение будет хорошо вот в этом случае, а вот такое в другом (при этом задача алгоритмически остается одной и той же).
Название: Re: ещё про цикл дейкстры
Отправлено: albobin от Июль 23, 2012, 10:48:39 am
2 DIzer
В реплике, что Вас воодушевила, было и продолжение.
Удачные подходы (техника, как хотите назовите) проявляют себя наилучшим образом в общей сумме частных проблемок, и вовсе не обязательно в каждой из них.
Название: Re: ещё про цикл дейкстры
Отправлено: albobin от Июль 23, 2012, 10:55:01 am
В том смысле, что ЦД возможно хорош для тех случаев когда мы пишем write-only код
Странно, что такого нечитабельного в ЦД ?
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 23, 2012, 10:55:13 am
2albobin - ничего не имею против(в том числе и продолжения).. ;D
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Июль 23, 2012, 11:00:59 am
В том смысле, что ЦД возможно хорош для тех случаев когда мы пишем write-only код
Странно, что такого нечитабельного в ЦД ?
Лучше задать вопрос иначе - а что в нем читабельного? :-) И не в самом ЦД как таковом, а в решениях различных задач на нем.
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 23, 2012, 11:08:53 am
В том смысле, что ЦД возможно хорош для тех случаев когда мы пишем write-only код
Странно, что такого нечитабельного в ЦД ?
Лучше задать вопрос иначе - а что в нем читабельного? :-) И не в самом ЦД как таковом, а в решениях различных задач на нем.
Ну как же..Вот не далее как пару дней назад, один известный в определенных кругах специалист , стал решать школьную задачку и...вуаля ЦД! аж мозги свело...
Название: Re: ещё про цикл дейкстры
Отправлено: ilovb от Июль 23, 2012, 11:23:17 am
В том смысле, что ЦД возможно хорош для тех случаев когда мы пишем write-only код
Странно, что такого нечитабельного в ЦД ?

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

Сам люблю извращаться, но стараюсь это делать только в сугубо личном коде. Напишу и любуюсь.... какой я молодец... ::)
Дедушка Фрейд все подлец... никуда не денешься... :)
Название: Re: ещё про цикл дейкстры
Отправлено: ilovb от Июль 23, 2012, 11:39:08 am
И да, кстати, есть один момент... Если чел задачу первый раз решает, то там в голове тараканы бывает сходняк устраивают с массовой попойкой... Нео с крыши первый раз тоже нае%?№лся... ибо мозг засран матрицей был...
В общем первый раз хоть тфкп применяй, но в релизе изволь уровень школьной арифметики выдерживать  ;D
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 23, 2012, 11:51:56 am
Приходится сначала притормозить, затем перестроиться, включить мозг, сжечь кучу калорий, постичь истину, попытаться понять профит от изварщения, разочароваться, послать мысленно проклятия автору, сплюнуть в раздражении (либо переписать сие почеловечьи), ну и вновь набирать темп, а тут как водится обед ужо....  ;D

Эк какой вы  "впечатлительный"-может вам стоит в коровне закалить психику и организм? -во избежании "треволнений"...
Название: Re: ещё про цикл дейкстры
Отправлено: ilovb от Июль 23, 2012, 11:55:10 am
А вас такое не напрягает?
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 24, 2012, 06:52:01 am
Конечно противно, когда преподаватель у которого "практики выше крыши", и является "управленец с 10 летним стажем"
Не "управленец" - чиновник... Принципиальная разница в том, что управленец не только воздействует на субъект, но и принимает меру ответственности... А чиновник отвечать не хочет, критику не терпит, мнение имеет только то, что не противоречит "уставу"... (дабы убедится возвращаемся к началу топика... и не только этого... топика). Честно говоря, жаль его... имел шанс...
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 25, 2012, 02:50:21 pm
по СМЫСЛУ задачи у нас есть зависимость(в каком то виде):  ученик->кол.во сданных экзаменов, пусть они хранятся в массиве exams[], его размер (Max)=количеству учеников, i-тый элемент массива=количество экзаменов сданных i-тым учеником
У Вас нет этих данных, Вам их придётся сначала подготовить, и это будет уже совсем другой, отсутствующий у Вас кусок алгоритма.
Кроме того, в исходных данных у Вас будут не номера учеников, а их номера паспортов, по которым Вы не проиндексируетесь.
Перечитайте внимательно условие.
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 25, 2012, 08:27:57 pm

У Вас нет этих данных, Вам их придётся сначала подготовить, и это будет уже совсем другой, отсутствующий у Вас кусок алгоритма.
Кроме того, в исходных данных у Вас будут не номера учеников, а их номера паспортов, по которым Вы не проиндексируетесь.
Перечитайте внимательно условие.
1. Я ЧИТАЛ
2.Разумеется нет- для того что бы его составить,задача должна быть поставлена более четко.
3. А я вообще не представляю что такое "номера паспорта" (числа это или набор литер)- но знаю что им можно вполне  сопоставить
последовательность целых чисел начиная  с единицы -большего и не нужно.
Но суть  Илья в другом- собственно я просто показал, что  сама по себе задача сводится к элементарному подсчету,в подходящей
"системе координат" без всякого ЦД и танцев -обсеранцев вокруг него.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 26, 2012, 05:59:17 pm
Так сопоставьте сначала, напишите цикл, нумерующий эти номера.

Короче, возьмите конкретный пример входных данных, текстовый файл, приведённый ниже, и подумайте, сколько ещё придётся дописать преобразований, прежде чем применить написанный Вами "элементарный подсчёт".

5409135678
5409135678
5406995567
5406995567
5406995567
5406995567
5406995567
5406995579
5406995579
5406995579

(это фрагмент экспорта, говорящий о том, что один человек сдал 4 экзамена, другой - 5, третий - 3).
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 26, 2012, 06:04:34 pm
Вообще, отношение к ЦД такое же, какое долгое время была у русскоязычных программёров к SWITCH-методу Шалыто. Сколько Абрамыча по форумам поливали, что "ничего там нет, это нахрен не нужно, это банально, это тупо, мы и так код пишем прекрасно без всяких автоматов" и проч.
Хотя совершенно очевидно, что это метод, который позволяет во многих ситуациях регуляризовать решение задачи. Как можно запрограммировать состояние объекта и его изменение через раздельные переменные (булевы признаки и проч.) - и всегда будут и случаи, и сторонники, когда это будет, вроде, нагляднее. С другой стороны, проводились сравнения для сложных задач, что программист, нахреначивший кучу логических признаков и их изменения в разных местах, допускал много ошибок и долго отлаживался, а программист, вводящий одну переменную состояния и анализировавший регулярным образом все случаи, успешно решал задачу.

Так и ЦД позволяет по-другому подойти к построению алгоритма, вытащив на один уровень то, что расслоено обычно по нескольким. Иметь в арсенале такую штуку очень полезно.
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Июль 26, 2012, 07:06:36 pm
Так и ЦД позволяет по-другому подойти к построению алгоритма, вытащив на один уровень то, что расслоено обычно по нескольким. Иметь в арсенале такую штуку очень полезно.
В арсенале нужно иметь действительно самые разные штуки. И ЦД и goto и рекурсию и много иных разных. Достаточно глупо превозносить какую-то одну методику над другими.
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Июль 26, 2012, 07:08:18 pm
Кстати, вот есть еще несправедливо забытый всеми цикл-паук, который по сути является дальнейшим развитием ЦД (там больше контроля).
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 26, 2012, 08:31:39 pm
Вообще, отношение к ЦД такое же, какое долгое время была у русскоязычных программёров к SWITCH-методу Шалыто. Сколько Абрамыча по форумам поливали, что "ничего там нет, это нахрен не нужно, это банально, это тупо, мы и так код пишем прекрасно без всяких автоматов" и проч.
Весьма своеобразные аналогии...

Хотя совершенно очевидно, что это метод, который позволяет во многих ситуациях регуляризовать решение задачи. Как можно запрограммировать состояние объекта и его изменение через раздельные переменные (булевы признаки и проч.) - и всегда будут и случаи, и сторонники, когда это будет, вроде, нагляднее. С другой стороны, проводились сравнения для сложных задач, что программист, нахреначивший кучу логических признаков и их изменения в разных местах, допускал много ошибок и долго отлаживался, а программист, вводящий одну переменную состояния и анализировавший регулярным образом все случаи, успешно решал задачу.
Примеров можно приводить много и за то, и за это... Но вот здесь был вполне конкретный пример... Сравнить решения (с циклом Дейкстры и без него) - трудно?.. Говорить о состояниях будем после... тема вполне интересная, и совсем не такая однозначная, как Вы описываете... Для примера состояние узла зависит от состояния деталей... Сколько переменных вводить будем?..

Так и ЦД позволяет по-другому подойти к построению алгоритма, вытащив на один уровень то, что расслоено обычно по нескольким. Иметь в арсенале такую штуку очень полезно.
А вот за такое "вытаскивание" руки надо отрубать... по самые плечи... но постепенно, по сантиметрику... в месяц... чтоб больше неповадно было...
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 26, 2012, 10:23:06 pm
Примеров можно приводить много и за то, и за это... Но вот здесь был вполне конкретный пример... Сравнить решения (с циклом Дейкстры и без него) - трудно?..
Строить без цикла Дейкстры умеем, резонно желание попробовать и оценить с ЦД. Горячие крики "это не читабельно" я пока услышал только от деятелей (типа Тышова на нашем форуме), для которых понятия предусловия, инварианта пустой звук, а программа - просто последовательность действий, которую надо "гонять в уме", а не анализировать логически. Другие отзываются более сдержанно, на уровне "ну и что мы выигрываем". Если мы имеем сравнимый по результату, но другой метод решения, то вполне оправдано и дальше его пробовать. Просто потому, что он другой и может скрывать в себе интересные выгоды.

А вот за такое "вытаскивание" руки надо отрубать... по самые плечи... но постепенно, по сантиметрику... в месяц... чтоб больше неповадно было...
Принцип диалектики - отрицание отрицания. Я тоже за отрубание. Именно поэтому считаю для себя неопасным попробовать и обратное, в нужной и полезной форме. Что непозволено тому, кто не умеет структурировать, то позволено тому, кто умеет.
Логический аппарат, например (в том числе автоматический - типа систем Model-Cheking) ориентирован на рассмотрение регуляризованных конструкций, а не "расслоенных" в соответствии с исходной семантикой задачи. Т.е. могут быть какие-то интересные выгоды.
Очевидно, что понять, какой именно вычислительный процесс порождается ЦД может быть проще, чем понять, какой процесс порождается конструкцией вложенности 4-5.
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 26, 2012, 11:05:13 pm
Так сопоставьте сначала, напишите цикл, нумерующий эти номера.

Короче, возьмите конкретный пример входных данных, текстовый файл, приведённый ниже, и подумайте, сколько ещё придётся дописать преобразований, прежде чем применить написанный Вами "элементарный подсчёт".

5409135678
5409135678
5406995567
5406995567
5406995567
5406995567
5406995567
5406995579
5406995579
5406995579

(это фрагмент экспорта, говорящий о том, что один человек сдал 4 экзамена, другой - 5, третий - 3).
Не тупите  -  минимум (1 цикл).
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 26, 2012, 11:47:06 pm
Если вас интересует конкретика,то посмотрите решение Alexus'a -мое будет практически таким же (единственное- вместо внутреннего
цикла я в таких случаях использую условный оператор - на мой взгляд, гораздо легче воспринимается).
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 27, 2012, 01:59:10 am
таки приведу его в терминах Alexus'а
assert(cntItems>0);
 cur_pass := pass[1]; k := 1;
 for i:=2 to cntItems do begin
        if cur_pass <> pass[i] then begin
           inc(stat[k]);   
           k := 0;
        end;
                inc(k);   
        end;
  inc(stat[k]); 
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 27, 2012, 02:22:57 am
assert(cntItems>0);
 cur_pass := pass[1]; k := 1;
 for i:=2 to cntItems do begin
     if cur_pass <> pass[i] then begin
        inc(stat[k]);   
        k := 0; cur_pass := pass[i];
     end;
     inc(k);   
     end;
  inc(stat[k]);

 
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 27, 2012, 06:27:27 am
Примеров можно приводить много и за то, и за это... Но вот здесь был вполне конкретный пример... Сравнить решения (с циклом Дейкстры и без него) - трудно?..
Строить без цикла Дейкстры умеем, резонно желание попробовать и оценить с ЦД. Горячие крики "это не читабельно" я пока услышал только от деятелей (типа Тышова на нашем форуме), для которых понятия предусловия, инварианта пустой звук, а программа - просто последовательность действий, которую надо "гонять в уме", а не анализировать логически. Другие отзываются более сдержанно, на уровне "ну и что мы выигрываем". Если мы имеем сравнимый по результату, но другой метод решения, то вполне оправдано и дальше его пробовать. Просто потому, что он другой и может скрывать в себе интересные выгоды.
Цикл Дейкстры - частный случай, который легко восполняется простыми IF ... THEN ... ELSE. Вводить конструкцию подобную циклу Дейкстры - явно избыточно и опасно для начинающих (см. про сваливание логик различных уровней в одну кучу). Применительно к Дейкстре... столько бороться с GoTo, чтобы вернуться к тому же "спагетти"... с другой стороны... неразумно.

Цитата: alexus
А вот за такое "вытаскивание" руки надо отрубать... по самые плечи... но постепенно, по сантиметрику... в месяц... чтоб больше неповадно было...
Принцип диалектики - отрицание отрицания. Я тоже за отрубание. Именно поэтому считаю для себя неопасным попробовать и обратное, в нужной и полезной форме.
Что здесь "нужного", а тем более "полезного"?.. Это бесполезно и даже вредно, о чём свидетельствует Ваш же пример...

Что непозволено тому, кто не умеет структурировать, то позволено тому, кто умеет.
... или думает, что умеет... Кто проведёт грань между умеющими и не умеющими?.. Тестирование (ЕГЭ в миниатюре)?..

Логический аппарат, например (в том числе автоматический - типа систем Model-Cheking) ориентирован на рассмотрение регуляризованных конструкций, а не "расслоенных" в соответствии с исходной семантикой задачи. Т.е. могут быть какие-то интересные выгоды.
Логично... кривые инструменты порождают кривые конструкции... а потом кривизна закрепляется в "неокрепших умах". Но... "это не наш путь" (с).
Название: Re: ещё про цикл дейкстры
Отправлено: albobin от Июль 27, 2012, 07:54:31 am
Цикл Дейкстры - частный случай, который легко восполняется простыми IF ... THEN ... ELSE.
  И даже без EXIT или специальной переменной для катапультирования ? :)
Название: Re: ещё про цикл дейкстры
Отправлено: albobin от Июль 27, 2012, 08:07:41 am
Маркетолог бы тут сразу вкурил, что дело в названии и предложил бы сменить на "Цикл Лао-цзы"  :)
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 27, 2012, 10:44:14 am
assert(cntItems>0);
 cur_pass := pass[1]; k := 1;
 for i:=2 to cntItems do begin
        if cur_pass <> pass then begin
           inc(stat[k]);   
           k := 0;
        end;
                inc(k);   
        end;
  inc(stat[k]); 

Это уже не первые ваши "2 строчки".
Тогда уж вариант вот этот:
http://forum.oberoncore.ru/viewtopic.php?p=73513#p73513
Заметьте, что albobin получил его чисто преобразованием (выносом "за скобки") исходного ЦД. Что ещё раз подчёркивает его фундаментальность.

В приведённом Вами цикле "странности", которые осложняют его восприятие: идёт не с первого, а со второго элемента, не работает правильно на пустой последовательности... При чтении такого кода нет доверия - придётся проверять, что всё там правильно "подогнано".
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 27, 2012, 10:50:48 am
Цикл Дейкстры - частный случай, который легко восполняется простыми IF ... THEN ... ELSE. Вводить конструкцию подобную циклу Дейкстры - явно избыточно и опасно для начинающих (см. про сваливание логик различных уровней в одну кучу).

Никто не спорит, что восполняется. Речь не про иметь-не иметь конструкцию, а про саму структуру цикла.
А форма ЦД - такой же "частный случай", как ДНФ или КНФ в логике...
Что как раз хорошо ещё раз посмотрели на пример "эксклюзивно написанного" кода Дизера и сопоставимого кода от albobin-а, строго "свернутого" из ЦД.
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 27, 2012, 11:00:56 am
assert(cntItems>0);
 cur_pass := pass[1]; k := 1;
 for i:=2 to cntItems do begin
        if cur_pass <> pass then begin
           inc(stat[k]);   
           k := 0;
        end;
                inc(k);   
        end;
  inc(stat[k]); 

Это уже не первые ваши "2 строчки".
Тогда уж вариант вот этот:
http://forum.oberoncore.ru/viewtopic.php?p=73513#p73513
Заметьте, что albobin получил его чисто преобразованием (выносом "за скобки") исходного ЦД. Что ещё раз подчёркивает его фундаментальность.

В приведённом Вами цикле "странности", которые осложняют его восприятие: идёт не с первого, а со второго элемента, не работает правильно на пустой последовательности... При чтении такого кода нет доверия - придётся проверять, что всё там правильно "подогнано".
Тьфу и еще раз тьфу-вы даже привели вариант с ошибкой.. не знаю что было в коровнике, но общение с вами меня утомило - я и не представлял, что вырождение зашло так далеко...
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Июль 27, 2012, 11:04:33 am
Кстати про goto - оно, очевидно, фундаментально, и весьма активно используется в описаннии различных алгоритмов в CS (видимо просто чтобы не плодить сущности). Причем используется в форме не доступной в современных ЯП (том же Си например) - используемая форма, форма с вычисляемой меткой.
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 27, 2012, 11:05:26 am
2Alexus- признаю в отношении Ильи вы были правы, я-нет.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Июль 27, 2012, 11:08:13 am
Время всё расставит по своим местам.
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Июль 27, 2012, 11:12:22 am
Время всё расставит по своим местам.
Каким образом?

Мне действительно любопытно как время что-то в данном случае может расставить по своим местам, как мы это увидим?
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 27, 2012, 11:16:01 am
Кстати про goto - оно, очевидно, фундаментально, и весьма активно используется в описаннии различных алгоритмов в CS (видимо просто чтобы не плодить сущности). Причем используется в форме не доступной в современных ЯП (том же Си например) - используемая форма, форма с вычисляемой меткой.
???
Название: Re: ещё про цикл дейкстры
Отправлено: albobin от Июль 27, 2012, 11:28:38 am
Кстати про goto - оно, очевидно, фундаментально, и весьма активно используется в описаннии различных алгоритмов в CS (видимо просто чтобы не плодить сущности). Причем используется в форме не доступной в современных ЯП (том же Си например) - используемая форма, форма с вычисляемой меткой.
Ещё как доступна в МАМПСе  (как многое другое ещё).
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Июль 27, 2012, 11:36:02 am
Кстати про goto - оно, очевидно, фундаментально, и весьма активно используется в описаннии различных алгоритмов в CS (видимо просто чтобы не плодить сущности). Причем используется в форме не доступной в современных ЯП (том же Си например) - используемая форма, форма с вычисляемой меткой.
Ещё как доступна в МАМПСе  (как многое другое ещё).
Это который http://en.wikipedia.org/wiki/MUMPS ? Оно же сдохло :-) А я говорил про современные ЯП ;-)
Название: Re: ещё про цикл дейкстры
Отправлено: albobin от Июль 27, 2012, 11:40:21 am
"Слухи о моей смерти сильно преувеличены" Мампс Твен.
Название: Re: ещё про цикл дейкстры
Отправлено: albobin от Июль 27, 2012, 11:45:27 am
Вот один из процветающих покойничков http://www.intersystems.com/ (http://www.intersystems.com/)
вот другой http://www.fisglobal.com/products-technologyplatforms-gtm (http://www.fisglobal.com/products-technologyplatforms-gtm)
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Июль 27, 2012, 01:32:56 pm
Время всё расставит по своим местам.
Каким образом?

Мне действительно любопытно как время что-то в данном случае может расставить по своим местам, как мы это увидим?
так и расставит - это значит, что с определенной периодичностью подобная ситуация будет повторяться (как повторялась и ранее)- в этом весь Илья
(думать не хочет, предпочитает затыкать мозги оппоненту пустыми цитатами и ссылками, а если не выходит дешевой демагогией-правда это хорошо проходит только в коровнике, с "авторитетным" профессором и ручными эцилопами). Сейчас он меня конечно "уделал"-я думал, что он всерьез хочет пояснений... >:( ну да ладно -тьфу...
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Июль 27, 2012, 03:11:20 pm
Цикл Дейкстры - частный случай, который легко восполняется простыми IF ... THEN ... ELSE. Вводить конструкцию подобную циклу Дейкстры - явно избыточно и опасно для начинающих (см. про сваливание логик различных уровней в одну кучу).

Никто не спорит, что восполняется.
Всё, на этом месте ставим жирную точку. А к тому, кто не согласен приглашаем мистера Оккама с его инструментом... для шаловливых ручек...
Название: Re: ещё про цикл дейкстры
Отправлено: Peter Almazov от Июль 30, 2012, 05:15:09 am
Дурдом.
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Июль 30, 2012, 10:18:36 am
Я вот удивляюсь такому ажиотажу вокруг цикла Дейкстры -- цикл как цикл, что за страсти вокруг него? )))
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 07, 2012, 03:43:27 pm
Я вот удивляюсь такому ажиотажу вокруг цикла Дейкстры -- цикл как цикл, что за страсти вокруг него? )))

У тех, кто всё-таки не удовлетворен "технологичностью" программирования в малом, есть желание экспериментировать с новыми схемами-методами, в поисках большей регулярности кода (какую дало для задач парсинга и управляющих алгоритмов применение конечных автоматов).
Есть люди, которым улучшение "программирования в малом" не интересно, т.к. они считают, что всё можно парировать на уровне организации процессов (юнит-тестирование и проч.), либо, например, применением ФП.
Ну а Dizer-у простительны любые страсти, человек нашёл себе миссию и смысл жизни, защитить мир от оберонщиков, пускай защищает :)
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 07, 2012, 03:46:20 pm
У тех, кто всё-таки не удовлетворен "технологичностью" программирования в малом, есть желание экспериментировать с новыми схемами-методами, в поисках большей регулярности кода (какую дало для задач парсинга и управляющих алгоритмов применение конечных автоматов).
Есть люди, которым улучшение "программирования в малом" не интересно, т.к. они считают, что всё можно парировать на уровне организации процессов (юнит-тестирование и проч.), либо, например, применением ФП.
По моему, ФП как раз и решает проблемы программирования в малом. У ФП есть конечно потенциал и для большого, но обычно демонстрируется именно программирование в малом.
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Август 07, 2012, 03:47:51 pm
.
Ну а Dizer-у простительны любые страсти, человек нашёл себе миссию и смысл жизни, защитить мир от оберонщиков, пускай защищает :)
   :D Спасибо.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 07, 2012, 03:50:34 pm
По моему, ФП как раз и решает проблемы программирования в малом. У ФП есть конечно потенциал и для большого, но обычно демонстрируется именно программирование в малом.

Цена маскировки понятия последовательности действий, понятия "поведение системы", вообще состояния - слишком большая цена, с моей точки зрения. Кроме того, не видно пути, на котором рантайм и компилятор языков типа Haskell-а мог бы стать таким же простым, как Обероновский. Пишется на Си, баги, патчи, протечки памяти - вон даже в журнале ФП Льва Валкина народ пишет об этих проблемах при практическом использовании.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 07, 2012, 03:59:25 pm
а если не выходит дешевой демагогией

Вы можете формально упрекать в демагогии, потому что многое приходится высказывать из пока спорного, что кажется неправдопобным мейнстримщику.
Но, если положа руку на сердце, ну не вижу я никакого другого варианта в ИТ (кроме узких, специфических), который позволил бы что-то делать в этой сфере, "наклав" на зависимость от больших корпораций, либо больших сообществ. Можете считать меня утопистом, "маньяком натурального хозяйства", но я пытаюсь нащупать путь, на котором люди могут быстро догнать и сделать что-то свое против, казалось бы, необъятных систем.
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 07, 2012, 04:02:01 pm
По моему, ФП как раз и решает проблемы программирования в малом. У ФП есть конечно потенциал и для большого, но обычно демонстрируется именно программирование в малом.

Цена маскировки понятия последовательности действий, понятия "поведение системы", вообще состояния - слишком большая цена, с моей точки зрения. Кроме того, не видно пути, на котором рантайм и компилятор языков типа Haskell-а мог бы стать таким же простым, как Обероновский. Пишется на Си, баги, патчи, протечки памяти - вон даже в журнале ФП Льва Валкина народ пишет об этих проблемах при практическом использовании.
Можно ссылку на таковые протечки памяти которые именно из за сишной сущности рантайма хаскеля вылезают?

Мне в плане хаскелля все равно насколько сложен или прост рантайм, мне важна его эффективность и надежность, а к этому можно прийти минуя этап простоты, другое дело что на это потребуется больше усилий. Но усилий не моих :-)

В общем, как по мне, цена вполне адекватна. Да и все там видно в принципе (состояние системы и так далее) после того как с полгодика на этом деле попишешь более-менее активно.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 07, 2012, 04:30:10 pm
Нет, соврал, не в журнале ФП. Был пример разработки модели процессора, но в ФП как раз у них получилось на Haskell, а где-то в блогах разработчики подобного проекта жаловались, что на Haskell текла память, из-за чего они перешли на какой-то другой функциональный язык.

Ну а из-за чего могут быть баги с управлением памятью, как не из-за сишного рантайма?

А как быть с автоматическим управлением памятью, которое теперь начинает упираться в большой размер ОЗУ? Вон в Java новое поветрие - out-of-heap-memory (разработчики "Одноклассников" стали использовать, так как при большом ОЗУ и мелких объектах огромные тормоза). А уж ФП-рантайм ещё больше "автоматический", чем любой императивный.
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 07, 2012, 04:33:50 pm
Нет, соврал, не в журнале ФП. Был пример разработки модели процессора, но в ФП как раз у них получилось на Haskell, а где-то в блогах разработчики подобного проекта жаловались, что на Haskell текла память, из-за чего они перешли на какой-то другой функциональный язык.

Ну а из-за чего могут быть баги с управлением памятью, как не из-за сишного рантайма?
Это скорее всего блог Зефирова (thesz.livejournal.com), память текла не из за сишного рантайма, а из за ленивости haskell'я, в принципе подобным образом может и java течь и оберон (если у него есть сборщик мусора). Перешли скорее всего на ocaml - это язык энергичный и таких "утечек по умолчанию" там не будет. То есть это утечки логические на прикладном уровне, сборщиком не собираемые в принципе.

Короче, нужно уже заканчивать все грехи на Си списывать :-) Он не так страшен как кажется.
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 07, 2012, 04:37:02 pm
Нет, соврал, не в журнале ФП. Был пример разработки модели процессора, но в ФП как раз у них получилось на Haskell, а где-то в блогах разработчики подобного проекта жаловались, что на Haskell текла память, из-за чего они перешли на какой-то другой функциональный язык.

Ну а из-за чего могут быть баги с управлением памятью, как не из-за сишного рантайма?
Это скорее всего блог Зефирова (thesz.livejournal.com), память текла не из за сишного рантайма, а из за ленивости haskell'я, в принципе подобным образом может и java течь и оберон (если у него есть сборщик мусора). Перешли скорее всего на ocaml - это язык энергичный и таких "утечек по умолчанию" там не будет. То есть это утечки логические на прикладном уровне, сборщиком не собираемые в принципе.

Короче, нужно уже заканчивать все грехи на Си списывать :-) Он не так страшен как кажется.

В общем вот ссылка на разъяснение ситуации от самого автора этого самого эмулятора процессора: http://thesz.livejournal.com/904938.html?thread=6950634
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 07, 2012, 04:39:20 pm
А как быть с автоматическим управлением памятью, которое теперь начинает упираться в большой размер ОЗУ? Вон в Java новое поветрие - out-of-heap-memory (разработчики "Одноклассников" стали использовать, так как при большом ОЗУ и мелких объектах огромные тормоза). А уж ФП-рантайм ещё больше "автоматический", чем любой императивный.
Он более автоматический в малом. То есть всякие fusion'ы благодаря которым не создаются промежуточные структуры данных и вычисления не производятся и так далее. При масштабировании это все к проблемам не приводит, в отличае от сборщиков мусора в ИЯ (огромное общее адресное пространство).
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 07, 2012, 04:46:30 pm
Ну а из-за чего могут быть баги с управлением памятью, как не из-за сишного рантайма?
Кстати, я точно помню на этот вопрос именно в контексте этого случая (эмулятор процессора от Зефирова) и именно тебе несколько лет назад на оберонкоре отвечал Geniepro, и отвечал именно про ленивость :-) Подобное знание видимо плохо усваивается, и заменяется снова "знанием" аля "это все сишный рантайм виноват!". Я не в плане критики, я в том плане, что обрати на это внимание, звоночек то не хороший, эдак и мозгом закостенеть не долго.
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Август 07, 2012, 05:00:06 pm
а если не выходит дешевой демагогией

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

Но, если положа руку на сердце, ну не вижу я никакого другого варианта в ИТ (кроме узких, специфических), который позволил бы что-то делать в этой сфере, "наклав" на зависимость от больших корпораций, либо больших сообществ. Можете считать меня утопистом, "маньяком натурального хозяйства", но я пытаюсь нащупать путь, на котором люди могут быстро догнать и сделать что-то свое против, казалось бы, необъятных систем.
В общем, серебряных пуль искатели и уловители со всех стран объединяйтесь! :)
Сегодня бороться с большими софтверными корпорациями - это несколько странно... Дело не в том, что они всасывают в себя "мозги", а в том, как они это делают. Возникла у человека идея, хорошая продуктивная идея, которая требует выхода, реализации, то бишь. Что делает такой человек? Он начинает искать сторонников, и находит в виде... венчурных компаний, которые внимательно его выслушивают, дают денег и помогают организовать стартап. Реализовали идею, и... можете свой продукт продавать, а можете с потрохами продаться "большой корпорации". Первое долго, рискованно и хлопотно, второе быстро и гарантированно выгодно безо всяких хлопот.
Что касается краткости и эффективности пути, то он начинается с хорошей модели, качественного проектирования и, наконец, кодирования. А поскольку на первых двух этапах напряг, то о кодировании лучше вообще не вспоминать... всуе. Остаётся любимое занятие врямяубийцев - искать серебряную пулю.
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 07, 2012, 05:04:19 pm
Цена маскировки понятия последовательности действий, понятия "поведение системы", вообще состояния - слишком большая цена, с моей точки зрения. Кроме того, не видно пути, на котором рантайм и компилятор языков типа Haskell-а мог бы стать таким же простым, как Обероновский.
А при чём здесь именно ФП???
ФП -- это не только Хаскелл. Тот же Caml Light, например, очень прост и ложится на ассемблер не хуже сей.
Не говоря уж о Scheme -- куда уж проще-то? Да у ваших оберонов жутчайший "синтаксический оверхед" по сравнению со схемой...

Пишется на Си, баги, патчи, протечки памяти - вон даже в журнале ФП Льва Валкина народ пишет об этих проблемах при практическом использовании.
Любой сложный язык сейчас именно так и реализуется -- на Си, с багами, патчами, протечками памяти и чего угодно -- это вовсе никак не связано с ФП, так что не надо клеветать-то...
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Август 07, 2012, 05:34:35 pm
а если не выходит дешевой демагогией

Вы можете формально упрекать в демагогии, потому что многое приходится высказывать из пока спорного, что кажется неправдопобным мейнстримщику.
Природа не терпит не только пустоты, но и заумности тоже. Первое она заполняет, второе отрезает.
  :( C каких это пор демагогия стала синонимом пустоты и /или заумности. По поводу последней и "общности", а также "серебрянных пуль" - типичная точка зрения представителей инженерных вузов, классический пример уродства - "правило Лопиталя" , как "заучили" на первом курсе так и всю свою жизнь применяют по любому поводу и без оного...
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 10, 2012, 10:05:01 am
Кстати, я точно помню на этот вопрос именно в контексте этого случая (эмулятор процессора от Зефирова) и именно тебе несколько лет назад на оберонкоре отвечал Geniepro, и отвечал именно про ленивость :-) Подобное знание видимо плохо усваивается, и заменяется снова "знанием" аля "это все сишный рантайм виноват!".

Ну, я понял это пояснение так, что из-за ленивости логика сборки мусора сложнее, и рантайм оказался неспособен правильно отработать.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 10, 2012, 10:10:08 am
Любой сложный язык сейчас именно так и реализуется -- на Си, с багами, патчами, протечками памяти и чего угодно -- это вовсе никак не связано с ФП, так что не надо клеветать-то...

Ну так я и говорю о том, что передовой край ФП (статические функциональные языки с мощной системой типов) относятся именно к "любым сложным языкам". ФП чрезмерно повышает уровень программирования, а значит, требует более жирных рантаймов.
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 10, 2012, 10:13:02 am
Кстати, я точно помню на этот вопрос именно в контексте этого случая (эмулятор процессора от Зефирова) и именно тебе несколько лет назад на оберонкоре отвечал Geniepro, и отвечал именно про ленивость :-) Подобное знание видимо плохо усваивается, и заменяется снова "знанием" аля "это все сишный рантайм виноват!".

Ну, я понял это пояснение так, что из-за ленивости логика сборки мусора сложнее, и рантайм оказался неспособен правильно отработать.
А, ну тогда все ок - ты просто тогда не правильно понял :-)
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 10, 2012, 10:21:03 am
Что касается краткости и эффективности пути, то он начинается с хорошей модели, качественного проектирования и, наконец, кодирования. А поскольку на первых двух этапах напряг, то о кодировании лучше вообще не вспоминать... всуе. Остаётся любимое занятие врямяубийцев - искать серебряную пулю.

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

У меня не "напряг" на первых двух этапах, я просто придерживаюсь принципа постепенного проявления модели.
Можно тужиться сразу увидеть модель, а можно взять серию задач интересующего класса и начать заходить попеременно снизу и сверху. Прочувствовал конкретный случай (получил опыт) - подумал, как можно абстрагироваться от его частных особенностей и вынести более общее средство. Взял другую задачу - применил средство, проанализировал возникшие проблемы или их отсутствие, обобщил дальше.
Вы в наших спорах всегда за "прыжок" сразу в точку, а я - за постепенный спуск к ней. Иногда даже не кратчайшим путём, но никогда не теряя из виду цели. Но Вы всегда пытаетесь приписать мне третье - беспорядочное блуждание в конкретных задачах.
Я, так же как и Вы, верю в силу интуитивного озарения, но убеждён, что интуиция проявляется сильнее, быстрее, "гарантированнее", если её кормить многими частными задачами, постепенным накоплением опыта.
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 10, 2012, 11:15:00 am
Ну, я понял это пояснение так, что из-за ленивости логика сборки мусора сложнее, и рантайм оказался неспособен правильно отработать.
Вы неправильно поняли, Илья.
Отложенные вычисления не являются мусором -- ведь на них есть живые ссылки, в отличие от мусора.
Отложенные вычисления могут быть в любой момент востребованы во время вывода результатов на печать/файл/сеть и тд. -- вот тогда они и вычисляются, а пока они не оказались востребованы, они находятся в памяти в виде формулы вычисления значения.
Проблема лишь в том, что эта формула занимает много места, иногда на много порядков больше, чем результирующее значение...
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 10, 2012, 11:20:16 am
Ну так я и говорю о том, что передовой край ФП (статические функциональные языки с мощной системой типов) относятся именно к "любым сложным языкам". ФП чрезмерно повышает уровень программирования, а значит, требует более жирных рантаймов.
При чём здесь ФП? В ФП есть только один язык, который можно отнести к этой категории (статические функциональные языки с мощной системой типов) -- это Хаскелл.

А ведь существуют подобные языки, которые не являются ФЯ -- Scala, например. Сложность её системы типов не меньше, чем у Хаскелла.

Есть так же системы доказательства теорем со своими языками (Agda2, Coq) -- не знаю, можно ли их относить к только ФП, там всё-таки много больше, чем просто программирование...
Название: Re: ещё про цикл дейкстры
Отправлено: Влад Жаринов от Август 10, 2012, 11:32:42 am
...
Отложенные вычисления не являются мусором -- ведь на них есть живые ссылки, в отличие от мусора.
Отложенные вычисления могут быть в любой момент востребованы во время вывода результатов на печать/файл/сеть и тд. -- вот тогда они и вычисляются, а пока они не оказались востребованы, они находятся в памяти в виде формулы вычисления значения.
Проблема лишь в том, что эта формула занимает много места, иногда на много порядков больше, чем результирующее значение...
Это то же самое, что в императивном представлении можно сделать в рекурсии?..
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 10, 2012, 11:46:27 am
...
Отложенные вычисления не являются мусором -- ведь на них есть живые ссылки, в отличие от мусора.
Отложенные вычисления могут быть в любой момент востребованы во время вывода результатов на печать/файл/сеть и тд. -- вот тогда они и вычисляются, а пока они не оказались востребованы, они находятся в памяти в виде формулы вычисления значения.
Проблема лишь в том, что эта формула занимает много места, иногда на много порядков больше, чем результирующее значение...
Это то же самое, что в императивном представлении можно сделать в рекурсии?..
Я не понял вопроса, если честно. При чём здесь рекурсия?
Рекурсия -- это разновидность цикла.
Отложенное вычисление -- это ссылка на функцию, которую нужно вычислить, что бы получить значение вместо этой ссылки.
Это совершенно несвязанные вещи...
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 10, 2012, 11:49:40 am
Это то же самое, что в императивном представлении можно сделать в рекурсии?..
Отложенные вычисления в императивных языках могут приводить к неверным расчётам.
Поэтому, хотя и есть специальные библиотеки для императивных языков, в сами языки (императивные) ленивость обычно не встраивают.
Название: Re: ещё про цикл дейкстры
Отправлено: Влад Жаринов от Август 10, 2012, 03:27:46 pm
Имел в виду, что для рекурсивных алгоритмов указывается возможность откладывания операторов, если определённым образом расположить их в структуре маршрутов. Видел такое в этой книге (Гл. 18 выдержки) (http://forum.oberoncore.ru/download/file.php?id=1883). Вот и интересно - это можно считать отложенными вычислениями, как Вы их используете здесь (или аналогом)?..
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Август 10, 2012, 03:38:12 pm
Никакого отношения к "серебрянной пуле" сказанное мной не имеет. Создание компонентов, библиотек, которые решают конкретные задачи (например, разработку серверных приложений определённого класса) и при этом имеют небольшой размер и простую логику - это не "серебрянная пуля". Стремление раскрыть весь потенциал удачного языка (КП) в нише С/С++ - это тоже не "серебрянная пуля".
Всё правильно. "Серебряная пуля" нужна тогда, когда есть серьёзный проект, команда приличного размера. Собственно, Ф, Брукс об этом говорил.

У меня не "напряг" на первых двух этапах, я просто придерживаюсь принципа постепенного проявления модели.
Не проявится... IMHO.

Можно тужиться сразу увидеть модель, а можно взять серию задач интересующего класса и начать заходить попеременно снизу и сверху. Прочувствовал конкретный случай (получил опыт) - подумал, как можно абстрагироваться от его частных особенностей и вынести более общее средство. Взял другую задачу - применил средство, проанализировал возникшие проблемы или их отсутствие, обобщил дальше.
Этот реверсивный способ хорошо объясняется в экстремальном программировании. Работает великолепно... пока проект можно охватить одним взглядом. Стоит проекту чуть-чуть подрасти и работа зацикливается на "рефакторинге". Поймите правильно, я никуда Вас не зову, ничего Вам не предлагаю. Только тот путь, который Вы описываете ведёт в тупик. Возвращаясь к моделям, для простых случаев можно использовать Ваш подход, но только для простых.

Вы в наших спорах всегда за "прыжок" сразу в точку, а я - за постепенный спуск к ней. Иногда даже не кратчайшим путём, но никогда не теряя из виду цели. Но Вы всегда пытаетесь приписать мне третье - беспорядочное блуждание в конкретных задачах.
Я, так же как и Вы, верю в силу интуитивного озарения, но убеждён, что интуиция проявляется сильнее, быстрее, "гарантированнее", если её кормить многими частными задачами, постепенным накоплением опыта.
Это не вопрос веры... для меня. И я не ратую за какие-то "прыжки в точку", речь только о том, что не поняв сути задачи браться за решение чего-то там... не стоит. И если вдуматься, то Ваш путь и есть блуждание, хотя Вы его принимаете за спуск. Да, и интуиция от подобной диеты может "ноги протянуть".
В общем, снова ни о чём.
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 10, 2012, 05:07:28 pm
Имел в виду, что для рекурсивных алгоритмов указывается возможность откладывания операторов, если определённым образом расположить их в структуре маршрутов. Видел такое в этой книге (Гл. 18 выдержки) (http://forum.oberoncore.ru/download/file.php?id=1883). Вот и интересно - это можно считать отложенными вычислениями, как Вы их используете здесь (или аналогом)?..
Прочитал эту "Гл. 18" -- интересный взгляд на рекурсию. Но это всё же не то же самое, что ленивые вычисления в традиционном понимании.
В этой главе просто показано, что происходит при выполнении рекурсивных подпрограмм, не имеющих хвостовой рекурсии.
Если рекурсивная подпрограмма не имеет хвосовой рекурсии, то она начинает потреблять память в стеке -- занимает память в стеке под копию локальных переменных и адрес возврата из подпрограммы. Такую рекурсию ещё называют наивной.

В каком-то смысле действительно может показаться, что в рекурсивной подпрограмме каждый рекурсивный вызов её же является отложенным вычислением, но так говорить как-то не принято...
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 10, 2012, 05:32:57 pm
<...> речь только о том, что не поняв сути задачи браться за решение чего-то там... не стоит.

Но ведь очень часто мы просто не понимаем сути задачи, пока не возьмёмся её решать. Постоянно возникают изменения задачи, и вчерашнее её понимание оказывается неполным, а то и вовсе не верным...
Что же делать в этом случае?
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Август 10, 2012, 05:40:24 pm
<...> речь только о том, что не поняв сути задачи браться за решение чего-то там... не стоит.

Но ведь очень часто мы просто не понимаем сути задачи, пока не возьмёмся её решать. Постоянно возникают изменения задачи, и вчерашнее её понимание оказывается неполным, а то и вовсе не верным...
Что же делать в этом случае?
Согласен с обоими высказываниями - общего решения нет, но  очень много дают  оценки затрат на реализацию = скажем так, без удовлетворяющей меня подобной оценки я не берусь(стараюсь не делать этого) за реализацию (другое дело что ЭТО НЕ ВСЕГДА ВОЗМОЖНО - перевешивает "волшебное" слово -НУЖНО).
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Август 10, 2012, 06:27:25 pm
<...> речь только о том, что не поняв сути задачи браться за решение чего-то там... не стоит.

Но ведь очень часто мы просто не понимаем сути задачи, пока не возьмёмся её решать. Постоянно возникают изменения задачи, и вчерашнее её понимание оказывается неполным, а то и вовсе не верным...
Что же делать в этом случае?
Думать над задачей, над тем, откуда она взялась, почему сформулирована именно так. Но слово "решение" здесь имеет два смысловых оттенка. Можно решать задачу без понимания сути, но решить её таким образом нельзя. (Я говорил о втором, то есть, о том, что не поняв сути задачи, браться за решение не стоит, потому что решить задачу не получится). Но моё высказывание не говорит о том, что думать над задачей не надо. Надо. Это вопрос "частного" и "общего". Частные решения можно получить, не понимая сути, но общего решения так получить нельзя.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 12, 2012, 05:30:12 pm
Это не вопрос веры... для меня. И я не ратую за какие-то "прыжки в точку", речь только о том, что не поняв сути задачи браться за решение чего-то там... не стоит.

Насколько я понял из Вашего ответа мне в соседней ветке, Вам приходилось заниматься решением задач автоматизации ещё до рождения вашей модели. И Вы сказали, что долго мучились в поиске объясняющей простой модели, которая была бы "ключом" к тому зоопарку, который Вы видели.
Я абсолютно уверен, что если бы Вы сначала не повидали сам "зоопарк", то и ключ бы к нему не нашли.
Другой вопрос, что следующий "зоопарк" (другая сфера деятельности) может иметь скрытые сходства с предыдущим, и там уже умудрённый прошлыми успехами человек может себе позволить понять суть задачи ещё до знакомства со всем их множеством.
Без эмпирики нет обобщения, ибо обобщать просто будет нечего...
Если со временем у Вас возникает обобщение, являющееся ключом к огромному множеству задач, и Вы отбрасываете эмипирику как уже скучную, ненужную, Вы её переросли, это не повод забывать, что в основе когда-то лежала всё равно она...
Вот этот тонкий момент является причиной одной вашей неприятной манеры - снобизма ко всем тем, кто не торопится сразу обобщать, а сначала изучает. "Кладбище кривых обобщений" у человечества слишком велико, чтобы тут торопиться.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 12, 2012, 05:55:11 pm
Опять же, одинаковый вред приносят как те, кто за деревьями не видят леса, так и те, кто увлечённо масштабирует свои модели за пределы сферы их применения. Я подчеркиваю, что я не имею в виду Вас.
Поэтому позиция классической науки, основанной во многом на бэконовском эмпиризме, - лучше честно сказать "это мы пока не знаем" и остаться с набором точных фрагментов, чем поспешить объединить эти фрагменты и получить недостоверную картину. Позиция "да, у меня пока нет целостной картины, обхожусь без неё и стремлюсь построить" честнее, чем позиция "я тут придумал целостную картину и готов натянуть её на что попросите".
Название: Re: ещё про цикл дейкстры
Отправлено: alexus от Август 12, 2012, 08:41:17 pm
Это не вопрос веры... для меня. И я не ратую за какие-то "прыжки в точку", речь только о том, что не поняв сути задачи браться за решение чего-то там... не стоит.
Насколько я понял из Вашего ответа мне в соседней ветке, Вам приходилось заниматься решением задач автоматизации ещё до рождения вашей модели. И Вы сказали, что долго мучились в поиске объясняющей простой модели, которая была бы "ключом" к тому зоопарку, который Вы видели.
Я абсолютно уверен, что если бы Вы сначала не повидали сам "зоопарк", то и ключ бы к нему не нашли.
Нельзя найти то, что не ищешь.
То, что я занимался какими-то задачами, не определяет того, что было найдено. Многие, гораздо более умные, знающие и опытные, чем я, решают те же задачи. А решение вот оно... школьнику понятно. Почему же они не видят того, что столь просто и лежит на поверхности?
(Одного понять не могу, в чём Вы меня убедить хотите... или Вы себя в своей правоте убеждаете?)

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

Если со временем у Вас возникает обобщение, являющееся ключом к огромному множеству задач, и Вы отбрасываете эмипирику как уже скучную, ненужную, Вы её переросли, это не повод забывать, что в основе когда-то лежала всё равно она...
Вот этот тонкий момент является причиной одной вашей неприятной манеры - снобизма ко всем тем, кто не торопится сразу обобщать, а сначала изучает. "Кладбище кривых обобщений" у человечества слишком велико, чтобы тут торопиться.
У меня снобизма к кому бы то ни было, к Вам, в том числе. Есть разное мировоззрение.
Вот, Вы читаете про мои модели, соглашаетесь с тем, что и просто, и понятно, и ёмко. Но эти модели малая толика того, что можно с их помощью отобразить, превратить в знания. Понимаете весь путь человечества начертан просто и строго логически. Можно понимать путь и следовать по нему, а можно не понимать и... блуждать между Сциллой и Харибдой. Для Вас же всё это не существует, Вам важнее частные проекции, которые могут вызвать интерес или не вызвать (гипотезы, что с них возьмёшь).
Понимаете, я начал серьёзно заниматься экономикой не до того, как понял её устройство, а после того, чтобы найти способ объяснить. История мне стала интересна потому, что я знаю тот путь, который мы прошли и тот, который может быть пройдём... и мне просто нужны факты для иллюстрации. Лингвистика вызвала у меня интерес, поскольку многие слова слишком точны и образны, но эта точность и образность затёрты в обиходе. Для кого-то строить - это возводить стены, а для кого-то строить - означает с-троить, соединить воедино руки, ум и сердце. Для кого-то счастье - это просто слово, отражающее пик позитивных чувств и ощущений (некий синоним оргазма), а для кого-то счастье - это со-частию, воссоединение целого с частью.
Илья, я хорошо понимаю, что Вы идёте своей дорогой, я вовсе не стараюсь Вас с неё сбить. Давайте же в очередной раз, но уже навсегда закроем эту тему.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 12, 2012, 09:15:51 pm
У меня снобизма к кому бы то ни было, к Вам, в том числе. Есть разное мировоззрение.
Вот, Вы читаете про мои модели, соглашаетесь с тем, что и просто, и понятно, и ёмко. Но эти модели малая толика того, что можно с их помощью отобразить, превратить в знания. Понимаете весь путь человечества начертан просто и строго логически. Можно понимать путь и следовать по нему, а можно не понимать и... блуждать между Сциллой и Харибдой.
Но каким образом я могу убедиться, что показуемая мне (или даже возникшая у меня в голове) простая, строгая и очень всеобщая модель - это не прелесть (в православном смысле этого слова), не ложная картина? Математик успокаивается на том, что нет противоречий внутри. Но хочется абсолютно достоверного соответствия реальности. Если мы, конечно, убеждены в её наличии.
Моя критика - это всего лишь защитная реакция, из убеждения, что лучше иметь на своей карте белые пятна, чем позволить кому-то (даже себе) их додумать и дорисовать, без гарантии, что дорисовка соответствует действительности.
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 13, 2012, 05:34:27 am
Но каким образом я могу убедиться, что показуемая мне (или даже возникшая у меня в голове) простая, строгая и очень всеобщая модель - это не прелесть (в православном смысле этого слова), не ложная картина?
А не является ли Оберон для Вас той самой "православной прелестью"?
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 13, 2012, 10:07:57 am
Оберон даёт конкретные возможности, про которые я уже говорил: накласть на фантазии всех вместе взятых Микрософтов и GNU-сообществ;  или, например, запустить в начале рабочего дня ББ и перейти к решению всех своих задач не только программистских, но и других, типа документооборота; и знать, что всё это тебе подконтрольно и работает предсказуемо.

В то время, как Убунта, зараза, втянула какое-то обовление - и диспетчер окон сегодня работает уже не так, как вчера, когда я перетаскиваю окно с одного монитора на другой :) А если я не втяну обновление, то не дождусь исправления какого-нибудь ещё бага... Ну на хрен мне эта свистопляска? :)
Название: Re: ещё про цикл дейкстры
Отправлено: ilovb от Август 13, 2012, 10:21:05 am
Илья, а как еще можно обновлять ПО? Вы можете предложить альтернативу?
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 13, 2012, 10:35:31 am
Оберон даёт конкретные возможности, про которые я уже говорил: накласть на фантазии всех вместе взятых Микрософтов и GNU-сообществ;  или, например, запустить в начале рабочего дня ББ и перейти к решению всех своих задач не только программистских, но и других, типа документооборота; и знать, что всё это тебе подконтрольно и работает предсказуемо.

В то время, как Убунта, зараза, втянула какое-то обовление - и диспетчер окон сегодня работает уже не так, как вчера, когда я перетаскиваю окно с одного монитора на другой :) А если я не втяну обновление, то не дождусь исправления какого-нибудь ещё бага... Ну на хрен мне эта свистопляска? :)
Вот именно, Илья, на хрен Вы всё ещё сидите на этой углюченной бубунте? Почему у Вас на компе до сих пор не Active Oberon System или Native Oberon? Нелогичненько как-то...
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 13, 2012, 10:53:44 am
В то время, как Убунта, зараза, втянула какое-то обовление - и диспетчер окон сегодня работает уже не так, как вчера, когда я перетаскиваю окно с одного монитора на другой :) А если я не втяну обновление, то не дождусь исправления какого-нибудь ещё бага... Ну на хрен мне эта свистопляска? :)
Ну да, а в случае Оберонов выбора нет (обновлять и получить возможно другое поведение или не обновлять, но остаться с багами). Обновлений гарантированно нет :-)

PS. Если хочется стабильности, то зачем убунта? У меня дебиан. Обновления НИКОГДА не приводят к изменению поведения.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 13, 2012, 10:59:57 am
Илья, а как еще можно обновлять ПО? Вы можете предложить альтернативу?

Не обновлять, а разрабатывать.

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

Почему сижу на Убунте - потому что нужна совместимость и не на всё сразу хватает ресурсов. Уже не на Винде, хотя бы.
(Активный Оберон - экспериментальная ветка, которую лично мне не нравится). Кроме того, ОС всё-таки уже сродни оборудованию - базовый уровень, который можно "экранировать". У меня есть серверные приложения на ББ, которые вообще имеют один и тот же набор файлов (и кодовых) для обоих ОС, отличаясь только несколькими системными модулями. И два пускача рядом - exe и elf. И разницы, на чём я в данный момент, никакой.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 13, 2012, 11:01:44 am
PS. Если хочется стабильности, то зачем убунта? У меня дебиан. Обновления НИКОГДА не приводят к изменению поведения.

У нас в коллективе так сложилось. В 2005-м использовали ASP, потом у них пошло оставание, в частности, по 64 бит, перешли на Убунту...
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 13, 2012, 11:21:03 am
PS. Если хочется стабильности, то зачем убунта? У меня дебиан. Обновления НИКОГДА не приводят к изменению поведения.

У нас в коллективе так сложилось. В 2005-м использовали ASP, потом у них пошло оставание, в частности, по 64 бит, перешли на Убунту...
Я где-то в 2008 году ушел с убунты, ибо задолбало :-)
Впрочем, как серверная система она мало чем от дебиана отличается (ибо убунта по жизни и есть debian unstable).

PS. А обновления которые обычно прилетают в дистрибутивах линукса (что в дебиане что в убунте) обычно никакого отношения к ОС не имеют - это обычный прикладной софт обновляется, например те же иксы (X11) или вообще какой-нибудь оконный менеджер. Я не знаю как там сейчас в убунте, но в дебиане всегда было так - в рамках одной версии дебиана (скажем 6) обновления приходят только в плане исправления ошибок и в первую очередь исправляются уязвимости (кстати, собственно в ОС таких проблем я не упомню, в прикладухе да, бывают), новый же функционал (новые версии софта) - в следующей версии дистрибутива, ну либо самостоятельно можно поставить из репозитория новой версии. Проблем не вижу в общем то.

PPS. Помню когда сидел на BeOS меня была примерно та же позиция что у тебя, Илья, то есть смотрел я на этот весь линукс да винды, как посмотришь на новостные сайты - постоянно какая-то возня у них была, новые версии, уязвимости… То ли дело BeOS - пять лет без изменений вообще! Но потом, поковырявшись и в коде BeOS и вообще, стало понятно, что изменений, "багов" и уязвимостей нет не потому что их там реально нет и изменения не нужны, а потому что BeOS к тому времени была как тот самый неуловимый Джо - неуловимый потому что нафиг никому не нужен :-) Теперь есть Haiku, в плане архитектурном и в плане кода там все намного лучше чем в BeOS (и код открыт, да), а вот багофиксов, обновлений и так далее там на порядок больше чем было в BeOS. Как думаешь, почему? :-)

В общем, это вполне распространенная ловушка. Я в ней уже был.
Название: Re: ещё про цикл дейкстры
Отправлено: Илья Ермаков от Август 14, 2012, 08:53:51 am
Но потом, поковырявшись и в коде BeOS и вообще, стало понятно, что изменений, "багов" и уязвимостей нет не потому что их там реально нет и изменения не нужны, а потому что BeOS к тому времени была как тот самый неуловимый Джо - неуловимый потому что нафиг никому не нужен :-) Теперь есть Haiku, в плане архитектурном и в плане кода там все намного лучше чем в BeOS (и код открыт, да), а вот багофиксов, обновлений и так далее там на порядок больше чем было в BeOS. Как думаешь, почему? :-)

Корреляция с популярностью, естественно, есть - но не только в том плане, что делаются нужные вещи. Кроме этого, около популярной системы напорядок больше толпиться любителей "надо щось робити" (как говаривал Владимир Лось). "А давайте..." - ну и пошло-поехало :) В условиях дефицита сил на развитие волей-неволей выбираются приоритеты. А когда сил становится дохрена, часто начинаются фантазии "а давайте покрасим коровники в синий цвет. У меня есть ещё много конструктивных предложений".
Название: Ещё про циклы
Отправлено: Влад Жаринов от Август 21, 2012, 07:16:01 am
Вот тут предложена некая классификация циклов вообще...
Цитата: http://www.rsdn.ru/forum/philosophy/4862458.aspx?tree=tree
...
Дело в том, что на практике есть не два, а 5 видов циклов.
 1. Подлинно бесконечный цикл, с остановкой по исключению.
 2. Цикл опроса (предмет цикла меняется извне; покуда он не изменился, мы молотим почти бесконечный цикл).
 3. Цикл неограниченных итераций, с остановкой по условию (предмет цикла меняется в его теле, но последовательность значений нетривиальна, а то и непредсказуема — например, проблема 3X+1)
 4. Цикл линейного пробега по всему диапазону.
 5. Цикл линейного поиска.

 К сожалению, в Си есть только три языковые конструкции: for, while/do-while и проклятая if-goto
 Вот и приходится выделываться с while(true), for(;;) и break/continue.
...
Типа от жизни обосновывается.
Как я понимаю, в доказательном подходе предлагается выводить первые три обычно через 4 и/или 5. Для того же и ЦД. Или я чего-то не понимаю?.. :)
Название: Re: Ещё про циклы
Отправлено: valexey от Август 21, 2012, 07:28:45 am
Вот тут предложена некая классификация циклов вообще...
Цитата: http://www.rsdn.ru/forum/philosophy/4862458.aspx?tree=tree
...
Дело в том, что на практике есть не два, а 5 видов циклов.
 1. Подлинно бесконечный цикл, с остановкой по исключению.
 2. Цикл опроса (предмет цикла меняется извне; покуда он не изменился, мы молотим почти бесконечный цикл).
 3. Цикл неограниченных итераций, с остановкой по условию (предмет цикла меняется в его теле, но последовательность значений нетривиальна, а то и непредсказуема — например, проблема 3X+1)
 4. Цикл линейного пробега по всему диапазону.
 5. Цикл линейного поиска.

 К сожалению, в Си есть только три языковые конструкции: for, while/do-while и проклятая if-goto
 Вот и приходится выделываться с while(true), for(;;) и break/continue.
...
Типа от жизни обосновывается.
Как я понимаю, в доказательном подходе предлагается выводить первые три обычно через 4 и/или 5. Для того же и ЦД. Или я чего-то не понимаю?.. :)
Замечу, что 5 не является подмножеством 4. Кроме того, в Обероне пункт 4 отсутствует.
Название: Re: ещё про цикл дейкстры
Отправлено: Влад Жаринов от Август 21, 2012, 07:36:02 am
Так автор и не утверждает обратного вроде... :)
Я как раз и к тому - нужно ли каждый из этих видов самостоятельно определять в языке?..
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 21, 2012, 07:38:23 am
Так автор и не утверждает обратного вроде... :)
Я как раз и к тому - нужно ли каждый из этих видов самостоятельно определять в языке?..
Смотря в каком языке. В Haskell'e не надо, там это все делается библиотекой. (и этой библиотекой все активно пользуются, так что с циклами в haskell'e все много лучше чем в императивных языках, даже если на них ставят печать "годен для доказательного программирования").
Название: Re: ещё про цикл дейкстры
Отправлено: Влад Жаринов от Август 21, 2012, 07:47:06 am
Ну, "годен для доказательного программирования (сиречь, дедуктивной верификации)" - это по теории получается прежде всего, "удовлетворяет структурной теореме"... :) так что печать вроде как ставит кодер, воздерживающийся от иного... ;)
А вот для верификации проверкой моделей вроде как и goto не помеха... там, правда, надо не забыть представить все существенные техтребования в виде *TL-формул... :)

Я скорее к тому, что вот язык, применимый для программной реализации систем в смысле Усова - он должен такие различия учитывать?.. и вообще это м.б. один из существующих языков (Хаскель или иной)?.. можно что-то с позиции CS-профессионала сказать?..
Название: Re: Ещё про циклы
Отправлено: Peter Almazov от Август 21, 2012, 07:54:23 am
Вот тут предложена некая классификация циклов вообще...
Цитата: http://www.rsdn.ru/forum/philosophy/4862458.aspx?tree=tree
...
Дело в том, что на практике есть не два, а 5 видов циклов.
 1. Подлинно бесконечный цикл, с остановкой по исключению.
 2. Цикл опроса (предмет цикла меняется извне; покуда он не изменился, мы молотим почти бесконечный цикл).
 3. Цикл неограниченных итераций, с остановкой по условию (предмет цикла меняется в его теле, но последовательность значений нетривиальна, а то и непредсказуема — например, проблема 3X+1)
 4. Цикл линейного пробега по всему диапазону.
 5. Цикл линейного поиска.

 К сожалению, в Си есть только три языковые конструкции: for, while/do-while и проклятая if-goto
 Вот и приходится выделываться с while(true), for(;;) и break/continue.
...
Типа от жизни обосновывается.
Как я понимаю, в доказательном подходе предлагается выводить первые три обычно через 4 и/или 5. Для того же и ЦД. Или я чего-то не понимаю?.. :)
Замечу, что 5 не является подмножеством 4. Кроме того, в Обероне пункт 4 отсутствует.
Классификация достойна пера великого художника http://oberspace.dyndns.org/index.php/topic,172.msg2841.html#msg2841
Название: Re: ещё про цикл дейкстры
Отправлено: Влад Жаринов от Август 21, 2012, 08:05:25 am
Мысль (вроде от Питера Брейгеля?) понятна... :)
Кстати, автор поста вроде как не любитель ДРАКОНа... :D

А как Вы бы подразделили?.. для языка?..
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 21, 2012, 08:06:19 am
Ну, "годен для доказательного программирования (сиречь, дедуктивной верификации)" - это по теории получается прежде всего, "удовлетворяет структурной теореме"... :) так что печать вроде как ставит кодер, воздерживающийся от иного... ;)
Это теорема которая:
Цитировать
Любую схему алгоритма можно представить в виде композиции вложенных блоков begin и end, условных операторов if, then, else, циклов с предусловием (while) и может быть дополнительных логических переменных (флагов).
?

Замечу, что тут if/then/else лишние (избыточные). Хватило бы блоков с while.

Почитал про это самое доказательное программирование (вот тут: http://aivt.ftk.spbstu.ru/media/files/2012/course/quality/deductive_verification.pdf), собственно ясно что оно не пригодно для применения в обычном производстве софта, ибо слишком трудоемко и плохо масштабируется. Годится для простых систем (той же встроенки), там это себе можно позволить. С другой стороны уж там то баги часто с логикой программы (которую можно верифицировать) ну никак не связаны.
Название: Re: ещё про цикл дейкстры
Отправлено: Влад Жаринов от Август 21, 2012, 08:18:50 am
А с чем? Управление памятью?..

Кстати, возможно, поэтому проверка моделей больше востребована - тот же Спин сделала Белл для себя... потом и МС стала применять аналогичную систему для верификации драйверов и их взаимодействия с другими частями ОС... как поддержка чего вроде появилась "модель драйверов"...

Насчёт избыточности ветвления - это первыми заметили сами авторы теоремы... вот тут всплыло: http://forum.oberoncore.ru/viewtopic.php?p=73992#p73992 ... ;) Я так понимаю, что путаница с тем, что при доказательстве используются и обе структуры циклов, и ветвление...
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 21, 2012, 08:25:44 am
А с чем? Управление памятью?..
Не понял вопроса.

Насчёт избыточности ветвления - это первыми заметили сами авторы теоремы... вот тут всплыло: http://forum.oberoncore.ru/viewtopic.php?p=73992#p73992 ... ;) Я так понимаю, что путаница с тем, что при доказательстве используются и обе структуры циклов, и ветвление...
Ну, собственно это написано в любой книжке где описывается структурное программирование. Я это тоже где-то вычитал.
Название: Re: ещё про цикл дейкстры
Отправлено: Влад Жаринов от Август 21, 2012, 08:35:44 am
Да, вспомнил - для встроенки ведь актуально проверять системы процессов. При дедукции для этого м.б. использованы модифицированные исчисления программ - вроде
Цитата: http://grafkont.ru/ischislenie_ua_rv.html
этого
. Можно и описать логику поведения и величины состоояния - а дальше автоматизированный анализ/синтез софта для целевой платформы.
Название: Re: ещё про цикл дейкстры
Отправлено: Peter Almazov от Август 21, 2012, 10:22:53 am
Почитал про это самое доказательное программирование (вот тут: http://aivt.ftk.spbstu.ru/media/files/2012/course/quality/deductive_verification.pdf), собственно ясно что оно не пригодно для применения в обычном производстве софта, ибо слишком трудоемко и плохо масштабируется. Годится для простых систем (той же встроенки), там это себе можно позволить. С другой стороны уж там то баги часто с логикой программы (которую можно верифицировать) ну никак не связаны.
Тоже пролистал по диагонали.
Нежизнеспособно.
Даже нельзя сказать, что оно отомрет при реальной работе.
Оно до нее просто не доживет.
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 21, 2012, 11:01:23 am
Почитал про это самое доказательное программирование (вот тут: http://aivt.ftk.spbstu.ru/media/files/2012/course/quality/deductive_verification.pdf), собственно ясно что оно не пригодно для применения в обычном производстве софта, ибо слишком трудоемко и плохо масштабируется. Годится для простых систем (той же встроенки), там это себе можно позволить. С другой стороны уж там то баги часто с логикой программы (которую можно верифицировать) ну никак не связаны.
Почитай, что Дейкстра об этом писал (http://club.shelek.ru/viewart.php?id=147):
Цитата: Edsger W. Dijkstra
•Кое-кто из вас сомневается, что упомянутые ранее "приемы эффективного доказательства", столь изящные для маленьких программ, способны масштабироваться, я цитирую, "применимо к устрашающим размерам и явной сложности большинства программ". Что ж, они окажутся бессильны, если вы попытаетесь использовать их для распутывания хаоса, созданного группой некомпетентных, неорганизованных программистов. Их сила проявляется в фазе конструирования, когда (i) они приводят к значительно более коротким исходным текстам, чем созданные без их помощи, и (ii) длина вывода программы растет не быстрее, чем линейно, с ростом самой программы. Наконец, программы, произведенные таким способом, получаются бесконечно лучшими, чем обычный программный хлам.
Название: Re: ещё про цикл дейкстры
Отправлено: Peter Almazov от Август 21, 2012, 11:20:39 am
Почитал про это самое доказательное программирование (вот тут: http://aivt.ftk.spbstu.ru/media/files/2012/course/quality/deductive_verification.pdf), собственно ясно что оно не пригодно для применения в обычном производстве софта, ибо слишком трудоемко и плохо масштабируется. Годится для простых систем (той же встроенки), там это себе можно позволить. С другой стороны уж там то баги часто с логикой программы (которую можно верифицировать) ну никак не связаны.
Почитай, что Дейкстра об этом писал (http://club.shelek.ru/viewart.php?id=147):
Как минимум, он не мог писать об этом http://aivt.ftk.spbstu.ru/media/files/2012/course/quality/deductive_verification.pdf
:)
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 21, 2012, 12:08:31 pm
Почитал про это самое доказательное программирование (вот тут: http://aivt.ftk.spbstu.ru/media/files/2012/course/quality/deductive_verification.pdf), собственно ясно что оно не пригодно для применения в обычном производстве софта, ибо слишком трудоемко и плохо масштабируется. Годится для простых систем (той же встроенки), там это себе можно позволить. С другой стороны уж там то баги часто с логикой программы (которую можно верифицировать) ну никак не связаны.
Почитай, что Дейкстра об этом писал (http://club.shelek.ru/viewart.php?id=147):
Цитата: Edsger W. Dijkstra
•Кое-кто из вас сомневается, что упомянутые ранее "приемы эффективного доказательства", столь изящные для маленьких программ, способны масштабироваться, я цитирую, "применимо к устрашающим размерам и явной сложности большинства программ". Что ж, они окажутся бессильны, если вы попытаетесь использовать их для распутывания хаоса, созданного группой некомпетентных, неорганизованных программистов. Их сила проявляется в фазе конструирования, когда (i) они приводят к значительно более коротким исходным текстам, чем созданные без их помощи, и (ii) длина вывода программы растет не быстрее, чем линейно, с ростом самой программы. Наконец, программы, произведенные таким способом, получаются бесконечно лучшими, чем обычный программный хлам.

Нужно четко понимать контекст слов Дейкстры, какое тогда было время и какие техники программирования. Тогда была распространено писать на asm'e и в высокоуровневых языках плодить лапшу из goto. Естественно те програмки которые тогда писались (а они относительно сегодняшнего дня маленькие или средние) быстро становились не поддерживаемыми.

Применительно же к сегодняшнему дню я не видел ни одного примера когда доказательное написание приводило бы к уменьшению числа строк кода/объема кода.
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 21, 2012, 12:28:15 pm
Нужно четко понимать контекст слов Дейкстры, какое тогда было время и какие техники программирования. Тогда была распространено писать на asm'e и в высокоуровневых языках плодить лапшу из goto. Естественно те програмки которые тогда писались (а они относительно сегодняшнего дня маленькие или средние) быстро становились не поддерживаемыми.

Применительно же к сегодняшнему дню я не видел ни одного примера когда доказательное написание приводило бы к уменьшению числа строк кода/объема кода.

Это была выдержка из EWD1305 от 2000 г. -- не так уж и давно это было...
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 21, 2012, 12:43:55 pm
Нужно четко понимать контекст слов Дейкстры, какое тогда было время и какие техники программирования. Тогда была распространено писать на asm'e и в высокоуровневых языках плодить лапшу из goto. Естественно те програмки которые тогда писались (а они относительно сегодняшнего дня маленькие или средние) быстро становились не поддерживаемыми.

Применительно же к сегодняшнему дню я не видел ни одного примера когда доказательное написание приводило бы к уменьшению числа строк кода/объема кода.

Это была выдержка из EWD1305 от 2000 г. -- не так уж и давно это было...

ok. Но это всего лишь заявление и не факт что оно было сделано с учетом современных реалий а не его богатого опыта 70-х и 80-х. Поэтому неплохо бы показать каким образом это может работать. На реальном примере.
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Август 21, 2012, 01:13:50 pm

Применительно же к сегодняшнему дню я не видел ни одного примера когда доказательное написание приводило бы к уменьшению числа строк кода/объема кода.
:D тут вы забыли еще о длине  самого доказательства  ;D которая не меньше чем длина "оптимизированного" кода, весьма крутые требования к команде кодеров
( а где таких на практике взять? = разве что в коровнике  :D ). Во общем, время рассудит - или уже рассудило?  ;)
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 21, 2012, 01:19:32 pm
Поэтому неплохо бы показать каким образом это может работать. На реальном примере.

Так не проблема же -- бери в руки книшку "Дисциплина программирования" -- и вперёд! )))
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Август 21, 2012, 01:26:40 pm
Поэтому неплохо бы показать каким образом это может работать. На реальном примере.

Так не проблема же -- бери в руки книшку "Дисциплина программирования" -- и вперёд! )))
Лучше так:  "бери в руки книшку "Дисциплина программирования" , засунь под подушку и спать(шоб расстояние между гениальными идеями, содержащимися в ней ,и мозгом было минимальным),  а с утра в перед!  :D
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Август 21, 2012, 01:31:51 pm
...а если не прокатило то "вы попытаетесь использовать их для распутывания хаоса, созданного группой некомпетентных, неорганизованных программистов" - короче, сам дурак....
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 22, 2012, 02:34:31 am
Формальная верификация Си кода
http://habrahabr.ru/post/148709/
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Август 22, 2012, 03:12:12 am

Применительно же к сегодняшнему дню я не видел ни одного примера когда доказательное написание приводило бы к уменьшению числа строк кода/объема кода.
:D тут вы забыли еще о длине  самого доказательства  ;D которая не меньше чем длина "оптимизированного" кода, весьма крутые требования к команде кодеров
( а где таких на практике взять? = разве что в коровнике  :D ). Во общем, время рассудит - или уже рассудило?  ;)
Нда , слишком я оптимистичен был сравнивая длину доказательства с длинной доказываемого кода.... реальность воистину поражает:

"How big is seL4?

8,700 lines of C code plus 600 lines of ARM assembly code.
How much of it is verified?

7,500 lines of C code. We currently do not verify the assembly code and the boot code (1,200 lines).
How big is the proof?

 All together 200,000 lines of Isabelle proof script. Manually written, machine checked. Roughly 3,500 A4 pages if printed out (a stack about half a meter high).

 This is one of the largest formal proofs ever done. For comparison, the famous machine-checked proof of the four colour theorem is about 60,000 lines in the theorem prover. The only other proof that we know of that is larger, is from the Verisoft project (they report about 245,000 proof steps). Of course, in mathematics, the smaller the proof, the better it is considered to be :-)"
Название: Re: ещё про цикл дейкстры
Отправлено: vlad от Август 22, 2012, 03:12:19 am
Формальная верификация Си кода
http://habrahabr.ru/post/148709/

Мда. Впечатляет. Как иллюстрация того, что оно даже "не дойдет до попыток применения на реальном коде" :)
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Август 22, 2012, 03:19:15 am
т.е. коэффициент 1 к 30, не, пожалуй выну я Дейкстру из под подушки.... ;D А если учесть что эти 200000 строк писались ручками и по сути дела являются отдельной программой для прувера.... чур чура.....
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 22, 2012, 03:52:57 am
How much work was it?

 In total, design, documentation, implementation and verification of the seL4 kernel come to about 25-30 person years. This includes a lot of new research, new tools, and new libraries. If we were to do it again, we think it would be less than 10 person years.

 As a comparison, an industry rule of thumb for software certification in the Common Criteria process at Evaluation Level 6 (which is not even the highest) is $1,000 per line of code. That means a traditional process would be around $8.7 Million for seL4 and would give less assurance.

How many bugs have you found?

We found 160 bugs in the C code in total. 16 of these were found during testing and internal student projects running the kernel before the C verification had started in earnest. 144 bugs were found during the C verification phase.
Название: Re: ещё про цикл дейкстры
Отправлено: Влад Жаринов от Август 22, 2012, 04:03:49 am
А с чем? Управление памятью?..
Не понял вопроса.
...
Я имел в виду - с чем связано по-Вашему?.. м.б. как раз с ошибками в требованиях к программе?..
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 22, 2012, 05:28:31 am
А с чем? Управление памятью?..
Не понял вопроса.
...
Я имел в виду - с чем связано по-Вашему?.. м.б. как раз с ошибками в требованиях к программе?..
Самая большая проблема в отладке микроконтроллерного софта -- это воспроизведение внешних воздействий, сигналов с датчиков и тд. и тп...
Название: Re: ещё про цикл дейкстры
Отправлено: Влад Жаринов от Август 22, 2012, 09:14:39 am
А, это то, что решается типа как здесь (http://forum.oberoncore.ru/viewtopic.php?p=67448#p67448) или здесь (http://forum.oberoncore.ru/viewtopic.php?p=73579#p73579) говорилось...

Кстати, исходные данные для прувера как раз и можно понимать как "формализацию ТЗ"...
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 22, 2012, 09:41:18 am
А с чем? Управление памятью?..
Не понял вопроса.
...
Я имел в виду - с чем связано по-Вашему?.. м.б. как раз с ошибками в требованиях к программе?..
А, про это то. С памятью в мк  проблем вообще нет - какие могут быть проблемы когда ты знаешь в лицо каждый из 256 доступных байт? :-)

Основные проблемы, собственно как и везде, со взаимодействием с другими компонентами (не важно железные они или програмные). Общение с другой железкой (скажем сенсором) по I2C например бывает ну очень увлекательным. Не работает и все. Хоть ты пополам разорвись. Потом оказывается что документация лжет (и вообще все лгут) и клок в мегагерц оно не держит, и нужно сильно ниже например. Полно багов в самих кристалах (на уровне железа), впрочем это я описывал уже: http://oberspace.dyndns.org/index.php/topic,261.msg6259.html#msg6259

Ну и сторонние либы (например для реализации bluetooth стека). Там тоже бывает весело. И, замечу, это все и одновременно. В отличае от толстых десктопов и мобильников, в мк корректность работы это не только правильные алгоритмы, но и еще нужно уложиться по времени. Жесткий (настоящий) реалтайм. Ах, да, по энергопотреблению тоже уложиться нужно, ибо если твой мк жрет 4 mA, то он никому не нужен. И то что работает как часы без энергосбережения начинает глючть в одном из энергосберегающих режимов (на уровне железа с не софта).

Собственно от логики в мк (которую можно верифицировать) ну очень мало. В этом плане программы там очень простые - не запутаешься. Поэтому там вполне применим Дракон :-)
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Август 22, 2012, 12:41:51 pm
How much work was it?
.....
Geniepro - я пошутил, не принимайте так близко...,  лет через пятьдесят возможно будет использоваться автоматизированная верификация программ  - пока это мало кто себе может позволить, но развиваться в этом направлении стоит.. вот кто из живущих 60 лет назад мог бы по думать о сегодняшнем развитии вычь техники - я лишь смеюсь над кучкой людей сотворивших фетиш и толпой поклоняющихся ему.
Название: Re: ещё про цикл дейкстры
Отправлено: Влад Жаринов от Август 23, 2012, 04:37:56 am
Ну, формальная верификация проверкой моделей уже применяется всё шире...
Вот с формальной верификацией доказательством всё сложнее... не совсем ясно, что именно она даёт. Скорее в этом случае оправданно "сразу правильно строить программы"... по не сразу правильному формальному ТЗ... ;) т.е. нужна будет методика итеративного проектирования...

...
Собственно от логики в мк (которую можно верифицировать) ну очень мало. В этом плане программы там очень простые - не запутаешься. Поэтому там вполне применим Дракон :-)
А, так значит моё мнение, что техноязык немного продвинулся в практику (даже в такой с-ложной среде, как Ты-реализация) не случайно в первую очередь именно на этом направлении, было не случайным... ;) именно простота проектов и неудобство копания в асм-кодах в текстовой записи по сравнению с графикой икон и силуэтными джампами...
Название: Re: ещё про цикл дейкстры
Отправлено: valexey от Август 23, 2012, 09:43:47 am
...
Собственно от логики в мк (которую можно верифицировать) ну очень мало. В этом плане программы там очень простые - не запутаешься. Поэтому там вполне применим Дракон :-)
А, так значит моё мнение, что техноязык немного продвинулся в практику (даже в такой с-ложной среде, как Ты-реализация) не случайно в первую очередь именно на этом направлении, было не случайным... ;) именно простота проектов и неудобство копания в асм-кодах в текстовой записи по сравнению с графикой икон и силуэтными джампами...

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

На асме под мк пишут относительно редко. Обычно сейчас все же пишут на Си. Кроме того, соблюдать согласованность придуманной схемы на Драконе с рукописным кодом на асме будет тяжко. Так что основных причин две:
1) простота алгоритмов + малый размер кодовой базы (поэтому Дракон в принципе применим)
2) широкое применение графических схем в не програмных частях проекта (схемотехника) => банальная привычка к ним + будет экономия времени из за отсутствия необходимости переключения мозга с графического на текстовый "режим" восприятия и обработки.

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

(поэтому, кстати, оберон никогда не победит си и наоборот - никто из них многократно (в плане языка как инструмента) другого не превосходит, поэтому при выборе оберон или си влияет не сам язык, но окружение, инструментарий а также привычка/навыки конкретного человека)
Название: Re: ещё про цикл дейкстры
Отправлено: Kemet от Август 23, 2012, 10:16:55 am
Скорее потенциальная популярность Дракона у микроконтроллерщиков связана с их привычкой к графическим двумерным схемам
Под микроконтроллеры не пишут тонны кода, поэтому вполне реально и кому-то даже удобно, рисовать блок-схемы. Как только размер программы начинает увеличиваться, и рисовать становится абсолютно непродуктивно, блок-схемы уходят даже не на второй, а на третий план, ибо писать программы и рисовать блок-схемы несколько разные вещи.

valexey: поправил оформление цитаты
Название: Re: ещё про цикл дейкстры
Отправлено: Влад Жаринов от Август 23, 2012, 11:11:01 am
...
На асме под мк пишут относительно редко. Обычно сейчас все же пишут на Си. Кроме того, соблюдать согласованность придуманной схемы на Драконе с рукописным кодом на асме будет тяжко.
В принципе да.. в том же ГРАФИТ-ФЛОКСЕ есть кодогенератор...
И Дмитрий_ВБ в своей среде ЯВУ-программы представляет. Хотя в её обсуждении один разработчик, как можно понять из "визуальных требований" здесь (http://forum.easyelectronics.ru/viewtopic.php?p=204726#p204726), как раз предлагал и асм-запись употреблять... и в ГРАФКОНТе на асме можно писать, как и смотреть сгенерённый код... отсюда (http://grafkont.ru/rabota_s_redaktorom_fayla_opisaniy_fp_i_lp.html) вроде как следует...

...
Так что основных причин две:
1) простота алгоритмов + малый размер кодовой базы (поэтому Дракон в принципе применим)
2) широкое применение графических схем в не програмных частях проекта (схемотехника) => банальная привычка к ним + будет экономия времени из за отсутствия необходимости переключения мозга с графического на текстовый "режим" восприятия и обработки.
Ага... а то вот такими тезисами (http://forum.oberoncore.ru/viewtopic.php?p=73879#p73879) обосновывается вроде как неограниченная применимость... и приходится показывать, что, во-первых, ограниченная, а во-вторых, в любом случае не как "вещи в себе" - а в связи с другими аспектами содержания проекта (допустим, когда процедуры маленькие - то, как замечают Лаптев и Прохоренко, не их схемы в первую очередь нужны - а схемы зависимостей между ними)...

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

(поэтому, кстати, оберон никогда не победит си и наоборот - никто из них многократно (в плане языка как инструмента) другого не превосходит, поэтому при выборе оберон или си влияет не сам язык, но окружение, инструментарий а также привычка/навыки конкретного человека)
Ну, короче, тот же принцип "консерватизма языковых ниш", ещё Кауфманом (http://forum.oberoncore.ru/viewtopic.php?p=71218#p71218) сформулированный, работает... :)
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Август 23, 2012, 12:35:49 pm

(поэтому, кстати, оберон никогда не победит си и наоборот - никто из них многократно (в плане языка как инструмента) другого не превосходит, поэтому при выборе оберон или си влияет не сам язык, но окружение, инструментарий а также привычка/навыки конкретного человека)
Да нужно учитывать и взвешивать множество факторов, но есть  такой момент как "безрыбье"... правда в этом случае  наличие одного компилятора не спасет
нужно полное окружение для комфортной работы, причем на современном уровне (попытки юродствовать, как показывает пример коровника ни к чему полезному не приводят)
Название: Re: ещё про цикл дейкстры
Отправлено: Geniepro от Август 24, 2012, 02:22:55 am
Таки скачал я этот seL4 http://ertos.nicta.com.au/software/seL4/home.pyl
Люббопытно стало... Но что там в 60 метров архива уместилось??? Вот тебе и 8700 строк микроядра )))
Название: Re: ещё про цикл дейкстры
Отправлено: DIzer от Август 24, 2012, 04:38:10 am
Вот и  скажите  :D
Название: Re: ещё про цикл дейкстры
Отправлено: Peter Almazov от Ноябрь 29, 2018, 07:11:05 am
Хотелось бы зафиксировать одно наблюдение про цикл Дейкстры.
Оно, конечно, абсолютно очевидное, часто всплывает в примерах, но я не припомню, чтобы кто-то его четко сформулировал.
А именно: цикл Дейкстры всегда можно тупо преобразовать в обычный цикл без exit-ов и break-ов.
Нужно собрать в заголовке все предохранители.

do
  P1 → S1,
  P2 → S2,
   …
  Pn → Sn
od

=>

while (P1 or P2 ... or Pn) do
  if P1 then
    S1;
  else if P2 then
    S2
    ...
  else if Pn then
    Sn
  end if
end while

Неэффективно, да.
Но полезно для рассуждений.