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

I>>Если буквально — то можно. Любые типы данных можно класть в дерево, даже само дерево можно. Никто не запрещает.
I>>Самое главое — не важно, что происходит между загрузкой и конечной обработкой и какие требования кастомера, главное — засунуть в дерево.

G>Ты же хотел сортировку за О(N), я тебе говорю — вставляй в дерево в момент появления данных. Доставать в нужном порядке будешь без дополнительных затрат.

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

Итого — твое дерево и обход за O(N) это уже дополнительные затраты, ибо нет никакого дерева, сортировка за линейное время, данные отдаются не за O(N) а за O(1).
Данные в памяти ибо этого требует рендеринг и N других фич, гриды, деревья и прочие вещи, которые используют те же данные, только дают другое представление.

Скажем, типичный сценарий, клик пользователя дает в результате запрос который аффектает 100 тыс основных объектов и юзер получает почти мгновенный отклик во всех вьюшках.
100 тыс и более основных это от 1 млн объектов для рендеринга, они перестраиваются, обновляются и тд, т.к. у многих гарантировано изменится Z-order. Вот из за этого Z-order и нужны оптимизации, что бы рисовать быстрее.
Фокус такой, что объекты не прямоугольные, локальность изменений, как в MsPaint, невозможно обеспечить, отсечения соответсвенно трудоемкие.

Собственно для чего все нужно — пол-секунды на клик можно потратить куда более эффективно, нежели на qsort или твои деревья. Я например нашел оптимизацию, которая сэкономила 200мс на каждый фрейм — радости было как у ребенка, сам себе до сих пор завидую

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

I>>Контора "именно такая и была" не имела никогда проблем с набором
V>Ты уж определись имела или нет.

Ты AV больше слушай, я, в отличие от него, там работал и трижды возвращался, ибо было зачем и о времени на той конторе не жалею нисколько, ибо было практически все что меня интересовало(и интересует) —
1. проф развитие
2. Интересный проект
3. Толковый менеджмент, QA.
4. ЗП
5. офис, расположение, куча кафешек-столовых в округе
6. свободный график
7. комфортный темп работы, без судорожных хватаний "всё пропало !!!!111расрас"

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

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

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

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

I>Это как раз и требует понимания, что такое ссылки. Скажем ссылка требует уверенного понимания идентити и хотя бы представляения о том, что есть референс тайпы и валюе тайпы.

Чушь.Понимание ссылок не требует ни первого , ни второго. Я со ссылками работал (работал — т.е. понимал, что делал) сильно раньше до того, как начитался про identity и ref/val types.

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

I>>Это как раз и требует понимания, что такое ссылки. Скажем ссылка требует уверенного понимания идентити и хотя бы представляения о том, что есть референс тайпы и валюе тайпы.

W>Чушь.Понимание ссылок не требует ни первого , ни второго. Я со ссылками работал (работал — т.е. понимал, что делал) сильно раньше до того, как начитался про identity и ref/val types.

Есть сильные сомнения в этом. Читать про идентити не нужно, нужно показать в коде все свое понимание.

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

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

I>>>Если буквально — то можно. Любые типы данных можно класть в дерево, даже само дерево можно. Никто не запрещает.
I>>>Самое главое — не важно, что происходит между загрузкой и конечной обработкой и какие требования кастомера, главное — засунуть в дерево.

G>>Ты же хотел сортировку за О(N), я тебе говорю — вставляй в дерево в момент появления данных. Доставать в нужном порядке будешь без дополнительных затрат.

I>Пудозреваю, баттхерт у тебя случился из за "все данные в памяти" а ты как истинный веб-разработчик точно знаешь что в веб-приложении такого быть не может.
I>Успойкойся, про веб никто и не говорил, ты сам это додумал.
С чего ты взял?

I>Итого — твое дерево и обход за O(N) это уже дополнительные затраты, ибо нет никакого дерева, сортировка за линейное время, данные отдаются не за O(N) а за O(1).
I>Данные в памяти ибо этого требует рендеринг и N других фич, гриды, деревья и прочие вещи, которые используют те же данные, только дают другое представление.
Отдать N элементов быстрее O(N) никак не выйдет. Или ты о чем-то другом?
Кто мешает иметь и дерево и список одновременно?

