IT-встречи в Таллине (на русском)

Домашнее заданее на июль месяц

Всем привет!
Последнее домашнее задание явно показывает, что многим нравиться делать небольшие и несложные домашние задачки. По-этому вот вам ещё одна! =)

Задание:
Надо написать метод, которые переставляет первые 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! (т.е. конкретно то, что выдаёт программа во время запуска)

Удачи и до встречи на следующем, Июльском девклабе!!

Назад

Нужен Джедай!

Далее

Анонс июльской встречи: 27.07.2010

46 комментариев

  1. Dmitri Konovalov

    Еще 1 решение на Java http://pastebin.com/SLGK3R3g

  2. Oleg Tsernetsov

    Java, 3 строки:
    http://pastebin.com/NzrRxPpF

    • А реализация от 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).

        • Меня именование и стиль смутили.

        • Oleg Tsernetsov

          «… на малых или рэндом аксесс массивах»
          Оговорился — не массивах, конечно, а списках.

          • Давайте будем совсем честными:
            if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
            rotate1((List)list, distance);
            else
            rotate2((List)list, distance);
            первый первый алгоритм быстрее в несколько раз, но для него нужен произвольный доступ,
            второй медленнее (но тоже линейный), зато работает и на связных списках (ну, ещё, второй выглядит проще на первый взгляд).

            • Oleg Tsernetsov

              Будем честными? значит что-то все-таки было не совсем честно :)?

              Оба алгоритма работают на любых списках. То, что первый быстрее второго в несколько раз — утверждение неверное, поскольку все зависит от сложности доступа к элементу в списке. В случае константного доступа — это так, но например если доступ к элементу в списке линейный — то второй алгоритм будет быстрее.

              На списках с быстрым доступом к элементу ИЛИ прочих коротких списках лучше перформит первый алгоритм.
              Для остальных случаев выбирается второй, который покрывает длинные списки с медленным доступом.

              • >То, что первый быстрее второго в несколько раз – утверждение неверное, поскольку все зависит от сложности >доступа к элементу в списке.

                Именно по этому перед вызовом первого алгоритма и проверятеся что:
                list instanceof RandomAccess

    • Oleg Tsernetsov

      Кагбе даже в 2 можно уложить
      http://pastebin.com/myr6n0t5

  3. Oleg Tsernetsov

    Тест и вывод соответственно.
    http://pastebin.com/kfma3bPr

  4. Ruby здесь вне конкуренции 🙂 в 1.9.2 есть метод Array.rotate(n=1)
    A если версия более ранняя, то банально
    def rotate(n=1)
    (n%self.size).times{ push shift }; self
    end

  5. 15 строчек жоской императивщины на Clojure http://pastebin.com/LrBharR0

    • 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 сек

  6. Sergei Kirjanov

    почти то же, что выше но на перл-е:

    http://pastebin.com/LWA26tmT

    sub moveNElementsToTheEndInPlace{
    my($l,$n)=@_;
    @$l = @$l[$n..$#$l,0..$n-1];
    $l
    }

    Насколько я понимаю интерпретатор, это (в случае перл-а) временные массивы не делает,
    поскольку слайс не создает массива, а кладет кучу значений на стек

  7. Kirill Linnik

    пффф…. чего-то только не придумают умельцы… PHP решит все ваши проблемы в пару строчек 😛

    http://codepad.org/aK1kDDqR
    or
    http://pastebin.com/cz7x7nNz

  8. Andrei Poryvkin

    Использование array_push() для добавления одного элемента не самый лучший выбор, так как это намного медленнее, чем $array[] = $val

    • Andrei Poryvkin

      Это был комментарий к решению Dumka, так что можно удалить 14. ветку

  9. Решил выложить и свое решение. Решение оказалось настолько простым, что даже как-то стыдно выкладывать на 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)

  10. v Google na interview tozhe sprashivajut pro String Rotation http://habrahabr.ru/blogs/google/102482/#habracut 🙂

Добавить комментарий для m-a-m-o-n.livejournal.com/ Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *

*

Работает на WordPress & Автор темы: Anders Norén