Python : 많은 수의 목록에서 가능한 모든 2 회전 사이의 교차로의 빠른 추출

StackOverflow https://stackoverflow.com/questions/1757698

문제

CA의 데이터 세트가 있습니다. 가변 길이의 9k 목록 (1 내지 100k 요소). 교차로의 길이를 계산해야합니다. 가능한 모든 2-리스트 조합 이 데이터 세트에서. 각 목록의 요소는 독특하므로 파이썬에서 세트로 저장할 수 있습니다.

파이썬에서 이것을 수행하는 가장 효율적인 방법은 무엇입니까?

편집하다 교차점 값을 해당 목록 쌍과 일치시키는 기능이 필요하다는 것을 지정하는 것을 잊었습니다. 혼란에 대한 신속한 응답과 사과에 감사드립니다!

도움이 되었습니까?

해결책

세트가 S에 저장된 경우 : 예를 들어 :

s = [set([1, 2]), set([1, 3]), set([1, 2, 3]), set([2, 4])]

그런 다음 사용할 수 있습니다 itertools.combinations 그들을 두 개로 가져 가서 교차로를 계산하려면 (Alex가 지적했듯이, combinations 버전 2.6 이후에만 사용할 수 있습니다). 여기에는 목록 comherension (예제를 위해서만)이 있습니다.

from itertools import combinations
[ i[0] & i[1] for i in combinations(s,2) ]

또는 루프에서 아마도 필요한 것일 것입니다.

for i in combinations(s, 2):
    inter = i[0] & i[1]
    # processes the intersection set result "inter"

따라서 각각의 길이를 갖기 위해서는 "처리"가 될 것입니다.

    l = len(inter)

반복자를 사용하여 모든 조합을 계산하고 모든 것을 미리 준비하지 않기 때문에 이것은 매우 효율적입니다.

편집하다:이 메소드를 사용하면 목록 "S"의 각 세트는 실제로 다른 것일 수 있습니다. 세트를 반환합니다, 발전기처럼. 메모리가 부족한 경우 목록 자체가 단순히 생성기 일 수 있습니다. 이러한 요소를 생성하는 방법에 따라 훨씬 느릴 수 있지만, 전체 세트 목록을 메모리에 동시에 가질 필요는 없습니다 (경우에 문제가되지 않아야 함).

예를 들어, 각 세트가 함수로 만들어진 경우 gen:

def gen(parameter):
    while more_sets():
        # ... some code to generate the next set 'x'
        yield x

with open("results", "wt") as f_results:
    for i in combinations(gen("data"), 2):
        inter = i[0] & i[1]
        f_results.write("%d\n" % len(inter))

편집 2: 지수를 수집하는 방법 (Redrat의 의견에 따라).

내가 의견으로 대답 한 빠른 솔루션 외에도 세트 지수를 수집하는보다 효율적인 방법은 목록을 갖는 것입니다. (index, set) 목록 대신 set.

새로운 형식의 예 :

s = [(0, set([1, 2])), (1, set([1, 3])), (2, set([1, 2, 3]))]

어쨌든 조합을 계산하기 위해이 목록을 작성하는 경우 새로운 요구 사항에 적응하는 것이 간단해야합니다. 기본 루프는 다음과 같습니다.

with open("results", "wt") as f_results:
    for i in combinations(s, 2):
        inter = i[0][1] & i[1][1]
        f_results.write("length of %d & %d: %d\n" % (i[0][0],i[1][0],len(inter))

루프에서 i[0] 그리고 i[1] 튜플 일 것입니다 (index, set), 그래서 i[0][1] 첫 번째 세트, i[0][0] 그 지수.

다른 팁

결과의 (n x n/2) 매트릭스, 즉 O (n Squared) 출력의 매트릭스를 생성해야하므로 모든 언어에서는 접근 방식이 O (N Squared)보다 적을 수 없습니다. (n은 당신의 질문에서 "약 9k"입니다). 따라서 (a) 필요한 n 세트를 만드는 것보다 본질적으로 더 빠른 것은 없습니다. (b) 출력을 생성하기 위해 (b) 가장 간단한 접근법을 생성하기 위해 반복합니다. iow :

def lotsofintersections(manylists):
  manysets = [set(x) for x in manylists]
  moresets = list(manysets)
  for  s in reversed(manysets):
    moresets.pop()
    for z in moresets:
      yield s & z

이 코드는 이미 약간의 최적화를 추가하려고 노력하고 있습니다 (예 : 목록의 전면을 튀어 나오는 것을 피하거나 다른 O (n 제곱) 요소를 추가 할 수 있습니다.

사용 가능한 코어 및/또는 노드가 많고 병렬 알고리즘을 찾고 있다면 물론 다른 경우입니다. 그렇다면, 귀하가 가지고있는 클러스터의 종류, 크기, 노드 및 코어가 가장 잘 통신 할 수있는 방법을 언급 할 수 있습니다. , 기타 등등?

편집하다: OP가 코멘트에서 우연히 언급했듯이 (!) 실제로 교차하는 세트의 숫자가 필요하다고 생각합니다 (실제로 사양의 중요한 부분을 생략하는 이유는 무엇입니까? 이것은 이것을 다음으로 변경하면됩니다.

  L = len(manysets)
  for i, s in enumerate(reversed(manysets)):
    moresets.pop()
    for j, z in enumerate(moresets):
      yield L - i, j + 1, s & z

(진보적 식별자의 경우 "1에서 카운트"해야하는 경우 - 그렇지 않으면 명백한 변경).

그러나 그것이 사양의 일부라면 더 간단한 코드를 사용할 수도 있습니다. 곰팡이를 잊어 버리고 :

  L = len(manysets)
  for i xrange(L):
    s = manysets[i]
    for j in range(i+1, L):
      yield i, j, s & manysets[z]

이번에는 당신이 "0에서 카운트"를 대신하고 싶다고 가정합니다.

이 시도:

_lists = [[1, 2, 3, 7], [1, 3], [1, 2, 3], [1, 3, 4, 7]]
_sets = map( set, _lists )
_intersection = reduce( set.intersection, _sets )

그리고 인덱스를 얻기 위해 :

_idxs = [ map(_i.index, _intersection ) for _i in _lists ]

건배,

호세 마리아 가르시아

추신 : 죄송합니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top