I>Скажем, типичный сценарий, клик пользователя дает в результате запрос который аффектает 100 тыс основных объектов и юзер получает почти мгновенный отклик во всех вьюшках.
I>100 тыс и более основных это от 1 млн объектов для рендеринга, они перестраиваются, обновляются и тд, т.к. у многих гарантировано изменится Z-order. Вот из за этого Z-order и нужны оптимизации, что бы рисовать быстрее.
I>Фокус такой, что объекты не прямоугольные, локальность изменений, как в MsPaint, невозможно обеспечить, отсечения соответсвенно трудоемкие.
Разрешение экрана примерно 2М пикселей, при 1М объектов это 2 пикселя на объект. Видимо не все объекты попадают в область рисования, то есть ты их отсекаешь по каким-либо признакам еще до растериризации.
Самый эффективный способ отсечения — построение дерева по этому признаку, по крайней мере лет 7 назад был, когда я графику изучал.

Вторая оптимизация — создание слоев из несвязанных типов элементов с разной частотой изменений. Это используется повсеместно в ГИСах.

До сих пор ты так и не объяснил почему в твоем случае это не подойдет.

I>Собственно для чего все нужно — пол-секунды на клик можно потратить куда более эффективно, нежели на qsort или твои деревья. Я например нашел оптимизацию, которая сэкономила 200мс на каждый фрейм — радости было как у ребенка, сам себе до сих пор завидую
Ну так расскажи секрет, что за магические оптимизации?

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

I>>Пудозреваю, баттхерт у тебя случился из за "все данные в памяти" а ты как истинный веб-разработчик точно знаешь что в веб-приложении такого быть не может.
I>>Успойкойся, про веб никто и не говорил, ты сам это додумал.
G>С чего ты взял?

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

I>>Итого — твое дерево и обход за O(N) это уже дополнительные затраты, ибо нет никакого дерева, сортировка за линейное время, данные отдаются не за O(N) а за O(1).
I>>Данные в памяти ибо этого требует рендеринг и N других фич, гриды, деревья и прочие вещи, которые используют те же данные, только дают другое представление.
G>Отдать N элементов быстрее O(N) никак не выйдет. Или ты о чем-то другом?

Считай сам — взяли готовые данные и отсортировали коллекцию на месте. Сколько времени займет вернуть эту отсортированую коллекцию ? Я даже не знаю, как надо постараться что бы "return x" стало хуже чем O(1)

G>Кто мешает иметь и дерево и список одновременно?

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

I>>Фокус такой, что объекты не прямоугольные, локальность изменений, как в MsPaint, невозможно обеспечить, отсечения соответсвенно трудоемкие.
G>Разрешение экрана примерно 2М пикселей, при 1М объектов это 2 пикселя на объект. Видимо не все объекты попадают в область рисования, то есть ты их отсекаешь по каким-либо признакам еще до растериризации.

Разумеется. Сортировка, в частности, так же нужна для всевозможных оптимизаций.

G>Самый эффективный способ отсечения — построение дерева по этому признаку, по крайней мере лет 7 назад был, когда я графику изучал.

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

"локальность изменений, как в MsPaint, невозможно обеспечить, отсечения соответсвенно трудоемкие"

G>Вторая оптимизация — создание слоев из несвязанных типов элементов с разной частотой изменений. Это используется повсеместно в ГИСах.

"локальность изменений, как в MsPaint, невозможно обеспечить, отсечения соответсвенно трудоемкие"

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

G>До сих пор ты так и не объяснил почему в твоем случае это не подойдет.

"локальность изменений, как в MsPaint, невозможно обеспечить, отсечения соответсвенно трудоемкие"

I>>Собственно для чего все нужно — пол-секунды на клик можно потратить куда более эффективно, нежели на qsort или твои деревья. Я например нашел оптимизацию, которая сэкономила 200мс на каждый фрейм — радости было как у ребенка, сам себе до сих пор завидую
G>Ну так расскажи секрет, что за магические оптимизации?

Это долго объяснять и к твоему дереву это не имеет отношения.

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

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

