Obróć elementy w tablicy w JavaScript


86

Zastanawiałem się, jaki jest najbardziej efektywny sposób na obrócenie tablicy JavaScript.

Wymyśliłem takie rozwiązanie, w którym dodatnia nobraca tablicę w prawo, a ujemna nw lewo ( -length < n < length):

Array.prototype.rotateRight = function( n ) {
  this.unshift( this.splice( n, this.length ) );
}

Które można następnie wykorzystać w ten sposób:

var months = ["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"];
months.rotate( new Date().getMonth() );

Moja oryginalna wersja powyżej ma wadę, jak wskazał Christoph w komentarzach poniżej, poprawna wersja to (dodatkowy zwrot pozwala na łańcuch):

Array.prototype.rotateRight = function( n ) {
  this.unshift.apply( this, this.splice( n, this.length ) );
  return this;
}

Czy istnieje bardziej kompaktowe i / lub szybsze rozwiązanie, prawdopodobnie w kontekście frameworka JavaScript? (żadna z przedstawionych poniżej propozycji nie jest ani bardziej zwarta, ani szybsza)

Czy istnieje framework JavaScript z wbudowaną funkcją obracania tablicy? (Nadal nikt nie odpowiedział)


1
Nie rozumiem, co powinien zrobić twój przykład. Dlaczego po prostu nie użyjesz months[new Date().getMonth()]nazwy bieżącego miesiąca?
Gumbo

1
@Jean: kod jest zepsuty: sposób, w jaki to robisz, cofnie splatane elementy jako tablicę, a nie pojedynczo; będziesz musiał użyć, apply()aby Twoja implementacja działała
Christoph,

Dziś rotacja zmieniłaby miesiące, aby pokazać tę listę (z Decna pierwszej pozycji):["Dec", "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov"]
Jean Vincent

@ Christoph, masz rację, to nie działałoby jako ogólna funkcja obracania. Działa tylko wtedy, gdy zostanie użyty do konwersji na ciąg zaraz po.
Jean Vincent

@Jean: możesz naprawić swoją wersję przez Array.prototype.unshift.apply(this, this.splice(...))- moja wersja robi to samo, ale używa push()zamiastunshift()
Christoph

Odpowiedzi:


60

Bezpieczna dla typu, ogólna wersja, która modyfikuje tablicę:

Array.prototype.rotate = (function() {
    // save references to array functions to make lookup faster
    var push = Array.prototype.push,
        splice = Array.prototype.splice;

    return function(count) {
        var len = this.length >>> 0, // convert to uint
            count = count >> 0; // convert to int

        // convert count to value in range [0, len)
        count = ((count % len) + len) % len;

        // use splice.call() instead of this.splice() to make function generic
        push.apply(this, splice.call(this, 0, count));
        return this;
    };
})();

W komentarzach Jean poruszył problem, że kod nie obsługuje przeciążania push()i splice(). Nie sądzę, żeby to było naprawdę przydatne (patrz komentarze), ale szybkim rozwiązaniem (chociaż trochę hack) byłoby zastąpienie linii

push.apply(this, splice.call(this, 0, count));

z tym:

(this.push || push).apply(this, (this.splice || splice).call(this, 0, count));

Używanie unshift()zamiast tego push()jest prawie dwa razy szybsze w Operze 10, podczas gdy różnice w FF były nieistotne; kod:

Array.prototype.rotate = (function() {
    var unshift = Array.prototype.unshift,
        splice = Array.prototype.splice;

    return function(count) {
        var len = this.length >>> 0,
            count = count >> 0;

        unshift.apply(this, splice.call(this, count % len, len));
        return this;
    };
})();

2
Niezłe buforowanie Array.prototypemetod! +1
James

Bardzo ładna, kuloodporna implementacja, ale generalnie wolałbym polegać na wyjątkach lub po prostu na zwykłych złych odpowiedziach w przypadku złego użycia. Ma to na celu zachowanie czystości i szybkości kodu. Obowiązkiem użytkownika jest przekazanie prawidłowych parametrów lub poniesienie konsekwencji. Nie podoba mi się kara dla dobrych użytkowników. Poza tym jest to doskonałe, ponieważ modyfikuje Array zgodnie z żądaniem i nie cierpi z powodu wady mojej implementacji, która spowodowała cofnięcie przesunięcia tablicy zamiast poszczególnych elementów, jak zauważyłeś. Zwracanie tego również lepiej jest pozwolić na tworzenie łańcucha. Więc dziękuję.
Jean Vincent

Jaki jest koszt zamknięcia tutaj, tylko po to, aby buforować wypychanie i łączenie?
Jean Vincent

@Jean: cóż, domknięcia obejmują cały łańcuch zasięgu; tak długo, jak zewnętrzna funkcja znajduje się na najwyższym poziomie, wpływ powinien być pomijalny i tak czy inaczej wynosi O (1), podczas gdy wyszukiwanie metod Array to O (n) w liczbie wywołań; optymalizacja implementacji może wbudować wyszukiwanie, więc nie będzie żadnego zysku, ale z dość głupimi interpreterami, z którymi mieliśmy do czynienia przez długi czas, buforowanie zmiennych w niższym zakresie może mieć znaczący wpływ
Christoph

