MapReduce, Python 및 NetworkX

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

문제

NetworkX를 사용하여 Python으로 내장 된 그래프에 대한 비가 중 임의의 산책 함수를 구현했습니다. 아래는 임의의 산책을 다루는 내 프로그램의 스 니펫입니다. 내 프로그램의 다른 곳에서는 그래프를 작성하는 메소드가 있으며 작성한 다양한 사용자 지정 그래프 테스트 방법을 시뮬레이션하는 메소드가 있습니다. 이러한 그래프 테스트 방법 중 하나는 그래프에서 무작위로 두 개의 노드를 선택하고 두 노드 사이에서 임의의 산책을 실행합니다. 이 랜덤 워크에서 계산되는 두 가지는 타임 (시작에서 끝까지 가로지는 링크 수)과 출퇴근 시간 (시작부터 끝까지, 다시 시작하는 것부터 시작점으로 이동하는 링크의 수입니다. ). 

def unweighted_random_walk(starting_point,ending_point, graph):
    '''
    starting_point: String that represents the starting point in the graph
    ending_point: String that represents the ending point in the graph
    graph: A NetworkX Graph object
    '''
    ##Begin the random walk
    current_point=starting_point
    #current_node=graph[current_point]
    current_point_neighors=graph.neighbors(current_point)
    hitting_time=0

    #Determine the hitting time to get to an arbitrary neighbor of the
    #starting point
    while current_point!=ending_point:
        #pick one of the edges out of the starting_node with equal probs
        possible_destination=current_point_neighbors[random.randint(0,current_point_neighors)]
        current_point=possible_destination
        current_point_neighbors=graph.neighbors(current_point)
        hitting_time+=1
    return hitting_time

무작위 보행에 대한 내 코드는 끝점에 도달 할 때까지 임의의 노드를 선택하기 때문에 꽤 간단합니다. 그러나이 현재 구현은 몇 번의 임의의 산책을 시도 할 때 매우 느립니다 (어느 시점에서 백만을 실행해야한다고 생각합니다).

내 질문은 : Hadoop Mapreduce를 사용 하여이 임의의 산책을 위해 여기에서 진행중인 작업을 병렬화 할 수있는 방법이 있습니까? 임의의 산책을 할 수있는 더 좋은 방법이 있습니까?

도움이 되었습니까?

해결책

귀하의 질문을 해결하려면 :

  1. Ned의 의견을 다루어야합니다. 그는 나를 말하기 위해 나를 이겼다. 코드를 설명하십시오. 나중에 그것에 대해 더.

  2. 나는 병렬로 실행할 수있는 걷기 알고리즘을 추측 할 수 없습니다. 바로 본질적으로, 그들은 각각 선형 과정입니다. 각 단계는 이전 단계에 따라 다릅니다. 시작 노드를 제외하고 (시작 노드를 제외하고) 이전 노드를 알지 못하고 다음 노드가 무엇을 점프할지 알 수 없습니다. 귀하의 코드가 실제로 선택이 이전의 코드와 독립적 인 임의의 코드를 나타내는 경우, 귀하의 질문에서이를 설명해야합니다.

  3. 그러나 각 임의의 산책이 독립적이라고 가정하면 ~할 수 있다 많은 임의의 산책을 동시에 실행하십시오. 우리는이 시나리오를 호출합니다 부패하게 평행합니다, 그리고 그것은 매우 운이 좋은 것입니다.

  4. 왜 당신이 왜 Hadoop, 특히 여기에서 사용하고 싶은지 전혀 모른다. 첫 번째 단계는 "기본 프로그램으로 작성하고 QSUB (또는 동등한) 스크립트를 사용 하여이 프로그램의 많은 실행을 서버로 늘릴 수 있습니까?" 대답이 아니오 인 경우 다음 단계는 "내가 사용할 수 있습니까? 다중 프로세싱 모듈? "멀티 프로세싱을 사용하면 살펴볼 수 있습니다. Pycon 2009의 Jesse Noller의 멀티 프로세싱 프레젠테이션.

이제 특정 코드와 관련하여 ...

  1. 그래프의 노드가 무엇인지 설명해야합니다. 나는 당신이 그들을 사전처럼 취급하는 이유를 혼란스럽게합니다 (전화 .keys()) 그들에게. 사전이라면 키와 값이 무엇인지 알려주십시오. 네트워크는 이미 당신에게 그것을 제공하기 때문에 이웃을 열쇠로 저장하지 않기를 바랍니다. Graph.neighbors() 방법. 노드 자체에 노드의 이웃을 저장하는 경우 NetworkX 라이브러리를 오해 할 수 있습니다. 그래프가 당신을 위해 일을하게하십시오.

  2. 당신은 동일한 논리를 두 번 가지고 있습니다 unweighted_random_walk(), 시작 노드에서 대상 노드로의 트립을 한 번, 다시 대상 노드를 시작 노드로 다시 시작하십시오. 왜요? 한 방향에 대한 논리 만 있으면됩니다. 이 기능을 두 번 호출하십시오. 시작 및 대상 노드와 함께 인수로 호출하여 방향을 한 방향으로 얻은 다음 인수 순서를 목적지로 바꾸고 다른 방향으로 걸어 가기 시작합니다. 그런 다음 두 개의 독립적 인 통화가 있으며 이제 동시에 실행할 수 있습니다.

  3. 사용하지 마십시오 while True:- 여기가 아니라 일반적으로. 항상 계속할 실제 조건을 표시해야합니다. 예,

    while current_point != ending_point:
    ...

  4. 정보 문자열을 반환하지 말고 정보를 직접 반환하십시오. 예,

    return hitting_time

    바로 위의 지점 2에서의 조언을 따르면 타격 시간을 반환하고 총 통근 시간을 얻기 위해 전화와 백 컬러의 타격 시간을 합산하면됩니다. 편리합니까?

또한보십시오

편집하다: Jesse Noller의 프레젠테이션 및 디스코에 대한 링크가 포함되었습니다.

다른 팁

Map-Reduce가 당신을 어떻게 도울 수 있는지 모르겠습니다. 두 부분으로 작동하는 경우에 사용됩니다. 첫 번째 부분은 여러 다른 데이터 요소에서 독립적으로 수행 할 수있는 계산이며, 두 번째 부분은 어떻게 든 모든 결과를 결합하는 것입니다. 아마도이 임의의 산책에 도움을주기 위해 Map-Reduce를 사용하는 영리한 방법이있을 것입니다. 그러나 나는 그것을 보지 못합니다.

당신의 임의의 산책은 완전히 무작위입니다. 많은 루프로 끝날 수도 있고, 계속하기 전에 같은 두 노드 사이를 앞뒤로 움직일 수도 있습니다. 어쩌면 당신은 어떻게 든 그것을 구속하고 싶을 때, 당신은 검색 할 공간이 너무 커서?

자세한 공식을 사용하는 경우 실제로 랜덤 워크를 수행 할 필요가 없습니다. 이 종이.

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