세 번째 변수를 사용하지 않고 두 변수 값 바꾸기
인터뷰에서 묻는 매우 까다로운 질문 중 하나입니다.
같은 두 변수의 값을 교환 a=10하고 b=15.
일반적으로 두 변수 값을 바꾸려면 다음과 같은 세 번째 변수가 필요합니다.
temp=a;
a=b;
b=temp;
이제 요구 사항은 세 번째 변수를 사용하지 않고 두 변수의 값을 바꾸는 것입니다.
은 Using XOR 스왑 알고리즘을
void xorSwap (int* x, int* y) {
if (x != y) { //ensure that memory locations are different
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
왜 테스트입니까?
테스트는 x와 y가 다른 값이 아닌 다른 메모리 위치를 가지고 있는지 확인하는 것입니다. 이는 (p xor p) = 0x와 y가 동일한 메모리 위치를 공유하는 경우 하나가 0으로 설정되면 둘 다 0으로 설정되기 때문입니다. * x와 * y가 모두 0이면 * x 및 * y에 대한 다른 모든 xor 연산은 동일합니다. 0 (동일하므로), 이는 함수가 * x와 * y를 모두 0으로 설정 함을 의미합니다.
값은 같지만 메모리 위치가 같지 않으면 모든 것이 예상대로 작동합니다.
*x = 0011
*y = 0011
//Note, x and y do not share an address. x != y
*x = *x xor *y //*x = 0011 xor 0011
//So *x is 0000
*y = *x xor *y //*y = 0000 xor 0011
//So *y is 0011
*x = *x xor *y //*x = 0000 xor 0011
//So *x is 0011
이것을 사용해야합니까?
일반적인 경우에는 그렇지 않습니다. 컴파일러는 임시 변수를 최적화하고 스와핑이 일반적인 절차라는 점을 고려할 때 플랫폼에 대한 최적의 기계 코드를 출력해야합니다.
예를 들어 C로 작성된이 빠른 테스트 프로그램을 살펴보십시오.
#include <stdlib.h>
#include <math.h>
#define USE_XOR
void xorSwap(int* x, int *y){
if ( x != y ){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
void tempSwap(int* x, int* y){
int t;
t = *y;
*y = *x;
*x = t;
}
int main(int argc, char* argv[]){
int x = 4;
int y = 5;
int z = pow(2,28);
while ( z-- ){
# ifdef USE_XOR
xorSwap(&x,&y);
# else
tempSwap(&x, &y);
# endif
}
return x + y;
}
다음을 사용하여 컴파일 :
gcc -Os main.c -o swap
xor 버전은
real 0m2.068s
user 0m2.048s
sys 0m0.000s
임시 변수가있는 버전은 다음과 같습니다.
real 0m0.543s
user 0m0.540s
sys 0m0.000s
일반적인 형식은 다음과 같습니다.
A = A operation B
B = A inverse-operation B
A = A inverse-operation B
그러나 잠재적으로 오버플로를 조심해야하며 모든 작업에 작업이 정의 된 모든 값에 대해 잘 정의 된 역이있는 것은 아닙니다. 예 * 및 / A 또는 B가 0이 될 때까지 작동
xor는 모든 int에 대해 정의되고 자체 역이므로 특히 즐겁습니다.
a = a + b
b = a - b // b = a
a = a - b
std::swap아직 아무도 사용을 제안 하지 않았습니다.
std::swap(a, b);
나는 임시 변수를 사용하지 않으며 유형 a과 b구현 에 따라 어느 쪽도 아닌 specalization을 가질 수 있습니다. 구현은 '트릭'이 적절한 지 여부를 알고 작성되어야합니다. 두 번째 추측을 시도하는 것은 의미가 없습니다.
일반적으로 ADL이 가능한 한 더 나은 오버로드를 찾을 수 있도록하는 클래스 유형에 대해 작동하므로 이와 같은 작업을 수행하고 싶을 것입니다.
using std::swap;
swap(a, b);
물론이 답변에 대한 면접관의 반응은 공석에 대해 많은 것을 말할 수 있습니다.
manu에서 이미 언급했듯이 XOR 알고리즘은 모든 정수 값에 대해 작동하는 인기있는 알고리즘입니다 (포인터 포함, 운과 캐스팅 포함). 완전성을 위해 더하기 / 빼기를 사용하는 덜 강력한 또 다른 알고리즘을 언급하고 싶습니다.
A = A + B
B = A - B
A = A - B
여기서는 오버 플로우 / 언더 플로우에주의해야하지만 그렇지 않으면 잘 작동합니다. XOR이 허용되지 않는 경우 float / doubles에서 이것을 시도 할 수도 있습니다.
어리석은 질문에는 적절한 답변이 필요합니다.
void sw2ap(int& a, int& b) {
register int temp = a; // !
a = b;
b = temp;
}
register키워드 의 유일한 좋은 사용 .
#include<iostream.h>
#include<conio.h>
void main()
{
int a,b;
clrscr();
cout<<"\n==========Vikas==========";
cout<<"\n\nEnter the two no=:";
cin>>a>>b;
cout<<"\na"<<a<<"\nb"<<b;
a=a+b;
b=a-b;
a=a-b;
cout<<"\n\na="<<a<<"\nb="<<b;
getch();
}
원래 솔루션은 다음과 같습니다.
temp = x; y = x; x = temp;
다음을 사용하여 2 개의 라이너로 만들 수 있습니다.
temp = x; y = y + temp -(x=y);
그런 다음 다음을 사용하여 하나의 라이너로 만듭니다.
x = x + y -(y=x);
변수 대신 2 개의 어셈블리 레지스터에 대해 묻는 질문을 조금 변경하면 xchg작업을 하나의 옵션으로 사용하고 스택 작업을 다른 옵션으로 사용할 수 있습니다 .
고려 a=10, b=15:
더하기와 빼기 사용
a = a + b //a=25
b = a - b //b=10
a = a - b //a=15
나누기와 곱하기 사용
a = a * b //a=150
b = a / b //b=10
a = a / b //a=15
#include <iostream>
using namespace std;
int main(void)
{
int a,b;
cout<<"Enter a integer" <<endl;
cin>>a;
cout<<"\n Enter b integer"<<endl;
cin>>b;
a = a^b;
b = a^b;
a = a^b;
cout<<" a= "<<a <<" b="<<b<<endl;
return 0;
}
업데이트 : 여기서는 사용자로부터 두 개의 정수를 입력합니다. 그런 다음 비트 XOR 연산을 사용하여 스왑합니다.
우리는 두 개의 정수가 있다고 가정 a=4하고 b=9다음과 :
a=a^b --> 13=4^9
b=a^b --> 4=13^9
a=a^b --> 9=13^9
여기에 하나 이상의 솔루션이 있지만 단일 위험이 있습니다.
암호:
#include <iostream>
#include <conio.h>
void main()
{
int a =10 , b =45;
*(&a+1 ) = a;
a =b;
b =*(&a +1);
}
a + 1 위치의 모든 값이 무시됩니다.
물론 C ++ 대답은 std::swap.
그러나 다음 구현에는 세 번째 변수도 없습니다 swap.
template <typename T>
void swap (T &a, T &b) {
std::pair<T &, T &>(a, b) = std::make_pair(b, a);
}
또는 한 줄로 :
std::make_pair(std::ref(a), std::ref(b)) = std::make_pair(b, a);
세 번째 변수를 사용하여 두 숫자를 바꾸는 것은 다음과 같습니다.
int temp;
int a=10;
int b=20;
temp = a;
a = b;
b = temp;
printf ("Value of a", %a);
printf ("Value of b", %b);
세 번째 변수를 사용하지 않고 두 숫자 바꾸기
int a = 10;
int b = 20;
a = a+b;
b = a-b;
a = a-b;
printf ("value of a=", %a);
printf ("value of b=", %b);
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
a ^= b;
b ^= a;
a ^= b;
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
이것이 올바른 XOR 스왑 알고리즘입니다.
void xorSwap (int* x, int* y) {
if (x != y) { //ensure that memory locations are different
if (*x != *y) { //ensure that values are different
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
}
A XOR A = 0이기 때문에 메모리 위치가 다르고 실제 값이 다른지 확인해야합니다.
당신은 .... 쉽게 할 수 있습니다 ... 한 줄로 논리
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
int a = 1,b = 2;
a=a^b^(b=a);
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
또는
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
int a = 1,b = 2;
a=a+b-(b=a);
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
public void swapnumber(int a,int b){
a = a+b-(b=a);
System.out.println("a = "+a +" b= "+b);
}
가장 좋은 대답은 XOR을 사용하는 것이고 한 줄로 사용하는 것이 멋질 것입니다.
(x ^= y), (y ^= x), (x ^= y);
x, y는 변수이고 그 사이의 쉼표는 시퀀스 포인트를 도입하므로 컴파일러에 종속되지 않습니다. 건배!
세 번째 변수를 사용하지 않고 두 숫자를 바꾸는 간단한 c 예제를 살펴 보겠습니다.
프로그램 1 :
#include<stdio.h>
#include<conio.h>
main()
{
int a=10, b=20;
clrscr();
printf("Before swap a=%d b=%d",a,b);
a=a+b;//a=30 (10+20)
b=a-b;//b=10 (30-20)
a=a-b;//a=20 (30-10)
printf("\nAfter swap a=%d b=%d",a,b);
getch();
}
산출:
스왑 전 a = 10 b = 20 스왑 후 a = 20 b = 10
프로그램 2 : * 및 / 사용
* 및 /를 사용하여 두 숫자를 바꾸는 또 다른 예를 살펴 보겠습니다.
#include<stdio.h>
#include<conio.h>
main()
{
int a=10, b=20;
clrscr();
printf("Before swap a=%d b=%d",a,b);
a=a*b;//a=200 (10*20)
b=a/b;//b=10 (200/20)
a=a/b;//a=20 (200/10)
printf("\nAfter swap a=%d b=%d",a,b);
getch();
}
산출:
스왑 전 a = 10 b = 20 스왑 후 a = 20 b = 10
프로그램 3 : 비트 XOR 연산자 사용 :
비트 XOR 연산자를 사용하여 두 개의 변수를 바꿀 수 있습니다. 두 숫자 x와 y의 XOR은 x와 y의 비트가 다를 때마다 모든 비트가 1 인 숫자를 반환합니다. 예를 들어, 10 (이진 1010) 및 5 (이진 0101)의 XOR은 1111이고 7 (0111) 및 5 (0101)의 XOR은 (0010)입니다.
#include <stdio.h>
int main()
{
int x = 10, y = 5;
// Code to swap 'x' (1010) and 'y' (0101)
x = x ^ y; // x now becomes 15 (1111)
y = x ^ y; // y becomes 10 (1010)
x = x ^ y; // x becomes 5 (0101)
printf("After Swapping: x = %d, y = %d", x, y);
return 0;
산출:
스와핑 후 : x = 5, y = 10
프로그램 4 :
아무도 std :: swap 사용을 제안하지 않았습니다.
std::swap(a, b);
I don't use any temporary variables and depending on the type of a and b the implementation may have a specialization that doesn't either. The implementation should be written knowing whether a 'trick' is appropriate or not.
Problems with above methods:
1) The multiplication and division based approach doesn’ work if one of the numbers is 0 as the product becomes 0 irrespective of the other number.
2) Both Arithmetic solutions may cause arithmetic overflow. If x and y are too large, addition and multiplication may go out of integer range.
3) When we use pointers to a variable and make a function swap, all of the above methods fail when both pointers point to the same variable. Let’s take a look what will happen in this case if both are pointing to the same variable.
// Bitwise XOR based method
x = x ^ x; // x becomes 0
x = x ^ x; // x remains 0
x = x ^ x; // x remains 0
// Arithmetic based method
x = x + x; // x becomes 2x
x = x – x; // x becomes 0
x = x – x; // x remains 0
Let us see the following program.
#include <stdio.h>
void swap(int *xp, int *yp)
{
*xp = *xp ^ *yp;
*yp = *xp ^ *yp;
*xp = *xp ^ *yp;
}
int main()
{
int x = 10;
swap(&x, &x);
printf("After swap(&x, &x): x = %d", x);
return 0;
}
Output:
After swap(&x, &x): x = 0
Swapping a variable with itself may be needed in many standard algorithms. For example, see this implementation of QuickSort where we may swap a variable with itself. The above problem can be avoided by putting a condition before the swapping.
#include <stdio.h>
void swap(int *xp, int *yp)
{
if (xp == yp) // Check if the two addresses are same
return;
*xp = *xp + *yp;
*yp = *xp - *yp;
*xp = *xp - *yp;
}
int main()
{
int x = 10;
swap(&x, &x);
printf("After swap(&x, &x): x = %d", x);
return 0;
}
Output:
After swap(&x, &x): x = 10
Maybe off topic, but if you know what you are swapping a single variable between two different values, you may be able to do array logic. Each time this line of code is run, it will swap the value between 1 and 2.
n = [2, 1][n - 1]
You could do:
std::tie(x, y) = std::make_pair(y, x);
Or use make_tuple when swapping more than two variables:
std::tie(x, y, z) = std::make_tuple(y, z, x);
But I'm not sure if internally std::tie uses a temporary variable or not!
In javascript:
function swapInPlace(obj) {
obj.x ^= obj.y
obj.y ^= obj.x
obj.x ^= obj.y
}
function swap(obj) {
let temp = obj.x
obj.x = obj.y
obj.y = temp
}
Be aware to execution time of both options.
By run this code i measured it.
console.time('swapInPlace')
swapInPlace({x:1, y:2})
console.timeEnd('swapInPlace') // swapInPlace: 0.056884765625ms
console.time('swap')
swap({x:3, y:6})
console.timeEnd('swap') // swap: 0.01416015625ms
As you can see (and as many said), swap in place (xor) take alot time than the other option using temp variable.
a = a + b - (b=a);
It's very simple, but it may raise a warning.
single line solution for swapping two values in c language.
a=(b=(a=a+b,a-b),a-b);
second_value -= first_value;
first_value += second_value;
second_value -= first_value;
second_value *= -1;
참고URL : https://stackoverflow.com/questions/1826159/swapping-two-variable-value-without-using-third-variable
셸에서 가비지 수집을 어떻게 강제합니까?
그래서 원격 상자에 jmap이있는 힙을보고 있으며 가비지 수집을 강제하고 싶습니다. jvisualvm 또는 jconsole 및 친구에 들어 가지 않고 어떻게 할 수 있습니까?
나는 당신이 가비지 콜렉션을 강요해서는 안된다는 것을 안다. 힙이 왜 커지거나 커지는 지 알아 내야한다.
또한 System.GC ()가 실제로 가비지 수집을 강제하지 않는다는 것을 알고 있습니다. 단지 GC에 발생하기를 원한다는 것을 알려줍니다.
이것을 쉽게 할 수있는 방법이 있다고 말했습니까? 누락 된 명령 줄 앱이 있습니까?
무료 jmxterm 프로그램을 통해이 작업을 수행 할 수 있습니다 .
다음과 같이 실행하십시오.
java -jar jmxterm-1.0-alpha-4-uber.jar
여기에서 호스트에 연결하고 GC를 트리거 할 수 있습니다.
$>open host:jmxport
#Connection to host:jmxport is opened
$>bean java.lang:type=Memory
#bean is set to java.lang:type=Memory
$>run gc
#calling operation gc of mbean java.lang:type=Memory
#operation returns:
null
$>quit
#bye
bash / perl / ruby / other 스크립트에이를 포함하는 방법에 대한 정보는 jmxterm 웹 사이트의 문서를 참조하십시오. 이 작업을 수행하기 위해 Python에서 popen2를 사용하거나 Perl에서 open3을 사용했습니다.
업데이트 : 여기 jmxterm을 사용하는 한 줄짜리가 있습니다.
echo run -b java.lang:type=Memory gc | java -jar jmxterm-1.0-alpha-4-uber.jar -n -l host:port
JDK 7부터 다음과 같은 JDK 명령 도구 'jcmd'를 사용할 수 있습니다.
jcmd <pid> GC.run
를 실행 jmap -histo:live <pid>하면 아무것도 출력하기 전에 힙에 전체 GC가 강제 실행 됩니다.
user3198490 의 답변에 추가 . 이 명령을 실행하면 다음 오류 메시지가 표시 될 수 있습니다.
$ jcmd 1805 GC.run
[16:08:01]
1805:
com.sun.tools.attach.AttachNotSupportedException: Unable to open socket file: target process not responding or HotSpot VM not loaded
...
이것은 이 stackoverflow 답변의 도움으로 해결할 수 있습니다.
sudo -u <process_owner> jcmd <pid> GC.run
<process_owner>PID로 프로세스를 실행하는 사용자는 어디에 있습니까 <pid>? 둘 다 top또는htop
몇 가지 다른 솔루션이 있습니다 (이미 여기에 좋은 솔루션이 많이 있습니다).
- MemoryMBean 에 액세스 하고을 호출 하는 코드를 작성 하십시오
gc(). - 명령 줄 JMX 클라이언트 (예 : cmdline-jmxclient , jxmterm )를 사용하고 MemoryMBean 에서
gc()작업을 실행합니다.
다음 예는 cmdline-jmxclient에 대한 것입니다.
$ java -jar cmdline-jmxclient-0.10.3.jar - localhost:3812 'java.lang:type=Memory' gc
이것은 한 줄 뿐이고 스크립트에 정말 쉽게 넣을 수 있기 때문에 좋습니다.
동일한 명령 줄 옵션이 없다고 생각합니다.
동일한 경우 jvisualvm / jconsole을 사용해야합니다.
이 도구를 사용하여 프로그램의 메모리가 높은 이유를 확인하는 것이 좋습니다.
어쨌든 GC를 강요해서는 안됩니다. GC 알고리즘을 방해하고 프로그램을 느리게 만들 수 있기 때문입니다.
애플리케이션과 함께 jolokia 를 사용하는 경우 다음 명령을 사용하여 가비지 컬렉션을 트리거 할 수 있습니다.
curl http://localhost:8558/jolokia/exec/java.lang:type=Memory/gc
Linux의 경우 :
$ jcmd $(pgrep java) GC.run
jcmdJDK와 함께 패키지화되어 $(pgrep java)Java의 프로세스 ID를 가져옵니다.
다만:
kill -SIGQUIT <PID>
참고 URL : https://stackoverflow.com/questions/3523837/how-do-you-force-garbage-collection-from-the-shell
'Programming' 카테고리의 다른 글
| Red Hat Linux에서 표준 도구를 사용하여 파일의 행을 무작위 화하려면 어떻게해야합니까? (0) | 2020.08.25 |
|---|---|
| Android TextView에서 HTML 목록 태그가 작동하지 않습니다. (0) | 2020.08.25 |
| 텍스트를 변경할 때마다 UITextView를 맨 위로 스크롤하려면 어떻게해야합니까? (0) | 2020.08.25 |
| Java에서 String []을 쉼표로 구분 된 문자열로 변환 (0) | 2020.08.25 |
| 단일 파일을 사용한 Python 로깅 (함수 이름, 파일 이름, 줄 번호) (0) | 2020.08.25 |