1
Nie spowoduje to rotacji dużych tablic. Sprawdziłem dzisiaj i może obsłużyć tylko tablicę o długości 250891 elementów. Najwyraźniej liczba argumentów, które można przekazać za pomocą applymetody, jest ograniczona przez pewien rozmiar stosu wywołań. W terminologii ES6 operator spreadu również cierpiałby na ten sam problem z rozmiarem stosu. Poniżej podaję mapę metody robienia tego samego. Jest wolniejszy, ale działa w przypadku milionów elementów. Możesz także zaimplementować mapę z prostą pętlą for lub while i będzie to znacznie szybsze.
Redu

144

Można użyć push(), pop(), shift()i unshift()metody:

function arrayRotate(arr, reverse) {
  if (reverse) arr.unshift(arr.pop());
  else arr.push(arr.shift());
  return arr;
}

stosowanie:

arrayRotate(['h','e','l','l','o']);       // ['e','l','l','o','h'];
arrayRotate(['h','e','l','l','o'], true); // ['o','h','e','l','l'];

Jeśli potrzebujesz countargumentu, zobacz moją drugą odpowiedź: https://stackoverflow.com/a/33451102 🖤🧡💚💙💜


Nie ma liczby, chociaż nie jest to wielka sprawa w zależności od zastosowania.
JustGage

@JustGage, publikuję kolejną odpowiedź ze wsparciem licznika stackoverflow.com/questions/1985260/ ...
Yukulélé

2
Uwaga: uważaj, ta metoda jest uciążliwa i będzie manipulować tablicą wysłaną jako parametr. Nie jest trudno rozwiązać powielanie tablicy przed jej wysłaniem
fguillen

Oto wersja w maszynopisie z lewą prawą zmienną stackblitz.com/edit/typescript-vtcmhp
Dživo Jelić

38

Prawdopodobnie zrobiłbym coś takiego:

Array.prototype.rotate = function(n) {
    return this.slice(n, this.length).concat(this.slice(0, n));
}

Edycja     Oto wersja mutatora:

Array.prototype.rotate = function(n) {
    while (this.length && n < 0) n += this.length;
    this.push.apply(this, this.splice(0, n));
    return this;
}

pamiętaj, że ta funkcja zachowuje oryginalną tablicę niezmienioną
Christoph,

Musi zmodyfikować oryginalny Array (this), tak jak robią to push, pop, shift, unshift, concat i splice. Poza tym jest to ważne.
Jean Vincent

@Gumbo, dlaczego pętla while? Nie musimy robić n dodatnim, połączenie działa również z wartościami ujemnymi. Na koniec jest to poprawne, ale prawie wersja Christopha, która najpierw zrobiła to dobrze, bez zastrzeżenia przeciążenia.
Jean Vincent

@Gumbo, poprawka do mojego poprzedniego komentarza, liczby ujemne działają tylko w wersji splotu (n. This.length). Używanie splice (0, n), tak jak w twojej wersji, wymaga dodatniego int.
Jean Vincent

1
Dodałem n = n % this.lengthprzed instrukcją return, aby obsługiwać liczby ujemne i / lub spoza zakresu.
iedmrc

25

Ta funkcja działa w obie strony i działa z dowolną liczbą (nawet z liczbą większą niż długość tablicy):

function arrayRotate(arr, count) {
  count -= arr.length * Math.floor(count / arr.length);
  arr.push.apply(arr, arr.splice(0, count));
  return arr;
}

stosowanie:

for(let i = -6 ; i <= 6 ; i++) {
  console.log(arrayRotate(["🧡","💚","💙","💜","🖤"], i), i);
}

wynik:

[ "🖤", "🧡", "💚", "💙", "💜" ]    -6
[ "🧡", "💚", "💙", "💜", "🖤" ]    -5
[ "💚", "💙", "💜", "🖤", "🧡" ]    -4
[ "💙", "💜", "🖤", "🧡", "💚" ]    -3
[ "💜", "🖤", "🧡", "💚", "💙" ]    -2
[ "🖤", "🧡", "💚", "💙", "💜" ]    -1
[ "🧡", "💚", "💙", "💜", "🖤" ]    0
[ "💚", "💙", "💜", "🖤", "🧡" ]    1
[ "💙", "💜", "🖤", "🧡", "💚" ]    2
[ "💜", "🖤", "🧡", "💚", "💙" ]    3
[ "🖤", "🧡", "💚", "💙", "💜" ]    4
[ "🧡", "💚", "💙", "💜", "🖤" ]    5
[ "💚", "💙", "💜", "🖤", "🧡" ]    6

Korzystając z tej funkcji napotkałem problem, ponieważ zmienia ona oryginalną tablicę. Znalazłem kilka obejść tutaj: stackoverflow.com/questions/14491405
ognockocaten

