Есть список имён хранящийся в  

необходимо:
 при добавлении в список нового имени проверить нет ли такого в списке,
и если есть то прибавить к имени 1 или ....

то есть при многократном добавлении  одного и того же имени (например - temp) список должен быть типа того:
temp
temp1
temp12
temp123   

или 

I]temp
temp1
temp2
temp3[/I] 

Подскажите пожалуйста алгоритм!  

сейчас делаю так:


Когда имена в списке упорядочены как в примере, вроде работает...
Но в когда имена в случайном порядке  -  появляются имена двойники..

Смотри сюда http://forum.vingrad.ru/act-ST/f-104/t-305998.html

Это сообщение отредактировал(а) arcsupport - 15.3.2012, 18:37

Используйте LinkedHashSet

knopka, как-то так?


Добавлено через 3 минуты и 46 секунд

Почему именно этот класс? Он же синхронизированный, значит медленный.

Спасибо всем кто откликнулся... но видимо я не совсем понятно всё объяснил...

List<String> - принципиально, он используется ещё кучей разных методов, 
к тому же я предельно всё упростил, что бы не грузить коллег не нужной информацией ...

А алгоритм должен работать как то так:

проверяем добавляемое имя например  ТЕСТ 
такое имя уже есть - пытаемся добавить ТЕСТ1
если есть такое - пытаемся добавить ТЕСТ2
если есть такое - пытаемся добавить ТЕСТ3
.........
если есть такое  - пытаемся добавить ТЕСТn 
если такого нет то добавляем ТЕСТn в список   

Вроде бы List имеет indexOf. Зачем перебирать элементы вручную?
что-то вроде 

Откуда инфа? 

1. Он не синхронизированный, о чем прямо говориться в документации.
2. Он сохраняет порядок добавления элементов в отличии от обычного HashSet.

LSD, Stolzen,  упс. Почему-то слова:

Прочитал как

  

Попробовал написать алгоритм, к сожалению не работает.
Условие  с  equals не срабатывает... 
Exception StackOverflowError ...  и т.д.

Подскажите что не так?

Насколько принципиально? Какую такую задачу решает в вашем случае именно List, что нельзя вернуть Collection?


Гипотетическая ситуация - строка является именем пользователя "VasyaPupkin1337", после инкремента получили "VasyaPupkin1338". Это правильно? Можете гарантировать, что аналогичной ситуации в жизни никогда-никогда-никогда не произойдёт?

Правильной задаче - правильная структура данных.
Моё такое ИМХО, что Map<String, Integer>, где ключом является строка, а значением - количество её вхождений, решает все проблемы и не создаёт новых.

to Shaggie

  - да, будет правильно...



Не понял какой ситуации?  

VasyaPupkin1338  и дальше может инкриминироваться  пока в списке будут такие же имена

только когда, например VasyaPupkin2012 , будет уникальным для списка - алгоритм закончит работу



 

Что вы хотели получить от этого кода? Что именно должна делать функция validateName? 


Поддерживаю. А еще есть такая вещь, как Bag (commons collections) или Multiset (guava collections) - рекомендую.

Добавлено через 2 минуты и 17 секунд
Да, еще, может вы немного расскажите о решаемой задаче? Возможно, существуют более простые способы ее решения. 

По большому счету все не так. Вы проовали читать свой текст?
Пусть добавляемое имя не совпало с первым именем в списке. Тогда if  не сработает
и stop останется истиной. Следовательно будет произведен повторный вызов. В котором произойдет тоже самое.
Естественное следствие этого алгоритма - stack overflow. А чего Вы хотели?

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

Честно говоря я не понимаю, зачем Вы написали вопрос, если не читаете ответов?
Зачем перебирать List вручную, если можно воспользоваться indexOf?
Чего Вы добиваетесь такой программой? Роста времени?

Возможно есть смысл воспользоваться другим видом коллекции, как Вам советовали. Но если Вы настаиваете на List, то почему не хотите использовать нормально его методы?

Это сообщение отредактировал(а) Mirkes - 17.3.2012, 19:51

Пардон, а как же написанное Вами выше:
? Может, тогда после VasyaPupkin1337 должно идти VasyaPupkin13378?
Прошу, уточните: если надо просто подсчитать количество слов в тексте, то тут, как Вам уже советовали лучше использовать Map, а если вывод должен быть именно temp1, temp12, temp123 и т. д., это уже интереснее, я над этим подумаю!    

