Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу 4. Написать программу, которая возвращает список
Ответ
 
Опции темы Опции просмотра
  (#31 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 25.12.2017, 14:58

Цитата:
Сообщение от SergeMukhin78 Посмотреть сообщение
...мой алгоритм самый быстрый, всего за три прохода...
- вот это вот не понял, как это за три раза. И один раз поинтересовался. Потом напомнал о своей просьбе. Так нифига и не увидел.
От пустой балаболки слышу!!!)))

P.S. Пардон - от балаболки с картинками!!!

Последний раз редактировалось aag; 25.12.2017 в 15:02
Ответить с цитированием
  (#32 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 565
Сказал(а) спасибо: 17
Поблагодарили 35 раз(а) в 35 сообщениях
Регистрация: 28.03.2012
По умолчанию 25.12.2017, 15:09

я привел алгоритм! то что некоторые не понимают этого - их проблема.

мене, текел, фарес
Ответить с цитированием
  (#33 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 25.12.2017, 15:13

Люди!!! Пожалуйста!!!
Кто понял, спасите идиота(меня)!!!
Приведите тута реализацию(три максимума за три прохода), ОГРОМНОЕ ПОЖАЛУЙСТА!!!
Ответить с цитированием
  (#34 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 565
Сказал(а) спасибо: 17
Поблагодарили 35 раз(а) в 35 сообщениях
Регистрация: 28.03.2012
По умолчанию 25.12.2017, 15:29

Хорошо, попробуем показать как надо решать такие задачи. Пишу нудно, но аудитория просит.

Давай решим сначала задачу проще, где нет повторов, или их надо игнорировать.
Это понятно как делать? Или надо расписывать подробней?

подробней:
Если нет то мы просто вводим в предикат поиска максимума дополнительный параметр значение, выше которого искать не надо. Реализация такого предиката понятна? (Это всё повтор, что я уже писал!)

Вернёмся к начальной задаче. Чем она отличается от той что мы только что решили? Надо искать дубликаты. Я привёл ТРИ варианта, как это делать. И ещё два придумал после этого. Возьмём например такой.
Запомним индекс максимума. И в следующий раз ищем с этой точки это же значение. Если находим - добавляем в рещультат, нет ищем следующее по величине значение.
фу. мы писали, мы писали, наши пальчики устали.

что тут не понятно?

Попробуйте написать

Последний раз редактировалось SergeMukhin78; 25.12.2017 в 15:35 Причина: опечатка
Ответить с цитированием
  (#35 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 25.12.2017, 15:33

Не - ну Вы отдохните, наверное. Не тратьте на меня Ваше драгоценное время. Теории тута уже до попы)))
Кто-нибудь, кто понял, спасите идиота)))
Ответить с цитированием
Ads.
  (#36 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 565
Сказал(а) спасибо: 17
Поблагодарили 35 раз(а) в 35 сообщениях
Регистрация: 28.03.2012
По умолчанию 25.12.2017, 15:41

спасибо за заботу.
вот так я тестировал и получал тайминги (может поможет кому-нибудь, кто умеет писать на прологе):
Visual Prolog Код:
class predicates
    prof : (unsigned* List, function{unsigned*, unsigned*}) -> real Sec.
clauses
    prof(List, Function) = performanceCounter::run2seconds({  :- _ = Function(List) }).

class predicates
    makeList : (unsigned N) -> unsigned* List.
clauses
    makeList(N) =
        [ X ||
            _I = std::cIterate(N),
            X = math::random(10 * N)
        ].

clauses
    run() :-
        foreach N0 = std::fromTo(1, 100) do
            N = 1000 * N0,
            memory::garbageCollect(),
            List = makeList(N),
            Sln = prof(List, algNlnN),
            S3 = prof(List, algN3),
            stdio::writef("%5d,%,%\n", N, Sln, S3)
%            Result1 = algNlnN(List),
%            Result2 = algN3(List),
%            stdio::writef("%   % \n", Result1, Result2),
%            try
%                Result1 == Result2
%            catch TraceId do
%                stdio::writef("List:% \n", List),
%                exception::continue_unknown(TraceId)
%            end try
        end foreach.
Ответить с цитированием
Ads
  (#37 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 25.12.2017, 16:02

Ну - кто бы сомневался!!! В деле тестирования Вы давно и однозначно впереди планеты всей)))
Рекомендую настоятельно: если кому надо чего протестировать, обращайтесь к Мухину. Он лучший!!!

Мне же три максимума за три прохода, кто-нибудь, кто понял.

