Обещал прекратить дискуссию, но не удержался.
Обидно, что простое обсуждение скатилось к общению на уровне "От дурака слышу" (эту фразу в научный мир ввел известный чам и гениальный физик Лев Ландау).
Сразу извинюсь перед студентом, что отвечать буду с позиции профессора и программиста, за плечами которого множество внедренных продуктов.
Мне приходилось преподавать технологию программирования и я прекрасно знаю разницу в сложности алгоритмов.
Однако в мне приходилось участовать в разработке проектов, когда определенная структура данных хорошо подходит для одной задачи в проекте и жутко тормозит в другой. Тогда как другая структура дданных прекрасно работает во втором месте и просто не пригодна (по времени обработки) в первом.
Иногда можно пойти на трансформацию структур данных, но это сильно зависит от сложности трансформации. Предлагаемая замена List на Set происходит с потерей информации. Причем эта информация (порядок записей) может быть очень важна.
Сегодня закончил научный проект в котором довольн долго колебался между Set и List. Для оценки что лучше пришлось реализовать оба варианта и проверить что даст выигрыш. В моем случае выигрыш дал List, поскольку обращение по индексу быстрее обращения по ключу, а в большинстве мест мне нужен был перебор всех элементов последовательно. Более того, в некоторых местах сначала формировал List, а затем трансформировал его в обычный массив. Это давало существенный выигрыш во времени.
Теперь о том проекте, который послужил темой для обсуждения. Я не знаю деталей, но судя по ряду ответов автора темы, добавление нового "пользователя" это частный случай работы со структурой. Во всех остальных местах нужен List. Ради получения выигрыша в одном месте Вы предлагаете поменять структуру всего проекта. Скорее всего это будет не эффективно, поскольку приведет к потере производительности в других местах. Второе Ваше предложение - делать локальное преобразование не выдерживает никакой критики в случае больших массивов данных. Преобразование будет работать мног дольше, чем поиск одного или нескольких имен. В случае последовательного внесения нескольких имен возникнет еще более сложная проблема - добавлять нужно будет сразу в обе коллекции.
Именно это я подразумевал под "общим трепом об О(0) и О(n)". Оценка сложности одного алгоритма актуальна только в том случае, когда способ ускорения не затрагивает других алгоритмов. В противном случае нужно оценивать эффективность для ВСЕХ алгоритмов, а не для одного выделенного.
Позволю себе профессорскиое отступление. Сегодня на лекции я обсуждал со студентами различие между учебными и реальными задачами в информатике.
В нашем случае учебная задача - задача о реализации одного алгоритма. А реальная задача, как правило, подразумевает несколько этапов обработки.
Надеюсь я достаточно четко объяснил причину того, что мы все согласились с условием автора поста, и обсуждали решение в рамках, заданных автором.

\m/ \m/ ? 


О порядке элементов? Set - это не тип, а интерфейс. Есть и Set с сохранением порядка элементов, LinkedHashSet, который предложили выше.


А для этого обязательно по чему-то обращаться? Есть же итераторы и foreach (вот не знаю можно ли в яве так сделать, но в питоне есть for key, value in hash.iteritems())


Преобразование имхо будет работать быстрее поиска нескольких имен подряд.


Зачем держать параллельно List и Set, есть структуры, которые сочетают и порядок элементов, и поиск за O(1).


Опечатка?

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

Класс сложности одной операции имеет таки не абсолютный приоритет, но имеет. Может, лично у Вас (проект-то научный? вычислялка какая-то?) это оказалось не так, но как правило, будет наоборот, и проверить в любом случае не помешает. То есть, позиция по умолчанию - брать структуру с лучшим классом сложности на типичных операциях, иной выбор должен быть обоснован. У Вас он был обоснован (тесты ведь проводили?). 
Иначе будет как с Git. Сишники этим славились (не знаю, как сейчас) - нужных структур данных искаропки нет, или пишем свои с ошибками, или используем массив вместо хеш-массива, т.к. реализовать проще, а на класс сложности пох. 





Это сообщение отредактировал(а) Karadul - 26.3.2012, 19:02

to Karadul

Позволю себе как автору изложить своё видение вопроса.

Абстрактно:

Я как первоклассник спросил: как сложить 2 + 2, на что коллеги мне объяснили, что нужно к двум палочкам приложить ещё две палочки и посчитать получившееся количество. Меня устроил предложенный способ...
Но тут встревает ученик 11 класса и говорит: 
- Всё не так,  и это плохой очень сложный способ...
        Разве вы не знаете, что компьютер использует двоичную арифметику!
        нужно число два преобразовать в двоичный код и складывать, а потом полученный результат преобразовать!!!
 
Когда же 11 класснику предложили взять и показать как эти палочки преобразовать в двоичный код, он дал множество исчерпывающих ответов:

1. я не учитель, что бы бесплатно палочки перекладывать

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

3. ваши палочки плохо обструганы

4. и мне в жизни никогда не придётся складывать палочки


--------- конец абстракции

То, что я не гуру программист на Java, ещё не значит, что я не разбираюсь в сложности алгоритмов. 
5 лет преподавания в ВУЗе предмета "Структуры и алгоритмы обработки данных" позволяют мне это утверждать. 

Меня устроило предложенное решение, при этом я конечно учитывал и сложность и требования своей конкретной задачи. 
К чему надо было влазить с рассуждениями о сложности, в уже решённый вопрос. 
Есть соответствующие разделы форума, заведите тему и вперёд...

Надеюсь, я никого не обидел

Я не учитель, чтобы учить складывать 2+2. У меня не работал эклипс, чтобы проверить код, а заменить метод на нужный - задача, с которой можно не справиться только при нежелании. Поэтому я и сказал, что здесь не бесплатный цирк, и для того, чтобы тебе помогли, стоит самому приложить какие-то усилия.

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


Ого! 5 лет преподавания - и сами хреначим поиск в списке? Это как безопасник, который ставит пароль 123 на доступный в инете сервер  А потом отвечает "я же безопасник, все под контролем, не лезьте, без вас разберутся".

Как у автора темы, можно спросить: а почему все-таки List, а не что-то другое? Знания явы не позволили? Так посоветовали же LinkedHashSet. Или просто по барабану? Без претензий, просто интересно.
Про ожидаемый размер списка и частоту поиска в нем в теме не было ни слова.

А к чему влазить... ну если структуры с неподходящим классом сложности тут никого не смущают - может валить отсюда, как поросенок Петр? Меня просто возмутило то, что на такие "мелочи" никто не обращает внимание, и понеслось.

Предельно не внимательно. Читаем третий пост от начала темы.
Я таки окончательно выхожу из дискуссии, поскольку по содержанию и даже по теории сказано уже все.

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

Граждане тема о чем ? ,  
запутался немного   

НУ вот Вы доколупались до причины выбора! Ну, хочется так человеку!

Вот этот пост здорово улыбнул! Отличная ирония, можно при случае воспользуюсь без ссылки на авторство? 
З. Ы.

Походу, уже ни о чём, но читать интересно! 

Добавлено через 2 минуты и 42 секунды
to Karadul Вы тоже очень смешной человек! Пытаетесь всем доказать, что Вы не верблюд, и, на мой взгляд, преуспели в этом: Вы гораздо упрямее! 

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

похоже ты форумом ошибся , 

M LSD

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

Proof of concept решения с List<String> и временем порядка O(log(n)):