1
@ognockocaten To nie jest problem, tak działa ta funkcja. jeśli chcesz zachować niezmienioną oryginalną tablicę, var arr2 = arrayRotate(arr.slice(0), 5)
sklonuj

To naprawdę świetna odpowiedź i pomogła mi. Jednak najlepsze byłoby zapewnienie alternatywy, która nie powoduje mutacji oryginalnej tablicy. Jasne, że łatwo jest po prostu utworzyć kopię oryginału, nie jest to najlepsza praktyka, ponieważ niepotrzebnie wykorzystuje pamięć.
Hybrydowy programista internetowy

@Hybridwebdev useconst immutatableArrayRotate = (arr, count) => ArrayRotate(arr.clone(), count)
Yukulélé

8

Tak wiele z tych odpowiedzi wydaje się zbyt skomplikowanych i trudnych do odczytania. Chyba nie widziałem nikogo używającego splice z concat ...

function rotateCalendar(){
    var cal=["Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"],
    cal=cal.concat(cal.splice(0,new Date().getMonth()));
    console.log(cal);  // return cal;
}

console.log output (* wygenerowane w maju):

["May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec", "Jan", "Feb", "Mar", "Apr"]

Jeśli chodzi o zwartość, mogę zaoferować kilka ogólnych funkcji jednowierszowych (nie licząc części console.log | return). Po prostu podaj tablicę i wartość docelową w argumentach.

Łączę te funkcje w jedną dla programu do gry w karty dla czterech graczy, w którym macierz to ['N', 'E', 'S', 'W']. Zostawiłem je osobno na wypadek, gdyby ktoś chciał skopiować / wkleić do swoich potrzeb. Dla moich celów korzystam z funkcji, szukając, kto będzie następny grać / działać w różnych fazach gry (Pinochle). Nie przejmowałem się testowaniem szybkości, więc jeśli ktoś inny chce, daj mi znać o wynikach.

* uwaga, jedyną różnicą między funkcjami jest „+1”.

function rotateToFirst(arr,val){  // val is Trump Declarer's seat, first to play
    arr=arr.concat(arr.splice(0,arr.indexOf(val)));
    console.log(arr); // return arr;
}
function rotateToLast(arr,val){  // val is Dealer's seat, last to bid
    arr=arr.concat(arr.splice(0,arr.indexOf(val)+1));
    console.log(arr); // return arr;
}

funkcja kombinacji ...

function rotateArray(arr,val,pos){
    // set pos to 0 if moving val to first position, or 1 for last position
    arr=arr.concat(arr.splice(0,arr.indexOf(val)+pos));
    return arr;
}
var adjustedArray=rotateArray(['N','E','S','W'],'S',1);

AdjustArray =

W,N,E,S

1
Niezła odpowiedź. Czy to było sprzed przejścia na ciemną stronę (PHP)?
Nick

... Urodziłem się po ciemnej stronie.
mickmackusa

:) btw użyłem go tutaj
Nick

6

Używanie spreadu ES6 jako niezmiennego przykładu ...

[...array.slice(1, array.length), array[0]]

i

[array[array.items.length -1], ...array.slice(0, array.length -1)]

Prawdopodobnie nie jest to najbardziej wydajne, ale jest zwięzłe.


5

Proste rozwiązanie z plastrami i destrukturyzacją:

const rotate = (arr, count = 1) => {
  return [...arr.slice(count, arr.length), ...arr.slice(0, count)];
};

const arr = [1,2,3,4,5];

console.log(rotate(arr, 1));  // [2, 3, 4, 5, 1]
console.log(rotate(arr, 2));  // [3, 4, 5, 1, 2]
console.log(rotate(arr, -2)); // [4, 5, 1, 2, 3]
console.log(rotate(arr, -1)); // [5, 1, 2, 3, 4]


2
To jest naprawdę fajne! Możesz uniknąć konieczności sprawdzania count === 0, ustawiając wartość domyślną. To pozwoliłoby ci uczynić to jednym liniowcem:const rotate = (arr, n = 1) => [...arr.slice(n, arr.length), ...arr.slice(0, n)];
Nick F

@NickF miło, dziękuję! Nie myślałem w ten sposób.
kashesandr

4

Oto bardzo prosty sposób na przesuwanie elementów w tablicy:

function rotate(array, stepsToShift) {

    for (var i = 0; i < stepsToShift; i++) {
        array.unshift(array.pop());
    }

    return array;
}

3

@ Christoph, zrobiłeś czysty kod, ale 60% wolniej niż ten, który znalazłem. Spójrz na wynik w jsPerf: http://jsperf.com/js-rotate-array/2 [Edytuj] OK, teraz jest więcej przeglądarek i te nieoczywiste metody czarownic są najlepsze