И - у нас тута уже Рождественские каникулы. Потом прочее. Пару недель не до всех этих компутеров - но я обязательно вернусь)))
Всех с Наступающим!!!
Ответить с цитированием
  (#38 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 565
Сказал(а) спасибо: 17
Поблагодарили 35 раз(а) в 35 сообщениях
Регистрация: 28.03.2012
По умолчанию 26.12.2017, 11:03

есть совсем уж простое решение с трёмя проходами (хотя формально с 6-ю), правда не оптимальное, т.к. требует три (в худшем случае) перезаписи списка. (0 в хорошем и 1,5 в среднем).

т.е. сложность алгоритма O(N)

как-то так:

Visual Prolog Код:
class predicates
    alg3remove : (unsigned* List) -> unsigned* Result.
clauses
   alg3remove(List) = Result :-
        VList = varM::new(List),
        Result =
            [ M ||
                _ = std::cIterate(3),
                M = list::maximum(VList:value),
                VList:value := list::remove(VList:value, M)
            ].

и по скорости показывает лучше чем с сортировкой, но хуже чем мой.
Миниатюры
capture.png  

Последний раз редактировалось SergeMukhin78; 26.12.2017 в 11:04 Причина: уж
Ответить с цитированием
  (#39 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 26.12.2017, 15:08

Цитата:
Сообщение от SergeMukhin78 Посмотреть сообщение
есть совсем уж простое решение с трёмя проходами (хотя формально с 6-ю)...
Ну да. Но зачем фсе эти понты, которые к тому же студенту не простят?!)))
От студента ждут чего-нибудь такое:
Visual Prolog Код:
p(0, _ ) = [] :- !.
p(N, List) = [ M | p(N-1, list::remove(List,M)) ] :- M = list::maximum(List).

Три прохода таки зажали - ну, чиво Вы тама, в сет-е индексы храните?! Гениально.
Я эту страшную тайну тоже никому не скажу!!!
Но сет студенту не пропустят.

Если кому-то когда-то почему-то придётся в промышленных масштабах ворочать
"M каких-то из списка длинной N", то попробуйте таки посортировать.
Слиянием, конечно. На этапе этого слияния и усекать до нужной длины М.
В ВИПе это просто: добавить один аргумент и одну голову в
merge2 : (comparator{A}, A*, A*) -> A*(класс list).
Мона ещё и на этапе разбиения исходного на подсписки до М рубить, но есть пара "но"))).

