Всем привет!
Последнее домашнее задание явно показывает, что многим нравиться делать небольшие и несложные домашние задачки. По-этому вот вам ещё одна! =)
Задание:
Надо написать метод, которые переставляет первые 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! (т.е. конкретно то, что выдаёт программа во время запуска)
Удачи и до встречи на следующем, Июльском девклабе!!
http://pastebin.com/x7UrQj9D
Правильное решение:
http://pastebin.com/DCEU4Yem
Оч. клёва! А можно там же оставить дебаг всех стэйтов массива после каждого изминения?
Так есть же:
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)
ок. не так вырзился значит. Поправил. Я имел ввиду вот то что ты выше написал что бы было там же по ссылке. Рядом с кодом.
Пардон, пропустил момент, версия с комментарием:
http://pastebin.com/5m7SDKWD
Ты уже встречался с это задачей ранее?
Вряд ли, но очень похоже на задачки для первого курса паскаля.
Кстати, по счастливому стечению обстоятельств алгоритм Дмитрия аналогичен имплементации SUN-a (Collections.rotate2())
.
См. Section 2.3, p.14 of Jon Bentley’s Programming Pearls (Addison-Wesley, 1986).
ДА ДА да … про жемчужены я был в курсе. По-этому и удивился, что он именно так и сделал. Обычно чего-то мудряд а до этого не доходят сами.
Но я не знал, что в жаве оно решено =\ Вобщем будут ещё ДЗ =) Ждите.
Еще 1 решение на Java http://pastebin.com/SLGK3R3g
Суепр! А Листинг дебага всех изминения массива можно? (там же на пасте-хостинге)
Я так понимаю при dimension = 8 и n = 4 –> не работает?
Верно, как оказалось алгоритм не работает в случае с кратными параметрами, добавил решение и для таких случаев. Оно кстати тоже описано в “Жемчужинах”. Листинги дебага можно посмотреть по ссылке после кода.
http://pastebin.com/Njei5ffS
Java, 3 строки:
http://pastebin.com/NzrRxPpF
А реализация от sun хороша, rotate1(), rotate2().
Это два разных алгоритма, один перформит лучше в случае больших объемов, другой – на малых или рэндом аксесс массивах.
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).
Меня именование и стиль смутили.
“… на малых или рэндом аксесс массивах”
Оговорился – не массивах, конечно, а списках.
Давайте будем совсем честными:
if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
rotate1((List)list, distance);
else
rotate2((List)list, distance);
первый первый алгоритм быстрее в несколько раз, но для него нужен произвольный доступ,
второй медленнее (но тоже линейный), зато работает и на связных списках (ну, ещё, второй выглядит проще на первый взгляд).
Будем честными? значит что-то все-таки было не совсем честно
?
Оба алгоритма работают на любых списках. То, что первый быстрее второго в несколько раз – утверждение неверное, поскольку все зависит от сложности доступа к элементу в списке. В случае константного доступа – это так, но например если доступ к элементу в списке линейный – то второй алгоритм будет быстрее.
На списках с быстрым доступом к элементу ИЛИ прочих коротких списках лучше перформит первый алгоритм.
Для остальных случаев выбирается второй, который покрывает длинные списки с медленным доступом.
>То, что первый быстрее второго в несколько раз – утверждение неверное, поскольку все зависит от сложности >доступа к элементу в списке.
Именно по этому перед вызовом первого алгоритма и проверятеся что:
list instanceof RandomAccess
Кагбе даже в 2 можно уложить
http://pastebin.com/myr6n0t5
Тест и вывод соответственно.
http://pastebin.com/kfma3bPr
Ruby здесь вне конкуренции
в 1.9.2 есть метод Array.rotate(n=1)
A если версия более ранняя, то банально
def rotate(n=1)(n%self.size).times{ push shift }; self
end
Даже без циклов:
http://pastebin.com/UAPqqBAm
Если не считать, что
self[new_start..-1] и self[0...new_start] два отдельных массива (новых) и + делает третий – тоже новый =)
Но да, коротко.
Ну первый вариант с push и shift не создаёт
15 строчек жоской императивщины на Clojure http://pastebin.com/LrBharR0
Положил дебаг внутрь линка
PHP: http://pastebin.com/qaNvP4FY
ещё такой вариант 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
Использование array_push() для добавления одного элемента не самый лучший выбор, так как это намного медленнее, чем $array[] = $val.
Спасибо за совет, вот исправленная версия – 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 one-line:
http://pastebin.com/WDwGkj88
Это всё делает временные массивы – что не есть спортивно и не по заданию =)
Ne sovsem po pravilam
http://pastebin.com/B1eEUvAg
Без обид:
http://pastebin.com/TJh2GV3T
А собственно зачем? =)
почти то же, что выше но на перл-е:
http://pastebin.com/LWA26tmT
sub moveNElementsToTheEndInPlace{
my($l,$n)=@_;
@$l = @$l[$n..$#$l,0..$n-1];
$l
}
Насколько я понимаю интерпретатор, это (в случае перл-а) временные массивы не делает,
поскольку слайс не создает массива, а кладет кучу значений на стек
пффф…. чего-то только не придумают умельцы… PHP решит все ваши проблемы в пару строчек
http://codepad.org/aK1kDDqR
or
http://pastebin.com/cz7x7nNz
Использование array_push() для добавления одного элемента не самый лучший выбор, так как это намного медленнее, чем $array[] = $val
Это был комментарий к решению Dumka, так что можно удалить 14. ветку
Решил выложить и свое решение. Решение оказалось настолько простым, что даже как-то стыдно выкладывать на 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)
Sorry, не заметил “Использовать можно только один (данный) массив”.
v Google na interview tozhe sprashivajut pro String Rotation http://habrahabr.ru/blogs/google/102482/#habracut