var rotateArray = function(a, inc) {
    for (var l = a.length, inc = (Math.abs(inc) >= l && (inc %= l), inc < 0 && (inc += l), inc), i, x; inc; inc = (Math.ceil(l / inc) - 1) * inc - l + (l = inc))
    for (i = l; i > inc; x = a[--i], a[i] = a[i - inc], a[i - inc] = x);
    return a;
};

var array = ['a','b','c','d','e','f','g','h','i'];

console.log(array);
console.log(rotateArray(array.slice(), -1)); // Clone array with slice() to keep original

@molokocolo Intuicyjnie, Twoje rozwiązanie działałoby wolniej, ponieważ przyrost byłby wyższy, ponieważ używasz pętli. Zaktualizowałem Twój przypadek testowy z przyrostem o 5 i wydaje się, że działa wolniej: jsperf.com/js-rotate-array/3
Jean Vincent

Nie rozumiem, co robi funkcja rotateArray () ^^ tylko, że działa :) (to dziwny kod!) Chrome zachowuje się prawie odwrotnie niż Firefox ...
molokoloco

Ta metoda jest bardzo interesująca, działa poprzez zamianę odwołań do elementów w tablicy. Rozmiar tablicy nigdy się nie zmienia, dlatego jest bardzo szybki z wadą używania pętli. Interesującą rzeczą, którą pokazuje, jest to, że Firefox najszybciej radzi sobie z pętlami, podczas gdy chrome jest najszybszy w manipulowaniu tablicami.
Jean Vincent

1
Po przeanalizowaniu kodu znalazłem słabość, która pokazuje, że to rozwiązanie jest szybsze tylko dla mniejszych tablic i określonych liczników rotacji: jsperf.com/js-rotate-array/5 Spośród wszystkich przeglądarek najszybszy pozostaje Google Chrome ze złączem / unshift rozwiązanie. Oznacza to, że jest to naprawdę kwestia optymalizacji metody Array, którą Chrome robi lepiej niż inne przeglądarki.
Jean Vincent

3

zobacz http://jsperf.com/js-rotate-array/8

function reverse(a, from, to) {
  --from;
  while (++from < --to) {
    var tmp = a[from];
    a[from] = a[to];
    a[to] = tmp;
  }
}

function rotate(a, from, to, k) {
  var n = to - from;
  k = (k % n + n) % n;
  if (k > 0) {
    reverse(a, from, from + k);
    reverse(a, from + k, to);
    reverse(a, from, to);
  }
}

3

Kiedy nie mogłem znaleźć gotowego fragmentu, aby rozpocząć listę dni od `` dzisiaj '', zrobiłem to w ten sposób (niezupełnie ogólny, prawdopodobnie znacznie mniej wyrafinowany niż powyższe przykłady, ale wykonałem zadanie):

//returns 7 day names with today first
function startday() {
    const days = ['Sun','Mon','Tue','Wed','Thu','Fri','Sat'];
    let today = new Date();
    let start = today.getDay(); //gets day number
    if (start == 0) { //if Sunday, days are in order
        return days
    }
    else { //if not Sunday, start days with today
        return days.slice(start).concat(days.slice(0,start))
    }
}

Dzięki drobnemu refaktorowi dokonanemu przez lepszego programistę niż ja jest to o linię lub dwie krótsze niż moja początkowa próba, ale wszelkie dalsze komentarze na temat wydajności są mile widziane.


3
function rotate(arr, k) {
for (var i = 0; i < k+1; i++) {
    arr.push(arr.shift());
}
return arr;
}
//k work as an index array
console.log(rotate([1, 2, 7, 4, 5, 6, 7], 3)); //[5,6,7,1,2,7,4]
console.log(rotate([-1, -100, 3, 99], 2));     //[99,-1,-100,3]

3
// Example of array to rotate
let arr = ['E', 'l', 'e', 'p', 'h', 'a', 'n', 't'];

// Getting array length
let length = arr.length;

// rotation < 0 (move left), rotation > 0 (move right)
let rotation = 5;

// Slicing array in two parts
let first  = arr.slice(   (length - rotation) % length, length); //['p', 'h', 'a' ,'n', 't']
let second = arr.slice(0, (length - rotation) % length); //['E', 'l', 'e']

// Rotated element
let rotated = [...first, ...second]; // ['p', 'h', 'a' ,'n', 't', 'E', 'l', 'e']

W jednej linii kodu:

let rotated = [...arr.slice((length - rotation) % length, length), ...arr.slice(0, (length - rotation) % length)];

2

Zaakceptowana odpowiedź ma wadę polegającą na tym, że nie jest w stanie obsłużyć tablic większych niż rozmiar stosu wywołań, który zależy od sesji, ale powinien wynosić około 100 ~ 300K elementów. Na przykład w bieżącej sesji przeglądarki Chrome, którą wypróbowałem, było to 250891. W wielu przypadkach możesz nawet nie wiedzieć, do jakiego rozmiaru może dynamicznie wzrosnąć tablica. Więc to jest poważny problem.

