Привет, решение данной задачи на Java. Покритикуйте. (файл-список городов в аттаче):


Это сообщение отредактировал(а) m1st - 19.7.2010, 17:49

Присоединённый файл ( Кол-во скачиваний: 14 )
 cities.txt 1,73 Kb

Первое что можно исправить (мое личное мнение) - это при чтении из файла создать коллекцию для поиска такого вида:

Она поможет исправить поиск города по первой букве.

При использовании какого-нибудь города его просто удалять из коллекции (естественно из копии оригинальной коллекции, созданной при чтении из файла), а не использовать массив used.

Желательно отформатировать исходный код перед отправкой на форум (а то уж очень не удобно читать с такими страшными отступами)

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

Данный код:

по моему лучше смотриться так (но это только мое мнение и к нему не обязательно прислушиваться):


Это сообщение отредактировал(а) Kircul - 19.7.2010, 16:55

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

"Premature optimization is the root of all evil" ©
ИМХО, не стоит сходу все выкидывать и писать заново, для начала сойдет и составление коллекции citiesIndex, а уж дальше смотреть что еще можно изменить.

Действительно, отпадает необходимость хранить первую букву в плохочитаемом поле. 
Set<String> сразу решает проблему с дубликатами и ускорением поиска по hashCode().

Сорри, код отформатировал.

По-моему тоже так лучше. Если честно, первый раз увидел такую конструкцию... 

Спасибо!

кстати если заранее неизвестен размер списка, лучше использовать LinkedList, ArrayList основан на массиве и создается с некоторым дефолтным по размеру, когда кол-во элементов превышает размер массива, создается новый и в него копируются значения старого, в LinkedList этого нет.
резюме: 
ArrayList - быстр при доступе по индексу но медленный и неэкономно расходует ресурсы если неизвестно кол-во элементов
LinkedList - быстр при добавлении новых элементов, но медленее при обращении по индексу

+ если вам напрямую ненужны методы ArrayList лучше тип переменной указать как List, работа с интерфейсами или абстрактными классами делает систему более легкой для внесения изминений
мое маленькое имхо  

Это сообщение отредактировал(а) ki6opr - 20.7.2010, 09:43

Однозначно верно.

[offtopic]

А вот это уже спорно, в теории все должно быть так как вы говорите, но на практике ArrayList работает быстрее (при добавлении елементов в конец списка). Сам наткнулся на эти грабли вот тут. LinkedList хорош тогда когда необходимо проводить довольно много добавлений в середину списка.
[/offtopic]

Эффект можно минимизировать грамотным заданием capacity при создании листа.
Полностью поддерживаю Kircul, LinkedList предназначен для специфических случаев:

Если говорить о мелочной оптимизации не самого лучшего алгоритма и кода, то я бы посоветовал:
а) Вместо массива boolean использовать BitSet
б) Вместо String использовать StringBuffer/StringBuilder - это даст существенный выигрыш на текстовых операциях, типа:

в) В циклах убрать постоянное обращение к методу size() - примерно так:

г) Вообще постоянное создание стековых переменных в теле цикла - это тоже не очень хорошо - известно что это замедляет скорость
д) Красяво, да и быстрее по скорости можно было бы вместо   ArrayList cities = new ArrayList(); объявить:

    1) List дешевле ArrayList
    2) Компилятор знает тип объекта внутри списка, так что операция каста будет оптимизирована

ivanovpv, 
Вы не могли бы пояснить эту мысль? На первый взгляд из преимуществ только loose coupling и возможность подмены реализации. Откуда прирост в скорости?
Я уже не говорю о том, что List - это интерфейс, его инстанс создать никак нельзя. 

А в чем тут выигрыш?

В классе StringBuffer:


В классе String:


В том, что операция сложения нужна лишняя?

Если уж заменять String операции то тогда на StringBuilder, потому как он не thread save, и не будет затрачено время на блокирование. как бы syncronized нехило отъедает ресурсов.

Кстати я насколько знаю компилятор проводит оптимизацию и часто операции с String заменяются на StringBuilder

и плюс много к грамотному заданию Capacity и BitSet. булин в яве сделан через integer если я правильно помню ?

Это сообщение отредактировал(а) ki6opr - 21.7.2010, 04:54

Не так все однозначно... Я неверно указал на StringBuffer, надо использовать StringBuilder. Прогоните такой тестик:


На моей системе выдача такая:


Так что эффективнее все же StringBuilder

Это сообщение отредактировал(а) ivanovpv - 21.7.2010, 09:08

ivanovpv, тест конечно верный. StringBuilder работает быстрее. Вот только 50 мс разница на сто миллиардов операции практически не имеет влияния на производительность. Не такое это уж и узкое место. Разница в реализации метода charAt для классов String и StringBuilder минимальна:

String:


AbstractStringBuilder:


Выигрыш последнего только за счет отсутствия операции index + offset. На таком огромном количестве операции, что вы проводили при тестировании,  разница может быть и видна. Но на миллионе уже не так.
 

1) Тут речь идет не столько о методе charAt(), а о других методах. Смысл то в том, что если есть массовые операции над строками - лучше использовать StringBuilder
2) Выигрыш я думаю не в арифметике, а в блокировках

А вообще согласен, все это копейки   

Есть еще интересная замена StringBuilder. Для расширения кругозора 

Представление строк в виде связок символов

Следуя вашим советам, вот что получилось:


Это сообщение отредактировал(а) m1st - 27.9.2010, 13:54

Допустим, существует набор городов "Абв", "Акв", "Вба": для данного набора городов возможны два варианта решения и в моем алгоритме будут вычеслены обе цепочки (хотя это не нужно), как оптимизировать алгоритм так чтобы при таком раскладе вычислялась только одна цепочка (не важно какая)?

Как оптимизировать решения для городов с одинаковыми первой и последней буквой ("Анапа")?