I>>>Пудозреваю, баттхерт у тебя случился из за "все данные в памяти" а ты как истинный веб-разработчик точно знаешь что в веб-приложении такого быть не может.
I>>>Успойкойся, про веб никто и не говорил, ты сам это додумал.
G>>С чего ты взял?

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

I>>>Итого — твое дерево и обход за O(N) это уже дополнительные затраты, ибо нет никакого дерева, сортировка за линейное время, данные отдаются не за O(N) а за O(1).
I>>>Данные в памяти ибо этого требует рендеринг и N других фич, гриды, деревья и прочие вещи, которые используют те же данные, только дают другое представление.
G>>Отдать N элементов быстрее O(N) никак не выйдет. Или ты о чем-то другом?

I>Считай сам — взяли готовые данные и отсортировали коллекцию на месте. Сколько времени займет вернуть эту отсортированую коллекцию ? Я даже не знаю, как надо постараться что бы "return x" стало хуже чем O(1)

Что значит "вернуть коллекцию" ? Если ты её дальше не обрабатываешь, что можно любую возвращать, а если обрабатываешь, то зависит от того как ты это делаешь. А ты опять этот момент пропустил.

G>>Кто мешает иметь и дерево и список одновременно?
I>Время и память. Визуализация и так жрет слишком много памяти и процессора, что бы пихать туда и список и дерево да еще и результат отдавать за O(N) когда само работает за O(1)
Памяти мало?
А время на что? У тебя на момент отдачи результата никаких дополнительных действий не происходит.

I>Это хорошо работает, когда границы изменений легко локализовать. В противном случае построение дерева превращается в АДъ.
I>"локальность изменений, как в MsPaint, невозможно обеспечить, отсечения соответсвенно трудоемкие"
А тогда как ты выполняешь отсечение? Ты же сортируешь по ключу, вот по этому ключу и построй дерево.

Ты опять что-то не договариваешь.


I>>>Собственно для чего все нужно — пол-секунды на клик можно потратить куда более эффективно, нежели на qsort или твои деревья. Я например нашел оптимизацию, которая сэкономила 200мс на каждый фрейм — радости было как у ребенка, сам себе до сих пор завидую
G>>Ну так расскажи секрет, что за магические оптимизации?
I>Это долго объяснять и к твоему дереву это не имеет отношения.
Ну не сливайся, хоть раз расскажи что ты делаешь на самом деле то.

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

I>>Считай сам — взяли готовые данные и отсортировали коллекцию на месте. Сколько времени займет вернуть эту отсортированую коллекцию ? Я даже не знаю, как надо постараться что бы "return x" стало хуже чем O(1)

G>Что значит "вернуть коллекцию" ? Если ты её дальше не обрабатываешь, что можно любую возвращать, а если обрабатываешь, то зависит от того как ты это делаешь. А ты опять этот момент пропустил.

Не пропустил, а указал ограничения. Не важно, что дальше, важно какие ограничения на входе-выходе.

G>>>Кто мешает иметь и дерево и список одновременно?
I>>Время и память. Визуализация и так жрет слишком много памяти и процессора, что бы пихать туда и список и дерево да еще и результат отдавать за O(N) когда само работает за O(1)
G>Памяти мало?

И это очевидно, более того, я тебе постоянно про это говорю.

G>А время на что? У тебя на момент отдачи результата никаких дополнительных действий не происходит.

Время на все — от подготовки данных до рендеринга примитивов.

I>>Это хорошо работает, когда границы изменений легко локализовать. В противном случае построение дерева превращается в АДъ.
I>>"локальность изменений, как в MsPaint, невозможно обеспечить, отсечения соответсвенно трудоемкие"
G>А тогда как ты выполняешь отсечение? Ты же сортируешь по ключу, вот по этому ключу и построй дерево.

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

G>>>Ну так расскажи секрет, что за магические оптимизации?
I>>Это долго объяснять и к твоему дереву это не имеет отношения.
G>Ну не сливайся, хоть раз расскажи что ты делаешь на самом деле то.

Уже все что надо было сказано.

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

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

I>>>Считай сам — взяли готовые данные и отсортировали коллекцию на месте. Сколько времени займет вернуть эту отсортированую коллекцию ? Я даже не знаю, как надо постараться что бы "return x" стало хуже чем O(1)

