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

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
ещё про цикл дейкстры
« : Июль 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 понимает без проблем.
Впрочем, для глобальных функций всё равно принято специфицировать типы...
to iterate is human, to recurse, divine

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

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #1 : Июль 20, 2012, 06:06:49 am »
Это решение другой, более удобной для решателя, задачи  :)
В решении Ильи ответом является массив, по которому можно дать ответ на вопрос: скока человек решили ровно 5 задач? Ответ: stat[5] = 0, т.е. 0 человек.

А ЦД там можно выкинуть в конце. Он использовался на этапе рассуждений.
« Последнее редактирование: Июль 20, 2012, 06:12:15 am от Peter Almazov »

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #2 : Июль 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
to iterate is human, to recurse, divine

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

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #3 : Июль 20, 2012, 07:54:31 am »
Ну и что в итоге-то выигрываем, в последнем варианте? Достаточно хитрая комбинация трансформаций... Что думать над циклом, что думать над ней... Только уровень абстракции гораздо выше - вам нужно правильно применить достаточно сложные по поведению общие средства к решению частной задачи... По моему убеждению, легче (и надёжнее) собирать из простых частных элементов, нежели комбинировать и параметризовать сложные обобщённые.

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

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

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: ещё про цикл дейкстры
« Ответ #4 : Июль 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

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #5 : Июль 20, 2012, 08:27:34 am »
Этот вариант был бы прекрасен, если бы структура БД была открытой и документированной. Всё, что мы имеем, - это CSV или XLS-экспорт.
Можно было, правда, как вариант, быстренько залить в какой-нить MySQL и поиметь это дело запросами...
С другой стороны, всё равно CSV надо сначала как-то машинно преобразовать в дамп для загрузки.

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #6 : Июль 20, 2012, 08:31:48 am »
Ну и что в итоге-то выигрываем, в последнем варианте? Достаточно хитрая комбинация трансформаций...
Да ничего особо хитрого там нет. Просто пошаговые приближения от исходных данных к требуемому результату...

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

Я написал цикл буквально за минуту-другую, не отрывая ручки от бумаги...
Несколько минут с подготовкой тестовых данных и тестированием...
А Ваш цикл на бумаге кишел ошибками, и если одну указал бы компилятор, то другую пришлось бы отлаживать тестами.
to iterate is human, to recurse, divine

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

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #7 : Июль 20, 2012, 08:42:52 am »
Какими ошибками? При вводе с листка на экран очевидная опечатка не поменялось бы на c i на j?

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: ещё про цикл дейкстры
« Ответ #8 : Июль 20, 2012, 09:07:26 am »
Этот вариант был бы прекрасен, если бы структура БД была открытой и документированной. Всё, что мы имеем, - это CSV или XLS-экспорт.
Можно было, правда, как вариант, быстренько залить в какой-нить MySQL и поиметь это дело запросами...
С другой стороны, всё равно CSV надо сначала как-то машинно преобразовать в дамп для загрузки.

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

ps. Упс... У меня там вместо sum count должен быть
« Последнее редактирование: Июль 20, 2012, 09:11:00 am от ilovb »

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: ещё про цикл дейкстры
« Ответ #9 : Июль 20, 2012, 09:22:00 am »
Эта задача чисто SQL-ная.

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

Этот вариант не подойдет только тогда, когда нужно выжать максимум скорости.

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #10 : Июль 20, 2012, 09:57:53 am »
Какими ошибками? При вводе с листка на экран очевидная опечатка не поменялось бы на c i на j?
Ну Вам эта ошибка очевидна, мне, например, нет. Я сильно не рассамтривал Ваш алгоритм, не анализировал его, но всё же с первого взгляда его суть я не понял...
to iterate is human, to recurse, divine

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

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #11 : Июль 20, 2012, 09:59:42 am »
На вражеском форуме новая тема про ЦД: http://forum.oberoncore.ru/viewtopic.php?f=82&t=4027
Там у Ермакова получился запутанный и глючный ЦД, походу он его ни разу не тестировал.
Ну, во первых, то не вражеский форум а просто альтернативный с очень альтернативными порядками и модераторами. Там просто идеалогия важнее истины :-)

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

В данном случае прошу озвучить условие решаемой задачи.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #12 : Июль 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
to iterate is human, to recurse, divine

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

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: ещё про цикл дейкстры
« Ответ #13 : Июль 20, 2012, 11:27:24 am »
Посмотрел на том форуме.... чета слишком заумно для такой задачи.

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

Список = Новый Массив;
   Список.Добавить("10");
   Список.Добавить("10");
   Список.Добавить("20");
   Список.Добавить("30");
   Список.Добавить("30");
   Список.Добавить("30");
   Список.Добавить("40");
   Список.Добавить("50");
   Список.Добавить("50");
   Список.Добавить("50");
   
   МаксимумЭкзаменов = 100;
   
   Статистика = Новый Массив(МаксимумЭкзаменов);
   
   ТекЭлемент = Неопределено;
   КоличествоЭкзаменов = 0;
   
   Для Каждого Элемент Из Список Цикл
      
      Если Элемент = ТекЭлемент Тогда // считаем
         КоличествоЭкзаменов = КоличествоЭкзаменов + 1;
      Иначе // обрабатываем результат и берем следующий элемент
         Статистика[КоличествоЭкзаменов] = Статистика[КоличествоЭкзаменов] + 1;
         КоличествоЭкзаменов = 1;
         ТекЭлемент = Элемент;
      КонецЕсли;
      
   КонецЦикла;
   
   Статистика[КоличествоЭкзаменов] = Статистика[КоличествоЭкзаменов] + 1;

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #14 : Июль 20, 2012, 12:17:30 pm »
Ваш цикл тоже, по структуре, оптимизированный ЦД (где условие "пока не конец последовательности" вынесено).