Вот, посмотрите, это то, что Вам надо? Я руководствовался условием:

Запустите программу и введите в консоль несколько раз слово temp
Посмотрите вывод. Для выхода введите 0.
P. S. Писал "на коленке", код не оптимальный, но рабочий. Если надо, могу оптимизировать.
P. P. S. Помню, знакомый junior программером устраивался, ему нечто похожее задавали  .

to Pawl спасибо за программу...

to Mirkes спасибо за  

после этого наступило просветление   

Просьба покритиковать окончательное решение

 

я не понял, а зачем тогда Вы ранее писали, что должно быть так:
? Для дезинформации?  
Для определения, есть ли в списке искомый элемент, лучше вместо 
написать так:
эффект тот же, но понятнее, короче и меньше переменных. А если Вам непременно хочется использовать indexOf() - уберите цикл, он тут лишний, т. к., если name есть в списке, он сработает ровно 1 раз, а если нет - прокрутится впустую, что увеличит время работы программы, а на результат никак не повлияет.

Не совсем так. Поскольку name меняется в цикле то цикл действительно нужен.
Вариант с contains вполне возможен. Думаю от дает тот-же ответ, просто без указания места в списке. 
Так что с ним тоже нужен будет цикл типа


Этот вариант мне то же нравится больше чем с indexOf, просто я не знал о contains  .

Тогда надо менять логику метода. Вы запустите код и посмотрите как он работает: что есть цикл, что его нет, на выходе все-равно test1.
Даже если в списке дважды встречается test, test12 не получается.

Хотя, нет, не надо. Если в список добавить test1, то да, test12 получится.

ТС-у категорически советую понять, что такое класс сложности. А если не в состоянии - пусть берет какой-нибудь LinkedHashSet и не парится.

ИМХО, совершенно непонятно, какое практическое применение у данной задачи! Я сужу по ее формулировке и приведенной реализации. Даже для тестовой она выглядит извращенно... А я тут извратился еще больше  - сделал рекурсивный вариант решения - как изначально пытался сделать автор. Результат получается точь в точь, как в его реализации с циклом !

Сишники тут не нужны.

Добавлено через 57 секунд
что интересно, никогда на С не писал!

to Pawl посмотрите заголовок поста: Как избежать двойников в списке   - двойников нет? нет! значит алгоритм работает.

и  в вопросе я писал      ключевое слово - типа того


задачу описал в предельно упрощённом виде, String и name - тоже упрощение. 
В реальности всё намного, намного сложнее.  
Но зачем утомлять коллег ненужной информацией... ну привёл бы я полное описание задачи строк на 400, кто бы его прочитал?
Вы? Приведённого описания на мой взгляд вполне хватало для выбора алгоритма

to Karadul

прежде, чем писать - прочитайте предыдущие сообщения!

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

Добавлено через 29 секунд
Вопрос решён

Так я чё? Я ж ни чё - работает и слава Богу! Как гласит золотое правило программиста: работает - не трогай! 

ну, значит и решение должно быть, типа, того!   
А серьезно - главное, что Вы разобрались с Вашей проблемой. 

О господи! Модеры! Знающие люди! Вы здесь есть? Сделайте что-нибудь! Почему все толкают алгоритмы  с O(n) и все молчат?

Вот, почитайте.

Гм... Господину Kardual действительно следует сделать замечание.
Во первых, не прочитав постановку задачи и обсуждения дает рекомендации в несколько грубоватой форме.
Во ворых, не задумывается над тем, что пишет.
В третьих, рекомендует материал, решающий совершенно (принципиально) другую задачу.
В четвертых, говорит о классах сложности, но видимо не совсем четко понимает как определить класс сложности задачи.
В пятых поучает более опытных коллег по поводу использования или не использования синтаксиса языка Java. То что синтаксис языка С-подобен не вина и не заслуга пользователя, а просто факт.
Прошу прощения, если получилось грубовато.

Чё, серьезно?

Класс сложности будет O(n). Обьяснить почему или сам догадаешься? С HashMap был бы O(1).

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

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

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

Сорри если грубовато получилось. Хотя так надо 