G>>Что значит "вернуть коллекцию" ? Если ты её дальше не обрабатываешь, что можно любую возвращать, а если обрабатываешь, то зависит от того как ты это делаешь. А ты опять этот момент пропустил.

I>Не пропустил, а указал ограничения. Не важно, что дальше, важно какие ограничения на входе-выходе.
Это ты уже вилять начинаешь. Если тебя интересует быстродействие, то нельзя заниматься локальной оптимизацией.
Как все таки массив обрабатываться будет?

G>>>>Кто мешает иметь и дерево и список одновременно?
I>>>Время и память. Визуализация и так жрет слишком много памяти и процессора, что бы пихать туда и список и дерево да еще и результат отдавать за O(N) когда само работает за O(1)
G>>Памяти мало?
I>И это очевидно, более того, я тебе постоянно про это говорю.
Но как-бы тебе никто не верит. На современном компе сложно забить память. Представим даже что у тебя 1М элементов, каждый по 100 байт. Это всего 100мб.
Даже если ты построишь индексы, типа древовидные, то это еще 50 мб даст.


G>>А время на что? У тебя на момент отдачи результата никаких дополнительных действий не происходит.
I>Время на все — от подготовки данных до рендеринга примитивов.
Готовь данные заранее, вставляй в отсортированное дерево.

I>>>Это хорошо работает, когда границы изменений легко локализовать. В противном случае построение дерева превращается в АДъ.
I>>>"локальность изменений, как в MsPaint, невозможно обеспечить, отсечения соответсвенно трудоемкие"
G>>А тогда как ты выполняешь отсечение? Ты же сортируешь по ключу, вот по этому ключу и построй дерево.
I>Ты лучше расскажи на примере, как ты собираешься это дерево использовать. Пудозреваю, ты имеешь в виду какой то книжный алгоритм, заточеный под трассировку лучей для случая, когда области можно легко изолировать.
Сначала ты скажи как твой отсортированный массив обрабатывается, скорее всего за o(N). Потом я тебе покажу как это положить на дерево за o(log n).

G>>>>Ну так расскажи секрет, что за магические оптимизации?
I>>>Это долго объяснять и к твоему дереву это не имеет отношения.
G>>Ну не сливайся, хоть раз расскажи что ты делаешь на самом деле то.
I>Уже все что надо было сказано.
Ну конечно, потому что сказать еще немного и все твои позиции рассыпятся

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

I>>Не пропустил, а указал ограничения. Не важно, что дальше, важно какие ограничения на входе-выходе.
G>Это ты уже вилять начинаешь. Если тебя интересует быстродействие, то нельзя заниматься локальной оптимизацией.

Спасибо капитан.

G>Как все таки массив обрабатываться будет?

Не важно.

I>>И это очевидно, более того, я тебе постоянно про это говорю.
G>Но как-бы тебе никто не верит. На современном компе сложно забить память. Представим даже что у тебя 1М элементов, каждый по 100 байт. Это всего 100мб.

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

G>Даже если ты построишь индексы, типа древовидные, то это еще 50 мб даст.

А если бы ты спросил про количество объектов, то узнал бы, что всего в памяти 3..30 млн объектов. Это, в частности, означает, что 8-байтный хедер который есть у всех объектов, займет 24..240мб.

G>>>А время на что? У тебя на момент отдачи результата никаких дополнительных действий не происходит.
I>>Время на все — от подготовки данных до рендеринга примитивов.
G>Готовь данные заранее, вставляй в отсортированное дерево.

Они и так заранее готовятся. Не ясно, какой профит от дерева.

I>>Ты лучше расскажи на примере, как ты собираешься это дерево использовать. Пудозреваю, ты имеешь в виду какой то книжный алгоритм, заточеный под трассировку лучей для случая, когда области можно легко изолировать.
G>Сначала ты скажи как твой отсортированный массив обрабатывается, скорее всего за o(N). Потом я тебе покажу как это положить на дерево за o(log n).

Примерно так — самые большие операции это генерация примитивов и отсечение самих примитивов. Где ты тут хочешь log n всунуть, мне, честно говоря, совершенно непонятно.

