Всем привет!
Последнее домашнее задание явно показывает, что многим нравиться делать небольшие и несложные домашние задачки. По-этому вот вам ещё одна! =)
Задание:
Надо написать метод, которые переставляет первые n элементов массива в конец этого массива. При этом есть одно ограничение: Использовать можно только один (данный) массив.
Т.е. реализовать такой вот метод:
Object[] moveNElementsToTheEnd(Object[] initArray, int n), где входной массив [1, 2, 3, 4, 5, 6, 7] с n=3 должен выдать [4, 5, 6, 7, 1, 2, 3].
Как обычно код предоставляем в комментариях в виде ссылок на сайты типа http://codepad.org/ или http://pastebin.com/. Язык написания — любой, качество написание (уровень говнокодистости) — любой.
И ещё одна деталь — если возможно, там же в листинге кода оставьте какой-нибудь лог промежуточных состояний этого массива во время выполнения алгоритма для массивов чисел от 1 до 10 и от 1 до 13! (т.е. конкретно то, что выдаёт программа во время запуска)
Удачи и до встречи на следующем, Июльском девклабе!!
m-a-m-o-n.livejournal.com/
http://pastebin.com/x7UrQj9D
m-a-m-o-n.livejournal.com/
Правильное решение:
http://pastebin.com/DCEU4Yem
Александр Мочёнов
Оч. клёва! А можно там же оставить дебаг всех стэйтов массива после каждого изминения?
m-a-m-o-n.livejournal.com/
Так есть же:
run:
debug: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
debug: [10, 2, 3, 4, 5, 6, 7, 8, 9, 1]
debug: [10, 9, 3, 4, 5, 6, 7, 8, 2, 1]
debug: [10, 9, 8, 4, 5, 6, 7, 3, 2, 1]
debug: [10, 9, 8, 7, 5, 6, 4, 3, 2, 1]
debug: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
debug: [4, 9, 8, 7, 6, 5, 10, 3, 2, 1]
debug: [4, 5, 8, 7, 6, 9, 10, 3, 2, 1]
debug: [4, 5, 6, 7, 8, 9, 10, 3, 2, 1]
debug: [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]
done
BUILD SUCCESSFUL (total time: 0 seconds)
Александр Мочёнов
ок. не так вырзился значит. Поправил. Я имел ввиду вот то что ты выше написал что бы было там же по ссылке. Рядом с кодом.
m-a-m-o-n.livejournal.com/
Пардон, пропустил момент, версия с комментарием:
http://pastebin.com/5m7SDKWD
Александр Мочёнов
Ты уже встречался с это задачей ранее? 😉
m-a-m-o-n.livejournal.com/
Вряд ли, но очень похоже на задачки для первого курса паскаля.
Oleg Tsernetsov
Кстати, по счастливому стечению обстоятельств алгоритм Дмитрия аналогичен имплементации SUN-a (Collections.rotate2()) :).
См. Section 2.3, p.14 of Jon Bentley’s Programming Pearls (Addison-Wesley, 1986).
Александр Мочёнов
ДА ДА да … про жемчужены я был в курсе. По-этому и удивился, что он именно так и сделал. Обычно чего-то мудряд а до этого не доходят сами.
Но я не знал, что в жаве оно решено = Вобщем будут ещё ДЗ =) Ждите.
Dmitri Konovalov
Еще 1 решение на Java http://pastebin.com/SLGK3R3g
Александр Мочёнов
Суепр! А Листинг дебага всех изминения массива можно? (там же на пасте-хостинге)
Александр Мочёнов
Я так понимаю при dimension = 8 и n = 4 —> не работает?
Dmitri Konovalov
Верно, как оказалось алгоритм не работает в случае с кратными параметрами, добавил решение и для таких случаев. Оно кстати тоже описано в «Жемчужинах». Листинги дебага можно посмотреть по ссылке после кода.
http://pastebin.com/Njei5ffS
Oleg Tsernetsov
Java, 3 строки:
http://pastebin.com/NzrRxPpF
m-a-m-o-n.livejournal.com/
А реализация от sun хороша, rotate1(), rotate2().
Oleg Tsernetsov
Это два разных алгоритма, один перформит лучше в случае больших объемов, другой — на малых или рэндом аксесс массивах.
http://java.sun.com/javase/6/docs/api/java/util/Collections.html#rotate(java.util.List, int)
…
For a more complete description of both algorithms, see Section 2.3 of Jon Bentley’s Programming Pearls (Addison-Wesley, 1986).
m-a-m-o-n.livejournal.com/
Меня именование и стиль смутили.
Oleg Tsernetsov
«… на малых или рэндом аксесс массивах»
Оговорился — не массивах, конечно, а списках.
m-a-m-o-n.livejournal.com/
Давайте будем совсем честными:
if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
rotate1((List)list, distance);
else
rotate2((List)list, distance);
первый первый алгоритм быстрее в несколько раз, но для него нужен произвольный доступ,
второй медленнее (но тоже линейный), зато работает и на связных списках (ну, ещё, второй выглядит проще на первый взгляд).
Oleg Tsernetsov
Будем честными? значит что-то все-таки было не совсем честно :)?
Оба алгоритма работают на любых списках. То, что первый быстрее второго в несколько раз — утверждение неверное, поскольку все зависит от сложности доступа к элементу в списке. В случае константного доступа — это так, но например если доступ к элементу в списке линейный — то второй алгоритм будет быстрее.
На списках с быстрым доступом к элементу ИЛИ прочих коротких списках лучше перформит первый алгоритм.
Для остальных случаев выбирается второй, который покрывает длинные списки с медленным доступом.
m-a-m-o-n.livejournal.com/
>То, что первый быстрее второго в несколько раз – утверждение неверное, поскольку все зависит от сложности >доступа к элементу в списке.
Именно по этому перед вызовом первого алгоритма и проверятеся что:
list instanceof RandomAccess
Oleg Tsernetsov
Кагбе даже в 2 можно уложить
http://pastebin.com/myr6n0t5
Oleg Tsernetsov
Тест и вывод соответственно.
http://pastebin.com/kfma3bPr
Juri Timoshin
Ruby здесь вне конкуренции 🙂 в 1.9.2 есть метод Array.rotate(n=1)
A если версия более ранняя, то банально
def rotate(n=1)(n%self.size).times{ push shift }; self
end
Juri Timoshin
Даже без циклов:
http://pastebin.com/UAPqqBAm
Александр Мочёнов
Если не считать, что
self[new_start..-1] и self[0…new_start] два отдельных массива (новых) и + делает третий — тоже новый =)
Но да, коротко.
Juri Timoshin
Ну первый вариант с push и shift не создаёт 🙂
zahardzhan
15 строчек жоской императивщины на Clojure http://pastebin.com/LrBharR0
Александр Мочёнов
Положил дебаг внутрь линка
Andrei Poryvkin
PHP: http://pastebin.com/qaNvP4FY
Dumka
ещё такой вариант PHP: http://pastebin.com/7BTFkwXd
Результат:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
2, 3, 4, 5, 6, 7, 8, 9, 10, 1
3, 4, 5, 6, 7, 8, 9, 10, 1, 2
4, 5, 6, 7, 8, 9, 10, 1, 2, 3
Andrei Poryvkin
Использование array_push() для добавления одного элемента не самый лучший выбор, так как это намного медленнее, чем $array[] = $val.
Dumka
Спасибо за совет, вот исправленная версия — http://pastebin.com/PuBCLA2P
Однако замечу что рекурсивный вызов функции в твоём случае не самый верный подход ибо он выполняется дольше чем с array_push в цикле. К томуже в твоём примере во время каждой рекурсии выделяется память для аргументов функции $initArray и $n.
Примитивный бенчмарк (100 000 вызовов с а=[1,2,3,4,5,6,7,8,9,10] и n=3, время взято среднее из 10ти попыток) показал (на моём серваке):
http://pastebin.com/qaNvP4FY — 2.33 сек
http://pastebin.com/7BTFkwXd — 1.82 сек
http://pastebin.com/PuBCLA2P — 1.35 сек
PHP
И от меня PHP one-line:
http://pastebin.com/WDwGkj88
Александр Мочёнов
Это всё делает временные массивы — что не есть спортивно и не по заданию =)
Elvis
Ne sovsem po pravilam
http://pastebin.com/B1eEUvAg
m-a-m-o-n.livejournal.com/
Без обид:
http://pastebin.com/TJh2GV3T
Александр Мочёнов
А собственно зачем? =)
Sergei Kirjanov
почти то же, что выше но на перл-е:
http://pastebin.com/LWA26tmT
sub moveNElementsToTheEndInPlace{
my($l,$n)=@_;
@$l = @$l[$n..$#$l,0..$n-1];
$l
}
Насколько я понимаю интерпретатор, это (в случае перл-а) временные массивы не делает,
поскольку слайс не создает массива, а кладет кучу значений на стек
Kirill Linnik
пффф…. чего-то только не придумают умельцы… PHP решит все ваши проблемы в пару строчек 😛
http://codepad.org/aK1kDDqR
or
http://pastebin.com/cz7x7nNz
Andrei Poryvkin
Использование array_push() для добавления одного элемента не самый лучший выбор, так как это намного медленнее, чем $array[] = $val
Andrei Poryvkin
Это был комментарий к решению Dumka, так что можно удалить 14. ветку
Jevgeni Tshaikin
Решил выложить и свое решение. Решение оказалось настолько простым, что даже как-то стыдно выкладывать на pastebin. Использовал естественно свой родной C#
public static Object[] moveNElementsToTheEnd(Object[] initArray, int n)
{
return initArray.Skip(n).Concat(initArray.Take(n)).ToArray();
}
П.С. не крашиться даже если
moveNElementsToTheEnd(input, 9)
moveNElementsToTheEnd(input, -1)
Jevgeni Tshaikin
Sorry, не заметил «Использовать можно только один (данный) массив».
Jevgeni Tshaikin
v Google na interview tozhe sprashivajut pro String Rotation http://habrahabr.ru/blogs/google/102482/#habracut 🙂