Aby przezwyciężyć to ograniczenie, wydaje mi się, że jedną z interesujących metod jest wykorzystanie Array.prototype.map()i odwzorowanie elementów poprzez zmianę układu indeksów w sposób okrężny. Ta metoda przyjmuje jeden argument będący liczbą całkowitą. Jeśli argument ten jest dodatni, to będzie się obracał po rosnących indeksach, a jeśli ujemny po kierunku spadków. Ma to tylko złożoność czasową O (n) i zwróci nową tablicę bez mutowania tej, do której została wywołana, podczas obsługi milionów elementów bez żadnego problemu. Zobaczmy, jak to działa;

Array.prototype.rotate = function(n) {
var len = this.length;
return !(n % len) ? this
                  : n > 0 ? this.map((e,i,a) => a[(i + n) % len])
                          : this.map((e,i,a) => a[(len - (len - i - n) % len) % len]);
};
var a = [1,2,3,4,5,6,7,8,9],
    b = a.rotate(2);
console.log(JSON.stringify(b));
    b = a.rotate(-1);
console.log(JSON.stringify(b));

Właściwie po tym, jak zostałem skrytykowany w dwóch następujących kwestiach;

  1. Nie ma potrzeby stosowania warunku dla dodatniego lub ujemnego sygnału wejściowego, ponieważ ujawnia on naruszenie DRY. Możesz to zrobić z jedną mapą, ponieważ każde ujemne n ma dodatni odpowiednik (Całkowicie dobrze ...)
  2. Funkcja Array powinna albo zmienić bieżącą tablicę, albo utworzyć nową. Twoja funkcja może to zrobić w zależności od tego, czy przesunięcie jest konieczne, czy nie (Całkowicie w prawo ..)

Zdecydowałem się zmodyfikować kod w następujący sposób;

Array.prototype.rotate = function(n) {
var len = this.length;
return !(n % len) ? this.slice()
                  : this.map((e,i,a) => a[(i + (len + n % len)) % len]);
};
var a = [1,2,3,4,5,6,7,8,9],
    b = a.rotate(10);
console.log(JSON.stringify(b));
    b = a.rotate(-10);
console.log(JSON.stringify(b));

Potem znowu; oczywiście funktory JS Array.prototype.map()są powolne w porównaniu z ich odpowiednikami zakodowanymi w zwykłym JS. Aby uzyskać więcej niż 100% wzrost wydajności, prawdopodobnie będę musiał wybrać, Array.prototype.rotate()czy kiedykolwiek będę musiał obrócić tablicę w kodzie produkcyjnym, takim jak ten, którego użyłem podczas mojej próbyString.prototype.diff()

Array.prototype.rotate = function(n){
  var len = this.length,
      res = new Array(this.length);
  if (n % len === 0) return this.slice();
  else for (var i = 0; i < len; i++) res[i] = this[(i + (len + n % len)) % len];
  return res;
};

shift () i splice (), tak wolne, jak mogą być, są w rzeczywistości szybsze niż użycie map () lub dowolnej metody używającej parametru funkcji. shift () i splice (), które są bardziej deklaratywne, są również łatwiejsze do optymalizacji w dłuższej perspektywie.
Jean Vincent,

@Jean Vincent Tak, masz rację ... mapa faktycznie może okazać się wolniejsza, ale uważam, że idealna logika rotacji jest taka. Po prostu starałem się pokazać logiczne podejście. Mapę można łatwo uprościć w dół za pomocą pętli for, co spowodowałoby znaczną poprawę szybkości ... Jednak prawda jest taka, że ​​przyjęta odpowiedź ma podejście opracowane z myślą o kilku innych językach. Nie jest to idealne rozwiązanie dla JS ... nie będzie działać nawet, gdy rozmiar tablicy jest większy niż rozmiar stosu wywołań. (w moim przypadku i w tej sesji okazało się, że jest ona ograniczona tylko do 250891 pozycji) Więc to jest to ..!
Redu

Masz rację co do rozmiaru stosu wywołań, który może przekroczyć, jest to bardziej ważny argument niż szybkość, rozważ edycję swojej odpowiedzi, aby podkreślić ten punkt za pomocą ulepszonego wcięcia.
Jean Vincent

2

Ta funkcja jest trochę szybsza niż akceptowana odpowiedź dla małych tablic, ale DUŻO szybsza dla dużych tablic. Ta funkcja pozwala również na dowolną liczbę obrotów większą niż długość tablicy, co jest ograniczeniem oryginalnej funkcji.

Wreszcie zaakceptowana odpowiedź obraca się w przeciwnym kierunku, jak opisano.

const rotateForEach = (a, n) => {
    const l = a.length;
    a.slice(0, -n % l).forEach(item => a.push( item ));
    return a.splice(n % l > 0 ? (-n % l) : l + (-n % l));
}

I funkcjonalny odpowiednik (który wydaje się mieć również pewne korzyści w zakresie wydajności):

