Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / Java |
![]() ![]() |
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 38 вперед Ctrl→ |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
Всем добрый день! Часто читаю в форумах что на собеседованиях задают вопросы из области : "Расскажите про ArrayList vs LinkedList" И если с теорией http://habrahabr.ru/post/162017/ у всех более менее все гладко , то вот с практикой возникают вопросы : Предлагаю такую задачку для решения и обсуждения : Есть список, (очередь элементов) нужно из него получить другой список (отсортировать элементы в другом порядке) : Пример простой : x(1),x(2),...,x(n) => x(1), x(n-1), x(2), x(n-2)... 1) Нужно написать код для Queue , LinkedList , ArrayList . 2) Без использования дополнительного списка (массива) - делать перестановки в этом же списке, массиве. 3) Оценить время, производительность , эффективность. |
14 ноя 13, 11:34 [15126582] Ответить | Цитировать Сообщить модератору |
Blazkowicz Member Откуда: Сообщений: 24443 |
С практикой тоже все просто. ArrayList в 99% случаев быстрее. То есть, чтобы LinkedList работал быстрее, нужно подогнать условия задачи под реализацию каждой из коллекций. В практике такого не встречается.
Queue это интерфейс а не реализация. Что мерять собрались? |
||||
14 ноя 13, 11:38 [15126636] Ответить | Цитировать Сообщить модератору |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
Нужен код для каждой реализации , вопрос на знание методов коллекций ! List list = Arrays.asList("1", "2", "3", "4", "5"); ArrayList<String> ain = new ArrayList<String>(list); LinkedList<String> lin = new LinkedList<String>(list); Queue<String> qin = new LinkedList<String>(list); |
||
14 ноя 13, 11:52 [15126771] Ответить | Цитировать Сообщить модератору |
Blazkowicz Member Откуда: Сообщений: 24443 |
Queue это реализация?
А документация на что?
Ожидается что эти двое как-то отличаются по производительности? |
||||||
14 ноя 13, 11:55 [15126791] Ответить | Цитировать Сообщить модератору |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
Интерфейс. Будем точными. Вопрос и заключается в том чтобы испытуемый написал простой алгоритм , а уже потом объяснил на его примере что да как работает. Queue и LinkedList имеют разные методы, требуется решить задачу - используя методы Queue , потом используя методы LinkedList , которых нет в интерфейсе Queue. |
||
14 ноя 13, 12:00 [15126828] Ответить | Цитировать Сообщить модератору |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
Blazkowicz , Сколько Вам нужно времени чтобы написать такой алгоритм ? Для проверки : List list1 = Arrays.asList("1"); List list2 = Arrays.asList("1", "2"); List list3 = Arrays.asList("1", "2", "3", "4", "5"); List list4 = Arrays.asList("1", "2", "3", "4", "5", "6"); |
||
14 ноя 13, 12:07 [15126897] Ответить | Цитировать Сообщить модератору |
mesier Member Откуда: Новокузнецк ► СПб Сообщений: 1038 |
А x(n) куда делся? |
||
14 ноя 13, 12:20 [15127017] Ответить | Цитировать Сообщить модератору |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
подумайте :) такой ряд был бы слишком простой : x(1),x(2),...,x(n) => x(1), x(n), x(2), x(n-1)... |
||||
14 ноя 13, 12:24 [15127057] Ответить | Цитировать Сообщить модератору |
mesier Member Откуда: Новокузнецк ► СПб Сообщений: 1038 |
Звучит как "додумайте". )) Последний член больше не нужен (как скрипач)? Или что? У меня преподаватель был в институте, он категорически отказывался на консультациях решать задачи, написанные на листочке. Говорит, вдруг ты в одном символе ошибся, а я мучайся потом.. Так вот, мне кажется это как раз тот случай! |
14 ноя 13, 12:46 [15127274] Ответить | Цитировать Сообщить модератору |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
Зачем листочек? Перед Вами компьютер с Вашей любимой IDE :) |
||
14 ноя 13, 13:03 [15127464] Ответить | Цитировать Сообщить модератору |
Andrew1411 Member Откуда: Москва Сообщений: 401 |
А зачем решать такие задачи? Что бы показать, что выбранная коллекция для этой задачи неоптимальна? В .Net подфоруме, пару месяцев назад один тип носился, в каждой теме твердил что связанный список быстрее всех остальных коллекций (бедняга, наверно тоже увидел лишь одну задачу). Я к чему это все, либо составляейте справочник типового решения разных задач на разных коллекциях - тогда поможете начинающим в выборе коллекции под задачу (а так же дадите "списать" решение под неудобный вариант использования коллекции), либо закопайте тему поглубже. Справочник, оформляйте как FAQ, либо вообще отдельным сайтом, с указанием ссылки. |
14 ноя 13, 13:58 [15128115] Ответить | Цитировать Сообщить модератору |
schwa Member Откуда: IT gulag Сообщений: 7634 |
in-place O(n^2) для arraylist O(n^3) для linkedlist не in-place O(n) arraylist. O(n^2) linkedlist. Queue в этой задаче делать нечего. |
14 ноя 13, 14:32 [15128556] Ответить | Цитировать Сообщить модератору |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
Отлично! Оценки есть ! Остался код ! Для затравки решение на Хаскель http://ideone.com/JiG0Ut Жду на java :) |
||
14 ноя 13, 15:26 [15129128] Ответить | Цитировать Сообщить модератору |
Сергей Арсеньев Member Откуда: Сообщений: 4113 |
Я правильно понял из 1,2,3,4 получить 1,3,2,2 и это называется сортировка? |
||
14 ноя 13, 16:00 [15129434] Ответить | Цитировать Сообщить модератору |
Озверин Member Откуда: Ростов-на-Дону Сообщений: 4785 |
Atum1, я может чего то не понимаю, но это в самом деле сортировка? |
14 ноя 13, 16:34 [15129779] Ответить | Цитировать Сообщить модератору |
ivanra Member Откуда: Сообщений: 844 |
Если это не сортировка, а перестановка элементов, то связанный однозначно быстрее O(n2) arraylist. O(n) linkedlist. |
14 ноя 13, 16:42 [15129839] Ответить | Цитировать Сообщить модератору |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
Сергей Арсеньев, Задача из одной последовательности получить другую по формуле. x(1),x(2),...,x(n) => x(1), x(n-1), x(2), x(n-2),..., x(n) Для 1,2,3,4 => 1,3,2,4 |
14 ноя 13, 16:43 [15129840] Ответить | Цитировать Сообщить модератору |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
Отлично! Нужен код. На любом известном Вам языке программирования . Идеально на java. Еще раз - есть последовательность элементов x(1),x(2),...,x(n) нужно на ее основании получить последовательность с другим порядком - такой же длинны . Но чтобы : 1) первый и последний элементы ее были на своих местах, x(1) ... x(n) 2) Остальные чередовались x(1), x(n-1), x(2), x(n-2) , x(3) , x(n-3) ... x(n) |
||
14 ноя 13, 16:48 [15129879] Ответить | Цитировать Сообщить модератору |
Blazkowicz Member Откуда: Сообщений: 24443 |
В идеальной сферической ЭВМ в вакууме? |
||
14 ноя 13, 16:51 [15129909] Ответить | Цитировать Сообщить модератору |
mesier Member Откуда: Новокузнецк ► СПб Сообщений: 1038 |
Ну наконец-то.. ) |
||
14 ноя 13, 17:29 [15130218] Ответить | Цитировать Сообщить модератору |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
Ура! Появилось первое решение для ArrayList vs LinkedList http://ideone.com/W3oqDP |
||
14 ноя 13, 17:50 [15130364] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 38815 |
Решил блеснуть интеллектом? Так слушай. Никто линкед-лист не сортирует. Нет в природе такой постановки. В тех структурах данных где LL действительно существует, он вспомогательный (LRU/MRU) и линкует обычно листовые узлы деревьев. Это его главное применение. Любые попытки сортировать (и поддерживать в ражнированом порядке LL) вызывают опухоль мозга у всего software. Структуры данных нужно использовать в правильных use-cases а не др@чиtь их. Прости модератор. |
||
14 ноя 13, 18:12 [15130494] Ответить | Цитировать Сообщить модератору |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
Мы не говорим о классической сортировке - где одно больше другого или меньше. Будьте внимательны - мы говорим , если хотите о шафлере, который выстраивает коллекцию в определенном порядке. был порядок x(1),x(2),...,x(n) стал x(1), x(n-1), x(2), x(n-2) ,..., x(n) |
||
14 ноя 13, 18:20 [15130541] Ответить | Цитировать Сообщить модератору |
Atum1 Member Откуда: СПБ Сообщений: 1834 |
Есть конкретная задача - Вам нужно применив ваши знания коллекций решить ее и дать оценку вашего решения. |
||
14 ноя 13, 18:22 [15130555] Ответить | Цитировать Сообщить модератору |
super-code Member Откуда: Сообщений: 244 |
Atum1, я решил на C# :) сложность ArrayList - N^2, LinkedList - N |
14 ноя 13, 18:43 [15130664] Ответить | Цитировать Сообщить модератору |
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 38 вперед Ctrl→ |
Все форумы / Java | ![]() |