JavaScript에서 객체 배열에 대한 효율적인 설정 작업

반응형

세트 연산은 거의 모든 애플리케이션에서 볼 수 있기 때문에 효율적인 방식으로 작성하는 것이 매우 중요합니다. 오늘은 Javascript의 세트 연산에 초점을 맞추고 어레이 내부의 데이터 교차, 차이 및 합계(세트 의미)를 작성하는 방법에 대한 두 가지 접근 방식을 비교할 것이다. 순진한 사람을 피하는 것이 왜 그렇게 중요한지도 알게 될 것이다.

예를 들어 시작해 보겠습니다.

예

당신이 인터넷 유명인사 존의 데이터 매니저라고 상상해 보세요. 존은 인스타그램과 트위터라는 두 개의 소셜 미디어에 계정을 가지고 있다. 당신의 임무는 그를 따르는 사용자들을 조사하는 것입니다. 두 가지 사용자 배열(Instagram과 Twitter)이 있습니다.

 

참고: 사용자를 비교하기 위해 이메일 주소 필드를 사용합니다(사용자가 두 소셜 미디어 계정에서 동일한 이메일 주소를 사용하는 것으로 가정합니다).

교차로 설정

당신은 누가 충실한 팬인지 알고 싶고 두 소셜 미디어 모두에서 존을 팔로우합니다. 이 방법은 instagramUsers 및 TwitterUsers 목록에 있는 고유한 사용자 목록을 찾는 교차 작업을 수행하는 것입니다.

한 목록의 모든 사용자를 반복한 다음 다른 목록의 모든 사용자에 대해 내부 반복을 수행하여 첫 번째 목록의 사용자가 다른 목록에 있는지 확인하는 방법이 있습니다. 코드는 다음과 같을 수 있습니다.

우리는 이 달콤한 원라이너로 변신할 수 있습니다.

 

이 코드의 문제는 무엇입니까?

두 번째 코드가 깨끗해 보일지라도, 프로젝트로 복사하지 마십시오! 성능 문제가 매우 큽니다. O(m*n)의 복잡도는 m과 n이 어레이 크기입니다. 이것은 모든 인스타그램 사용자들에게 우리가 모든 트위터 사용자들에 대해 반복한다는 것을 의미합니다.

우리의 예에서 30만 명의 인스타그램 사용자와 50만 명의 트위터 사용자가 있다면 우리는 150억 번의 반복을 할 것이다.

다른 접근이 필요해

최적화

 

이를 최적화하는 가장 좋은 방법은 세트를 사용하는 것입니다. 데이터 구조를 설정하면 조회 효율이 향상되어 정해진 시간 안에 원하는 요소를 찾을 수 있습니다(Set의 크기에 상관없이).

안타깝게도, JS에는 Set Intersection에 대한 연산 기능이 내장되어 있지 않기 때문에 (그 이유는 아직 궁금하기 때문에) 우리가 직접 구현을 작성할 것입니다.

먼저, 우리는 모든 이메일을 반복하고 집합에 추가하여 트위터로부터 이메일 세트를 만듭니다. 그런 다음 모든 Instagram 사용자를 검색하고 생성된 집합에 있는 전자 메일 주소를 확인합니다. 전자 메일이 안에 있으면 교차 결과에 추가합니다. 이 접근법에서 복잡도는 O(m+n)이다. 따라서 위의 예에서는 80만 번의 반복만 수행하면 됩니다.

더 짧은 대안적 접근 방식:

합집합

 

이제 우리 연예인 John에게 얼마나 많은 독특한 팔로워가 있는지 알아보자. 우리는 몇몇 팔로워를 두 번 셀 수 있기 때문에 인스타그램Users.length()와 twitterUsers.length()를 합칠 수는 없습니다. 우리는 모든 팔로워를 한 번만 종합하는 정해진 연합을 할 필요가 있습니다.

단순한 접근 방식은 모든 Instagram 사용자의 이메일 주소를 결과 배열에 추가한 후 모든 트위터 사용자를 통해 해당 이메일 주소가 배열 안에 있는지 확인합니다. 만약 그렇다면, 새로운 사용자가 없다면, 결과 목록에 새 이메일 주소를 추가합니다.

더 짧음:

다시 한번 O(n*m)입니다. 다시 한 번 세트를 사용해서 최적화해 봅시다.
최적의 접근 방식:

더 짧음:

 

이번에는 세트의 내장 기능 중 일부를 사용할 수 있습니다. 사용자 목록에서 두 개의 전자 메일 배열을 만든 다음 항목이 고유한지 확인하는 Set constructor에 목록으로 보냅니다. 우리는 ES6 확산 연산자(...)를 사용하는데, 이는 다른 배열에서 배열을 만드는 편리한 단축키로서 사용될 수 있다.

차이 설정

세트 차이를 수행해보면 인스타그램에서 존을 팔로우하는 독특한 팔로워가 얼마나 되는지 알 수 있다(트위터에서 존을 팔로우하지 않는 팔로워).

이전의 예들과 비슷하게, 순진한 접근법은 모든 인스타그램 사용자들에 대해 반복하고 모든 트위터 사용자들에 대해 내부 루프를 반복하고 트위터 사용자 목록이 아닌 사람들을 결과에 추가하는 것이다.

더 짧음:

 

그거 알아? O(n*m)입니다. 우리의 가장 친한 친구 세트를 사용할 시간입니다.
최적의 접근 방식:

더 짧음:

최종 참고 사항

다음 번에는 정해진 작업을 쓰실 때 잠시 멈춰서 이 기사를 다시 떠올리셨으면 합니다.
지금까지 살펴본 것처럼 이러한 운영은 여러 가지 방법으로 구현될 수 있으며 최적의 운영 방식을 작성하지 않으면 시간과 비용이 소요됩니다. 누가 이를 원하겠습니까?