I>>Уже все что надо было сказано.
G>Ну конечно, потому что сказать еще немного и все твои позиции рассыпятся

Это вряд ли — первый раз вижу такого кадра, который не интересуется ни объемом данных, ни ограничениями, ни показниями профайлера, но уверен, что знает лучше.

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

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

G>>Как все таки массив обрабатываться будет?
I>Не важно.
Вообще-то важно, если мы об оптимзации.

I>>>И это очевидно, более того, я тебе постоянно про это говорю.
G>>Но как-бы тебе никто не верит. На современном компе сложно забить память. Представим даже что у тебя 1М элементов, каждый по 100 байт. Это всего 100мб.
I>Ты похоже читаешь как то по особенному. Я говорю, что памяти мало и не хватает, а ты придумал себе непойми что.
Ну то что ты говоришь еще не значит что правда. Скорее наоборот.
Приведи факты: такая-то структура, столько то экземпляров, на таких-то устройствах работает.
А так ты рассказываешь про сферическую сортировку в вакууме.

G>>Даже если ты построишь индексы, типа древовидные, то это еще 50 мб даст.
I>А если бы ты спросил про количество объектов, то узнал бы, что всего в памяти 3..30 млн объектов. Это, в частности, означает, что 8-байтный хедер который есть у всех объектов, займет 24..240мб.
О как... А зачем столько объектов в памяти? Если попытаться отрисовать все, то выйдет меньше пикселя на объект. Получается что большая часть из них будет очень редко попадать в отрисовку, а следовательно нет смысла держать в памяти все миллионы.

G>>>>А время на что? У тебя на момент отдачи результата никаких дополнительных действий не происходит.
I>>>Время на все — от подготовки данных до рендеринга примитивов.
G>>Готовь данные заранее, вставляй в отсортированное дерево.
I>Они и так заранее готовятся. Не ясно, какой профит от дерева.
Ну так ты расскажи что дальше с массивом происходит и сразу станет ясно

I>>>Ты лучше расскажи на примере, как ты собираешься это дерево использовать. Пудозреваю, ты имеешь в виду какой то книжный алгоритм, заточеный под трассировку лучей для случая, когда области можно легко изолировать.
G>>Сначала ты скажи как твой отсортированный массив обрабатывается, скорее всего за o(N). Потом я тебе покажу как это положить на дерево за o(log n).
I>Примерно так — самые большие операции это генерация примитивов и отсечение самих примитивов. Где ты тут хочешь log n всунуть, мне, честно говоря, совершенно непонятно.
Ну если отсекать по упорядоченному дереву, то будет logn, вместо n.

I>>>Уже все что надо было сказано.
G>>Ну конечно, потому что сказать еще немного и все твои позиции рассыпятся
I>Это вряд ли — первый раз вижу такого кадра, который не интересуется ни объемом данных, ни ограничениями, ни показниями профайлера, но уверен, что знает лучше.
Ты от зеркала отвернись и прочитай сообщения. Я тебя прямо спрашивал про данные и алгоритм обработки. Ты только сверическую сортировку в вакууме привел.

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

I>>Не важно.
G>Вообще-то важно, если мы об оптимзации.

Я уже сказал — генерация примитивов и отсечение.

I>>Ты похоже читаешь как то по особенному. Я говорю, что памяти мало и не хватает, а ты придумал себе непойми что.
G>Ну то что ты говоришь еще не значит что правда. Скорее наоборот.

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

Извини, дальше буду отвечать только те, на которые мне будет интересно, ибо смысла нет раз уж "не значит что правда. Скорее наоборот"

G>О как... А зачем столько объектов в памяти? Если попытаться отрисовать все, то выйдет меньше пикселя на объект. Получается что большая часть из них будет очень редко попадать в отрисовку, а следовательно нет смысла держать в памяти все миллионы.

Спасибо, капитан. Ты похоже забыл, что визуализация не единственное, чем занято приложение. Объектов для визуализации где то около 500тыс, в основном потому, что они имеют сложную структуру, каждый объект состоит из 4-5 мелких. Все возможные упаковки, включая штук 30 битовых флагов, уже сделаны. Все что можно было, сделано структурами для экономии 8байт хедера.

