Автор Тема: Про необходимость for(each)  (Прочитано 53436 раз)

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #30 : Февраль 09, 2012, 11:07:15 am »
http://en.wikipedia.org/wiki/Dutch_national_flag_problem
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
(Dutch - голландский, нидерландский)
Там в решении присутствует swap, который можно заменить двумя присваиваниями, а не тремя, т.к. один элемент известен и не надо его запоминать.
Чтобы не пугать народ, я не сказал про Дейкстру. Ведь задача действительно простая. Это следует хотя бы из размера решения.
Но нормальный программист оказывается здесь безоружным и спотыкается. Он может расчитывать только на озарение и догадку, а они плохо предсказуемы.
Меня лично это не устраивает, я предпочитаю гарантированно переезжать такие задачи как трактор, почти не снижая скорости. Остальные, видимо, смирились с текущим положением. Может быть, хоть сейчас кто-то возмутится и спросит "ДОКОЛЕ?!"

Тут есть еще один интересный момент. Основатель "учения о линейном поиске" Info21, считает что в циклах бывает "либо полный проход, либо линейный поиск, либо аккуратненький Дейкстра. Исключений пока не встречал" http://forum.oberoncore.ru/viewtopic.php?p=59773#p59773
Здесь костыль "линейной поиск" не работает. Info21 не мог не видеть эту задачу в "Дисциплине программирования". Пример когнитивной слепоты, симптомы которой он так ярко сам описал. Еще один повод задуматься о "базовых схемах циклов".

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #31 : Февраль 09, 2012, 11:54:25 am »
Я не понял, в чём был прикол данной задачи.
Никаких ограничений на её решение не возлагалось -- например, не было требования линейного времени сортировки.
А значит: лучшее решение == самое простое.
Что может быть проще, чем вызвать стандартную процедуру сортировки массива?
to iterate is human, to recurse, divine

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

Berserker

  • Sr. Member
  • ****
  • Сообщений: 254
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #32 : Февраль 09, 2012, 11:57:33 am »
Я всё-таки не вижу, в чём бы не прав info21. Цикл Дейкстры в простейшем случае вырождается в одноветочный while, который сам по себе универсален.

vlad напомнил про развитие и поддержку. Что если цветов уже 4? А если пять? В таком случае проще один раз написать сортировку подсчётом, как золотую середину между конкретной ручной оптимизацией и полностью абстрактным вариантом от содержимого массива, как в случае с использованием библиотечной функции. Разумеется, это если есть подозрение, что мы выиграем хотя бы 10% в ощущаемой скорости программы.

DIzer

  • Гость
Re: Про необходимость for(each)
« Ответ #33 : Февраль 09, 2012, 12:26:29 pm »
подозрение, что мы выиграем хотя бы 10% в ощущаемой скорости программы.
Это стандартная задача на квалификацию ОБУЧЕННОГО программиста (прослушавшего БАЗОВЫЙ курс по алгоритмизации вуза, либо школьника из продвинутого лицея) решение о применении того или иного метода принимается по мере анализа задачи в данном случае мы имеем ЯРКО выраженную "специфичность" задачи (небольшое число различных значений сортируемых элементов идущих друг за другом). Выбор метода однозначен. На ощущения можно и должно ЗАБИТЬ если известен размер сортируемого массива. Все таки 2*N это не Nlog(N). А насчет HANDMADE  оптимизаций - ошибки Валерия показывают  правоту большинства высказавшихся по этому вопросу  - не фиг , если это не АБСОЛЮТНО критично. Что касается использования обычного sort'a - то я не против (а то слишком много развелось конкурентов )  :)

trurl

  • Full Member
  • ***
  • Сообщений: 133
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #34 : Февраль 09, 2012, 12:27:03 pm »
Тут есть еще один интересный момент. Основатель "учения о линейном поиске" Info21, считает что в циклах бывает "либо полный проход, либо линейный поиск, либо аккуратненький Дейкстра. Исключений пока не встречал" http://forum.oberoncore.ru/viewtopic.php?p=59773#p59773
Здесь костыль "линейной поиск" не работает.
Зато работает "аккуратненький Дейкстра". ;)

trurl

  • Full Member
  • ***
  • Сообщений: 133
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #35 : Февраль 09, 2012, 12:29:30 pm »
Я не понял, в чём был прикол данной задачи.
В исходной постановке определение цвета - очень дорогая операция.

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #36 : Февраль 09, 2012, 12:50:12 pm »
Я не понял, в чём был прикол данной задачи.
В исходной постановке определение цвета - очень дорогая операция.

То есть из этого следовало требование проделать всю работу за 1 проход по массиву?
to iterate is human, to recurse, divine

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

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #37 : Февраль 09, 2012, 08:38:20 pm »
А насчет HANDMADE  оптимизаций - ошибки Валерия показывают  правоту большинства высказавшихся по этому вопросу  - не фиг , если это не АБСОЛЮТНО критично.
На моё решение повлияло 2 обстоятельства: 1) его не собирались использовать в реальной жизни; 2) был уже час ночи, и я хотел побыстрее пойти спать. Именно поэтому я написал его, окинул ещё раз взглядом и выбросил сюда. На свежую голову или хотя бы при большем количестве времени я бы ошибки убрал. Так что первое: ошибки - это не правило.

Да, если бы я использовал sort, то ошибок бы не было. Но с чего вы взяли, что задача требовала сортировки?
Увидел массив чисел и быстро вспомнил, что уже умею с этим объектом делать, а потом выбрал для него ту операцию, в пояснении к которой больше слов пересекается с словами из задачи? Это называется "программирование по ассоциациям". Её продуктом становится индусский код. Например, нужно найти минимальное число в массиве. "Так, массив сортируется. Первым его элементом после этого будет тот, который мне нужен" - подумает "индус". И сделал. Циклы? В них же делают ошибки. Не нужны нам эти "оптимизации".

С элементом надо делать не то, что умеем, а то, что требуется. Отсюда следует второе: это была не оптимизация, а решение, ведущее к цели.

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #38 : Февраль 09, 2012, 09:23:34 pm »
Вот тут где-то советовали начинающим программистам пользоваться языком без сборки мусора. А что, это его (начинающего) главная цель? Освоить ручное управление памятью.

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

Умение вручную разместить и убрать переменную из памяти поможет ему? Нет. Можно ли без этого навыка обойтись в программировании? Довольно часто - да.
Умение сначала пытаться усвоить задачу перед её решением поможет ему? Да. Можно ли без него обойтись? Только в простейших случаях.

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

Хороша ли задача, которую привёл Пётр, чтобы преподаватели использовали её в качестве наработки навыка усваивания (или анализа - так, наверное, правильнее)? Сложный вопрос. Но, думаю, она даётся именно с этой целью. А не чтобы обезьяна нашла, как написать на клавиатуре sort.

DIzer

  • Гость
Re: Про необходимость for(each)
« Ответ #39 : Февраль 09, 2012, 09:24:48 pm »

.....Да, если бы я использовал sort, то ошибок бы не было. Но с чего вы взяли, что задача требовала сортировки?...

С элементом надо делать не то, что умеем, а то, что требуется. Отсюда следует второе: это была не оптимизация, а решение, ведущее к цели.
1. Так  поставил ее Петр
2. Да тут я ошибся - думал что вы стали делать этот вариант зная о сортировке подсчетом - в этом случае он выглядел оптимизацией, правильно было hand -made решение.
Уточнение - на фиг  hand -made решения и оптимизации без абсолютной необходимости.

alexus

  • Гость
Re: Про необходимость for(each)
« Ответ #40 : Февраль 10, 2012, 03:13:20 am »
Вот тут где-то советовали начинающим программистам пользоваться языком без сборки мусора. А что, это его (начинающего) главная цель? Освоить ручное управление памятью.
Не думаю, что такая постановка вопроса является правильной. Главная цель любого обучающегося - научиться... цель начинающего программиста - научиться пользоваться инструментами (см. ниже).

Умение вручную разместить и убрать переменную из памяти поможет ему? Нет. Можно ли без этого навыка обойтись в программировании? Довольно часто - да.
Умение сначала пытаться усвоить задачу перед её решением поможет ему? Да. Можно ли без него обойтись? Только в простейших случаях.

Усваивать не значит заучить текст и уметь его по памяти слово в слово прочитать его как слева направо, так и справа налево. Это такая вещь, которая может много где пригодиться по жизни. И никакое программирование ей не нужно. А вот обратное - хорошо программировать пренебрегая этой вещью - я думаю, невозможно. И поэтому, это умение должно быть освоено или до начала программирования или вместе с ним. И поэтому преподаватели (конкретно Илья и info21) считают, что
а) любые элементы в зыке программирования лишние, и мешают учиться правильно воспринимать задачу. Но поскольку без элементов не будет формы, в которую можно облекать решение, то пускай хотя бы их будет разумно минимально.
б) требуются задачи, на которых студент учился бы "отпускать" своё сознание для усваивания задачи, а не судорожно бы тыкался по списку запомненных операций над данными.
Перечисленные Вами господа учат не программированию, а решению задач. Они просто не различают суть: анализа, проектирования и кодирования. И это скверно... поскольку требования к каждому из этих направлений совершенно разные. Программист должен знать:
  • инструменты:
    • язык программирования,
    • библиотеки и иерархии классов,
    • API ОС,
    • отладчики и пр.;
  • приёмы и методы решения простейших задач (наподобие той, что была приведена ранее);
  • правила ведения технической документации;

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

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #41 : Февраль 10, 2012, 04:40:12 am »
Увидел массив чисел и быстро вспомнил, что уже умею с этим объектом делать, а потом выбрал для него ту операцию, в пояснении к которой больше слов пересекается с словами из задачи? Это называется "программирование по ассоциациям". Её продуктом становится индусский код. Например, нужно найти минимальное число в массиве. "Так, массив сортируется. Первым его элементом после этого будет тот, который мне нужен" - подумает "индус". И сделал. Циклы? В них же делают ошибки. Не нужны нам эти "оптимизации".
Неверно. Правильный "индус" вызовет стандартную процедуру поиска минимального элемента массива, которая решит данную задачу быстрее и надёжнее самопального цикла.
to iterate is human, to recurse, divine

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

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #42 : Февраль 10, 2012, 09:20:46 am »
Я не понял, в чём был прикол данной задачи.
Никаких ограничений на её решение не возлагалось -- например, не было требования линейного времени сортировки.
А значит: лучшее решение == самое простое.
Что может быть проще, чем вызвать стандартную процедуру сортировки массива?
Если бы я сказал, что это критичный кусок и произодительность стандартной сортировки не устраивает, то единственно правильным решением для программиста любой национальности было бы такое: смотреть справочник алгоритмов. Но тогда нечего было бы обсуждать.
Вот и пришлось давить не на производительность, а на самолюбие  ;)

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #43 : Февраль 10, 2012, 10:08:41 am »
Тут есть еще один интересный момент. Основатель "учения о линейном поиске" Info21, считает что в циклах бывает "либо полный проход, либо линейный поиск, либо аккуратненький Дейкстра. Исключений пока не встречал" http://forum.oberoncore.ru/viewtopic.php?p=59773#p59773
Здесь костыль "линейной поиск" не работает.
Зато работает "аккуратненький Дейкстра". ;)
Поначалу не хотел отвечать на дурацкий пост, т.к. чувствую бессмысленность. Все-таки отвечу.

Во-первых, решение можно попытаться переписать, используя ЦД, но это будет не "аккуратненький Дейкстра", а страшный изврат. Подгонка под "учение". Сам Римский Па Дейкстра этого не делает.



Во-вторых, и это самое главное, польза от решения применить ЦД не намного больше, чем от совета использовать для записи цикла алфавитно-цифровые символы. С линейным поиском хоть была догма об отрицании второго коньюнктивного члена.
В-третьих, если вы или кто-то соберется опровергать, делайте это примерами.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Про необходимость for(each)
« Ответ #44 : Февраль 10, 2012, 11:11:33 am »
Я не понял, в чём был прикол данной задачи.
Никаких ограничений на её решение не возлагалось -- например, не было требования линейного времени сортировки.
А значит: лучшее решение == самое простое.
Что может быть проще, чем вызвать стандартную процедуру сортировки массива?
Если бы я сказал, что это критичный кусок и произодительность стандартной сортировки не устраивает, то единственно правильным решением для программиста любой национальности было бы такое: смотреть справочник алгоритмов. Но тогда нечего было бы обсуждать.
Вот и пришлось давить не на производительность, а на самолюбие  ;)
А в результате каждый начал говорить о том, что болит конкретно у него :-) Например vlad про поддерживаемость (и я его понимаю - в такой большом проекте как у него, за все остальное в большенстве случаев нужно руки отрывать), я вначале подумал тоже про std::sort, потом про рабочекрестьянский метод как у Сергея (с поправкой на сишную специфику  - я бы таки memset/memcpy использовал бы для заполнения массива). А потом, параллельно, начал думать

1) о абстрактном решении этой задачи (элементов не 3 типа, а N, причем они не integer'ы а что-то другое (то есть нужно еще было формализовать требования к элементам))

2) о том какой из представленных тут алгоритмов лучше параллелится (ибо у меня это таки больной вопрос) посредством технологии Neon (в arm процессорах).

3) как эти алгоритмы лучше отобразить на msp430.

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