Mais rápido algoritmo para o deslocamento círculo N matriz de tamanho para a posição M
-
22-08-2019 - |
Pergunta
O que é o algoritmo mais rápido para círculo deslocando matriz para posições M?
Por exemplo, deslocamento [3 4 5 2 3 1 4]
m = 2 posições deve ser [1 4 3 4 5 2 3]
.
Muito obrigado.
Solução
Se você quiser tempo O (n) e sem o uso de memória extra (desde matriz foi especificado), usar o algoritmo do livro de Jon Bentley, "Programação Pérolas 2nd Edition". Ele troca todos os elementos duas vezes. Não tão rápido como usando listas ligadas, mas usa menos memória e é conceitualmente simples.
shiftArray( theArray, M ):
size = len( theArray )
assert( size > M )
reverseArray( theArray, 0, size - 1 )
reverseArray( theArray, 0, M - 1 )
reverseArray( theArray, M, size - 1 )
reverseArray (umArray, startIndex, endIndex) inverte a ordem dos elementos de startIndex a endIndex, inclusive.
Outras dicas
É apenas uma questão de representação. Manter o índice atual como uma variável inteira e ao atravessar a matriz operador de uso modulo para saber quando envolver em torno. Deslocando-se então mudando apenas o valor do índice corrente, enrolando-o em torno do tamanho da matriz. Este é, naturalmente, O (1).
Por exemplo:
int index = 0;
Array a = new Array[SIZE];
get_next_element() {
index = (index + 1) % SIZE;
return a[index];
}
shift(int how_many) {
index = (index+how_many) % SIZE;
}
Optimal solução
Pergunta pediu mais rápido. Revertendo três vezes é mais simples, mas move-se cada elemento exatamente duas vezes, leva tempo O (N) e O (1) espaço. É possível círculo deslocar uma matriz movendo cada elemento exactamente uma vez também em O (n) e S (1) espaço.
Idea
pode círculo deslocar uma matriz de N=9
comprimento por M=1
com um ciclo:
tmp = arr[0]; arr[0] = arr[1]; ... arr[7] = arr[8]; arr[8] = tmp;
E se N=9
, M=3
podemos turno círculo com três ciclos:
-
tmp = arr[0]; arr[0] = arr[3]; arr[3] = tmp;
-
tmp = arr[1]; arr[1] = arr[4]; arr[4] = tmp;
-
tmp = arr[2]; arr[2] = arr[5]; arr[5] = tmp;
Observe cada elemento é lido uma vez e escrito uma vez.
Diagrama de mudança N=9, M=3
O primeiro ciclo é mostrado em preto com números que indicam a ordem das operações. Os segundo e terceiro ciclos são mostrados a cinzento.
O número de ciclos necessários é a máximo divisor comum (GCD) da N
e M
. Se o GCD é 3, começamos um ciclo em cada um dos {0,1,2}
. Calculando o GCD é rápido com a binário GCD algoritmo .
código Exemplo:
// n is length(arr)
// shift is how many place to cycle shift left
void cycle_shift_left(int arr[], int n, int shift) {
int i, j, k, tmp;
if(n <= 1 || shift == 0) return;
shift = shift % n; // make sure shift isn't >n
int gcd = calc_GCD(n, shift);
for(i = 0; i < gcd; i++) {
// start cycle at i
tmp = arr[i];
for(j = i; 1; j = k) {
k = j+shift;
if(k >= n) k -= n; // wrap around if we go outside array
if(k == i) break; // end of cycle
arr[j] = arr[k];
}
arr[j] = tmp;
}
}
Código em C para qualquer tipo array:
// circle shift an array left (towards index zero)
// - ptr array to shift
// - n number of elements
// - es size of elements in bytes
// - shift number of places to shift left
void array_cycle_left(void *_ptr, size_t n, size_t es, size_t shift)
{
char *ptr = (char*)_ptr;
if(n <= 1 || !shift) return; // cannot mod by zero
shift = shift % n; // shift cannot be greater than n
// Using GCD
size_t i, j, k, gcd = calc_GCD(n, shift);
char tmp[es];
// i is initial starting position
// Copy from k -> j, stop if k == i, since arr[i] already overwritten
for(i = 0; i < gcd; i++) {
memcpy(tmp, ptr+es*i, es); // tmp = arr[i]
for(j = i; 1; j = k) {
k = j+shift;
if(k >= n) k -= n;
if(k == i) break;
memcpy(ptr+es*j, ptr+es*k, es); // arr[j] = arr[k];
}
memcpy(ptr+es*j, tmp, es); // arr[j] = tmp;
}
}
// cycle right shifts away from zero
void array_cycle_right(void *_ptr, size_t n, size_t es, size_t shift)
{
if(!n || !shift) return; // cannot mod by zero
shift = shift % n; // shift cannot be greater than n
// cycle right by `s` is equivalent to cycle left by `n - s`
array_cycle_left(_ptr, n, es, n - shift);
}
// Get Greatest Common Divisor using binary GCD algorithm
// http://en.wikipedia.org/wiki/Binary_GCD_algorithm
unsigned int calc_GCD(unsigned int a, unsigned int b)
{
unsigned int shift, tmp;
if(a == 0) return b;
if(b == 0) return a;
// Find power of two divisor
for(shift = 0; ((a | b) & 1) == 0; shift++) { a >>= 1; b >>= 1; }
// Remove remaining factors of two from a - they are not common
while((a & 1) == 0) a >>= 1;
do
{
// Remove remaining factors of two from b - they are not common
while((b & 1) == 0) b >>= 1;
if(a > b) { tmp = a; a = b; b = tmp; } // swap a,b
b = b - a;
}
while(b != 0);
return a << shift;
}
Editar : Este algoritmo também podem ter um melhor desempenho vs reversão array (quando N
é grande e M
é pequeno), devido à localidade cache, uma vez que estamos em loop sobre a matriz em pequenos passos.
Nota final: se a matriz é pequeno, reverso triplo é simples. Se você tem uma grande variedade, vale a pena a sobrecarga de elaboração da GCD para reduzir o número de movimentos por um fator de 2. Ref: http://www.geeksforgeeks.org/array-rotation/
configurá-lo com ponteiros, e leva quase nenhum tempo. Cada elemento aponta para o seguinte, e o "último" (não há passado, afinal, você disse que era circular) aponta para o primeiro. Um ponteiro para o "start" (primeiro elemento), e talvez um comprimento, e você tem sua matriz. Agora, para fazer o seu turno, você apenas passear com o ponteiro do início ao longo do círculo.
Peça um bom algoritmo, e você começa idéias sensatas. Peça mais rápido, e você começa idéias estranhas!
Esse algoritmo é executado em O (n) tempo e O.
A ideia é traçar cada grupo cíclico no deslocamento (numerados por nextGroup
variável).
var shiftLeft = function(list, m) {
var from = 0;
var val = list[from];
var nextGroup = 1;
for(var i = 0; i < list.length; i++) {
var to = ((from - m) + list.length) % list.length;
if(to == from)
break;
var temp = list[to];
list[to] = val;
from = to;
val = temp;
if(from < nextGroup) {
from = nextGroup++;
val = list[from];
}
}
return list;
}
def shift(nelements, k):
result = []
length = len(nelements)
start = (length - k) % length
for i in range(length):
result.append(nelements[(start + i) % length])
return result
Este código funciona bem mesmo em mudança negativa k
função C arrayShiftRight. Se mudança é negativa a matriz mudanças de função esquerda. Ele é otimizado para uso de memória menor. tempo de execução é O (n).
void arrayShiftRight(int array[], int size, int shift) {
int len;
//cut extra shift
shift %= size;
//if shift is less then 0 - redirect shifting left
if ( shift < 0 ) {
shift += size;
}
len = size - shift;
//choosing the algorithm which needs less memory
if ( shift < len ) {
//creating temporary array
int tmpArray[shift];
//filling tmp array
for ( int i = 0, j = len; i < shift; i++, j++ ) {
tmpArray[i] = array[j];
}
//shifting array
for ( int i = size - 1, j = i - shift; j >= 0; i--, j-- ) {
array[i] = array[j];
}
//inserting lost values from tmp array
for ( int i = 0; i < shift; i++ ) {
array[i] = tmpArray[i];
}
} else {
//creating temporary array
int tmpArray[len];
//filling tmp array
for ( int i = 0; i < len; i++ ) {
tmpArray[i] = array[i];
}
//shifting array
for ( int i = 0, j = len; j < size; i++, j++ ) {
array[i] = array[j];
}
//inserting lost values from tmp array
for ( int i = shift, j = 0; i < size; i++, j++ ) {
array[i] = tmpArray[j];
}
}
}
Uma solução muito simples. Esta é uma maneira muito rápida, aqui eu usar uma matriz temporária com o mesmo tamanho ou original e anexar a variável original no final. Este uso do método S (n) a complexidade temporal e O (n) a complexidade e espaço que é muito simples de implementar.
int[] a = {1,2,3,4,5,6};
int k = 2;
int[] queries = {2,3};
int[] temp = new int[a.length];
for (int i = 0; i<a.length; i++)
temp[(i+k)%a.length] = a[i];
a = temp;
Dependendo da estrutura de dados que você usa, você pode fazê-lo em O (1). Eu acho que a maneira mais rápida é manter a matriz na forma de uma lista ligada, e ter uma tabela hash que pode traduzir entre "index" na matriz de "ponteiro" para a entrada. Desta forma, você pode encontrar as cabeças e caudas relevantes em O (1), e fazer a reconexão em O (1) (e atualizar a tabela hash após a mudança em O (1)). Isto, obviamente, seria uma solução muito "confuso", mas se tudo que você está em interessado é a velocidade da mudança, que vai fazer (em detrimento de um maior inserção e pesquisa na matriz, mas ainda permanecerá O ( 1))
Se você tem os dados em uma matriz pura, eu não acho que você pode evitar O (n).
Codificação-wise, ele depende o idioma que você está usando.
Em Python por exemplo, você poderia "fatia"-la (assumem n é o tamanho shift):
result = original[-n:]+original[:-n]
(Eu sei que pesquisa de hash é, em teoria, não O (1), mas nós estamos aqui prático e não teórico, pelo menos eu espero que sim ...)
Isso deve funcionar a deslocar uma arry circularmente: Entrada: {1, 2, 3, 5, 6, 7, 8}; valor de saída presente na matriz após os forloops: {8,7,1,2,3,5,6,8,7}
class Program
{
static void Main(string[] args)
{
int[] array = { 1, 2, 3, 5, 6, 7, 8 };
int index = 2;
int[] tempArray = new int[array.Length];
array.CopyTo(tempArray, 0);
for (int i = 0; i < array.Length - index; i++)
{
array[index + i] = tempArray[i];
}
for (int i = 0; i < index; i++)
{
array[i] = tempArray[array.Length -1 - i];
}
}
}
que foi extraído de minha resposta a outra pergunta. Como girar uma matriz?
#include <iostream>
#include <vector>
// same logic with STL implementation, but simpler, since no return value needed.
template <typename Iterator>
void rotate_by_gcd_like_swap(Iterator first, Iterator mid, Iterator last) {
if (first == mid) return;
Iterator old = mid;
for (; mid != last;) {
std::iter_swap(first, mid);
++first, ++mid;
if (first == old) old = mid; // left half exhausted
else if (mid == last) mid = old;
}
}
int main() {
using std::cout;
std::vector<int> v {0,1,2,3,4,5,6,7,8,9};
cout << "before rotate: ";
for (auto x: v) cout << x << ' '; cout << '\n';
int k = 7;
rotate_by_gcd_like_swap(v.begin(), v.begin() + k, v.end());
cout << " after rotate: ";
for (auto x: v) cout << x << ' '; cout << '\n';
cout << "sz = " << v.size() << ", k = " << k << '\n';
}
Mantenha dois índices para a matriz, um índice começa do começo da matriz para o final do array. Outro índice começa a partir da posição do último Mth e circula através dos últimos elementos M qualquer número de vezes. Toma O (n) em todas as vezes. Não há espaço extra necessária.
circleArray(Elements,M){
int size=size-of(Elements);
//first index
int i1=0;
assert(size>M)
//second index starting from mth position from the last
int i2=size-M;
//until first index reaches the end
while(i1<size-1){
//swap the elements of the array pointed by both indexes
swap(i1,i2,Elements);
//increment first pointer by 1
i1++;
//increment second pointer. if it goes out of array, come back to
//mth position from the last
if(++i2==size) i2=size-M;
}
}
Veja este se você estiver interessado em uma implementação Java:
Pérolas Programação: Circular esquerda / Shift direita Operação
static int [] shift(int arr[], int index, int k, int rem)
{
if(k <= 0 || arr == null || arr.length == 0 || rem == 0 || index >= arr.length)
{
return arr;
}
int temp = arr[index];
arr = shift(arr, (index+k) % arr.length, k, rem - 1);
arr[(index+k) % arr.length] = temp;
return arr;
}
Rubi exemplo:
def move_cyclic2 array, move_cnt
move_cnt = array.length - move_cnt % array.length
if !(move_cnt == 0 || move_cnt == array.length)
array.replace( array[move_cnt..-1] + array[0...move_cnt] )
end
end
Em teoria, o mais rápido é um loop como este:
if (begin != middle && middle != end)
{
for (i = middle; ; )
{
swap(arr[begin++], arr[i++]);
if (begin == middle && i == end) { break; }
if (begin == middle) { middle = i; }
else if (i == end) { i = middle; }
}
}
Na prática, você deve perfil e veja.
Aqui está um nother (C ++):
void shift_vec(vector<int>& v, size_t a)
{
size_t max_s = v.size() / a;
for( size_t s = 1; s < max_s; ++s )
for( size_t i = 0; i < a; ++i )
swap( v[i], v[s*a+i] );
for( size_t i = 0; i < a; ++i )
swap( v[i], v[(max_s*a+i) % v.size()] );
}
Claro que não é tão elegante como a famosa solução reversa três vezes, mas dependendo da máquina que pode ser similary rápido .
circleArray
tem alguns erros e não está funcionando em todos os casos!
O loop deve continuar while i1 < i2
NÃO i1 < last - 1
.
void Shift(int* _array, int _size, int _moves)
{
_moves = _size - _moves;
int i2 = _moves;
int i1 = -1;
while(++i1 < i2)
{
int tmp = _array[i2];
_array[i2] = _array[i1];
_array[i1] = tmp;
if(++i2 == _size) i2 = _moves;
}
}
Um amigo meu, enquanto brincando me perguntou como mudar um array, eu vim com esta solução (veja link ideone), seu agora que eu vi, alguém parece um pouco esotérico.
Dê uma olhada aqui .
#include <iostream>
#include <assert.h>
#include <cstring>
using namespace std;
struct VeryElaboratedDataType
{
int a;
int b;
};
namespace amsoft
{
namespace inutils
{
enum EShiftDirection
{
Left,
Right
};
template
<typename T,size_t len>
void infernalShift(T infernalArray[],int positions,EShiftDirection direction = EShiftDirection::Right)
{
//assert the dudes
assert(len > 0 && "what dude?");
assert(positions >= 0 && "what dude?");
if(positions > 0)
{
++positions;
//let's make it fit the range
positions %= len;
//if y want to live as a forcio, i'l get y change direction by force
if(!direction)
{
positions = len - positions;
}
// here I prepare a fine block of raw memory... allocate once per thread
static unsigned char WORK_BUFFER[len * sizeof(T)];
// std::memset (WORK_BUFFER,0,len * sizeof(T));
// clean or not clean?, well
// Hamlet is a prince, a prince does not clean
//copy the first chunk of data to the 0 position
std::memcpy(WORK_BUFFER,reinterpret_cast<unsigned char *>(infernalArray) + (positions)*sizeof(T),(len - positions)*sizeof(T));
//copy the second chunk of data to the len - positions position
std::memcpy(WORK_BUFFER+(len - positions)*sizeof(T),reinterpret_cast<unsigned char *>(infernalArray),positions * sizeof(T));
//now bulk copy back to original one
std::memcpy(reinterpret_cast<unsigned char *>(infernalArray),WORK_BUFFER,len * sizeof(T));
}
}
template
<typename T>
void printArray(T infernalArrayPrintable[],int len)
{
for(int i=0;i<len;i++)
{
std::cout << infernalArrayPrintable[i] << " ";
}
std::cout << std::endl;
}
template
<>
void printArray(VeryElaboratedDataType infernalArrayPrintable[],int len)
{
for(int i=0;i<len;i++)
{
std::cout << infernalArrayPrintable[i].a << "," << infernalArrayPrintable[i].b << " ";
}
std::cout << std::endl;
}
}
}
int main() {
// your code goes here
int myInfernalArray[] = {1,2,3,4,5,6,7,8,9};
VeryElaboratedDataType myInfernalArrayV[] = {{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{8,8},{9,9}};
amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));
amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,4);
amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));
amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,4,amsoft::inutils::EShiftDirection::Left);
amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));
amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,10);
amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));
amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));
amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,4);
amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));
amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,4,amsoft::inutils::EShiftDirection::Left);
amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));
amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,10);
amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));
return 0;
}
Este método irá fazer este trabalho:
public static int[] solution1(int[] A, int K) {
int temp[] = new int[A.length];
int count = 0;
int orignalItration = (K < A.length) ? K :(K%A.length);
for (int i = orignalItration; i < A.length; i++) {
temp[i] = A[count++];
}
for (int i = 0; i < orignalItration; i++) {
temp[i] = A[count++];
}
return temp;
}
Semelhante ao @IsaacTurner e não que elegante devido a cópias desnecessárias, mas a implementação é bastante curta.
A idéia - elemento de swap A no índice 0 com o elemento B que fica no destino de A. Agora B é em primeiro lugar. Trocá-lo com o elemento C que fica no destino de B. Continue até que o destino não está em 0.
Se o máximo divisor comum não é 1, então você não está ainda terminado -. Você precisa para continuar trocando, mas agora usando o índice 1 no ponto de início e fim
Continue até que sua posição inicial não é o mdc.
int gcd(int a, int b) => b == 0 ? a : gcd(b, a % b);
public int[] solution(int[] A, int K)
{
for (var i = 0; i < gcd(A.Length, K); i++)
{
for (var j = i; j < A.Length - 1; j++)
{
var destIndex = ((j-i) * K + K + i) % A.Length;
if (destIndex == i) break;
var destValue = A[destIndex];
A[destIndex] = A[i];
A[i] = destValue;
}
}
return A;
}
Aqui está a minha solução em Java que me pegou 100% Task Score e 100% exatidão na Codility:
class Solution {
public int[] solution(int[] A, int K) {
// write your code in Java SE 8
if (A.length > 0)
{
int[] arr = new int[A.length];
if (K > A.length)
K = K % A.length;
for (int i=0; i<A.length-K; i++)
arr[i+K] = A[i];
for (int j=A.length-K; j<A.length; j++)
arr[j-(A.length-K)] = A[j];
return arr;
}
else
return new int[0];
}
}
Note que, apesar de ver dois loops for
, a iteração em toda a matriz é feito apenas uma vez.
Swift 4 versão para o deslocamento variedade esquerda.
func rotLeft(a: [Int], d: Int) -> [Int] {
var result = a
func reverse(start: Int, end: Int) {
var start = start
var end = end
while start < end {
result.swapAt(start, end)
start += 1
end -= 1
}
}
let lenght = a.count
reverse(start: 0, end: lenght - 1)
reverse(start: lenght - d, end: lenght - 1)
reverse(start: 0, end: lenght - d - 1)
return result
}
Por exemplo, se a matriz de entrada é a = [1, 2, 3, 4, 5]
, e compensar deslocamento para a esquerda é d = 4
, em seguida resultado será [5, 1, 2, 3, 4]