Что это в кратце означает — памятью кидаться нельзя и расход памяти должен быть обоснован. 2е GC работает в наиболе неудобном режиме, все объекты в Gen2. 3е — фрагментация никуда не делась, а следовательно менее жрущий алоритм выгоднее более жрущего.
Дерево которое ты предлагаешь, вынудит GC выделить целый хип под него. Сравнивая с нулевым расходом памяти при моей сортировке хочет ОЧЕНЬ большого профита от дерева.

G>>>Сначала ты скажи как твой отсортированный массив обрабатывается, скорее всего за o(N). Потом я тебе покажу как это положить на дерево за o(log n).
I>>Примерно так — самые большие операции это генерация примитивов и отсечение самих примитивов. Где ты тут хочешь log n всунуть, мне, честно говоря, совершенно непонятно.
G>Ну если отсекать по упорядоченному дереву, то будет logn, вместо n.

Отсекается не по приоритету, а в основном по координатам. Для чего нужа сортировка я уже говорил, вообще говоря.

Итого — где профит от дерева, не ясно.

I>>>>Уже все что надо было сказано.
G>>>Ну конечно, потому что сказать еще немного и все твои позиции рассыпятся
I>>Это вряд ли — первый раз вижу такого кадра, который не интересуется ни объемом данных, ни ограничениями, ни показниями профайлера, но уверен, что знает лучше.
G>Ты от зеркала отвернись и прочитай сообщения. Я тебя прямо спрашивал про данные и алгоритм обработки. Ты только сверическую сортировку в вакууме привел.

Да, на второй неделе тёрок ты, наконец, начал задавать кое какие вопросы, признаю.

Здравствуйте, Ночной Смотрящий, Вы писали:


НС>Ну попробуй тогда обосновать свое решение. Сколько проходов, какая сложность, есть ли ограничения на длину цепочки.

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

Кстати, а решение с разворачивающейся в цикл хвостовой рекурсией примешь?

Здравствуйте, Ночной Смотрящий, Вы писали:

НС>

НС>var head = ...;
НС>var current = head;
НС>var list = new List<Item>();
НС>while (current != null)
НС>{
НС>  list.Add(current);
НС>  current = current.Next;
НС>}
НС>list.Reverse();
НС>for (int i = 0; i < list.Count - 1; i++)
НС>  list[i].Next = list[i + 1];
НС>list[list.Count - 1].Next = null;
НС>

НС>Этим гугль не поможет, они и рабочий код будут писать по принципу "фигли тут думать, трясти надо".

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

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

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

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

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

Здравствуйте, Ночной Смотрящий, Вы писали:

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

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

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

НС>Скажи лучше, что в нем хорошего?
Ну ты же сам написал, что его пишут и понимают большинство программистов в отличии от...

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

НС>Знаешь, меня вот пугают все время преждевременными оптимизациями, но на практике я таких вижу только на форуме. Чтобы что то не делать, человека уговаривать долго не надо.

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

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

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

Что, правда что ли? Расскажи нам на базе "разделяй и властвуй", почему работает генетическая диф. эволюция например?..

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

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

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

E>Что, правда что ли? Расскажи нам на базе "разделяй и властвуй", почему работает генетическая диф. эволюция например?..

Я не знаю, что это

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

U>Т.е. проблемой проверки конкретного понимания на собеседовании является то, что невозможно понять почему человек не понимает какой-то принцип: 1) из-за того, что у него способностей 2) из-за того, что у вас просто разная терминология 3) из-за того, что человек с такими задачами не сталкивался

Дык можно же ему подсказывать. Типа видим, что задача для него нова, и пробуем ему её помочь решить в диалоге. Пусть он покажет вам, как он сможет учиться у вас...

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

I>Ты сначала говорил про какую то статистику, а теперь оказывается, что статистики у тебя нет


Вроде что-то в код комлите такое упоминалось...

Впрочем ты можешь взять базу багов за последний год, например, или там ещё какой период, выбрать багов 500 и быстренько поклассифицировать в типовом коде они были или нет, потом сопоставить скока того и другого у вас есть и прикинуть правда это или нет ДЛЯ ВАШИХ УСЛОВИЙ...