const rotateReduce = (arr, n) => {
    const l = arr.length;
    return arr.slice(0, -n % l).reduce((a,b) => {
        a.push( b );
        return a;
    }, arr).splice(n % l> 0 ? l + (-n % l) : -n % l);
};

Możesz sprawdzić podział wydajności tutaj.


Niestety to nie działa, zmniejsza tablicę do rozmiaru zero, co wyjaśnia, dlaczego jest o wiele szybsza po pierwszym uruchomieniu niż jakakolwiek inna poprawna implementacja, szczególnie na większych tablicach. Jeśli w teście porównawczym zamienisz kolejność testów i wyświetlisz na końcu długość, zobaczysz problem.
Jean Vincent

2

EDYTOWAĆ:: Hej, więc okazuje się, że dzieje się zbyt wiele iteracji. Żadnych pętli, żadnych rozgałęzień.

Nadal działa z ujemnym n dla obrotu w prawo i dodatnim n dla obrotu w lewo dla dowolnego rozmiaru n, bez mutacji

function rotate(A,n,l=A.length) {
  const offset = (((n % l) + l) %l)
  return A.slice(offset).concat(A.slice(0,offset))
}

Oto wersja kodu golfowego dla chichotów

const r = (A,n,l=A.length,i=((n%l)+l)%l)=>A.slice(i).concat(A.slice(0,i))

EDIT1 :: * Bezgałęziowa, bez mutacji implementacja.

Więc hej, okazuje się, że miałem gałąź, w której jej nie potrzebowałem. Oto działające rozwiązanie. ujemna liczba = prawy obrót o | num | dodatnia liczba = lewo obrót o num

function r(A,n,l=A.length) {
  return A.map((x,i,a) => A[(((n+i)%l) + l) % l])
}

Równanie ((n%l) + l) % l odwzorowuje dokładnie dodatnie i ujemne liczby dowolnie dużych wartości n

ORYGINAŁ

Obróć w lewo iw prawo. Obróć w lewo z dodatnim n, obróć w prawo z ujemnymn .

Działa w przypadku nieprzyzwoicie dużych danych wejściowych n .

Brak trybu mutacji. Za dużo mutacji w tych odpowiedziach.

Ponadto mniej operacji niż większość odpowiedzi. Bez popu, bez pchania, bez łączenia, bez przesunięcia.

const rotate = (A, num ) => {
   return A.map((x,i,a) => {
      const n = num + i
      return n < 0 
        ? A[(((n % A.length) + A.length) % A.length)]
        : n < A.length 
        ? A[n] 
        : A[n % A.length]
   })
}

lub

 const rotate = (A, num) => A.map((x,i,a, n = num + i) => 
  n < 0
    ? A[(((n % A.length) + A.length) % A.length)]
    : n < A.length 
    ? A[n] 
    : A[n % A.length])

//test
rotate([...Array(5000).keys()],4101)   //left rotation
rotate([...Array(5000).keys()],-4101000)  //right rotation, num is negative

// will print the first index of the array having been rotated by -i
// demonstrating that the rotation works as intended
[...Array(5000).keys()].forEach((x,i,a) => {
   console.log(rotate(a,-i)[0])
}) 
// prints even numbers twice by rotating the array by i * 2 and getting the first value
//demonstrates the propper mapping of positive number rotation when out of range
[...Array(5000).keys()].forEach((x,i,a) => {
   console.log(rotate(a,i*2)[0])
})

Wyjaśnienie:

odwzorowuj każdy indeks A na wartość przy przesunięciu indeksu. W tym przypadku

offset = num

jeśli offset < 0wtedyoffset + index + positive length of A wskaże odwrotne przesunięcie.

Jeśli offset > 0 and offset < length of A następnie po prostu zamapuj bieżący indeks na indeks przesunięcia A.

W przeciwnym razie zamodulo przesunięcie i długość, aby odwzorować przesunięcie w granicach tablicy.

Weźmy na przykład offset = 4i offset = -4.

Kiedy offset = -4i A = [1,2,3,4,5]dla każdego wskaźnika, offset + indexwielkość (lub Math.abs(offset)) będzie mniejsza.

Wyjaśnijmy najpierw obliczenie indeksu ujemnego n. A[(((n % A.length) + A.length) % A.length)+0]i był onieśmielony. Nie bądź. Rozpracowanie tego zajęło mi 3 minuty w replice.

  1. Wiemy, że njest negatywny, ponieważ tak jest n < 0. Jeśli liczba jest większa niż zakres Array, n % A.lengthzamapuje ją na zakres.
  2. n + A.lengthdodaj tę liczbę do A.lengthprzesunięcia n do prawidłowej kwoty.
  3. Wiemy, że njest negatywny, ponieważ tak jest n < 0. n + A.lengthdodaj tę liczbę do A.lengthprzesunięcia n do prawidłowej kwoty.
  4. Następnie odwzoruj go na zakres długości A za pomocą modulo. Drugi moduł jest niezbędny do odwzorowania wyniku obliczenia na indeksowalny zakres

    wprowadź opis obrazu tutaj

  5. Pierwszy indeks: -4 + 0 = -4. A. długość = 5. A. długość - 4 = 1. A 2 to 2. Odwzoruj indeks od 0 do 2.[2,... ]

  6. Następny indeks, -4 + 1 = -3. 5 + -3 = 2. A 2 to 3. Odwzoruj indeks od 1 do 3.[2,3... ]
  7. Itp.

Ten sam proces dotyczy offset = 4. Kiedy offset = -4i A = [1,2,3,4,5]dla każdego indeksu offset + indexzwiększy wielkość.

  1. 4 + 0 = 0. Zamapuj A [0] na wartość w A [4].[5...]
  2. 4 + 1 = 5, 5 jest poza zakresem podczas indeksowania, więc zamapuj A 2 na wartość w pozostałej części 5 / 5, czyli 0. A 2 = wartość w A [0].[5,1...]
  3. powtarzać.

1
Follow a simpler approach of running a loop to n numbers and shifting places upto that element.

function arrayRotateOne(arr, n) {
  for (let i = 0; i < n; i++) {
    arr.unshift(arr.pop());
  }
  return arr;
}
console.log( arrayRotateOne([1,2,3,4,5,6],2));



function arrayRotateOne(arr,n) {
  for(let i=0; i<n;i++){
      arr.push(arr.shift());
      console.log('execute',arr)
    }
     return arr;
 }

console.log (arrayRotateOne ([1,2,3,4,5,6], 2));


1

Rozwiązanie niemutujące

var arr = ['a','b','c','d']
arr.slice(1,arr.length).concat(arr.slice(0,1)

z mutacją

var arr = ['a','b','c','d']
arr = arr.concat(arr.splice(0,1))

1

Dzielę się swoim rozwiązaniem, którego używam do obracania się na karuzeli. Może się zepsuć, gdy rozmiar tablicy jest mniejszy niż displayCount, ale możesz dodać dodatkowy warunek, aby zatrzymać obracanie, gdy jest mały, lub połączyć również razy tablicę główną * displayCount.

function rotate(arr, moveCount, displayCount) {
  const size = arr.length;

  // making sure startIndex is between `-size` and `size`
  let startIndex = moveCount % size;
  if (startIndex < 0) startIndex += size; 

  return [...arr, ...arr].slice(startIndex, startIndex + displayCount);
}

// move 3 to the right and display 4 items
// rotate([1,2,3,4,5], 3, 4) -> [4,5,1,2]

// move 3 to the left and display 4 items
// rotate([1,2,3,4,5], -3, 4) -> [3,4,5,1]

// move 11 to the right and display 4
// rotate([1,2,3,4,5], 3, 4) -> [2,3,4,5]

0

Co powiesz na zwiększenie licznika, a następnie uzyskanie pozostałej części z dzielenia przez długość tablicy, aby uzyskać miejsce, w którym powinieneś być.

var i = 0;
while (true);
{
    var position = i % months.length;
    alert(months[position]);
    ++i;
}

Pomijając składnię języka, powinno to działać dobrze.


2
W żaden sposób nie powoduje to obrócenia tablicy.
Jean Vincent

1
Prawda (jak stwierdzono w odpowiedzi), ale oszczędza konieczności obracania tablicy.
tgandrews

1
Ale celem tego jest obrócenie tablicy, zgodnie z tytułem, aby nie wyświetlać tablicy z określonego przesunięcia. Jeśli użyjesz tej samej pętli do odbudowania nowej tablicy, będzie to znacznie wolniejsze niż inne wersje używające natywnych metod Array. Poza tym zapomniałeś wyrwać się z nieskończonej pętli.
Jean Vincent

0

Jeśli twoja tablica będzie duża i / lub będziesz dużo obracać, możesz rozważyć użycie połączonej listy zamiast tablicy.


Zgoda, ale pytanie dotyczy tablic, a dokładniej rozszerzenia czasowników tablicowych.
Jean Vincent

0

@molokoloco Potrzebowałem funkcji, którą mógłbym skonfigurować, aby obracała się w określonym kierunku - prawda dla przodu i fałsz dla tyłu. Utworzyłem fragment kodu, który przyjmuje kierunek, licznik i tablicę i wyprowadza obiekt z licznikiem zwiększonym w odpowiednim kierunku, a także wartości wcześniejsze, bieżące i następne. NIE modyfikuje oryginalnej tablicy.

Zmierzyłem też to z Twoim fragmentem kodu i chociaż nie jest szybszy, jest szybszy niż te, z którymi porównujesz - o 21% wolniej http://jsperf.com/js-rotate-array/7 .

function directionalRotate(direction, counter, arr) {
  counter = direction ? (counter < arr.length - 1 ? counter + 1 : 0) : (counter > 0 ? counter - 1 : arr.length - 1)
  var currentItem = arr[counter]
  var priorItem = arr[counter - 1] ? arr[counter - 1] : arr[arr.length - 1]
  var nextItem = arr[counter + 1] ? arr[counter + 1] : arr[0]
  return {
    "counter": counter,
    "current": currentItem,
    "prior": priorItem,
    "next": nextItem
  }
}
var direction = true // forward
var counter = 0
var arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'];

directionalRotate(direction, counter, arr)

Nie powoduje to obrócenia Array. Aby odpowiedzieć na to pytanie, musisz zwrócić tablicę, w której pierwszy element znajdował się na liczniku.
Jean Vincent,

0

Spóźniam się, ale mam cegiełkę do dodania do tych dobrych odpowiedzi. Poproszono mnie o zakodowanie takiej funkcji i najpierw:

Array.prototype.rotate = function(n)
{
    for (var i = 0; i < n; i++)
    {
        this.push(this.shift());
    }
    return this;
}

Ale wydawało się, że jest mniej wydajne niż śledzenie, gdy njest duże:

Array.prototype.rotate = function(n)
{
    var l = this.length;// Caching array length before map loop.

    return this.map(function(num, index) {
        return this[(index + n) % l]
    });
}

0

Nie jestem pewien, czy jest to najbardziej efektywny sposób, ale podoba mi się sposób, w jaki czyta, jest wystarczająco szybki do większości dużych zadań, ponieważ przetestowałem go na produkcji ...

function shiftRight(array) {
  return array.map((_element, index) => {
    if (index === 0) {
      return array[array.length - 1]
    } else return array[index - 1]
  })
}

function test() {
  var input = [{
    name: ''
  }, 10, 'left-side'];
  var expected = ['left-side', {
    name: ''
  }, 10]
  var actual = shiftRight(input)

  console.log(expected)
  console.log(actual)

}

test()


0

Natywny, szybki, mały, semantyczny, działa na starych silnikach i można go „curry”.

function rotateArray(offset, array) {
    offset = -(offset % array.length) | 0 // ensure int
    return array.slice(offset).concat(
        array.slice(0, offset)
    )
}

0

** Korzystając z najnowszej wersji JS, możemy go łatwo zbudować **

 Array.prototype.rotateLeft = function (n) {
   this.unshift(...this.splice(-(n), n));
    return this
  }

tutaj porusza się: liczba obrotów , tablica , którą można podać liczbę losową

let a = [1, 2, 3, 4, 5, 6, 7];
let moves = 4;
let output = a.rotateLeft(moves);
console.log("Result:", output)

0

Arrayw JS ma wbudowaną metodę, której można użyć do dość łatwego obracania tablicy i oczywiście te metody są niezmienne z natury.

  • push: Wstawia element na koniec tablicy.
  • pop: Usuwa element z końca tablicy.
  • unshift: Wstawia element na początek tablicy.
  • shift: Usuwa element z początku tablicy.

Poniższe rozwiązanie ( ES6) przyjmuje dwa argumenty, tablicę należy obrócić in, ile razy tablica powinna zostać obrócona.

const rotateArray = (arr, n) => {
  while(arr.length && n--) {
    arr.unshift(arr.pop());
  }
  return arr;
}

rotateArray(['stack', 'overflow', 'is', 'Awesome'], 2) 
// ["is", "Awesome", "stack", "overflow"]

Można go dodać do Array.prototype i używać w całej aplikacji

Array.prototype.rotate = function(n) {
 while(this.length && n--) {
   this.unshift(this.pop());
 }
 return this;
}
[1,2,3,4].rotate(3); //[2, 3, 4, 1]

0

Korzystanie z pętli for. Oto kroki

  1. Przechowuj pierwszy element tablicy jako zmienną tymczasową.
  2. Następnie zamień od lewej do prawej.
  3. Następnie przypisz zmienną tymczasową do ostatniego elementu tablicy.
  4. Powtórz te kroki dla liczby obrotów.

function rotateLeft(arr, rotations) {
    let len = arr.length;
    for(let i=0; i<rotations; i++){ 
        let temp = arr[0];
        for(let i=0; i< len; i++){
            arr[i]=arr[i+1];
        }
        arr[len-1]=temp;
    }
    return arr;
}

let arr = [1,2,3,4,5];

let rotations = 3;
let output = rotateLeft(arr, rotations);
console.log("Result Array => ", output);



-2

Nie jestem pewien co do wydajności, ale zrobiłbym to w ten niemutujący sposób:

	Array.prototype.rotate = function( n ) {
  
		 return this.map( (item, index)=> this[ (this.length + index + n)%this.length ] )
	}


Tak więc pierwsza część Twojej odpowiedzi „Nie jestem pewien co do wydajności” jest jak powiedzenie „Nie wiem, czy to w ogóle odpowiada na Twoje pytanie”. Oryginalne pytanie nie dotyczy „dobrego sposobu obracania tablicy”, a konkretnie dotyczy zwartości i szybkości (odpowiednio pamięci i wydajności czasowej). Pytanie dotyczy wydajności i nie odpowiedziałeś na ten składnik.
richardpringle
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.