중간 색인 배열없이 numpy 배열에서 빠른 방법 선택

Question

다음 2 열 배열이 주어지면 첫 번째 열의 "edges"에 해당하는 항목을 두 번째 열에서 선택하려고합니다. 이것은 단지 예일뿐입니다. 사실 a은 잠재적으로 수백만 개의 행을 가질 수 있습니다. 따라서, 가능한 한 빨리이 작업을 수행하고 중간 결과를 만들지 않고 작업하고 싶습니다.

import numpy as np 
a = np.array([[1,4],[1,2],[1,3],[2,6],[2,1],[2,8],[2,3],[2,1], 
       [3,6],[3,7],[5,4],[5,9],[5,1],[5,3],[5,2],[8,2], 
       [8,6],[8,8]]) 

즉 I는 결과를 어디서 찾을 a[:,0] 변화에 대응 a[:,1] 항목이다

desired = np.array([4,6,6,4,2]) 

원한다. 솔루션입니다

하나, np.array([6,6,4,2]) 제공

b = a[(a[1:,0]-a[:-1,0]).nonzero()[0]+1, 1] 

, 나는 단순히 첫 번째 항목, 아무 문제를 앞에 추가 할 수있다. 그러나 첫 번째 항목의 인덱스 중간 배열을 만듭니다. 나는 지능형리스트를 사용하여 중간을 피할 수 :

는

c = [a[i+1,1] for i,(x,y) in enumerate(zip(a[1:,0],a[:-1,0])) if x!=y] 

이것은 또한 [6,6,4,2]을 제공합니다. 생성기 기반의 zip (파이썬 3에서는 true)을 가정하면, 이것은 중간 표현을 생성 할 필요가 없으며 매우 메모리 효율적이어야합니다. 그러나 내부 루프는 numpy가 아니므로 나중에 numpy 배열로 되돌려 야하는 목록을 생성해야합니다.

메모리 효율이 c 인 numpy 전용 버전을 사용할 수 있지만 속도 효율성은 b입니까? 이상적으로 한 번만 a 이상의 패스가 필요합니다.

(a이 매우 큰 경우를 제외하고 속도를 측정하는 것은, 많은 여기에 도움이되지 않습니다, 그래서, 난 그냥 효율적 이론적으로 빠르고 메모리 무언가를 원하는이 벤치마킹을 귀찮게하지 않을 것입니다. 예를 들어, 당신은 할 수 있습니다 a의 가정 행은 파일에서 스트리밍 및 액세스에 느린있다 - 그것은 a 이상의 두 번째 랜덤 액세스 패스를 필요로 한, b 솔루션을 방지하는 또 다른 이유)

편집 :. 방법은 큰 a를 생성하는 테스트 용 매트릭스 :

from itertools import repeat 
N, M = 100000, 100 
a = np.array(zip([x for y in zip(*repeat(np.arange(N),M)) for x in y ], np.random.random(N*M))) 

Answer 1

벡터화 된 방식으로이 작업을 수행하려는 경우 중급 배열을 피할 수 없으므로 두려워요. 내장 배열이 없기 때문에 가능합니다.

이제는 성능이 더 좋은 nonzero()이 아닌 벡터화 된 접근법을 살펴 보겠습니다. (a[1:,0]-a[:-1,0])의 원래 코드와 동일한 차별화 아이디어를 사용하여 "가장자리"또는 교대에 해당하는 0이 아닌 구분을 찾은 후 부울 식 색인을 사용할 수 있습니다.

a[np.append(True,np.diff(a[:,0])!=0),1] 

런타임 테스트

원래 솔루션 a[(a[1:,0]-a[:-1,0]).nonzero()[0]+1,1] 첫 번째 행을 건너 뛸 것 -

따라서, 우리는 그렇게 같은 벡터화 된 접근 방식을 가질 것이다. 하지만, 타이밍 목적을 위해 말하면, 그것은 유효한 결과입니다.이 게시물의 제안 된 해결책에 대한 실행 시간은 다음과 같습니다.

In [118]: from itertools import repeat 
    ...: N, M = 100000, 2 
    ...: a = np.array(zip([x for y in zip(*repeat(np.arange(N),M))\ 
           for x in y ], np.random.random(N*M))) 
    ...: 

In [119]: %timeit a[(a[1:,0]-a[:-1,0]).nonzero()[0]+1,1] 
100 loops, best of 3: 6.31 ms per loop 

In [120]: %timeit a[1:][np.diff(a[:,0])!=0,1] 
100 loops, best of 3: 4.51 ms per loop 

이제 첫 번째 행도 포함하고 싶다고 가정 해 보겠습니다.

d = np.fromiter((a[i+1,1] for i,(x,y) in enumerate(zip(a[1:,0],a[:-1,0])) if x!=y), int) 

나는이가하는 생각 :

In [123]: from itertools import repeat 
    ...: N, M = 100000, 2 
    ...: a = np.array(zip([x for y in zip(*repeat(np.arange(N),M))\ 
           for x in y ], np.random.random(N*M))) 
    ...: 

In [124]: %timeit a[np.append(0,(a[1:,0]-a[:-1,0]).nonzero()[0]+1),1] 
100 loops, best of 3: 6.8 ms per loop 

In [125]: %timeit a[np.append(True,np.diff(a[:,0])!=0),1] 
100 loops, best of 3: 5 ms per loop 

Answer 2

좋아 실제로 나는 막 np.fromiter, 발전기를 기반으로 NumPy와 배열을 구축 할 수 배웠습니다, 해결책을 발견 - 업데이트 된 런타임은 다음과 같이 보일 것입니다 그것은 중간 배열없이 numpy 배열을 생성합니다. 그러나주의해야 할 점은 그것이 그렇게 효율적이지 않은 것입니다! 테스트에 대한 질문에서 내가 말한 것을 잊어 버리십시오.

t = [lambda a: a[(a[1:,0]-a[:-1,0]).nonzero()[0]+1, 1], 
    lambda a: np.array([a[i+1,1] for i,(x,y) in enumerate(zip(a[1:,0],a[:-1,0])) if x!=y]), 
    lambda a: np.fromiter((a[i+1,1] for i,(x,y) in enumerate(zip(a[1:,0],a[:-1,0])) if x!=y), int)] 

from timeit import Timer 
[Timer(x(a)).timeit(number=10) for x in t] 

[0.16596235800034265, 1.811289312000099, 2.1662971739997374] 

첫 번째 해결 방법이 대폭 빨라졌습니다! 이것은 중간 데이터를 생성하더라도 내부 루프를 numpy로 완전히 수행 할 수 있고, 다른 한편으로는 배열의 각 항목에 대해 파이썬 코드를 실행하기 때문입니다.

내가 말했듯이, 이런 종류의 벤치마킹이 여기에 적합하지 않은 이유입니다. a에 대한 액세스가 훨씬 느리면 벤치 마크는 CPU가로드되지 않습니다. 생각?

누군가가 더 빨리 뭔가를 생각해 낼 수 있기를 기대하기 때문에이 대답을 수락하지 못합니다.

Answer 3

메모리 효율성을 염두에두면 다음과 같이 해결할 수 있습니다. 입력 데이터와 동일한 크기 순서의 중간 만 유형 bool (a [1 :, 0]! = a [: -1, 0]); 입력 데이터가 int32 인 경우 'a'자체보다 8 배 작습니다. 그 바이너리 배열의 nonzeros를 세어 출력 배열을 미리 할당 할 수 있습니다. ! =의 출력이 예제가 제시하는 것처럼 희소 한 경우에는 그다지 중요하지 않습니다.