Почитай ссылочку выше. Работать то работало, но как строк стало не 20, а 20 тысяч, работать стало крайне хреново.
Не уважают у вас тут класс сложности. Это только жавоиды или вообще все русские школолопрограммисты?

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

Поддерживаю! Однозначный хам.

Как аукнется, знаете ли.

Попка пригорела, лодыри? 

Это сообщение отредактировал(а) Karadul - 22.3.2012, 23:03

M LSD

Karadul, замечание насчет сложности справедливое, но хамишь ты напрасно. Цитата(Karadul @  22.3.2012,  23:23 ) Попка пригорела, лодыри? Предлагаю тебе в пятидневный срок реализовать алгоритм со сложностью хотя бы O(log(n)), соблюдая исходное условие про List<String>. Сможешь - молодец и замечания по делу. Не сможешь/не станешь - твои замечания троллинг и поступать с тобой надо как с троллем.

Где тут хамство? Быстро, решительно!

Конвертировать List в какой-нить Set. Если не позволяют условия - поменять их. Или вы всерьез будете отвечать на вопрос "Как отверткой чистить зубы? Отверткой потому что по условиям задачи так надо".

Меньше слов, больше кода  

Казахские программисты - самые суровые программисты в мире! Казахские программисты настолько суровы, что вообще не пользуются компьютером... 

Добавлено через 1 минуту и 17 секунд
Пы Сы Как аукнется, знаете ли.

Еще что-нибудь?

to Karadul

пример не рабочий


cannot find symbol method get(java.lang.String)

условие не выполнено

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



Сконвертируй в Set. Скажи поставившему условие, что он не прав. См. выше про отвертку.

подведем итоги:

есть метод contains... (его предлагали)
если вы считаете, что, вы напишете лучше (оптимальнее), то флаг вам в руки!


наверное это не возможно   
видимо ТС надо немного переделать рабочую программу

ну говорили же - "работает - не лезь!!!"   

Вас никто не просил работать бесплатно, Вас просили ответить за слова, с чем Вы, собственно, не справились.

Pawl, такую вещь, как заменить метод на нужный, ты и сам можешь сделать, или за тебя пеленки менять нужно?




... который работает через for c O(n). Более того, Set содержит тот же метод.


А переделать тип переменной из ArrayList в подходящий Set - это на грани выполнимого? Все остальное останется тем же.

Для особо одаренных поясню, что класс сложности определяется в контексте ВСЕГО ПРОЕКТА, а не в контексте конкретного фрагмента. Если в большинстве мест НУЖЕН List, то и в данном конкретном месте ПРИДЕТСЯ использовать List.
А общий треп по поводу О(1) и О(n) к делу не относится.
Автору предлагали использовать Hash, но он указал, что в других частях проекта используется List и выбора у него НЕТ.
Я дискуссию прекращаю.

А прочесть условие это на грани выполнимого?

Можно скопировать локально List в Set, если надо за раз проверить больше 1 имени. Можно заменить List на Set, который сохраняет порядок, и в остальных местах ты эту разницу просто не заметишь.
Если список с именами вряд ли будет большим и поиск в нем будет редко использоваться, то можно и так оставить. Но лучше так не делать.


Действительно, такие мелочи. Кроме меня, на них никто и внимания не обратил.
Надеюсь, мне с таким кодом дела иметь не придется.

Вот еще пример.
http://habrahabr.ru/post/137615/


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

Обещал прекратить дискуссию, но не удержался.
Обидно, что простое обсуждение скатилось к общению на уровне "От дурака слышу" (эту фразу в научный мир ввел известный чам и гениальный физик Лев Ландау).
Сразу извинюсь перед студентом, что отвечать буду с позиции профессора и программиста, за плечами которого множество внедренных продуктов.
Мне приходилось преподавать технологию программирования и я прекрасно знаю разницу в сложности алгоритмов.
Однако в мне приходилось участовать в разработке проектов, когда определенная структура данных хорошо подходит для одной задачи в проекте и жутко тормозит в другой. Тогда как другая структура дданных прекрасно работает во втором месте и просто не пригодна (по времени обработки) в первом.
Иногда можно пойти на трансформацию структур данных, но это сильно зависит от сложности трансформации. Предлагаемая замена 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)):