И это, таво, С Наступающим, каникулы, мля)))
Ответить с цитированием
  (#40 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 565
Сказал(а) спасибо: 17
Поблагодарили 35 раз(а) в 35 сообщениях
Регистрация: 28.03.2012
По умолчанию 26.12.2017, 17:52

Цитата:
Сообщение от aag Посмотреть сообщение
в сет-е индексы храните
нет, я считаю количество максимальных
Ответить с цитированием
  (#41 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 565
Сказал(а) спасибо: 17
Поблагодарили 35 раз(а) в 35 сообщениях
Регистрация: 28.03.2012
По умолчанию 26.12.2017, 17:54

Цитата:
Сообщение от aag Посмотреть сообщение
От студента ждут чего-нибудь такое:
это другой вид алгоритма с удалением, т.е. 6 проходов и три перезаписи

Последний раз редактировалось SergeMukhin78; 26.12.2017 в 17:55 Причина: и три
Ответить с цитированием
  (#42 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 565
Сказал(а) спасибо: 17
Поблагодарили 35 раз(а) в 35 сообщениях
Регистрация: 28.03.2012
По умолчанию 26.12.2017, 18:01

Цитата:
Сообщение от aag Посмотреть сообщение
Три прохода таки зажали
вот Винитарх про один проход говорил, и такое решение точно есть, но по алгоритмической сложности (не по жизни) оно все равно моим простым 3м проходам (и не равно 6 с перезаписью).

мб на прологе его (1проход) трудней реализовать, но я не думал.
Ответить с цитированием
  (#43 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 565
Сказал(а) спасибо: 17
Поблагодарили 35 раз(а) в 35 сообщениях
Регистрация: 28.03.2012
По умолчанию 26.12.2017, 18:07

Цитата:
Сообщение от SergeMukhin78 Посмотреть сообщение
(и не равно 6 с перезаписью).
здесь я ошибся. равно. Просто здесь 3 простых и 3 тяжёлых прохода, для качества программы это важно, для сложности алгоритма нет, она всё равно O(N).

Последний раз редактировалось SergeMukhin78; 26.12.2017 в 18:07 Причина: она
Ответить с цитированием
  (#44 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 565
Сказал(а) спасибо: 17
Поблагодарили 35 раз(а) в 35 сообщениях
Регистрация: 28.03.2012
По умолчанию 26.12.2017, 18:38

Цитата:
Сообщение от aag Посмотреть сообщение
Слиянием, конечно.
как раз сортировка слиянием здесь совсем не подходит имхо. heap сортировка или сортировка выбором - мб, надо смотреть.
Ответить с цитированием
  (#45 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,963
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 26.12.2017, 22:58

Друзья мои!
Вы меня утомили этой битвой на булавках.
Я здесь набросал и три быстрых прохода и один медленный.
Можете их чуть улучшить, зная внутреннюю реализацию обработки списков в VIP лучше меня.
Можете построить графики для их сравнения.
Visual Prolog Код:
implement main
open core, console

class predicates
max3 : (E*, E, unsigned [out]) -> E determ.   % три быстрых прохода
max3_ : (E*, E, E, unsigned, unsigned [out]) -> E determ.
max1 : (E*) -> E* determ.    % один медленный проход
max1_ : (E*,E,E,E) -> E* determ.

clauses
max3([Max|List], SuperMax, Count) = max3_(List, Max, SuperMax, 1, Count) :- Max<SuperMax,!.
max3([_|List], SuperMax, Count) = max3(List, SuperMax, Count).

max3_([Max|List], Max, SuperMax, I, Count) = max3_(List, Max, SuperMax, I+1, Count) :-!.
max3_([A|List], Max, SuperMax, _I, Count) = max3_(List, A, SuperMax, 1, Count) :- A>Max, A<SuperMax,!.
max3_([_|List], Max, SuperMax, I, Count) = max3_(List, Max, SuperMax, I, Count).
max3_([], Max, _SuperMax, I, I) = Max.

max1([A,B,C|List]) = max1_(List,A,B,C) :- A>=B, B>=C,!.
max1([A,B,C|List]) = max1_(List,A,C,B) :- A>=C, C>=B,!.
max1([A,B,C|List]) = max1_(List,B,A,C) :- B>=A, A>=C,!.
max1([A,B,C|List]) = max1_(List,B,C,A) :- B>=C, C>=A,!.
max1([A,B,C|List]) = max1_(List,C,A,B) :- C>=A, A>=B,!.
max1([A,B,C|List]) = max1_(List,C,B,A) :- C>=B, B>=A.

max1_([E|List],A,B,_C) = max1_(List,E,A,B) :- E>=A,!.
max1_([E|List],A,B,_C) = max1_(List,A,E,B) :- E>=B,!.
max1_([E|List],A,B,C) = max1_(List,A,B,E) :- E>=C,!.
max1_([_|List],A,B,C) = max1_(List,A,B,C).
max1_([],A,B,C) = [A,B,C].

run() :- List = [3,4,8,5,6,7,8],
            A = max3(List, upperBound(integer), I1),   % вызов трёх быстрых проходов
            ( I1 >= 3, Result = [A,A,A] orelse
               I1 = 2, B = max3(List, A, _), Result = [A,A,B] orelse
               I1 = 1, B = max3(List, A, I2),
               ( I2 >= 2, Result = [A,B,B] orelse
                 C = max3(List, B,_), Result = [A,B,C] )),
            write(Result),nl,
            Result1 = max1(List),   % вызов одного медленного прохода
            write(Result1),
            _=readchar() orelse
            write("Что-то не так..."),
            _=readchar().

end implement main

goal
    console::run(main::run).
Вот графики вычислительной сложности мне тоже интересны. Вернее интересна длина списка на которой надо подкачивать в кеш. Правда кеш у всех разный.
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Дан список. Написать функцию, которая возвращает количество уровней сложного списка н Елизавета Яросевич Задания за деньги 0 03.11.2013 20:42
Написать функцию,которая по двум числам формирует список Marishe Lisp 1 13.10.2010 11:37
Написать программу которая разделит исходный список denis120 Lisp 3 22.05.2010 00:19
Определить рекурсию, которая возвращает список hattation Lisp 3 10.02.2010 20:21
Написать функцию, которая по списку lst и атому obj возвращает множество klava Lisp 1 22.12.2009 14:05
Нужно написать рекурсивную функцию, которая возвращает t Bender266 Lisp 6 06.05.2009 14:40
Написать функцию, которая возвращает истину Bender266 Lisp 0 06.05.2009 13:47
Написать функцию ,которая добавляет в список по одному элементу Mozgolom Lisp 2 14.05.2008 03:22
Написать функцию, которая возвращает количество вершин Adebayor Lisp 11 16.12.2007 22:58
Написать функцию LAST1, которая возвращает предпоследний элемент списка Sw1ft Lisp 9 17.05.2007 20:25
Написать функцию, которая оращает многоуровневый список super_girl Lisp 2 13.04.2007 07:25
Написать программу которая закрывает любую программу из автозагрузки без перезагрузк Anonymous C++ Builder 1 07.10.2003 11:24



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов