Plus rapide algorithme de décalage de cercle N matrice de taille M pour la position
https://stackoverflow.com/questions/876293
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quel est l'algorithme le plus rapide pour le tableau de décalage cercle pour les positions M?
Par exemple, le décalage de [3 4 5 2 3 1 4] m = 2 positions doivent être [1 4 3 4 5 2 3].
Merci beaucoup.
La solution
Si vous voulez O (n) et aucune utilisation de la mémoire supplémentaire (puisque champ a été indiqué), utiliser l'algorithme du livre de Jon Bentley, « Programmation Pearls 2nd Edition ». Il permute tous les éléments deux fois. Pas aussi rapide que l'utilisation de listes chaînées, mais utilise moins de mémoire et est conceptuellement simple.
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 (unTableau, startIndex, endIndex) inverse l'ordre des éléments de startIndex à endIndex inclusivement.
Autres conseils
Il est juste une question de représentation. Gardez l'indice actuel comme une variable entière et en traversant l'utilisation réseau opérateur modulo de savoir quand enrouler autour. Changement de vitesse est alors seulement en changeant la valeur de l'indice courant, l'enroulant autour de la taille de la matrice. Ceci est bien sûr O (1).
Par exemple:
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;
}
solution optimale
Question posée pour le plus rapide. Inversion de trois fois la plus simple, mais se déplace chaque élément exactement deux fois, prend O (N) et le temps O (1) de l'espace. Il est possible de déplacer le tour d'un tableau à déplacer chaque élément d'espace exactement une fois aussi en O (n) et O (1).
Idée
On peut encercler déplacer une rangée de N=9 longueur par M=1 avec un cycle:
tmp = arr[0]; arr[0] = arr[1]; ... arr[7] = arr[8]; arr[8] = tmp;
Et si N=9, nous pouvons M=3 changement de cercle avec trois cycles:
-
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;
Notez chaque élément est lu une fois et une fois écrit.
Diagramme de décalage N=9, M=3
Le premier cycle est de montrer en noir avec des chiffres indiquant l'ordre des opérations. Les deuxième et troisième cycles sont représentés en gris.
Le nombre de cycles requis est le grand commun diviseur (GCD) de N et M. Si le GCD est 3, nous commençons un cycle à chacun des {0,1,2}. Calcul de la GCD est rapide avec le .
Exemple de code:
// 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;
}
}
code en C pour tout type de tableau:
// 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;
}
Modifier : Cet algorithme peut aussi avoir de meilleures performances par rapport inversion de tableau (quand N est grand et M est faible) en raison de la localité de cache, puisque nous en boucle sur le réseau en petites étapes.
Note finale: si votre tableau est petite, inverse triple est simple. Si vous avez un grand tableau, il vaut la peine les frais généraux de travail le GCD pour réduire le nombre de mouvements par un facteur de 2. Ref: http://www.geeksforgeeks.org/array-rotation/
Réglez avec des pointeurs, et il prend presque pas de temps. Chaque point d'élément à l'autre, et le « dernier » (il n'y a pas, après tout dernier, vous avez dit qu'il était circulaire) des points à la première. Un pointeur sur le « départ » (premier élément), et peut-être une longueur, et vous avez votre choix. Maintenant, pour faire votre quart de travail, vous marchez simplement votre pointeur de départ le long du cercle.
Demander un bon algorithme, et vous obtenez des idées sensibles. Demandez plus rapide , et vous obtenez des idées bizarres!
Cet algorithme fonctionne en O (n) et O (1) de l'espace.
L'idée est de tracer chaque groupe cyclique dans le passage (numérotée par variable nextGroup).
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
Ce code fonctionne bien même sur k changement négatif
fonction C arrayShiftRight. Si le décalage est un tableau négatif de la fonction décale vers la gauche. Il est optimisé pour une utilisation moindre de la mémoire. temps d'exécution est 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];
}
}
}
Une solution très simple. Ceci est une façon très rapide, j'utilise ici un tableau de température avec la même taille ou originale et attache à la variable d'origine à la fin. Cette méthode utilisation O (n) et la complexité temporelle O (n) la complexité de l'espace et il est très simple à mettre en œuvre.
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;
En fonction de la structure de données que vous utilisez, vous pouvez le faire en O (1). Je pense que le moyen le plus rapide est de tenir le tableau sous la forme d'une liste chaînée, et une table de hachage qui peut se traduire entre « index » dans le tableau à « pointer » à l'entrée. De cette façon, vous pouvez trouver les têtes et les queues pertinentes en O (1), et faire le rebranchement en O (1) (et mettre à jour la table de hachage après le passage en O (1)). Bien sûr, cela serait une solution très « désordre », mais si tout ce que vous êtes intéressé est la vitesse du changement, qui fera (au détriment de plus insertion et recherche dans le tableau, mais il sera toujours rester O ( 1))
Si vous avez les données dans un tableau pur, je ne pense pas que vous pouvez éviter O (n).
codage sage, il dépend de ce que la langue que vous utilisez.
En Python par exemple, vous pouvez "tranche" il (supposons que n est la taille de décalage):
result = original[-n:]+original[:-n]
(je sais que j'espère recherche de hachage est en théorie pas O (1), mais nous sommes ici pratique et non théorique, du moins ...)
Cela devrait fonctionner pour déplacer une circulairement Arry: Entrée: {1, 2, 3, 5, 6, 7, 8}; Valeur de sortie présente dans le tableau après les 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];
}
}
}
Voici un général simple et efficace en place tourne fonction en C ++, moins de 10 lignes.
qui est extrait de ma réponse à une autre question. Comment faire pivoter un tableau?
#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';
}
Gardez deux index au tableau, un index commence du début du tableau à la fin du tableau. Un autre index commence à partir de la position de Mth dernier, et les boucles à travers les éléments M derniers un nombre quelconque de fois. Prend O (n) à tout moment. Pas d'espace supplémentaire requis.
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;
}
}
Voir si vous êtes intéressé par une implémentation Java:
Perles de programmation: circulaire gauche / droite Maj opération
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;
}
Exemple Ruby:
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
En théorie, le plus rapide est une boucle comme ceci:
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; }
}
}
Dans la pratique, vous devez le profil et voir.
Voici un 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()] );
}
Bien sûr, il est loin d'être aussi élégante que la célèbre solution inverse-trois fois, mais en fonction de la machine, il peut être similairement rapide .
circleArray a quelques erreurs et ne fonctionne pas dans tous les cas!
La boucle doit continuer while i1 < i2 pas 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;
}
}
Un de mes amis m'a demandé en plaisantant comment passer un tableau, je suis venu avec cette solution (voir lien ideone), maintenant je l'ai vu le vôtre, quelqu'un semble un peu ésotérique.
#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;
}
Cette méthode va faire ce travail:
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;
}
Similaire à @IsaacTurner et pas élégant en raison de la copie inutile, mais la mise en œuvre est assez courte.
L'idée - élément swap A sur indice 0 avec l'élément B qui se trouve sur la destination de A. Maintenant B est tout d'abord. Échange avec l'élément C qui se trouve sur la destination de B. Continuer jusqu'à ce que la destination n'est pas à 0.
Si le plus grand commun diviseur n'est pas 1 alors vous n'êtes pas encore fini -. Vous devez continuer à échanger, mais en utilisant l'index 1 à votre point de départ et fin
Continuer jusqu'à ce que votre position de départ n'est pas le GCD.
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;
}
Voici ma solution en Java qui m'a Score Tâche 100% et 100% à Correctness 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];
}
}
Notez que, malgré avoir vu deux boucles de for, l'itération sur l'ensemble du réseau ne se fait qu'une seule fois.
Swift 4 version pour tableau de décalage à gauche.
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
}
Par exemple, si le tableau d'entrée est a = [1, 2, 3, 4, 5] et décalage vers la gauche de décalage est d = 4, alors résultat sera [5, 1, 2, 3, 4]
