Здравствуйте, Aen Sidhe, Вы писали:

AS>Павел, я тоже могу привести овер 9000 случаев, когда требовалась смекалка. Что теперь, весь софт обязан эти трюки использовать? Почему не взять двунаправленный список? Экономим 4(8) байт на указателе? Ну, удачи. В некоторых случаях это полезно. Процентах в 5-10.

Я так полагаю, что даже меньший % — при нынешней памяти. Но вот знать о такой возможности надо. Чтобы в том случае, когда попадешь в этот 1%, не устроить O(N).

Здравствуйте, Privalov, Вы писали:

P>Может, так?

P>

P> quality = (заказчик доволен) && (профессиональный анализ прошел успешно)
P>

Я так и хотел сначала написать, но потом решил все же подробнее

Здравствуйте, Oboltus, Вы писали:

O>К чему это приводит? К тому, что доктора начинают лечить не пациента, а болезнь. Супер-специалист по воспалению среднего уха излечивает это воспаление в 99% случаев, но при этом в 30% (все цифры условные) прописанные лекарства вызовут проблемы в других органах. Которыми займутся другие супер-специалисты...

Не совсем верно. Возьми любую листовку, там всегда есть раздел "Противопоказания". И он их обязан знать. В 99% случаев (вполне заурядных) это лечение закончится излечением или неудачей, но без побочных эффектов. А вот если ситуация сложная, то на это есть консилиум, где сойдутся узкие специалисты, но каждый в своей области, и будут решать, что делать.

А ты что предлагаешь ? Врача, который все умеет лечить ? Это не врач будет, а деревенский фельдшер, который, точно, умеет лечить от простуды до запора, только вполне по-дилетантски. Если это действительно простуда — вылечит аспирином (впрочем, я и сам им вылечусь). Но если это начинается воспаление легких или что-то еще — либо прозевает, либо отправит на консультацию к специалисту.

Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Можно, конечно, правда, остается выяснить, куда они будут показывать при одном элементе
Очевидно, p1 будет показывать на указатель на первый элемент, а p2 — на первый элемент.
Потому, что для вставки достаточно изменить только указатель. Весь предыдущий элемент нас не интересует.
PD>Разумеется. Может и не оказаться. Может этот подход и не годится в данном конкретном случае. Но я ведь не его обсуждаю, а просто сказал, что знание его может сильно упростить решение. Не всегда. Но его незнание — не упростит. Всегда. Так что надо знать.
Сильно упростить решение может умение думать головой, а не заучивать наизусть трюки.

З.Ы. Да, я в курсе про то, что для большинства интересных случаев оптимизация алгоритмов — это скорее искусство, чем техника.

Sinclair wrote:

> упростить решение может умение думать головой, а не заучивать наизусть
> трюки.

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

Здравствуйте, Pavel Dvorkin, Вы писали:

P>>

P>> quality = (заказчик доволен) && (профессиональный анализ прошел успешно)
P>>

PD>Я так и хотел сначала написать, но потом решил все же подробнее

Зачем? Читаемость не пострадала совершенно, даже, imho, улучшилась, а работать будет быстрее практически на любом языке.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Можно, конечно, правда, остается выяснить, куда они будут показывать при одном элементе
S>Очевидно, p1 будет показывать на указатель на первый элемент, а p2 — на первый элемент.

Что-то я не понял. Какого типа p1 — ListElement* или ListElement** ? Автор исходного предложения написал

>Можно два указателя вести -- на текущий и на предидущий элементы

из чего следует, что p1 и p2 одного и того же типа ListElement*. Как при нескольких элементах p1 может показывать на элемент и быть ListElement*, а при одном вдруг показывать на указатель, и стало быть, стать вдруг ListElement** — это, пожалуйста, объясни.

S>Сильно упростить решение может умение думать головой, а не заучивать наизусть трюки.

А кто предлагал заучивать ? Опять ты дискуссию пытаешься в сторону увести. речь шла о том. что надо знать не 5%, а пусть не 100, но что-то близкое. Я привел пример, когда знание 1% от всего, что должен знать тот, кто пишет код для списков, может сильно упростить решение. При чем тут заучивание ?

S>З.Ы. Да, я в курсе про то, что для большинства интересных случаев оптимизация алгоритмов — это скорее искусство, чем техника.

+1

Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Что-то я не понял. Какого типа p1 — ListElement* или ListElement** ? Автор исходного предложения написал
>>Можно два указателя вести -- на текущий и на предидущий элементы
PD>из чего следует, что p1 и p2 одного и того же типа ListElement*.
Совершенно верно. Автор исходного предложения поторопился (так же, как и автор идеи выполнять "копирование вперед").
PD>Как при нескольких элементах p1 может показывать на элемент и быть ListElement*, а при одном вдруг показывать на указатель, и стало быть, стать вдруг ListElement** — это, пожалуйста, объясни.
p1 всегда имеет тип ListElement**. p2 — ListElement*.
В начале p1 инициализируется в &head, p2 — в head.
А дальше на каждый шаг итерации:

p1 = &p2.next; p2=p2.next;

То есть добавив к итератору всего size_t байт, мы получили гарантию вставки "перед текущим" за O(1).
Вставка делается очевидным образом:

InsertBefore(Iterator current, ListElement element)
{
    element.next = current.p2;
    (*p1) = &element;
}

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, investigator, Вы писали:

I>>Можно два указателя вести -- на текущий и на предидущий элементы.

PD>Можно, конечно, правда, остается выяснить, куда они будут показывать при одном элементе

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

Интересно, неужели не нашлось своего варианта решения? Школьная ведь задачка. Даже грустно как-то.

>>А копирование в общем случае может оказаться не самым лучшим решением -- не понятно сколько придется копировать, хорошо если это будет указатель на структуру данных.

PD>Разумеется. Может и не оказаться. Может этот подход и не годится в данном конкретном случае. Но я ведь не его обсуждаю, а просто сказал, что знание его может сильно упростить решение. Не всегда. Но его незнание — не упростит. Всегда. Так что надо знать.

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

Есть, конечно, люди, которым только чтение может помочь Но мы же не про них?

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Разумеется. Может и не оказаться. Может этот подход и не годится в данном конкретном случае. Но я ведь не его обсуждаю, а просто сказал, что знание его может сильно упростить решение. Не всегда. Но его незнание — не упростит. Всегда. Так что надо знать.

Кстати, не нравится мне эта чистая ориентация на знания. Все-таки более важно, на мой взгляд, умение решать задачи, умение получать эти самые знания. Это-то и есть истинная инженерная ценность. Не нужен мне программист, который знает 75 способов сортировки, не нужен, также, программист, который знает 87 способов вставки элемента в список (плюс один секретный, подсмотренный у Вирта). Важно понимание принципов сортировки, понимание основ работы со списками. А когда возникнет необходимость, то нужный способ будет найден (если человека научили это делать, а не заставляли запоминать 75 способов).

Почему еще важно не просто знание, а способность его получать. Да просто потому, что само знание со временем может морально устареть. На смену модным методам 20 летней давности могут прийти современные подходы. Так что не 5 строк на странице 128 имеют значение, а способность в нужный момент их найти.

Главное, чтобы в институте (университете) правильные люди научили правильным вещам.

Здравствуйте, Sinclair, Вы писали:

S>p1 всегда имеет тип ListElement**. p2 — ListElement*.

А, тогда все ясно. Отметил бы это сразу, не было бы вопроса. Хорошо известный прием.

<объяснение skipped>

Что же, ты прекрасно подтвердил мою мысль о том, что надо знать не 5%, а ближе к 100. Я привел один прием, ты — другой. Оба они имеют право на существование, оба могут облегчить жизнь, упростить код. Оба не относятся к наиболее распространенной реализации списка. Можно еще привести примеры "список с барьером в конце", "список с заголовком", они тоже иногда бывают полезны.

Здравствуйте, investigator, Вы писали:

I>Интересно, неужели не нашлось своего варианта решения? Школьная ведь задачка. Даже грустно как-то.

Да нет, мне эти вещи давно известны. Я просто хотел указать на неточность твоего решения как ты его дал.

>>>А копирование в общем случае может оказаться не самым лучшим решением -- не понятно сколько придется копировать, хорошо если это будет указатель на структуру данных.

PD>>Разумеется. Может и не оказаться. Может этот подход и не годится в данном конкретном случае. Но я ведь не его обсуждаю, а просто сказал, что знание его может сильно упростить решение. Не всегда. Но его незнание — не упростит. Всегда. Так что надо знать.

I>Часто, к сожалению, конкретное знание закрывает путь к другим, возможно более эффективным решениям. Так что с утверждением "Всегда" позволю не согласиться.

Позволю не согласиться с твоим последним утверждением, так как оно логически не вытекает из того, что я сказал. Конкретное решение закрывает... — да, может быть верно. Но почему при этом можно не знать про его существование — не ясно. Возможно, оно закроет, и его лучше не применять. Возможно , нет. От задачи зависит. А знать о нем стоит, чтобы оценить плюсы и минусы в конкретной ситуации.

Здравствуйте, investigator, Вы писали:

I>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Разумеется. Может и не оказаться. Может этот подход и не годится в данном конкретном случае. Но я ведь не его обсуждаю, а просто сказал, что знание его может сильно упростить решение. Не всегда. Но его незнание — не упростит. Всегда. Так что надо знать.

I>Кстати, не нравится мне эта чистая ориентация на знания. Все-таки более важно, на мой взгляд, умение решать задачи, умение получать эти самые знания. Это-то и есть истинная инженерная ценность. Не нужен мне программист, который знает 75 способов сортировки, не нужен, также, программист, который знает 87 способов вставки элемента в список (плюс один секретный, подсмотренный у Вирта). Важно понимание принципов сортировки, понимание основ работы со списками. А когда возникнет необходимость, то нужный способ будет найден (если человека научили это делать, а не заставляли запоминать 75 способов).


I>Почему еще важно не просто знание, а способность его получать. Да просто потому, что само знание со временем может морально устареть. На смену модным методам 20 летней давности могут прийти современные подходы. Так что не 5 строк на странице 128 имеют значение, а способность в нужный момент их найти.

Ну эта идея совсем не нова, у нее есть даже образное представление , ты его наверняка знаешь — "студент не сосуд, который нужно наполнить, а факел, который нужно зажечь". Но я бы не стал так жестко противопоставлять. К примеру, та же сортировка. Ее принципы известны в детском саду, и при этом используется , видимо, нечто вроде простых вставок . А вот если бы я не знал qsort, очень сомневаюсь, что я бы ее сам придумал. Пузырек еще мог бы. а qsort — не уверен.

I>Главное, чтобы в институте (университете) правильные люди научили правильным вещам.

Остается сформулировать критерий правильности людей и вещей

А если серьезнее, то ты сам себе противоечишь, хотя и не замечаешь. Ты же только что сказал, что важнее умение решать, искать истину. А при поиске истины ошибки неминуемы. Ошибки в реализации qsort — это безобразие, за это двойку надо ставить, а если я новое что-то придумываю, то право на ошибку у меня есть. И вот тут, коль скоро главное — умение решать, очевидный ИМХО вывод — надо, чтобы люди (правильные или нет — судить не буду) учили не правильным вещам, а умению их искать. С ошибками и т.д.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>>Разумеется. Может и не оказаться. Может этот подход и не годится в данном конкретном случае. Но я ведь не его обсуждаю, а просто сказал, что знание его может сильно упростить решение. Не всегда. Но его незнание — не упростит. Всегда. Так что надо знать.

I>>Часто, к сожалению, конкретное знание закрывает путь к другим, возможно более эффективным решениям. Так что с утверждением "Всегда" позволю не согласиться.

PD>Позволю не согласиться с твоим последним утверждением, так как оно логически не вытекает из того, что я сказал. Конкретное решение закрывает... — да, может быть верно. Но почему при этом можно не знать про его существование — не ясно. Возможно, оно закроет, и его лучше не применять. Возможно , нет. От задачи зависит. А знать о нем стоит, чтобы оценить плюсы и минусы в конкретной ситуации.

Так в том-то и дело, что не даст ваше решение оценить плюсы и минусы, так как ухватитесь вы за него, как за старое проверенное. Это общая проблема шаблонных решений, когда ходят с пушкой и стреляют по всем сторонам. Иногда незнание ни одного подхода может оказаться полезней, так как есть шанс, что будут в равной степени изучены все, а не только то, которое запомнилось 10 лет назад. Собственно, претензия не к тому, что плохо знать, а к тому, что не всегда это хорошо.

И вообще, не считаю практичным утверждения со словом "всегда". Вот это, на мой взгляд, точно признак дилетантизма (без личностей -- чисто мнение).

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Что же, ты прекрасно подтвердил мою мысль о том, что надо знать не 5%, а ближе к 100. Я привел один прием, ты — другой. Оба они имеют право на существование, оба могут облегчить жизнь, упростить код. Оба не относятся к наиболее распространенной реализации списка.
Вот чего я не понимаю — это почему это подтверждает твою мысль. Я этот приём придумал, просто посмотрев на предложенную тобой задачу.

Он не является результатом вдумчивого изучения Кнута или Вирта, он не является плодом многолетней работы со связными списками. Я вообще связный список в последний раз году, наверное, в 96м руками трогал. Вон, даже -> с . перепутал. Я работаю в совершенно другой области.

Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ну эта идея совсем не нова, у нее есть даже образное представление , ты его наверняка знаешь — "студент не сосуд, который нужно наполнить, а факел, который нужно зажечь". Но я бы не стал так жестко противопоставлять. К примеру, та же сортировка. Ее принципы известны в детском саду, и при этом используется , видимо, нечто вроде простых вставок . А вот если бы я не знал qsort, очень сомневаюсь, что я бы ее сам придумал. Пузырек еще мог бы. а qsort — не уверен.
Ну почему ты так о себе плохо думаешь.
На мой взгляд, ценность Кнута — не в том, что он перечислил канонический список алгоритмов сортировки, а в том, что он показал, как правильно анализировать параметры алгоритма и как выбирать хорошее решение.
А об этом часто забывают. Вместо этого заучивают наизусть "факты" типа "qsort — самый быстрый алгоритм, bubble — самый медленный".

Понимаешь? Профессионал — это не тот, кто знает много "приемов". Это тот, кто хорошо понимает, чем приемы отличаются друг от друга, и что в них общего.

Вот грубый пример "профессионального роста":
1. "Связные списки медленно работают".
2. "Обращение к i-му элементу в списке требует O(N) операций"
3. "Обращение к i-му элементу в списке требует O(N) операций, если при последовательных обращениях все i равновероятны"
Уже на шаге три профессионалу становится понятно, что если i не равновероятны, то оценка O(N) неверна.
Поэтому при решении задачи "оптимизации кода" профессионал станет смотреть не только на скрижали, а также на распределение параметров.
Возможно, связный список окажется вполне подходящим — ведь очевидно, что для задачи последовательного перебора даже односвязного списка, когда iNext = iPrev+1 каждое обращение к элементу нетрудно сделать за O(1).

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ну эта идея совсем не нова, у нее есть даже образное представление , ты его наверняка знаешь — "студент не сосуд, который нужно наполнить, а факел, который нужно зажечь". Но я бы не стал так жестко противопоставлять. К примеру, та же сортировка. Ее принципы известны в детском саду, и при этом используется , видимо, нечто вроде простых вставок . А вот если бы я не знал qsort, очень сомневаюсь, что я бы ее сам придумал. Пузырек еще мог бы. а qsort — не уверен.

Одно из двух, либо ты не знаешь принципов сортировки (в чем я сомневаюсь), либо хочешь поспорить ради спора (времени жалко).

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

I>>Главное, чтобы в институте (университете) правильные люди научили правильным вещам.

PD>Остается сформулировать критерий правильности людей и вещей

PD>А если серьезнее, то ты сам себе противоечишь, хотя и не замечаешь. Ты же только что сказал, что важнее умение решать, искать истину. А при поиске истины ошибки неминуемы. Ошибки в реализации qsort — это безобразие, за это двойку надо ставить, а если я новое что-то придумываю, то право на ошибку у меня есть. И вот тут, коль скоро главное — умение решать, очевидный ИМХО вывод — надо, чтобы люди (правильные или нет — судить не буду) учили не правильным вещам, а умению их искать. С ошибками и т.д.

Где я говорил про поиск истины? Вот мои слова: "Все-таки более важно, на мой взгляд, умение решать задачи, умение получать эти самые знания." Слово истина встречается только в определении ценности инженера. Вобщем, придуманное противоречие.

Нехорошо. Либо не понял моей мысли, либо хочешь ее преднамеренно исказить. Признавайся, что есть правда.

Вчера послал ряд ответов, но они утеряны. Повторять не буду. Да и заканчивать пора это обсуждение.

Здравствуйте, Sinclair, Вы писали:

S>А об этом часто забывают. Вместо этого заучивают наизусть "факты" типа "qsort — самый быстрый алгоритм, bubble — самый медленный".

Кстати. Пузырек вообще-то быстрее quicksort-а на почти отсортированном массиве . Что делает его в некоторых случаях хорошим, годным алгоритмом. Не все знают .

Здравствуйте, Pavel Dvorkin, Вы писали:
..........
PD>Я однажды провел голосование на тему о том, что является наиболее важным для программиста в плане качества программы. Результат меня просто поразил — примерно половина выбрала пункт «главное — чтобы заказчик был доволен». То, что заказчик должен быть доволен, никакого сомнения не вызывает, но считать это главным в плане оценки профессионального качества — это уж из рук вон! Полагаться на мнение непрофессионалов в оценке качества — это все равно, что пригласить меня на выпускной экзамен в консерваторию и предложить оценить качество исполнения. Музыку я люблю, но вот слуха, увы, нет, так что если скрипач явно не сфальшивит, то я буду аплодировать, хотя консерваторские профессора за такое исполнение, возможно, влепят ему заслуженную двойку.

Это очень полезное понимание, универсального применения. СПАСИБО.

Например, я этим недавно делился с несколькими начинающими медиками. Так приятно было наблюдать их реакцию — настоящее озарение (и, как мне показалось, облегчение) от понимания, что итоговую оценку своей работе им надо искать среди коллег а не у больного. Им это реально понравилось и помогло.


PD>Что это ? Незрелость технологии ? Следствие экстенсивного развития в ущерб интенсивному ? Как долго это будет продолжаться ? Или же ИТ действительно отличается от других областей науки и техники ?

Видимо, люди с которыми Вы общались на поприще ИТ занимаются НЕ НАУКОЙ, а практикой; и степень их ознакомления с предметом имеет какую-то практическую ценность, но никакую научную. (продвигать вперед они ничего в отрасли не будут.)